PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Algorithms for Smooth Minimax Optimization

Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, Sewoong Oh

arXiv:1907.01543v1math.OCcs.LGstat.ML

TL;DR

The paper asks how to efficiently solve smooth minimax problems when maximization is concave but minimization is strongly convex or nonconvex. It combines Mirror-Prox with Nesterov’s accelerated gradient descent and uses an inexact proximal point method, obtaining improved rates in both settings. The results cover general strongly-convex–concave problems, nonconvex–concave problems, and finite minimax instances.

  • Problem

    Existing results largely focus on convex-concave minimax problems, motivating faster methods for strongly convex and broader nonconvex minimization settings.

  • Method

    The paper combines Mirror-Prox with Nesterov’s accelerated gradient descent and applies an inexact proximal point method whose subproblems are strongly-convex–concave.

  • Results

    The methods achieve eO(1/k^2) for general smooth strongly-convex–concave problems and eO(1/k^1/3) for smooth nonconvex–concave problems.

  • Takeaways & Limitations

    The paper improves state-of-the-art convergence rates for both strongly-convex–concave and nonconvex–concave smooth minimax optimization.

  • Takeaways & Limitations

    The results are presented in the Euclidean setting, and the dependence on the condition number may be sub-optimal; precise lower bounds for the nonconvex–concave setting remain largely unexplored.

Abstract

from arXiv · show

This paper studies first order methods for solving smooth minimax optimization problems $\min_x \max_y g(x,y)$ where $g(\cdot,\cdot)$ is smooth and $g(x,\cdot)$ is concave for each $x$. In terms of $g(\cdot,y)$, we consider two settings -- strongly convex and nonconvex -- and improve upon the best known rates in both. For strongly-convex $g(\cdot, y),\ \forall y$, we propose a new algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in $\tilde{O}(1/k^2)$ iterations, improving over current state-of-the-art rate of $O(1/k)$. We use this result along with an inexact proximal point method to provide $\tilde{O}(1/k^{1/3})$ rate for finding stationary points in the nonconvex setting where $g(\cdot, y)$ can be nonconvex. This improves over current best-known rate of $O(1/k^{1/5})$. Finally, we instantiate our result for finite nonconvex minimax problems, i.e., $\min_x \max_{1\leq i\leq m} f_i(x)$, with nonconvex $f_i(\cdot)$, to obtain convergence rate of $O(m(\log m)^{3/2}/k^{1/3})$ total gradient evaluations for finding a stationary point.

1 Introduction

The paper develops first-order methods for smooth minimax problems with concave maximization, addressing strongly convex and nonconvex minimization settings. It improves convergence rates by combining accelerated methods with proximal-point techniques.

  • Problem setting: Smooth minimax optimization is studied with concave maximization and either convex, strongly convex, or nonconvex minimization in g(·, y).The problem has applications in machine learning, optimization, statistics, mathematics, and game theory.
  • Strongly-convex–concave setting: 1/k^2 convergence is obtained for general smooth strongly-convex–concave minimax problems, improving the previous O(1/k) rate.The rate matches the known Ω(1/k^2) lower bound up to a poly-logarithmic factor.
  • Strongly-convex–concave setting: Mirror-Prox and Nesterov’s accelerated gradient descent are combined to achieve the strongly-convex–concave result.The method is designed for the general smooth setting rather than only special bilinear or y-linear cases.
  • Nonconvex–concave setting: 1/k^1/3 convergence is obtained for smooth nonconvex–concave problems, improving the previous best-known O(1/k^1/5) rate.The method uses an inexact proximal point approach whose inner problems are strongly-convex–concave.
  • Finite minimax problems: Finite minimax problems with smooth nonconvex f_i are included, and nonconvex constrained optimization can be reduced to this class.The paper also notes that machine-learning problems with non-decomposable losses belong to this setting.

2 Preliminaries and background material

The preliminaries define smooth minimax objectives, distinguish convex-concave from nonconvex-concave settings, and motivate stationarity measures for the latter. They also review Mirror-Prox and its O(1/k) primal-dual-gap rate.

  • Problem setup: The paper studies smooth minimax problems with g(x, ·) concave for every x, while allowing either convex or nonconvex behavior in x.
  • Convex-concave setting: In the convex-concave setting, Sion’s theorem makes max_y min_x g(x,y) equal to min_x max_y g(x,y) under compactness of Y.Optimality can therefore be characterized using primal-dual pairs and their primal-dual gap.
  • Nonconvex-concave setting: In the nonconvex-concave setting, global optimization is generally intractable and the minimax theorem may fail, so primal-dual gap is not always meaningful.The paper instead seeks approximate stationary points for the minimax objective.
  • Stationarity: An ε-FOSP is defined through the gradient of the Moreau envelope of an L-weakly convex function, using parameter 1/(2L).This definition is related to a nearby point having a subgradient of norm at most ε.
  • Mirror-Prox: Mirror-Prox achieves an O(1/k) convergence rate for the primal-dual gap in smooth convex-concave minimax problems.Its conceptual update evaluates gradients at the next iterate and can be implemented efficiently when the objective is smooth.

