PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity of Constrained Min-Max Optimization

Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis

arXiv:2009.09623v1cs.CCcs.LGmath.OC

TL;DR

For nonconvex-nonconcave min-max optimization, the complexity of finding approximate local min-max points remains poorly understood. The paper characterizes that complexity and proves that computing approximate local min-max solutions is PPAD-complete.

  • Problem

    The complexity of finding approximate local min-max solutions for nonconvex-nonconcave objectives is poorly understood, while approximate stationary points may not exist and checking their existence is NP-hard.

    Source: §1 · pp. 3–4

  • Method

    The authors prove complexity results via reductions that encode discrete games in smooth, Lipschitz objectives using novel, computationally efficient interpolation coefficients.

    Source: §1.1 · p. 8, §7.2.1 · p. 37

  • Results

    Computing (ε, δ)-local min-max solutions is PPAD-complete; in the local regime, this entails super-polynomial time in at least one of 1/ε, G, L, or d unless FP = PPAD.

    Source: §1 · p. 5, §4 · p. 20

  • Takeaways & Limitations

    The local min-max problem is markedly harder than finding local minima, which Projected Gradient Descent solves in polynomial time in these parameters.

    Source: §4 · p. 20

    For arbitrary ε and δ, finding an (ε, δ)-local min-max equilibrium is neither guaranteed to have a solution nor efficiently verifiable, even on [0, 1]^d.

    Source: §3.1 · p. 16

Abstract

from arXiv · show

Despite its important applications in Machine Learning, min-max optimization of nonconvex-nonconcave objectives remains elusive. Not only are there no known first-order methods converging even to approximate local min-max points, but the computational complexity of identifying them is also poorly understood. In this paper, we provide a characterization of the computational complexity of the problem, as well as of the limitations of first-order methods in constrained min-max optimization problems with nonconvex-nonconcave objectives and linear constraints. As a warm-up, we show that, even when the objective is a Lipschitz and smooth differentiable function, deciding whether a min-max point exists, in fact even deciding whether an approximate min-max point exists, is NP-hard. More importantly, we show that an approximate local min-max point of large enough approximation is guaranteed to exist, but finding one such point is PPAD-complete. The same is true of computing an approximate fixed point of Gradient Descent/Ascent. An important byproduct of our proof is to establish an unconditional hardness result in the Nemirovsky-Yudin model. We show that, given oracle access to some function $f : P \to [-1, 1]$ and its gradient $\nabla f$, where $P \subseteq [0, 1]^d$ is a known convex polytope, every algorithm that finds a $\varepsilon$-approximate local min-max point needs to make a number of queries that is exponential in at least one of $1/\varepsilon$, $L$, $G$, or $d$, where $L$ and $G$ are respectively the smoothness and Lipschitzness of $f$ and $d$ is the dimension. This comes in sharp contrast to minimization problems, where finding approximate local minima in the same setting can be done with Projected Gradient Descent using $O(L/\varepsilon)$ many queries. Our result is the first to show an exponential separation between these two fundamental optimization problems.

1 Introduction

The introduction explains how constrained nonconvex-nonconcave min-max optimization departs from the convex-concave setting and presents complexity results for existence, local equilibria, and oracle-query requirements. It also contrasts these problems with local minimization and outlines the techniques behind the hardness results.

1 Introduction

  • Convex-concave objectives admit solutions under compactness and are amenable to convex programming and first-order methods, while nonconvex-nonconcave applications such as GAN training evade that toolkit.The introduction also cites adversarial robustness as an application of nonconvex-nonconcave min-max optimization.Source: §1 · p. 3
  • Deciding whether an exact or approximate min-max solution exists is NP-hard even for smooth, Lipschitz objectives and constant approximation; checking for approximate stationary points is also NP-hard.The stationary-point hardness holds on [0, 1]^d with Lipschitzness and smoothness polynomial in d.Source: §1 · p. 4
  • When δ < ε/G, every feasible point is an (ε, δ)-local solution; in the interesting local regime, smoothness guarantees existence, and projected gradient descent-ascent fixed points exist and lie in PPAD.The paper relates computing local min-max solutions to computing approximate fixed points of the projected gradient descent-ascent dynamics.Source: §1 · p. 5
  • Computing (ε, δ)-local min-max equilibria in the local regime is PPAD-complete, even for smooth, Lipschitz objectives over polytopes inside [0, 1]^d with polynomially bounded parameters.Equivalently, computing α-approximate fixed points of projected gradient descent-ascent is PPAD-complete under the stated polynomial bounds.Source: §1 · p. 5
  • Oracle algorithms need exponentially many queries in at least one of 1/ε, L, G, or d, versus O(B · L/ε) queries for approximate local minima, yielding an exponential black-box separation.The d-exponential lower bound persists when L, G, 1/ε, and 1/δ are polynomial in d.Source: §1 · p. 7

