Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning

• The keywords identify min-max optimization, non-smooth optimization, stochastic optimization, and non-convex optimization as the paper’s topics.Source: ARTICLE HISTORY · p. 1

1. Introduction

• Existing non-convex minimization methods may require stochastic subgradients of the outer objective, which can be unavailable when the inner maximum is nontrivial or the objective is an expectation.Source: §1 · p. 2
• The paper analyzes first-order methods for weakly-convex-concave min-max problems without exactly solving the inner maximization at every iteration.The objective is weakly convex in the minimization variable and concave in the maximization variable.Source: §1 · p. 2

1.1. Applications Of WCC Min-Max Problem

• Distributionally robust learning can model losses over a data set with a maximization over probability weights, including when individual losses are non-convex.The formulation also allows robust learning from multiple data distributions, including distributions used to generate adversarial examples.Source: §1.1 · pp. 2–3
• The min-max formulation covers minimizing the sum of the top-k losses, including maximum-loss minimization when k = 1, even with non-convex losses.Source: §1.1 · pp. 2–3

1.2. Contributions

• For potentially non-smooth stochastic objectives given as expectations, the proposed stochastic primal-dual subgradient method has time complexity ˜O(1/ǫ^6) for finding a nearly ǫ-stationary solution.Source: §1.2 · p. 3
• With strongly convex r and a finite average of potentially non-smooth functions linear in y, the method improves to ˜O(n/ǫ^2 + 1/ǫ^4).Source: §1.2 · p. 3
• For smooth finite-sum objectives, the variance-reduced method has complexity ˜O(n/ǫ^2) when r is strongly convex and ˜O(n/ǫ^2 + 1/ǫ^6) when r is convex.Source: §1.2 · p. 3

• Stochastic gradient methods and variance-reduced methods have been analyzed for non-convex minimization, but those methods are not directly applicable when the outer objective is non-smooth.The cited variance-reduction work includes.Source: §2 · pp. 3–4
• Many methods for weakly convex non-smooth minimization require a stochastic subgradient of the outer objective, which may require exactly solving the concave inner maximization.This can be challenging when the objective involves expectations.Source: §2 · p. 4
• The prox-linear method for weakly convex composite optimization can be costly when evaluating its function and Jacobian requires handling an expectation or a large finite sum.Stochastic primal-dual methods can use sample approximations, but the cited approach still requires smoothness, unlike the analysis described here.Source: §2 · p. 4
• Compared with, the paper allows weakly convex but not necessarily smooth objectives, analyzes the Moreau-envelope gradient, and provides a variance-reduced method for smooth finite sums.The cited comparisons also note that prior methods in generally assume smoothness, while additionally assumes the Polyak-Lojasiewicz condition in y.Source: §2 · pp. 4–5

• The problem uses a Euclidean norm for x and a generic norm for y, allowing the method to adapt to the geometry of the maximization variable’s feasible set.The dual norm and the distance from a point to a set are defined alongside this choice.Source: §3 · p. 5
• The standing assumptions require f to be weakly convex in x and concave in y, while r is strongly convex relative to the specified Bregman divergence, possibly with zero strong-convexity parameter.Source: §3 · p. 6
• Because ψ is weakly convex and may be non-smooth, the paper targets nearly ǫ-stationary points measured by the gradient norm of its Moreau envelope.For γ > ρ, the envelope is smooth and the proximal minimization is strongly convex; its gradient norm bounds the distance to a corresponding stationary point of ψ.Source: §3 · p. 6
• A small Moreau-envelope gradient implies a nearby point whose subdifferential distance from zero is at most the gradient norm.Specifically, the proximal point is within γ times that norm of the evaluated point.Source: §3 · p. 6
• The paper’s complexity analysis focuses on first-order methods for finding nearly ǫ-stationary points of the outer objective.Source: §3 · p. 7

4. Proximally Guided Approach

• The proximally guided approach applies primal-dual first-order methods to an approximate min-max subproblem and uses its returned x as the next iterate.The paper considers potentially nonsmooth expectation objectives and smooth finite-sum objectives.Source: §4 · p. 7

4.1. Stochastic Min-Max Problem

