PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-Optimal Algorithms for Minimax Optimization

Tianyi Lin, Chi Jin, Michael. I. Jordan

arXiv:2002.02417v6math.OCcs.LGstat.ML

TL;DR

The paper asks whether first-order minimax algorithms can attain known lower complexity bounds. It uses accelerated proximal-point ideas with an accelerated solver for minimax proximal steps, achieving near-optimal rates for strongly convex-concave settings and strong results in broader settings.

  • Problem

    Existing first-order methods left a gap between upper bounds and lower bounds for general smooth strongly-convex-strongly-concave and strongly-convex-concave minimax problems.

  • Method

    The algorithms combine an accelerated proximal point method with an accelerated solver for minimax proximal steps.

  • Results

    The paper achieves ~O(√κxκy) gradient complexity for strongly-convex-strongly-concave problems, matching the lower bound up to logarithmic factors.

  • Takeaways & Limitations

    The approach extends to strongly-convex-concave, convex-concave, nonconvex-strongly-concave, and nonconvex-concave settings, matching or improving existing gradient-complexity results up to logarithmic factors.

  • Takeaways & Limitations

    The accelerated proximal-point iteration guarantee does not include the complexity of solving its proximal subproblems, which may be difficult in general.

Abstract

from arXiv · show

This paper resolves a longstanding open question pertaining to the design of near-optimal first-order algorithms for smooth and strongly-convex-strongly-concave minimax problems. Current state-of-the-art first-order algorithms find an approximate Nash equilibrium using $\tilde{O}(κ_{\mathbf x}+κ_{\mathbf y})$ or $\tilde{O}(\min\{κ_{\mathbf x}\sqrt{κ_{\mathbf y}}, \sqrt{κ_{\mathbf x}}κ_{\mathbf y}\})$ gradient evaluations, where $κ_{\mathbf x}$ and $κ_{\mathbf y}$ are the condition numbers for the strong-convexity and strong-concavity assumptions. A gap still remains between these results and the best existing lower bound $\tildeΩ(\sqrt{κ_{\mathbf x}κ_{\mathbf y}})$. This paper presents the first algorithm with $\tilde{O}(\sqrt{κ_{\mathbf x}κ_{\mathbf y}})$ gradient complexity, matching the lower bound up to logarithmic factors. Our algorithm is designed based on an accelerated proximal point method and an accelerated solver for minimax proximal steps. It can be easily extended to the settings of strongly-convex-concave, convex-concave, nonconvex-strongly-concave, and nonconvex-concave functions. This paper also presents algorithms that match or outperform all existing methods in these settings in terms of gradient complexity, up to logarithmic factors.

1 Introduction

The paper addresses the gap between lower and upper first-order complexity bounds for general minimax problems, proposing near-optimal algorithms across convexity settings.

  • The open problem is whether first-order algorithms can achieve lower bounds for strongly-convex-strongly-concave and strongly-convex-concave minimax optimization.
  • ~O(√κxκy) gradient complexity matches the lower bound up to logarithmic factors in the strongly-convex-strongly-concave setting.
  • ~O(√κx/ε) gradient complexity matches the lower bound up to logarithmic factors in the strongly-convex-concave setting.
  • ~O(ε^-1) gradient complexity matches lower and best existing upper bounds up to logarithmic factors in the general convex-concave setting.
  • For nonconvex-strongly-concave and nonconvex-concave problems, the paper gives accelerated algorithms with improved or state-of-the-art gradient complexity bounds.

2 Related work

Prior work established optimal or near-optimal rates for several special and convex-concave cases, while general strongly convex-concave and nonconvex-concave settings retained open complexity gaps.

  • O(ε^-1) is optimal for smooth convex-concave problems in terms of duality gap, with mirror-prox, dual extrapolation, and accelerated proximal-gradient methods achieving it.
  • Existing strongly convex-concave methods achieve ~O(κx+κy) or ~O(min{κx√κy, √κxκy}), whereas lower bounds include ~Ω(√κxκy).
  • Special-case algorithms address bilinear, composite bilinear, affinely constrained, and linear-coupling structures rather than general minimax problems.
  • Nonconvex-concave work studied stationarity of Φ, with deterministic rates ~O(ε^-2) for strongly concave y and ~O(ε^-6) for concave y.