1.1 Brief Overview of the Techniques

  • The PPAD-hardness proof introduces PPAD-hard BiSperner, encodes it in constrained discrete zero-sum local equilibria, then smoothly interpolates the game using novel coefficients for high dimensions.The construction’s final steps are designed to preserve computational and query efficiency for both white-box and black-box results.Source: §1.1 · pp. 7–8

1.2 Local Minimization vs Local Min-Max Optimization

  • Unlike min-min best-response paths, where objective values decrease and preclude cycles, min-max paths can cycle and reveal little about distance along long paths.This contrast helps explain why the hardness construction applies to min-max optimization but does not transfer to local minimization.Source: §1.2 · pp. 8–9

1.3 Further Related Work

  • The paper situates its results in total-search equilibrium complexity and uses Brouwer fixed-point oracle lower bounds to prove black-box lower bounds.Source: §1.3 · pp. 9–10

2 Preliminaries

The preliminaries specify the smooth, Lipschitz function setting and its access models, then define the complexity framework used to state the paper’s computational results.

2 Preliminaries

  • The studied objectives are continuously differentiable functions on polytopes in [0, 1]^d, with G-Lipschitzness and L-smoothness defined using Euclidean distance.Lipschitzness bounds changes in function value, while smoothness bounds changes in the gradient.Source: §2 · p. 11
  • The black-box model returns function and gradient values at queried points, while the white-box model supplies a polynomial-time machine that computes approximate values for both.The white-box machine’s running time is polynomial in input bit length and log(1/ε), with error at most ε; the black-box model follows the traditional optimization lower-bound model.Source: §2 · p. 11
  • Function access is promised to be consistent with differentiability, Lipschitzness, smoothness, and boundedness; hardness reductions syntactically ensure these properties.Upper bounds assume the promises hold, while lower-bound constructions satisfy them, so hardness does not rely on difficulty checking the promises.Source: §2 · pp. 11–12

2.1 Complexity Classes and Reductions

  • FNP comprises polynomially verifiable search relations with polynomial-length solutions, and NP consists of their associated decision problems.The paper uses polynomial-time reductions that map solutions of the target problem back to solutions of the original problem.Source: §2.1 · pp. 12–13
  • PPAD consists of search problems reducible to End-of-a-Line, a total problem whose solutions identify an endpoint or verify that the origin has balanced degree.PPAD includes fixed-point problems, and Brouwer is PPAD-complete, including for d = 2 and for γ = poly(1/d), L = poly(d).Source: §2.1 · p. 13

3 Computational Problems of Interest

The section defines constrained approximate stationary points, local minima, and local min-max equilibria, then formulates search problems for them and related gradient-dynamics fixed points.

3.1 Mathematical Definitions

  • The study focuses on feasible polytopes formed by intersecting [0, 1]^d with linear constraints, and defines its computational problems as promise problems.The promise ensures that the supplied function and gradient computations are consistent with the stated smoothness and Lipschitzness.Source: §3.1 · p. 14, §3.2 · p. 16
  • Constrained local minima always exist, but arbitrary-parameter solutions lack known polynomial-size, efficiently verifiable certificates; local min-max equilibria are neither always existent nor efficiently verifiable.The definitions use ε and δ: local minima compare the function with feasible points within distance δ, while local min-max equilibria require approximate minimization in x and maximization in y. Large δ can capture global optima, while small δ captures local ones.Source: §3.1 · pp. 15–16

3.2 First-Order Local Optimization Computational Problems

  • StationaryPoint is in FNP and is FNP-hard even for constant ε, the unconstrained hypercube, and G, L polynomial in d.Its promise formulation uses white-box access to a machine computing a Lipschitz, smooth function and gradient; black-box variants replace the machines with oracles. LocalMin and LocalMinMax behave differently across approximation regimes tied to ε, δ, G, L, and d.Source: §3.2 · pp. 16–17