3 Strongly-convex concave saddle point problem

For smooth strongly-convex-concave problems, the paper introduces DIAG, combining accelerated-gradient and Mirror-Prox ideas to track primal and dual iterates. It establishes a near-O(k^-2) primal-dual-gap rate with near-optimal ε-complexity, while noting suboptimal condition-number dependence.

  • 3 Strongly-convex concave saddle point problem: The strongly-convex-concave setting assumes g(·,y) is σ-strongly convex, g(x,·) is concave, and g is L-smooth over a convex compact Y.The objective is to find an ε-primal-dual pair.
  • Motivation: A direct accelerated-gradient method on the dual function does not preserve the desired primal rate: dual error Θ(k^-2) can yield primal error Θ(k^-1).The paper gives a bilinear-plus-quadratic example demonstrating this mismatch.
  • Algorithmic idea: DIAG, or Dual Implicit Accelerated Gradient, combines Nesterov’s AGD with ideas from Nemirovski’s Mirror-Prox derivation.Its outer step updates both x_k and y_k to better track the primal-dual gap.
  • Convergence and complexity: ˜O(k^-2) is the stated primal-dual-gap convergence rate for DIAG, matching the known Ω(1/k^2) lower bound up to polylogarithmic factors.The ε-primal-dual-pair complexity improves on Mirror-Prox’s O(1/ε) rate and has optimal dependence on ε and D_Y, according to the cited lower bound.
  • Algorithmic idea: DIAG’s conceptual update jointly selects x_{k+1} and y_{k+1}, with x_{k+1} minimizing g(·,y_{k+1}) and y_{k+1} corresponding to an AGD step for g(x_{k+1},·).The implementable algorithm approximates these requirements using accelerated-gradient subroutines and contraction-based updates.
  • Limitations: DIAG’s dependence on the condition number L/σ is identified as potentially suboptimal and left for future improvement.

4 Nonconvex concave saddle point problem

The paper addresses smooth nonconvex–concave minimax problems using an inexact proximal point method whose strongly-convex–concave subproblems are solved by DIAG. It derives improved stationary-point complexity and specializes the approach to finite max-type objectives.

  • The problem assumes concavity in y, nonconvexity in x, smoothness, and a lower-bounded objective; the target is an approximate first-order stationary point.
  • Prox-DIAG adds quadratic regularization so each proximal subproblem becomes strongly-convex–concave and solves it approximately with DIAG.
  • Omitted theorem expressions state that a bounded number of outer iterations yields an ε-FOSP, with total first-order complexity obtained by combining outer and inner iteration bounds.
  • Solving each quadratic approximation to accuracy O(ε^2) helps bound the Moreau-envelope gradient and improves over the prior general rate O(1/ε^5).
  • For finite max-type problems with smooth nonconvex components, Prox-FDIAG replaces DIAG with Nesterov’s finite convex minimax scheme and improves on the subgradient method’s O(m/ε^4) complexity.

5 Experiments

Experiments compare Prox-FDIAG, Adaptive Prox-FDIAG, and subgradient methods on synthetic finite max-type objectives. The proximal methods converge faster in the reported Moreau-envelope gradient experiments, with Adaptive Prox-FDIAG usually fastest.

  • The study evaluates three methods on randomly generated synthetic finite max-type objectives, using ten runs and a fixed initialization.
  • For small target accuracy ε, Adaptive Prox-FDIAG has the fastest convergence, followed by Prox-FDIAG and then the subgradient method.
  • The experiments plot the Moreau-envelope gradient norm against iteration count or total inner iterations, using log-log scatter plots and fitted lines.
  • Prox-FDIAG and Adaptive Prox-FDIAG converge faster than the subgradient method, while Adaptive Prox-FDIAG is almost always faster than Prox-FDIAG.
  • The subgradient baseline uses a diminishing, nonsummable but square-summable step size because fixed step sizes were observed to converge slowly.
  • Because computing the Moreau-envelope gradient is costly, the experiments retain the point with the lowest observed function value rather than the lowest envelope-gradient norm.

6 Conclusion

The paper presents improved algorithms for smooth minimax problems with concave maximization and either strongly convex or nonconvex minimization. It combines accelerated saddle-point optimization with an inexact proximal method and reports empirical superiority on finite max-type problems.

  • The paper studies smooth minimax problems where the maximization is concave and the minimization is either strongly convex or nonconvex.
  • For the strongly convex case, it combines Mirror-Prox with Nesterov’s accelerated gradient descent to tightly bound the primal-dual gap.
  • For the nonconvex case, it uses an inexact proximal method with a convergence rate to stationary points.
  • The results are presented in the Euclidean setting, with extension to non-Euclidean settings via Bregman divergences described as straightforward.
  • The paper empirically demonstrates superiority of its nonconvex algorithm over a state-of-the-art subgradient method for finite max-type nonconvex minimization.

