Source-linked AI summary
What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
Chi Jin, Praneeth Netrapalli, Michael I. Jordan
TL;DR
Nonconvex-nonconcave minimax problems lack a settled local-optimality notion suited to sequential games, where player order matters. The paper defines local minimax for this setting and studies its properties and existence. It connects these points to stable GDA limit points, up to degenerate points.
Problem
The paper asks for a suitable local-optimality notion for nonconvex-nonconcave minimax problems, since simultaneous-game local Nash notions do not reflect consequential player order in sequential games.
Source: §1 · p. 2Method
The paper defines local minimax as a local surrogate for global minimax in sequential games and analyzes its properties and existence.
Source: §1 · p. 2Results
Under idealized parameter settings, stable GDA limit points coincide with local minimax points up to degenerate points.
Source: §1 · p. 2, §5 · p. 12Takeaways & Limitations
Local minimax provides a game-theoretic interpretation of stable GDA limit points, except for degenerate points.
Source: §1 · p. 2Local minimax points need not exist in general.
Source: §3.2 · p. 9
Abstract
from arXiv · showhide
Minimax optimization has found extensive applications in modern machine learning, in settings such as generative adversarial networks (GANs), adversarial training and multi-agent reinforcement learning. As most of these applications involve continuous nonconvex-nonconcave formulations, a very basic question arises---"what is a proper definition of local optima?" Most previous work answers this question using classical notions of equilibria from simultaneous games, where the min-player and the max-player act simultaneously. In contrast, most applications in machine learning, including GANs and adversarial training, correspond to sequential games, where the order of which player acts first is crucial (since minimax is in general not equal to maximin due to the nonconvex-nonconcave nature of the problems). The main contribution of this paper is to propose a proper mathematical definition of local optimality for this sequential setting---local minimax, as well as to present its properties and existence results. Finally, we establish a strong connection to a basic local search algorithm---gradient descent ascent (GDA): under mild conditions, all stable limit points of GDA are exactly local minimax points up to some degenerate points.
1 Introduction
The paper asks how to define local optimality for nonconvex-nonconcave minimax problems, where sequential play makes the order of the players consequential. It proposes local minimax for this setting and studies its properties, existence, and relation to GDA.
1 Introduction
- Because modern machine-learning minimax problems are often nonconvex-nonconcave, global Nash equilibria may be computationally intractable, motivating a local notion.The paper notes applications including GANs, adversarial training, and multi-agent reinforcement learning.Source: §1 · pp. 1–2
1.2 Related work
- The paper distinguishes local optimality for sequential games from local Nash notions developed for simultaneous games, where player order is not represented.Prior work also studies nonconvex-but-concave and variational-inequality settings, while Evtushenko's local notion is not determined by values in a small neighborhood and Fiez et al.'s notion assumes a nondegenerate Hessian [2019].Source: §1 · p. 2, §1.2 · p. 3
1.1 Our contributions
- Local minimax models sequential play by making the min-player minimize the maximum payoff, and the paper studies its properties and existence.The paper also relates local minimax points to stable GDA limit points, up to degenerate points.Source: §1 · p. 2, §1.1 · p. 2
- The paper connects local minimax points to GDA: under idealized settings, stable limit points coincide with them up to degenerate points.It presents this as a game-theoretic interpretation of stable GDA limit points.Source: §1.1 · p. 2, §1 · p. 2
- The paper also gives an efficiency guarantee for cases where maximizing over y can be solved efficiently or approximately by a max-oracle.Related work includes algorithms for nonconvex-but-concave problems [Rafique et al., 2018; Nouiehed et al., 2019], variational-inequality settings [Lin et al., 2018], and mixed Nash equilibria [Hsieh et al., 2018].Source: §1.1 · p. 3, §1.2 · p. 3
2 Preliminaries
The preliminaries establish the paper's focus on continuous two-player zero-sum games and distinguish simultaneous play, sequential play, and general dynamics. They introduce local Nash and global minimax concepts, and define stability for dynamical systems.
2 Preliminaries
- The paper focuses on pure-strategy, two-player zero-sum games with continuous payoff functions and vector actions.Mixed strategies are discussed in Appendix A.Source: §2 · p. 4, §2.1 · p. 4
2.1 Simultaneous games
- Local Nash equilibria extend simultaneous-game Nash equilibria by requiring each player to be locally optimal while the other's action is fixed, but such equilibria may not exist.The paper gives a twice-differentiable function with no pure-strategy local or global Nash equilibrium.Source: §2.1 · pp. 4–5
2.2 Sequential games
- In sequential games, the second player observes the first player's action; the resulting global minimax solution has the first player minimize the second player's maximum payoff.For general nonconvex-nonconcave functions, player order matters, and the paper notes that a formal local analogue was absent from prior literature.Source: §2.2 · pp. 5–6
2.3 Dynamical systems
- For general dynamics, a fixed point is linearly stable when the Jacobian's spectral radius is at most one; the figure contrasts local minimax with local Nash.In the figure's right-hand example, the origin is local minimax but not local Nash; in the left-hand example, it is both.Source: §2.3 · pp. 6–7, Figure 1 · p. 7
3 Main Results
The paper defines local minimaxity as a local surrogate for global minimaxity in sequential games, then studies its properties, existence, and relationship to GDA. In the large-γ limit, stable GDA points coincide with local minimax points up to degenerate points.
3.1 Local minimax points
- Local minimax is proposed as a local surrogate for global minimaxity in sequential games, where the order of play matters.Its definition uses local neighborhoods that may shrink at different rates, making the criterion depend on an infinitesimal neighborhood of the point.Source: §3.1 · pp. 7–8
- For continuous f, local minimaxity is equivalent to the second player locally maximizing and the first player locally minimizing the resulting value.The second player maximizes over a neighborhood of y⋆, and the first player locally minimizes that maximized value for sufficiently small neighborhoods.Source: §3.1 · p. 8
- Every local Nash equilibrium is a local minimax point, and local minimaxity weakens local Nash equilibrium’s nonexistence issues.The paper also gives first- and second-order characterizations, with the second-order conditions reflecting the sequential order of play and the interaction between players.Source: §3.1 · p. 8, §3.2 · pp. 8–9, D Proofs for Section 3.2 · p. 21
3.2 Properties and existence
- Local minimax points need not exist in general, and a global minimax point may be neither local minimax nor stationary.The paper gives a twice-differentiable function on a compact domain with no local minimax points; under additional regularity, including strong concavity in y and globality of all local maxima, global minimax points are local minimax points.Source: §3.2 · p. 9
3.3 Relation to the limit points of GDA
- For fixed γ, the stable-point set of γ-GDA need not contain all local minimax points, nor be contained in the union of local minimax and local maximin points.The paper establishes that both non-containment cases can occur for twice-differentiable objectives.Source: §3.3 · p. 11
- As γ tends to infinity, the limiting GDA sets contain local minimax points and contain no other points except stationary points with degenerate ∇²_yy f.Thus, the two limiting sets agree with local minimax points up to these degenerate points.Source: §3.3 · p. 11
- The paper interprets ∞-GDA as strict linearly stable limit points when γ increases very slowly over time and eventually tends to infinity.For large γ, the method can move substantially in y while making only small changes in x, approximating a local maximum in y under small changes in x.Source: §3.3 · p. 11
4 Gradient Descent with Max-Oracle
The section studies gradient descent with an approximate maximization oracle for the inner player. Its limit points are approximately stationary for the outer objective, measured using the Moreau envelope.
4 Gradient Descent with Max-Oracle
- The algorithm alternates descent in x with approximate maximization in y using an oracle for the inner maximum.At each step it obtains a y whose payoff is within ϵ of the maximum, then updates x by gradient descent.Source: §4 · p. 11
- Algorithm 2 converges, and its limit points are approximately stationary for φ(x) := max_y f(x, y).Because φ may be nonsmooth, approximate stationarity is measured using the gradient of its Moreau envelope; a small envelope gradient implies proximity to an approximately stationary point of φ.Source: §4 · pp. 11–12
- When f is ℓ-gradient Lipschitz, φ(x) := max_y f(x, y) is ℓ-weakly convex, supporting the use of its Moreau envelope to measure approximate stationarity.For λ < 1/ℓ, the paper relates a small gradient of the Moreau envelope to approximate stationarity of the original objective.Source: §4 · p. 12
- Theorem 31 gives a convergence guarantee for GD with Max-Oracle under smoothness and Lipschitz assumptions, with an additive error due to approximate maximization.The theorem’s stated error contribution includes 4ℓϵ from the oracle’s inexact solution.Source: §4 · p. 12
5 Conclusions
The conclusion presents local minimax as a local optimality notion for general nonconvex-nonconcave minimax problems and connects it to GDA’s stable limit points.
5 Conclusions
- The paper proposes local minimax as a mathematical definition of local optimality for two-player sequential minimax problems and reports results on its properties and existence.It also states that local minimax points equal stable GDA limit points up to some degenerate points.Source: §5 · p. 12
A Relation to Mixed Strategy Games
Mixed strategies remove the distinction between simultaneous and sequential games and guarantee equilibrium existence, but optimizing over distributions is infinite-dimensional. For Lipschitz games on bounded domains, approximate mixed-strategy equilibria can instead be obtained through a polynomial-dimensional pure-strategy sequential minimax problem.
A Relation to Mixed Strategy Games
- For continuous games on compact domains, mixed-strategy Nash equilibria always exist, and allowing mixed strategies removes the intrinsic difference between simultaneous and sequential games.The section also notes that the order of play is no longer important in this setting.Source: A Relation to Mixed Strategy Games · p. 16
- For Lipschitz games with domain diameters at most D, an approximate mixed-strategy Nash equilibrium can be found by solving a polynomial-dimensional pure-strategy sequential minimax problem.Theorem 35 gives a sample-size bound of N ≥ c · d^2(LD/ϵ)^2 log(LD/ϵ) for an absolute constant c.Source: A Relation to Mixed Strategy Games · pp. 16–17
- The reduction addresses the infinite-dimensional optimization over probability measures by using an empirical distribution of sampled actions as a mixed strategy.The argument uses uniform convergence over y, enabled by Lipschitz continuity and bounded Y.Source: A Relation to Mixed Strategy Games · pp. 16–17
- Theorem 35’s approximate equilibrium guarantee follows by solving the corresponding minimax and maximin problems and forming empirical distributions for both players.The proof samples actions independently from an optimal mixed strategy and applies a covering argument over Y.Source: A Relation to Mixed Strategy Games · p. 17
B Relation to Evtushenko [1974]
Evtushenko’s minimax property requires a point to be globally minimax within some neighborhood, but its status can depend on function values far from the point. Local minimax points satisfy this property, whereas the reverse implication fails.
B Relation to Evtushenko [1974]
- Evtushenko’s minimax property requires a point to be a global minimax point within a local neighborhood.The paper argues that this is not genuinely local because the property may depend on function values far from the point.Source: B Relation to Evtushenko [1974] · p. 18
- A point can satisfy Evtushenko’s property on a larger neighborhood but fail it on a smaller one, so the property depends on behavior away from the point.The example uses nested neighborhoods W1 ⊂ W2 around (0, −π).Source: B Relation to Evtushenko [1974] · p. 18
- Every local minimax point is an Evtushenko minimax point, but the converse does not hold.A global minimax point can be an Evtushenko minimax point without being local minimax.Source: B Relation to Evtushenko [1974] · p. 18
- Evtushenko minimax points need not satisfy local minimax’s first- and second-order necessary conditions, and may be non-stationary.The paper gives an example of a global minimax point that is Evtushenko minimax but not stationary.Source: B Relation to Evtushenko [1974] · p. 19
C Proofs for Section 3.1
The proofs establish equivalent forms of the local minimax definition, characterize it through nearby maximization in the maximizing variable, and show that local Nash equilibria are a special case.
C Proofs for Section 3.1
- Definition 14 characterizes local minimax using neighborhoods whose maximizing-player radius h(δ) tends to zero as the minimizing-player neighborhood shrinks.The definition’s equivalent forms allow h to be restricted to a monotonic or continuous function.Source: C Proofs for Section 3.1 · p. 19
- The proof shows that restricting h to be monotonic or continuous does not change which points qualify as local minimax.It establishes inclusions among the unrestricted, monotonic, and continuous versions of the definition.Source: C Proofs for Section 3.1 · pp. 19–20
- A point is local minimax exactly when the maximizing variable is locally maximizing and the minimizing variable locally minimizes each sufficiently small neighborhood-maximized function g_ϵ.Here g_ϵ(x) maximizes f(x, y) over y within distance ϵ of y⋆.Source: C Proofs for Section 3.1 · p. 20
- Every local Nash equilibrium is a local minimax point.The proof uses h(δ)=0 in the local minimax definition.Source: C Proofs for Section 3.1 · p. 20
D Proofs for Section 3.2
The proofs establish first- and second-order necessary conditions for local minimax points and a second-order sufficient condition for strict local minimax points. They also show that global minimax points need not be local minimax, and that local minimax points need not exist.
D Proofs for Section 3.2
- Any local minimax point of a continuously differentiable function is stationary in both players’ variables.The necessary condition is ∇_x f(x, y)=0 and ∇_y f(x, y)=0.Source: D Proofs for Section 3.2 · p. 20
- For twice-differentiable functions, local minimax points satisfy a second-order necessary condition.The supplied proposition states the condition but its formula is not present in the passage.Source: D Proofs for Section 3.2 · p. 21
- A stationary point satisfying the stated second-order sufficient condition is a strict local minimax point.The proof constructs a shrinking neighborhood for the maximizing player based on the response to a perturbation in x.Source: D Proofs for Section 3.2 · p. 21
- A global minimax point need not be stationary or local minimax, while global minimax points are local minimax under strong concavity and global-maxima assumptions.The sufficient result assumes f(x, ·) is strongly concave near local maxima and that all such maxima are global.Source: D Proofs for Section 3.2 · p. 22
- A twice-differentiable function on a compact domain can have no local minimax points.The proof gives f(x, y)=y^2−2xy on [−1,1]×[−1,1] as an example.Source: D Proofs for Section 3.2 · p. 22
E Proofs for Section 3.3
The proofs characterize GDA stability through Jacobian eigenvalues and relate limiting stable points to local minimax points, with a degenerate-Hessian exception. Counterexamples distinguish fixed-parameter GDA stability from local Nash, local minimax, and local maximin optimality.
E Proofs for Section 3.3
- Strict linear stability under γ-GDA is characterized by the Jacobian eigenvalues; in the small-step limit, all must have negative real parts.The dynamics’ Jacobian is I + ηJγ, with eigenvalues 1 + ηλ_i.Source: E Proofs for Section 3.3 · p. 23
- For any fixed γ, every local Nash point is a γ-GDA stable point, but some γ-GDA stable points are not local Nash points.The proof uses the eigenvalue criterion for strict linear stability, equivalent to negative real parts as the GDA step size tends to zero.Source: E Proofs for Section 3.3 · p. 23
- For fixed γ, examples show that local minimax points need not be γ-GDA stable, and γ-GDA stable points need not be local minimax or local maximin.The examples establish both failures of set inclusion.Source: E Proofs for Section 3.3 · p. 24
- In the limiting GDA result, local minimax points are stable, while stable points are local minimax or stationary points with degenerate y-Hessian.The proof relates small-step Jacobian eigenvalues to the eigenvalues of B and A − CB^-1C^T.Source: E Proofs for Section 3.3 · pp. 24–26
F Proofs for Section 4
The proof of Theorem 31 adapts the proof of Davis and Drusvyatskiy by accounting for an approximate maximizer. It uses the Moreau envelope gradient and a telescoping argument to establish the result.
F Proofs for Section 4
- Theorem 31’s proof follows Davis and Drusvyatskiy’s Theorem 2.1 proof, with an additional error term because Algorithm 2 uses an approximate maximizer.The proof notes that the argument still goes through with this error term.Source: F Proofs for Section 4 · p. 26
- The proof uses an equation for the Moreau envelope gradient and invokes smoothness and approximate-maximizer conditions.The approximate maximizer is specified for each iterate x_t.Source: F Proofs for Section 4 · pp. 26–27
- It defines a proximal minimizer for each iterate, telescopes the resulting inequalities over t, and uses them to prove the result.The proof identifies the proximal point as the minimizer of φ(x) plus a quadratic penalty around x_t.Source: F Proofs for Section 4 · p. 27