3.3 Bonus Problems: Fixed Points of Gradient Descent/Gradient Descent-Ascent

  • In certain approximation regimes, GDFixedPoint is polynomial-time equivalent to LocalMin, while GDAFixedPoint is equivalent to LocalMinMax.The fixed points target projected gradient descent and projected gradient descent-ascent dynamics, respectively, with learning rate 1.Source: §3.3 · pp. 17–18

4 Summary of Results

The section characterizes constrained optimization across several regimes: stationary-point computation is FNP-complete, while local min-max computation is in PPAD and PPAD-hard, with an unconditional black-box query lower bound.

Complexity of approximate stationary points

  • StationaryPoint is FNP-complete for ε≤1/24; any algorithm that verifies existence and computes constrained approximate stationary points requires super-polynomial time in G, L, or d unless P=NP.Unlike the unconstrained bounded-range case, constrained approximate stationary points are not guaranteed to exist; unconstrained ones can be found in time poly(B, 1/ε, L).Source: §4 · p. 18

LocalMin and LocalMinMax regimes

  • In the global-optimum regime, LocalMin and LocalMinMax are FNP-hard; when δ<ε/G, every domain point solves both problems.The global-regime hardness holds even for ε=Θ(1) and G,L=O(d).Source: §4 · p. 19

Local regime

  • For δ<sqrt(2ε/L), Projected Gradient Descent solves LocalMin in time O(B·L/ε), while local min-max equilibria are guaranteed to exist and LR-LocalMinMax belongs to PPAD.In this regime, LocalMinMax is equivalent to GDAFixedPoint, and both problems belong to PPAD.Source: §4 · pp. 19–20
  • LR-LocalMinMax is PPAD-hard for δ≥sqrt(ε/L), even when 1/ε, G, L, and B are polynomially bounded in d.Consequently, computing local min-max equilibria requires super-polynomial time in at least one of 1/ε, G, L, or d unless FP=PPAD; local minima remain computable in polynomial time in those parameters.Source: §4 · pp. 19–20

Black-box lower bound

  • A black-box reduction proves an unconditional lower bound in the black-box model for finding approximate local min-max equilibrium, with an oracle supplying a G-Lipschitz, L-smooth function and its gradient.The oracle’s function is defined on P(A, b) and takes values in [-1, 1].Source: §4 · p. 20

5 Existence of Approximate Local Min-Max Equilibrium

Every G-Lipschitz, L-smooth objective admits an (ε, δ)-local min-max equilibrium when δ < sqrt(2ε/L), and LR-LocalMinMax is a total PPAD search problem.

5 Existence of Approximate Local Min-Max Equilibrium

  • For G-Lipschitz, L-smooth functions, an (ε, δ)-local min-max equilibrium exists whenever δ < sqrt(2ε/L).This establishes totality of LR-LocalMinMax for instances satisfying that condition.Source: §5 · p. 20
  • LR-LocalMinMax and GDAFixedPoint are equivalent under polynomial-time reductions.The proof uses this equivalence to establish totality and PPAD membership for LR-LocalMinMax.Source: §5 · p. 20
  • GDAFixedPoint and LR-LocalMinMax are both total search problems in PPAD.The paper notes that this theorem also implies Theorem 4.3.Source: §5 · p. 21

6 Hardness of Local Min-Max Equilibrium – Four-Dimensions

This section develops a four-dimensional reduction from PPAD-hard 2D-BiSperner, mapping its colorings to smooth objectives to establish PPAD-completeness for GDAFixedPoint and LR-LocalMinMax, and gives regularity bounds for the constructed objective. It also explains why the proof does not extend to minimization hardness.

6 Hardness of Local Min-Max Equilibrium – Four-Dimensions

  • A reduction from 2D-BiSperner to GDAFixedPoint uses input size poly(n), α = exp(−poly(n)), G = L = exp(poly(n)), and B = 2.The section establishes the hardness result through a four-dimensional reduction.Source: §6 · p. 21
  • GDAFixedPoint and LR-LocalMinMax are PPAD-complete even for d = 4 and B = 2.The result rules out algorithms polynomial in log G, log L, log(1/α), and B for GDAFixedPoint unless FP = PPAD; the section notes stronger parameter bounds require higher dimensions.Source: §6 · p. 21