3 Preliminaries

The preliminaries define the minimax assumptions, optimality criteria, notation, and accelerated-gradient component used throughout the paper.

  • 3.1 Minimax optimization: The paper studies smooth minimax problems over nonempty closed convex sets X and Y in finite-dimensional Euclidean spaces.
  • 3.1 Minimax optimization: In the convex-concave setting, an ε-saddle point is defined by a duality gap of at most ε.
  • 3. Preliminaries: Strong convexity and strong concavity are quantified by condition numbers κx=ℓ/µx and κy=ℓ/µy.
  • 3.1 Minimax optimization: In the nonconvex-concave setting, the paper seeks stationary-point surrogates because finding a global Nash equilibrium is generally intractable.
  • 3.2 Nesterov’s accelerated gradient descent: Nesterov’s accelerated gradient descent combines projected gradient descent with a momentum step and serves as a basic acceleration component.
  • 3.2 Nesterov’s accelerated gradient descent: AGD improves over gradient descent by a factor of √κ for smooth strongly convex minimization.

4 Algorithm Components

The paper combines accelerated proximal-point minimization with an accelerated minimax solver for proximal subproblems. This resolves the proximal solver’s generic condition-number gap when the proximal parameter matches the smoothness parameter.

  • Accelerated Proximal Point Algorithm: APPA accelerates minimization through momentum steps and inexact proximal subproblem solves.Its iteration guarantee does not require smoothness of the minimized function, but proximal subproblems must be solved.
  • Accelerated Proximal Point Algorithm: APPA is advantageous when the minimized function lacks smoothness but its proximal step is easy to solve, including minimax optimization problems.The paper identifies LASSO as another example of this setting.
  • Accelerated Solver for Minimax Proximal Steps: Maximin-AG2 solves minimax problems by combining inner AGD minimization with outer accelerated gradient ascent.The inner loop computes Ψ(y) := min_x∈X g(x, y), while the outer loop maximizes Ψ.
  • Accelerated Solver for Minimax Proximal Steps: The generic minimax proximal solver requires ˜O(κx√κy) iterations, which does not match the lower bound ˜Ω(√κxκy).The gap motivates exploiting the special structure of proximal subproblems in the final algorithm.
  • Accelerated Solver for Minimax Proximal Steps: κx = O(1) for proximal functions when the proximal parameter equals f’s smoothness, reducing proximal-step cost to ˜O(√κy) gradient evaluations.This property avoids the generic solver rate’s unfavorable dependence on κx.

5 Accelerating Convex-Concave Optimization

The paper applies an inexact accelerated proximal-point framework to convex-concave minimax problems. It obtains near-optimal rates for strongly-convex-strongly-concave, strongly-convex-concave, and convex-concave settings through proximal reductions.

  • 5.1 Strongly-convex-strongly-concave setting: Algorithm 4 uses inexact APPA on Φ(x) := max_y∈Y f(x, y) and Maximin-AG2 for each minimax proximal subproblem.After obtaining a near-optimal xT, it applies AGD to −f(xT, ·) to find a near-optimal y.
  • 5.1 Strongly-convex-strongly-concave setting: ˜O(√κxκy) gradient evaluations find an ǫ-saddle point in the strongly-convex-strongly-concave setting.Here κx = ℓ/µx and κy = ℓ/µy.
  • 5.2 Strongly-convex-concave setting: An (ǫ/2)-saddle point of fǫ,y is also an ǫ-saddle point of f, enabling reduction from strongly-convex-concave to strongly-convex-strongly-concave optimization.The auxiliary function fǫ,y becomes µx-strongly-convex-ǫ/(2D_y^2)-strongly-concave.
  • 5.2 Strongly-convex-concave setting: The strongly-convex-concave reduction yields an ǫ-saddle point with the gradient complexity stated in Corollary 5.2.The construction feeds fǫ,y into Minimax-APPA with strong concavity parameter ǫ/(4D_y^2).
  • 5.3 Convex-concave setting: The convex-concave reduction constructs a strongly-convex-strongly-concave fǫ and applies Minimax-APPA to obtain an ǫ-saddle point.Corollary 5.3 states the resulting gradient-complexity bound, with fǫ defined by equation (8).