• PG-SMD approximately solves each proximal subproblem; under D2, initializing the dual variable at an easily computed maximizer is key to exploiting strong concavity.That initialization supports the complexity reduction from Õ(ε^-6) to Õ(ε^-4).Source: §4.1 · p. 8
• For nonsmooth nonconvex min-max problems, the stochastic method improves nearly ε-stationary-point complexity from Õ(ε^-6) at μ=0 to Õ(ε^-4) at μ>0 under D2 in Assumption 2; D1 also gives Õ(ε^-6).Source: §4 · p. 7, §4.1 · p. 9

4.2. Smooth Finite-Sum Min-Max Problem

• PG-SVRG uses variance reduction because exact finite-sum gradients can be costly when n is large; an additional y-side proximal term makes its subproblem strongly convex and strongly concave.When r is already strongly concave, the additional term is removed.Source: §4.2 · pp. 9–10
• Algorithm 4 ensures E[∥∇ψγ(¯x(τ))∥²] ≤ ε² after T = Õ(ε⁻²) iterations, with total time complexity Õ(nε⁻²) if μ > 0 and Õ(nε⁻² + ε⁻⁶) if μ = 0.Source: §4.2 · p. 10

5.1. Robust Learning with Smooth Loss

• The smooth-loss linear experiment uses truncated logistic loss and compares PG-SMD and PG-SVRG with proximal-linear methods using stochastic mirror descent or variance reduction.The experiments use four imbalanced LIBSVM datasets; test sets are almost balanced.Source: §5.1 · pp. 11–12, Table 1 · p. 11
• Across four imbalanced datasets, PG methods are more advantageous than PL; PG-SVRG reduces long-run objective values, while PG-SMD reaches low test error faster and is more time-efficient.The comparisons track objective value, testing error, and F-score against data passes, and objective value against wall-clock time.Source: §5.1 · pp. 11, 13, Figure 1 · p. 12, Figure 2 · p. 13
• On imbalanced CIFAR10 with ResNet18 and VGG19, DRO is considerably better than ERM in training and testing accuracy in these two examples.The training-loss comparison is also plotted across epochs.Source: Figure 3 · p. 13, §5.1 · p. 14, Figure 4 · p. 14

5.2. Robust Learning with Non-Smooth Loss

• For non-smooth binary classification with a two-layer network, PG-SMD is slightly more advantageous than Alter-SGD and reduces objective value faster at small data-pass counts.The comparison uses imbalanced covtype and connect-4 datasets.Source: §5.2 · pp. 14–15, Figure 5 · p. 15

5.3. Robust Learning from Multiple Distribution

• For learning from five simulated distributions with non-smooth loss, PG-SMD performs better than Alter-SGD in the reported example.The comparison tracks objective value, testing classification error, and F-score as data passes increase.Source: §5.3 · pp. 15–16, Figure 6 · p. 16

6. Conclusion

• The work addresses min-max problems with a weakly convex minimization component and a concave maximization component, a class that includes robust learning applications.Source: §6 · p. 16
• It develops stochastic mirror descent and variance-reduced gradient methods for expectation-based and smooth finite-sum settings, respectively.Source: §6 · p. 16
• The paper analyzes computational complexity for finding nearly ǫ-stationary points and reports numerical experiments demonstrating effectiveness on distributionally robust learning with nonconvex losses.Source: §6 · p. 16

Appendix A. Proof of Theorem 4.1

• Proposition A.1 supplies the stochastic mirror descent convergence result under Assumptions 1 and 2 used in the proof.Source: Appendix A · p. 19
• The proof establishes Algorithm 2's convergence separately for cases D1 and D2 by applying Proposition A.1 in each case.Source: Appendix A · pp. 19, 22
• For the complexity accounting, the proof selects a uniform random iteration and bounds the stochastic subgradients used to generate its iterate in case D1.Source: Appendix A · pp. 23–24

Appendix B. Proof of Theorem 4.2

• The maximized and minimized regularized objectives are smooth, with gradient Lipschitz constants depending on the cross-variable smoothness and strong-convexity parameters.The proof uses the unique maximizer yx and Danskin’s theorem to express the gradient of the maximized objective as ∇xf(x, yx).Source: Appendix B · pp. 27, 31
• The cited passages identify Proposition B.2 as Algorithm 3’s convergence result under Assumptions 1 and 3, and introduce a convergence property for SVRG (Algorithm 4).Source: Appendix B · pp. 27–28
• Algorithm 4’s complexity analysis counts each inner stochastic gradient and each full gradient as n equivalent stochastic gradients, and treats µ>0 and µ=0 separately.The analysis bounds the total count for generating the output iterate in both cases.Source: Appendix B · pp. 33–35