6.1 The 2D Bi-Sperner Problem

  • 2D-BiSperner is PPAD-hard: its succinct circuit-defined grid instance asks for a panchromatic cell or a vertex violating the boundary-coloring rules.Each grid vertex receives one color from {1−, 1+} and one from {2−, 2+}; proper colorings enforce opposite first-color signs on the left and right boundaries and opposite second-color signs on the bottom and top.Source: §6.1 · p. 23

6.2 From 2D Bi-Sperner to Fixed Points of Gradient Descent/Ascent

  • The reduction encodes grid-vertex colors as gradient directions and smoothly interpolates corner functions, with domain constraints preventing interpolation derivatives from creating spurious fixed points.Its key correctness condition is that cells missing a color retain a sufficiently large gradient in the corresponding direction.Source: §6.2 · pp. 25–27
  • The constructed fCl is continuous and differentiable throughout [0, 1]^4, Θ(1/δ)-Lipschitz, and Θ(1/δ^2)-smooth, where δ = 1/(N − 1).The interpolation uses a smooth step function to ensure the overall function has a Lipschitz continuous gradient.Source: §6.2 · p. 28
  • The function fCl is differentiable across cell boundaries, O(1/δ)-Lipschitz, and Θ(1/δ^2)-smooth.The boundary argument establishes differentiability throughout [0, 1]^4.Source: §6.2 · p. 29

6.2.1 Description and Correctness of the Reduction – Proof of Theorem 6.1

  • The reduction uses constant-size linear constraints and sets G=O(2^n) and L=O(2^(2n)); its function-and-gradient evaluator is polynomial-time.The parameters bound the Lipschitzness and smoothness of fCl, respectively.Source: §6.2.1 · pp. 29–30
  • Theorem 6.1 reduces 2D-BiSperner to GDAFixedPoint: every fixed point yields a panchromatic cell or a violation of proper-coloring rules, and fCl ranges in [-2, 2].The reduction is constructed in polynomial time.Source: §6.2.1 · pp. 29, 30, 33
  • The authors explain that the proof does not establish minimization hardness because replacing xi−yi with xi+yi prevents a gradient lower bound of 1/2.The term |x2+y2| can dominate and make the derivative's sign depend on its value.Source: §6.2.1 · p. 33

7 Hardness of Local Min-Max Equilibrium – High-Dimensions

This section develops and verifies a high-dimensional reduction from HighD-BiSperner to GDAFixedPoint, using smooth, efficiently computable interpolation to construct Lipschitz and smooth functions. The reduction yields the stated polynomial-time and exponential black-box query lower bounds.

7 Hardness of Local Min-Max Equilibrium – High-Dimensions

  • The reduction rules out poly(d, G, L, 1/ε)-step algorithms for GDAFixedPoint unless FP = PPAD, with 1/α, G, and L polynomial in d; oracle-only LR-LocalMinMax requires exponentially many queries in at least one parameter.The lower-bound alternatives are d, G, L, or 1/ε.Source: §7 · p. 33, §7.1 · p. 36

7.1 The High Dimensional Bi-Sperner Problem

  • HighD-BiSperner uses succinct circuit colorings and asks for a polynomially checkable certificate of a panchromatic cubelet or a boundary-rule violation.The certificate gives paired vertices for each of d colors in one cubelet, avoiding the need to query all 2^d corners.Source: §7.1 · pp. 34–35
  • HighD-BiSperner is PPAD-hard: a polynomial-time reduction maps γ-SuccinctBrouwer instances to grids with N = Θ(d/γ^2).A panchromatic cubelet yields a γ-SuccinctBrouwer solution.Source: §7.1 · pp. 35–36

7.2 From High Dimensional Bi-Sperner to Fixed Points of Gradient Descent/Ascent

  • The reduction encodes a coloring circuit as a function on [0, 1]^d × [0, 1]^d, but canonical cubelet simplicization ensures Lipschitz continuity without ensuring smoothness.The challenge is to interpolate corner functions efficiently while preserving both properties.Source: §7 · pp. 33–34, §7.2 · p. 37

7.2.1 Smooth and Efficient Interpolation Coefficients

  • Smooth and efficient interpolation coefficients (SEIC) provide twice-differentiable convex weights with at most d + 1 active coefficients, identifiable in polynomial time.Their boundary property ensures an active vertex lies on the corresponding hypercube boundary when x is near that boundary.Source: §7.2.1 · p. 37