6 Accelerating Nonconvex-Concave Optimization

For nonconvex-concave problems, the paper replaces accelerated outer minimization with proximal point iterations while retaining the accelerated minimax proximal solver. A reduction adds strong concavity or transfers stationarity from an auxiliary function.

  • 6.1 Nonconvex-strongly-concave setting: Algorithm 5 uses Maximin-AG2 for proximal subproblems and unaccelerated PPA on Φ(x) := max_y∈Y f(x, y).The outer loop omits momentum because gradient descent is already optimal among first-order methods for the relevant objective.
  • 6.1 Nonconvex-strongly-concave setting: Theorem 6.1 finds an ǫ-stationary point with probability at least 2/3 for smooth functions that are strongly concave in y.The condition number is κy = ℓ/µy.
  • 6.1 Nonconvex-strongly-concave setting: ˜O(1/ǫ^2) outer iterations and ˜O(√κy) gradient evaluations per proximal step yield the theorem’s total complexity.The proximal function has condition number O(1) in the inner solver.
  • 6.2 Nonconvex-concave setting: For nonconvex-concave functions, an auxiliary function ˜fǫ has gradients close to those of f and is ǫ/(2D_y)-strongly concave in y.Thus an (ǫ/2)-stationary point of ˜fǫ is also an ǫ-stationary point of f.
  • 6.2 Nonconvex-concave setting: Corollary 6.2 applies Minimax-PPA to ˜fǫ and obtains an ǫ-stationary point of f with probability at least 2/3.The method assumes f is smooth and concave in y.

7 Conclusions

The paper develops near-optimal algorithms for strongly convex–concave and nonconvex–concave minimax problems, while defining stationarity-based targets for nonsmooth surrogates.

  • The paper provides the first near-optimal algorithms for strongly-convex-(strongly)-concave minimax problems and state-of-the-art algorithms for nonconvex-(strongly)-concave problems.
  • Global Nash equilibrium is generally intractable in the nonconvex-concave setting, motivating local surrogate objectives based on stationary points.The singleton-Y case already contains globally hard nonconvex minimization.
  • For strongly concave responses, the robust objective Φ is smooth and standard gradient stationarity applies.
  • When concavity is not strong, Φ may be nonsmooth, so weak convexity and Moreau-envelope stationarity provide a weaker optimality framework.
  • An ǫ-stationary Moreau-envelope point lies within ǫ/2ℓ of a point having a subgradient of norm at most ǫ.
  • In the nonconvex-strongly-concave setting, the method finds a point with ∥∇Φ(ˆx)∥≤ǫ using the same iteration count as the corresponding theorem.

A.3 Nonconvex-concave setting

This section reduces nonconvex-concave optimization to a strongly-concave surrogate and analyzes the resulting projected and accelerated procedures.

  • A.3 Nonconvex-concave setting: The reduction adds an O(ǫ2) regularization term to obtain a near-optimal point under the Moreau-envelope stationarity measure.
  • Guarantee: For nonconvex-concave functions, the reduction achieves ∥∇Φ1/2ℓ(ˆx)∥≤ǫ with probability at least 2/3.
  • Proof structure: The proof separates output accuracy, stopping conditions, and gradient-complexity analysis.
  • Proof structure: The analysis uses one-step projected gradient descent together with smoothness and strong convexity inequalities.
  • Proof structure: The proof concludes the required convergence and complexity statements after combining the intermediate inequalities.
  • Proof structure: Accelerated gradient descent supplies the iteration and gradient-complexity bounds needed to solve the strongly convex subproblems.

B.3 Proof of Theorem 4.2

