PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving Non-Convex Non-Concave Min-Max Games Under Polyak-{\L}ojasiewicz Condition

Maziar Sanjabi, Meisam Razaviyayn, Jason D. Lee

arXiv:1812.02878v1math.OCcs.GTcs.LG

TL;DR

The paper targets finding first-order stationary points in non-convex, non-concave min-max games. Under a PL condition on the inner problem, it uses an approximate gradient for a reduced objective and establishes gradient complexity within logarithmic factors of the lower bound.

  • Problem

    The paper considers how to find first-order stationary points in min-max games beyond the convex-concave and concave regimes, focusing on non-convex, non-concave games.

    Source: §1 · p. 1

  • Method

    Under a PL condition on the inner maximization problem, the method approximately computes the gradient of a reduced objective and uses it in a multi-step gradient descent-ascent algorithm.

    Source: §3 · pp. 3–4

  • Results

    With equal-complexity gradient oracles, the overall complexity is O(ε^-2 log(1/ε)), within a logarithmic factor of the lower bound.

    Source: §3 · p. 4

  • Takeaways & Limitations

    For the considered class of non-convex, non-concave games, the lower-bound order is achievable up to logarithmic factors.

    Source: §2 · p. 2, §3 · p. 4

    The approach assumes the inner maximization problem is easy to solve and satisfies the PL condition; its initial-solution condition is readily satisfied when the optimal solution to g and the iterates remain bounded.

    Source: §3 · pp. 3–4

Abstract

from arXiv · show

In this short note, we consider the problem of solving a min-max zero-sum game. This problem has been extensively studied in the convex-concave regime where the global solution can be computed efficiently. Recently, there have also been developments for finding the first order stationary points of the game when one of the player's objective is concave or (weakly) concave. This work focuses on the non-convex non-concave regime where the objective of one of the players satisfies Polyak-{\L}ojasiewicz (PL) Condition. For such a game, we show that a simple multi-step gradient descent-ascent algorithm finds an $\varepsilon$--first order stationary point of the problem in $\widetilde{\mathcal{O}}(\varepsilon^{-2})$ iterations.

1 Problem Formulation

The section frames the goal as finding first-order stationary points in non-convex, non-concave min-max games and states smoothness and gradient-Lipschitz assumptions. It also relates approximate stationarity to a necessary condition for local Nash equilibrium and to Quasi Nash Equilibrium.

1 Problem Formulation

  • The goal is to find a first-order stationary point of a zero-sum game in the non-convex, non-concave regime.The first player maximizes f and the other minimizes it.Source: §1 · p. 1
  • Approximate stationarity is stated to be necessary for a local Nash equilibrium and a special case of Quasi Nash Equilibrium.Source: §1 · p. 1
  • The function f is assumed twice continuously differentiable, with gradients in both variables Lipschitz continuous.Source: §1 · p. 2

2 A Simple Iteration Complexity Lower Bound

The section motivates the target complexity using the standard lower bound for non-convex optimization. It identifies an alpha-independent special case where the min-max problem reduces to finding a stationary point of a general non-convex function.

2 A Simple Iteration Complexity Lower Bound

  • O(ε^-2) gradient evaluations are required to find an ε-stationary solution when f is independent of α.In that case the min-max lower bound coincides with the lower bound for stationary points of a general non-convex function.Source: §2 · p. 2
  • Simple gradient descent achieves the O(ε^-2) lower bound for the alpha-independent non-convex case.Source: §2 · p. 2
  • The section sets up a comparison with a class of non-convex, non-concave min-max games for which the lower bound is achievable up to logarithmic factors.Source: §2 · p. 2

3 Finding Approximate Stationary Points in Min-Max Games

The section assumes a PL condition on the minimizing player’s objective and uses approximate gradients of a reduced objective to find an ε-stationary point. Its multi-step gradient descent-ascent method achieves the stated stationarity guarantee with near-lower-bound gradient complexity.

  • A PL-game requires −f(θ, α) to be µ-PL in α for every fixed θ, a condition that need not imply convexity.The section notes that PL conditions can hold for some non-convex functions.Source: §3 · p. 3
  • For each fixed θ, K inner ascent steps update α, then an outer descent step updates θ using an approximate gradient of g.The inner loop approximately solves the α optimization problem, yielding a Danskin-type gradient estimate for g.Source: §3 · pp. 3–4
  • Under the PL-game and bounded-gap assumptions, Algorithm 1 produces an ε-stationary iterate for some t≤T.The bounded-gap condition is g(θt)−f(θt, α0(θt))≤∆ throughout the iterations.Source: §3 · pp. 3–4
  • O(ε^-2) θ-gradient evaluations and O(ε^-2 log(1/ε)) α-gradient evaluations are required; equal-cost oracles put overall complexity a logarithmic factor from the lower bound.Source: §3 · p. 4
  • Remark 3.2.1 describes Theorem 3.2 as an extension of [7, Theorem 4.2], which gave a similar result when f(θ, α) is strongly concave in α; stochastic gradients yield a stochastic-setting extension.Source: §3 · p. 5

A Proofs

The proof establishes stability of the maximizing response under the PL condition, then shows that the maximized objective is smooth and has gradients inherited from the game objective. It also uses the implication from PL to quadratic growth.

A Proofs

  • A μ-PL function satisfies quadratic growth with constant γ = 4μ.The proof invokes this implication as a corollary of Theorem 2 in.Source: A Proofs · p. 6
  • For a family of μ-PL functions with closed A(θ), each maximizer at θ1 has a corresponding maximizer at θ2.Lemma A.2 establishes this stability of arg maxα f(θ, α) with respect to θ.Source: A Proofs · p. 6
  • The maximized function g(θ) is L-smooth, with L = L11 + L2, and ∇g(θ) equals ∇θf(θ, α) for any α ∈ A(θ).The directional derivative does not depend on which maximizing α is chosen.Source: A Proofs · pp. 6–7
  • The proof also invokes a gradient-descent result for L-smooth μ-PL functions using step size 1/L.The supplied passage identifies the lemma and its setup but does not state the resulting bound.Source: A Proofs · p. 7

A.1 Proof of Theorem 3.2

The proof treats the game as approximate gradient descent on the maximized function g, using inner ascent steps to approximate its gradient. It concludes that an iterate is ε-stationary for the game.

A.1 Proof of Theorem 3.2

  • The proof bounds the inner-iterate gradient error and uses that approximation to transfer the outer descent guarantee to the game.It identifies the first- and second-argument gradients separately when describing the update.Source: §A.1 · pp. 7–8
  • Using ∇θf(θt, αK(θt)) in place of ∇g(θt) in gradient descent on g leads to an ε-stationary solution.The proof strategy is to take enough ascent steps before each θ update to mimic gradient descent on g.Source: §A.1 · pp. 7–8
  • At least one iterate t has ∥∇g(θt)∥ ≤ 5ε under the approximate-gradient descent argument.The argument applies approximate gradient descent to an L-smooth g from θ0 with initial gap at most ∆g.Source: §A.1 · p. 8
Loading 1812.02878v1…