7.2.2 Definition of a Lipschitz and Smooth Function Based on a BiSperner Instance

  • The resulting coloring-based function is O(d^15/δ)-Lipschitz and O(d^27/δ^2)-smooth; the reduction uses it as the payoff over the polytope P(A, b).These bounds make the function a valid GDAFixedPoint input.Source: §7.2.2 · pp. 38–39, §7.2.3 · p. 39

7.2.3 Description and Correctness of the Reduction – Proof of Theorem 4.4

  • A polynomial-time Turing machine constructed from the input circuit computes the reduction’s function and gradient in time polynomial in the input bit lengths and log(1/ε).The machine computes the specified scalar and vector outputs to accuracy ε.Source: §7.2.3 · p. 40
  • The construction sets α = Δ/3, with G = O(d^15/δ) and L = O(d^27/δ^2).Here Δ = t·δ/d^14 for a positive constant t.Source: §7.2.3 · pp. 39, 42
  • Every solution to the constructed GDAFixedPoint instance yields a HighD-BiSperner solution, either through a vertex or a panchromatic cubelet.The construction’s function has range [-d, d], which completes the proof of Theorem 4.4 using Theorem 5.1.Source: §7.2.3 · p. 42

8 Smooth and Efficient Interpolation Coefficients

The section constructs smooth and efficient interpolation coefficients for every dimension and polynomial-size discretization, with properties (A)–(D). Smooth-step functions support the construction, including a higher-dimensional design whose properties are verified by lemmas.

8 Smooth and Efficient Interpolation Coefficients

  • The coefficients are nonnegative and sum to one; at most d + 1 are nonzero at any x, and the active set is computable in polynomial time.Near each coordinate boundary, an active vertex also has that coordinate equal to 0 or 1, respectively.Source: §8 · p. 42
  • For every d and N = poly(d), a family of smooth and efficient interpolation coefficients satisfying properties (A)–(D) exists.This is the section’s main construction result.Source: §8 · p. 43

8.1 Smooth Step Functions – Toy Single Dimensional Example

  • In one dimension, the authors use smooth step functions to construct N coefficients satisfying properties (A)–(D), while noting that extending this approach to multiple dimensions is harder.The construction uses S∞ and establishes twice differentiability, partition of unity, sparsity, and the boundary condition.Source: §8.1 · pp. 43–45
  • Lemma 8.3 states S and S∞ are monotone increasing, S(0)=S∞(0)=0 and S(1)=S∞(1)=1, and S′ and S′′ vanish at both endpoints.For every k in N, the kth derivative of S∞ at 1 is 0.Source: §8.1 · p. 43

8.2 Construction of SEIC Coefficients in High-Dimensions

  • A two-triangle split with a twice continuously differentiable soft-max fails in two dimensions because the resulting coefficients have discontinuous gradients along the diagonal.Source: §8.2 · p. 45
  • The higher-dimensional construction defines cubelet-local Qv functions and uses them to build the interpolation coefficients Pv.The Qv definition uses a cubelet’s corners and the point’s canonical representation.Source: §8.2 · p. 46

8.3 Sketch of the Proof of Theorem 8.1

  • The proof establishes that Pv is continuous and twice differentiable, vanishes with its first and second derivatives outside the cubelet, and has exactly d + 1 positive coefficients at each x.Source: §8.3 · p. 47
  • The proof also uses a boundary lemma to show that an active vertex has coordinate 0 near the lower boundary and 1 near the upper boundary, completing property (D).Source: §8.3 · p. 47

9 Unconditional Black-Box Lower Bounds

Section 9 derives unconditional black-box query lower bounds for constrained min-max optimization by reducing a hard fixed-point problem to the paper’s GDAFixedPoint and LR-LocalMinMax problems. The reduction preserves oracle access to the objective and its gradient, with each such query simulated using d + 1 HighD-BiSperner queries.