B.2 Proof of Lemma 1

This proof section characterizes the Moreau envelope of a weakly convex function through a strongly convex proximal objective and derives its gradient using optimality and Danskin’s theorem.

  • Adding the quadratic term makes the proximal objective (1/λ−L)-strongly convex when f is L-weakly convex.
  • Strong convexity ensures the proximal minimizer is well behaved, while the envelope’s minimizers coincide with those of f.
  • For L<1/λ, conjugacy arguments establish smoothness of the Moreau envelope.
  • Danskin’s theorem gives ∇f_λ(x)=(x−x̂_λ(x))/λ and places this gradient in ∂f(x).

B.3 Proof of Lemma 3

The proof converts smoothness into weak convexity, adds a quadratic regularizer to obtain convexity, and applies Danskin’s theorem to the resulting max function.

  • L-smoothness of g(·, y) implies L-weak convexity in x.
  • Adding L∥x∥2/2 to g produces a convex regularized function with subgradients shifted by Lx.
  • The quadratic regularizer is independent of y, so the maximizers over Y remain unchanged.
  • Danskin’s theorem is then used to characterize the max function’s subgradients and establish the required inequality.

B.4 Proof of Theorem 1

Theorem 1 analyzes DIAG as accelerated gradient ascent with an inexact Mirror-Prox-inspired update, using a decreasing potential to derive fast convergence and bound gradient computations.

  • DIAG modifies projected accelerated gradient ascent through Imp-STEP, whose update is inspired by conceptual Mirror-Prox.
  • Imp-STEP returns approximate primal-dual points and converges in O(log(1/εstep)) steps.
  • At each iteration, DIAG performs an accelerated gradient-ascent step on the concave function hk+1(y) = g(xk+1, y).
  • The potential function decreases under the selected step size, enabling the convergence analysis despite nonmonotone AGD function values.
  • The Mirror-Prox fixed-point principle is critical to proving the fast convergence rate.

B.4.1 Proof of Lemma 6

Lemma 6 establishes the behavior of Imp-STEP by exploiting strong convexity, Lipschitz continuity, contraction, and accelerated-gradient convergence.

  • Strong convexity makes x∗(y) unique and allows its Lipschitz continuity in y to be established.
  • The operation (·)+ is shown to be a contraction, so Banach’s theorem yields a unique fixed point ỹ.
  • Imp-STEP’s approximate primal iterate is close to x∗(yr) when the AGD error εagd is sufficiently small.
  • The distance from yr to ỹ decreases exponentially, and the final primal minimizer remains close to the returned iterate.
  • The inner value function h(y) = minx∈X g(x, y) is differentiable by Danskin’s theorem and is shown to be smooth.

B.6 Proof of Corollary 1

The corollary analyzes a finite max-type nonconvex objective through a strongly convex quadratic model, separating iterations by objective decrease or approximate stationarity.

  • Algorithm 5 applies Prox-FDIAG to finite nonconvex concave minimax optimization using functional components {fi}.
  • The model bf(x; xk) is the maximum of linearizations of fi plus a quadratic term and is L-strongly convex.
  • If bf(xk+1; xk) ≤ f(xk) − 3ε̃/4, the objective decreases by at least 3ε̃/4.
  • If bf(xk+1; xk) > f(xk) − 3ε̃/4, the proof shows that xk is an ε-FOSP.
  • The total number of inner steps needed to reach an ε-FOSP is obtained by combining the iteration bound with excessive-gap optimization of the inner max problem.

B.7 Adaptive Prox-FDIAG algorithm

Adaptive Prox-FDIAG finds increasingly accurate first-order stationary points by repeatedly invoking Prox-FDIAG with geometrically decreasing target accuracies. Under G-Lipschitzness, L-smoothness, and a lower-bounded objective, it retains Prox-FDIAG’s oracle complexity up to a logarithmic factor, while experiments report faster convergence.

  • Accuracy adaptation: Adaptive Prox-FDIAG successively finds ε′-FOSPs, halving ε′ until it reaches the target accuracy ε.Each ε′-FOSP initializes the search for an ε′/2-FOSP.
  • Oracle complexity: Adaptive Prox-FDIAG has the same first-order oracle complexity as Prox-FDIAG up to an O(log(1/ε)) factor.Each outer iteration runs Prox-FDIAG for the current ε′-FOSP target.
  • Convergence guarantee: Under G-Lipschitzness, L-smoothness, and a lower-bounded optimum, Adaptive Prox-FDIAG outputs an ε-FOSP after the stated number of outer steps.The lower-bound condition is f(x) ≥ f* > −∞.
  • Empirical behavior: Experiments observe faster convergence for Adaptive Prox-FDIAG than for Prox-FDIAG.
Loading 1907.01543v1…