The proof of Theorem 4.2 establishes accuracy and complexity for an accelerated minimax solver in the smooth strongly-convex-strongly-concave setting.

  • The auxiliary functions are well defined because the objective is strongly convex-concave.
  • The functions Φg and Ψg are respectively 2κyℓ-smooth, µx-strongly convex and 2κxℓ-smooth, µy-strongly concave.
  • Guarantee: The resulting Maximin-AG2 output satisfies the stated ǫ-accuracy guarantee for the maximized objective.
  • Accuracy: The proof controls primal and dual projected-gradient residuals through stopping conditions and structural inequalities.
  • Complexity: The algorithm uses estimate sequences and accelerated gradient subroutines to bound inner-solver iterations and gradient evaluations.
  • The condition numbers are κx=ℓ/µx and κy=ℓ/µy.

C.1 Proof of Theorem 5.1

The proof of Theorem 5.1 interprets Minimax-APPA as an inexact accelerated proximal point method and establishes approximate saddle-point guarantees for strongly convex-concave objectives.

  • Minimax-APPA is an inexact accelerated proximal point algorithm whose inner solver is Maximin-AG2 combined with AGD.
  • Strong convexity makes Φ(x)=maxy∈Y f(x,y) strongly convex, with a unique Nash equilibrium and x⋆=argminx∈X Φ(x).
  • Accuracy: The proof bounds primal and dual errors using strong concavity, Lipschitz continuity of y⋆(·), and projected-gradient inequalities.
  • Guarantee: Choosing sufficiently many outer iterations yields maxy∈Y f(ˆx,y)−minx∈X f(x,ˆy)≤ǫ.
  • Complexity: The total gradient complexity follows by combining the outer iteration bound with the per-iteration cost of Maximin-AG2.
  • Convex-concave reduction: For the convex-concave reduction, the proof again establishes an ǫ-saddle point before substituting the resulting parameters into Theorem 5.1.

D.1 Proof of Theorem 6.1

The proof establishes approximate stationarity by bounding averaged projected-gradient residuals across proximal iterations, then selecting a uniformly random iterate. It combines per-iteration solver accuracy with Markov’s inequality to obtain a probability guarantee and total gradient complexity.

  • Proximal structure: The proximal objective is strongly convex, so its minimizer is well defined and unique.This property supports the proximal-point analysis used to control the iterates.
  • Stationarity bound: The proof bounds the averaged projected-gradient residual by a potential decrease term and solver-error terms.The resulting inequality depends on ℓ(Φ(x0) − Φ(xT)), the iteration count T, and δ-dependent error terms.
  • Probabilistic guarantee: Uniformly selecting ˆx from the iterates and applying Markov’s inequality yields projected-gradient residual at most ǫ/2 with probability at least 2/3.The required iteration count satisfies T > cℓ∆Φǫ^-2.
  • Inner solver: The inner maximization is solved by AGD to tolerance δ ≤ ǫ^2/(10κ_y)^4ℓ, supplying the accuracy needed by the outer analysis.The proof also invokes the Maximin-AG2 solver at each iteration.
  • Complexity conclusions: The proof concludes that the output is an ǫ-stationary point and derives a total gradient-evaluation bound from the per-iteration Maximin-AG2 cost.The nonconvex-concave extension uses ˜f_ǫ and sets κ_y = 2ℓD_y/ǫ in the Theorem 6.1 complexity bound.

E.1 Proof of Lemma A.4

The lemma establishes basic properties of the Moreau envelope and proximal mapping, then derives smoothness and curvature properties of value functions induced by strongly convex or concave optimization.

  • Moreau envelope: The Moreau envelope and proximal mapping are well defined, and the envelope does not exceed the original function.These properties follow from weak convexity and strong convexity of the regularized objective.
  • Moreau envelope: The Moreau envelope is 4ℓ-smooth with gradient ∇Φ_1/2ℓ(x) = 2ℓ(x − prox_Φ/2ℓ(x)).The proof uses differentiability of the envelope and the 1-Lipschitz property of the proximal mapping.
  • Value function in y: Strong concavity in y makes the maximizer unique, allowing Danskin’s theorem to establish differentiability of the associated value function.The resulting function Ψ_g is 2κ_xℓ-smooth and µ_y-strongly concave.
  • Value function in x: Strong convexity in x makes the minimizer unique, allowing Danskin’s theorem to establish differentiability of the associated value function.The resulting function Φ_g is 2κ_yℓ-smooth and µ_x-strongly convex.
Loading 2002.02417v6…