9 Unconditional Black-Box Lower Bounds

  • For a 2-Lipschitz map M, finding w⋆ with ∥M(w⋆) − w⋆∥2 ≤ 1/(2c) requires at least 2^d distinct value queries.The theorem assumes black-box access to M : [0, 1]^d → [0, 1]^d, with c a universal constant.Source: §9 · p. 47
  • When N = O(d), solving a HighD-BiSperner instance in the black-box model requires at least 2^d oracle calls.This corollary supplies the query lower bound used in the reduction to the optimization problems.Source: §9 · p. 48
  • At least 2^d/(d + 1) oracle queries are needed to solve GDAFixedPoint and LR-LocalMinMax with black-box access to f and its gradient.Each query to the function-and-gradient oracle can be implemented with d + 1 HighD-BiSperner queries, and every solution reveals a solution to the starting instance; the proof assumes infinite-precision real operations.Source: §9 · pp. 47–49, Figure 8 · p. 48

10 Hardness in the Global Regime

In the global regime, the section establishes FNP-hardness for both LocalMinMax and LocalMin, and gives a black-box query lower bound for minimization.

10 Hardness in the Global Regime

  • LocalMinMax is FNP-hard even when ε is any value ≤1/384, δ is any value ≥1, and the feasible set P(A,b) is [0,1]^d.The formula φ is satisfiable if and only if f has a (1/384, 1)-local min-max equilibrium. A satisfying assignment can be found from an approximate stationary point using constructive proofs of the Lovász Local Lemma.Source: §10 · pp. 49–50
  • The LocalMin reduction is FNP-hard for ε≤1/24 and δ≥√n, the diameter of its feasible set.It uses the clause-polynomial sum: a satisfying formula has a point with f(x)=0, while f(x)≤1/24 implies satisfiability by the Lovász Local Lemma [EL73]; a constructive proof recovers an assignment [Mos09, MT10].Source: §10 · p. 51
  • Fewer than O(2^d/d) value/gradient queries cannot determine a global-regime LocalMin in the black-box construction.Each function query can be simulated with at most d+1 queries to the Boolean formula oracle, whose satisfiability requires Ω(2^d) queries; the constructed function encodes formula values at hypercube vertices.Source: §10 · pp. 51–52

A Proof of Theorem 4.1 · B Missing Proofs from Section 5

Appendix A proves Theorem 4.1 by reducing 3-SAT(3) to approximate StationaryPoint; Appendix B gives proofs of totality and PPAD inclusion for LR-LocalMinMax and GDAFixedPoint.

A Proof of Theorem 4.1

  • The proof reduces FNP-complete 3-SAT(3) to ε-StationaryPoint.This reduction is used to establish FNP-hardness.Source: A Proof of Theorem 4.1 · p. 59
  • For each 3-SAT(3) instance, the construction defines f on [0, 1]^(n+m) using a polynomial for each clause, formed from its literal variables.The function maps to [0, 1]; each literal contributes a factor determined by whether it is positive or negated.Source: A Proof of Theorem 4.1 · p. 59
  • The constructed function has Lipschitz constant G = Θ(√(n + m)) and smoothness L = Θ(n + m).Here n is the number of variables and m is the number of clauses.Source: A Proof of Theorem 4.1 · p. 59
  • A satisfying assignment exists if and only if the constructed function has a point with gradient norm below 1/24.For the reverse direction, independently rounding variables according to the point’s coordinates and applying the Lovász Local Lemma [EL73] yields a satisfying assignment.Source: A Proof of Theorem 4.1 · pp. 59–60
  • A satisfying assignment can be found from an approximate stationary point using constructive Lovász Local Lemma results [Mos09, MT10].The proof concludes that the formula is satisfiable exactly when f has a 1/24-approximate stationary point.Source: A Proof of Theorem 4.1 · p. 60

B Missing Proofs from Section 5

B.1 Proof of Theorem 5.1

The proof establishes polynomial-time reductions in both directions between LR-LocalMinMax and GDAFixedPoint. It shows how approximate fixed points and approximate local min-max equilibria imply one another under the theorem’s parameter choices.

B.1 Proof of Theorem 5.1

  • The proof reduces LR-LocalMinMax to GDAFixedPoint and GDAFixedPoint to LR-LocalMinMax.These are the two directions used to establish the theorem’s claims.Source: §B.1 · pp. 60–61
  • An α-approximate fixed point yields local min-max inequalities within ε throughout the feasible δ-neighborhoods of x⋆ and y⋆.The proof establishes the inequalities separately for feasible x near x⋆ and feasible y near y⋆.Source: §B.1 · pp. 60–61
  • Conversely, an (ε, δ)-local min-max equilibrium implies that both coordinates’ projected GDA updates are within α/2 of their current values.The proof shows the x-coordinate bound and states that the y-coordinate argument is identical.Source: §B.1 · p. 61
  • For the converse bound, the proof uses δ = α/(5L + 2) and handles larger projection displacements by testing a point δ away along the displacement direction.Local equilibrium and L-smoothness at that point yield the required projected-update bound.Source: §B.1 · pp. 61–62

B.2 Proof of Theorem 5.2

The proof reduces GDAFixedPoint to Brouwer, establishing totality and PPAD membership for GDAFixedPoint and, via Theorem 5.1, LR-LocalMinMax. It validates the reduction by showing that a sufficiently accurate fixed point of the constructed map yields an approximate fixed point of GDA.

B.2 Proof of Theorem 5.2

  • The reduction establishes totality and PPAD membership for GDAFixedPoint and LR-LocalMinMax, using Brouwer and the reduction in Theorem 5.1.Brouwer is total and in PPAD.Source: §B.2 · p. 62
  • The construction maps f and α to M on P(A, b), which is (L + 1)-Lipschitz when f is L-smooth.The Brouwer approximation parameter γ is chosen using α and G.Source: §B.2 · p. 62
  • The proof shows that a γ-approximate fixed point of M is an α-approximate fixed point of FGDA, completing the reduction’s validity argument.It combines projection-based inequalities for the x and y coordinates.Source: §B.2 · pp. 62–63

C Missing Proofs from Section 8 · C.1 Proof of Lemma 8.10 · Moreover if Qc

Appendix C supplies missing proofs for Section 8, including differentiability results for Q_c^v, smoothness of P_v across cubelet boundaries, and a polynomial-time bound on |R+(x)|.

C Missing Proofs from Section 8

  • Appendix C presents missing proofs for Lemmas 8.10, 8.11, and 8.12, and defines L_c(c) as the set of corners of cubelet L(c).L(c) is the cubelet whose down-left corner is c.Source: C Missing Proofs from Section 8 · p. 63

C.1 Proof of Lemma 8.10

  • The proof of Lemma 8.10 first analyzes the differentiability of the functions Q_c^v defined in Definition 8.7.Source: §C.1 · p. 64

Moreover if Qc

  • Q_c^v(x) is continuous and twice differentiable, with the indicated mixed second derivative equal to zero.Source: Moreover if Qc · p. 64
  • Across cubelet boundaries, Lemma C.2 establishes the matching conditions needed for P_v(x) to remain continuous and twice differentiable.The proof first establishes that Q_c^v is twice differentiable within a cubelet and that its functions change value smoothly between cubelets.Source: Moreover if Qc · p. 65
  • P_v(x) is continuous at cubelet boundaries, and its first derivative exists there because the one-sided limits agree for shared vertices.Source: Moreover if Qc · pp. 66–67
  • |R+(x)| is at most d + 1, and its vertices can be computed in polynomial time by sorting the canonical coordinates.Source: Moreover if Qc · p. 68

C.1.1 Proof of Lemma C.2

The proof establishes consistency of the cubelet-based representation and uses boundary derivative properties to handle the cases of Lemma C.2. It reduces the vertex cases to adjacent-cubelet comparisons.

C.1.1 Proof of Lemma C.2

  • On a shared boundary of adjacent cubelets, a point has the same canonical representation in both cubelets.This is the boundary-consistency property used in the subsequent comparisons.Source: §C.1.1 · pp. 68–69
  • At shared boundaries, derivatives in coordinates other than the differing coordinate agree, while derivatives involving that coordinate vanish at the relevant endpoints.The proof invokes S′(0) = S′(1) = 0 for first derivatives and S′(0) = S′(1) = S′′(0) = S′′(1) = 0 for second derivatives.Source: §C.1.1 · p. 69
  • For vertices common to both cubelets, the proof follows a sequence of corners and applies Lemma C.4 to establish Case 1 of Lemma C.2.The sequence keeps the vertex in each cubelet along the way.Source: §C.1.1 · pp. 69–70
  • For vertices in one cubelet but not the other, a corner sequence and Lemma C.4 reduce Case 2 to Case 1; Case 3 follows similarly.The sequence ends when the vertex no longer belongs to the cubelet under consideration.Source: §C.1.1 · p. 70

C.2 Proof of Lemma 8.11

The section proves Lemma 8.11 by establishing bounds on the gradient and Hessian of Pv(x) using auxiliary smooth-step properties and technical lemmas. The proof also bounds h(x) and uses a gap among coordinate values to obtain a vertex with separated coordinates.

C.2 Proof of Lemma 8.11

  • For every x in [0, 1], h(x) lies in [1/4, 1].The section establishes this bound before beginning the proof statements.Source: §C.2 · p. 71
  • For x ≥ 1/d, monotonicity of S∞ gives S∞(x) ≥ S∞(1/d) ≥ 2^-d.The lower bound uses h(1/d) ≤ 1.Source: §C.2 · p. 71
  • The section’s main result is a proof of the gradient and Hessian bounds for Pv(x) stated in Lemma 8.11.The proof concludes by combining Lemmas C.7 and C.9 after using Lemmas C.6 and C.8.Source: §C.2 · pp. 71, 75
  • A gap greater than 1/(d + 1) among 0, p1, …, pd, 1 yields a vertex whose cross-group coordinate differences are at least 1/(d + 1).For this vertex, the smoothed differences are bounded below by c2^-(d+1)^2.Source: §C.2 · p. 72

C.3 Proof of Lemma 8.12

The proof partitions canonical coordinates and uses positive-potential vertices or constructed corners to establish the lemma’s boundary statements, treating the upper-boundary case separately for odd and even N.

C.3 Proof of Lemma 8.12

  • For x_i < 1/(N −1), if B is empty then P_sc(x) > 0; otherwise a constructed corner v lies in R+(x), has P_v(x) > 0, and satisfies v_i = s_i = 0.The proof places coordinate i in A for this case.Source: §C.3 · p. 75
  • For odd N, s_i = 1 −1/(N −1) and t_i = 1; the empty-A case gives P_tc(x) > 0, while otherwise the constructed corner has v_i = t_i = 1.In the latter case, v lies in R+(x) and has positive potential.Source: §C.3 · p. 76
  • For even N, t_i = 1 −1/(N −1) and s_i = 1; if B is empty then P_sc(x) > 0, otherwise the constructed corner has v_i = s_i = 1.The constructed corner lies in R+(x) and has positive potential, completing the second statement together with the odd-N case.Source: §C.3 · p. 76

D Constructing the Turing Machine – Proof of Theorem 7.6 · E Convergence of PGD to Approximate Local Minimum

Section D establishes polynomial-time computability of fCl and its gradient; Section E presents projected-gradient convergence and its implication for LocalMin in the local regime.

D Constructing the Turing Machine – Proof of Theorem 7.6

  • Theorem 7.6 establishes that fCl and its gradient are computable by a polynomial-time Turing machine.The construction computes the relevant vertices and assembles the function from their coefficients.Source: D Constructing the Turing Machine –… · pp. 76, 83
  • Machines compute S∞(x) and S′∞(x) to b-bit accuracy in time polynomial in b = log(1/ε) and the binary representation of x.Here x is in [0, 1] and ε is supplied in binary.Source: D Constructing the Turing Machine –… · p. 76
  • Machines compute the relevant Q coefficients in polynomial time and identify at most d + 1 vertices with positive coefficients for each cell.The construction finds these vertices by sorting the coordinates of the canonical representation.Source: D Constructing the Turing Machine –… · pp. 79–80
  • Machines compute Pv(x) and its gradient in polynomial time for vertices with Pv(x) > 0, of which there are at most d + 1.The stated running time is polynomial in the accuracy bits, dimension, and binary representation of x.Source: D Constructing the Turing Machine –… · p. 81

E Convergence of PGD to Approximate Local Minimum

  • Projected Gradient Descent solves LocalMin in time poly(1/ε, L, G, d) when (ε, δ) are in the local regime.The section presents the result as following from the fast convergence of PGD to a first-order stationary point.Source: E Convergence of PGD to Approximate… · p. 83
  • Theorem E.1 considers PGD on an L-smooth function over a convex set, with step size η = 1/L and x⋆ a global minimizer.The section presents this as a convergence result for reaching a first-order stationary point.Source: E Convergence of PGD to Approximate… · pp. 83–84
  • The PGD proof assumes exact access to ∇f, and the section notes that it can be adapted to gradient access with accuracy ε^3.The adaptation is left as an exercise to the reader.Source: E Convergence of PGD to Approximate… · p. 83

Related papers

Loading 2009.09623v1…