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

Nonconvex-nonconcave min-max optimization is important but poorly understood, especially for first-order methods and approximate local solutions. This paper characterizes its computational difficulty, proving PPAD-completeness for finding approximate local min-max solutions and fixed points, alongside exponential oracle-query lower bounds contrasting with minimization.

  • Problem

    Nonconvex-nonconcave min-max optimization lacks effective first-order methods and has poorly understood computational complexity despite applications in deep learning.

  • Method

    The paper formulates first-order search problems and reduces discrete fixed-point problems through Lipschitz-smooth function constructions and smooth, efficient interpolation.

  • Results

    Finding approximate local min-max solutions and approximate Projected Gradient Descent-Ascent fixed points is PPAD-complete under polynomially bounded parameters.

  • Takeaways & Limitations

    Local min-max computation can require super-polynomial time in at least one of 1/ε, G, L, or d, unlike local minimization via Projected Gradient Descent.

  • Takeaways & Limitations

    The local min-max problem is not total and its solutions are not efficiently verifiable for all ε and δ, even on [0,1]^d.

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 paper studies why constrained nonconvex-nonconcave min-max optimization is substantially harder than minimization, characterizing existence, computational complexity, and first-order limitations. It proves PPAD-completeness in the local regime, NP-hardness in the global regime, and exponential black-box query lower bounds.

  • Problem: Nonconvex-nonconcave min-max solutions may not exist, and deciding whether exact or approximate solutions exist is NP-hard even for Lipschitz and smooth objectives.The hardness persists for absolute-constant approximation error.
  • Problem: Approximate local min-max equilibria are the paper’s main target because approximate stationary points may also fail to exist and their existence is NP-hard to decide.The paper therefore focuses on local min-max solutions, including approximate variants.
  • Main results: In the global regime, approximate local min-max solutions need not exist, and deciding their existence is NP-hard even for absolute-constant ε.By contrast, in the trivial regime δ < ε/G, every feasible point is an approximate local min-max solution.
  • Main results: In the local regime, computing approximate local min-max solutions over convex polytopes is PPAD-complete, equivalently matching the complexity of approximate projected gradient descent-ascent fixed points.The hardness holds with polynomially bounded smoothness, Lipschitzness, 1/ε, and 1/δ in the dimension.
  • Oracle complexity: With black-box access to f and ∇f, finding an ε-approximate local min-max point requires exponentially many queries in at least one of 1/ε, L, G, or d.Exponential dependence on d remains necessary even when L, G, 1/ε, and 1/δ are polynomial in d.
  • Comparison: These lower bounds sharply contrast with minimization, where projected gradient descent finds approximate local minima using O(B · L/ε) time or queries.The paper identifies an exponential black-box separation and a super-polynomial white-box separation assuming PPAD ≠ FP.

2 Preliminaries

The paper formalizes function access, regularity assumptions, feasible domains, and the complexity-theoretic framework used to analyze constrained optimization problems.

  • Function assumptions: The main objects are continuously differentiable G-Lipschitz and L-smooth functions on polytopes P ⊆ [0, 1]^d.Lipschitzness bounds function differences, while smoothness bounds gradient differences in Euclidean norm.
  • Function access and promises: Functions are studied through black-box or white-box access returning function values and gradients, under promises of consistency and regularity.The black-box model uses an oracle, while the white-box model uses a polynomial-time machine; both assume compatible smooth, Lipschitz, and bounded functions.
  • Function access and promises: The black-box model follows the Nemirovsky-Yudin tradition and permits real-number arithmetic while querying f(x) and ∇f(x).The white-box counterpart supplies a polynomial-time evaluator with accuracy-dependent running time.
  • Complexity framework: Polynomial-time reductions transform instances and translate any solution of the target problem back into a solution of the source problem.The reduction is specified by polynomial-time computable functions f and g.
  • Complexity framework: PPAD contains search problems reducible in polynomial time to End-of-a-Line, whose solutions arise from an implicit directed graph with bounded in-degree and out-degree.The framework includes fixed-point problems whose existence is guaranteed by Brouwer’s theorem.

3 Computational Problems of Interest

This section defines constrained stationary points, local minima, local min-max equilibria, and their associated search problems, then relates selected problems to gradient dynamics.

  • Problem landscape: The paper studies approximate stationary points, local minima, and local min-max equilibria as its principal constrained computational problems.It also introduces gradient descent and gradient descent-ascent fixed-point problems as related bonus problems.
  • Constraints: The feasible set is P(A, b) = {z ∈ [0, 1]^d | A^Tz ≤ b}, with emptiness testing polynomial-time decidable and projection well-defined for nonempty closed convex sets.The paper focuses on linear constraints, so feasible regions are polytopes.
  • Stationary points: An ε-stationary point has gradient norm below ε, but such points need not exist, even approximately, for continuously differentiable functions.Linear functions provide an example without stationary points.
  • Local minima: An (ε, δ)-local minimum always exists on the compact feasible set, although verifying it efficiently is not known for arbitrary ε and δ.As δ grows, the definition moves from ε-global optimality toward ε-local optimality.
  • Local min-max equilibria: An (ε, δ)-local min-max equilibrium imposes approximate minimization in x and approximate maximization in y within δ-radius neighborhoods.Unlike local minima, the corresponding search problem is neither total nor efficiently verifiable for all ε and δ.
  • Complexity results: StationaryPoint lies in FNP and is FNP-hard even for constant ε, the hypercube feasible set, and G, L polynomial in d.The search problem uses a relaxed output condition to preserve polynomial-size witnesses.
  • Bonus fixed-point problems: GDFixedPoint and GDAFixedPoint capture fixed points of projected gradient descent and gradient descent-ascent, respectively, and correspond under polynomial-time reductions to LocalMin and LocalMinMax.These equivalences hold in specified regimes of the approximation parameters.

4 Summary of Results

The paper characterizes constrained nonconvex-nonconcave min-max optimization across regimes, showing guaranteed approximate local equilibria can still be computationally hard to find.

  • Stationary points: FNP-completeness holds for finding approximate stationary points, even for ε ≤ 1/24 on the domain [0, 1]^d.The result applies to constrained problems and contrasts with unconstrained bounded-range settings where approximate stationary points can be found efficiently.
  • Regimes: When δ < ε/G, every feasible point solves both LocalMin and LocalMinMax because objective variation within the δ-neighborhood is below ε.This is the trivial regime, where local approximation requirements impose no effective search burden.
  • Local regime: The local regime δ < √(2ε/L) guarantees existence of approximate local min-max equilibria for G-Lipschitz, L-smooth functions.Projected Gradient Descent solves LocalMin in O(B · L/ε) time in this regime, while the complexity of LocalMinMax is substantially harder.
  • Local regime: PPAD-hardness holds for LR-LocalMinMax when δ ≥ √(ε/L), even with 1/ε, G, and L polynomial in d and B = d.Together with membership in PPAD, this establishes PPAD-completeness for the local-regime search problem under the stated parameter conditions.
  • Black-box complexity: Any black-box algorithm finding an (ε, δ)-local min-max equilibrium requires exponentially many oracle queries in at least one of 1/ε, G, L, or d.The lower bound holds even when the feasible polytope lies within [0, 1]^d and the function and gradient are accessed only through an oracle.
  • Proof strategy: The proof strategy uses Brouwer’s fixed-point theorem and an equivalence between LR-LocalMinMax and Gradient Descent/Ascent fixed points.This equivalence supports both PPAD membership and the connection between local min-max equilibria and GDAFixedPoint.

5 Existence of Approximate Local Min-Max Equilibrium

In the local regime, approximate local min-max equilibria are total search problems in PPAD, and their existence is established through a polynomial-time equivalence with Gradient Descent/Ascent fixed points.

  • Existence and totality: Every G-Lipschitz, L-smooth function admits an (ε, δ)-local min-max equilibrium when δ < √(2ε/L).This establishes totality of LR-LocalMinMax in the local regime.
  • Computational equivalence: LR-LocalMinMax and GDAFixedPoint are equivalent under polynomial-time reductions.The equivalence runs in both directions for feasible polytopes and G-Lipschitz, L-smooth objectives.
  • Computational equivalence: A sufficiently accurate fixed point of the Gradient Descent/Ascent map yields an (ε, δ)-local min-max equilibrium for δ < √(2ε/L).The reduction uses a bound relating the fixed-point approximation α to ε, δ, G, and L.
  • Computational equivalence: Conversely, an (ε, δ)-local min-max equilibrium can be converted into an approximate fixed point using parameter choices linking ε and δ to α and L.This supplies the reverse reduction required for polynomial-time equivalence.
  • Existence and totality: Both GDAFixedPoint and LR-LocalMinMax are total search problems belonging to PPAD.The PPAD membership follows from the fixed-point-based existence argument.

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

The four-dimensional hardness proof reduces the PPAD-hard 2D-BiSperner problem to fixed points of Gradient Descent/Ascent by constructing a smooth, Lipschitz function whose gradients encode grid colors. This establishes PPAD-completeness even in dimension four, with solutions yielding valid BiSperner outputs.

  • 6.2.1 Description and Correctness of the Reduction – Proof of Theorem 6.1: GDAFixedPoint and LR-LocalMinMax are PPAD-complete even in dimension d = 4 and B = 2.Every fixed point produced by the reduction lies in a cell that is panchromatic or violates proper-coloring rules, yielding a BiSperner solution.
  • 6.1 The 2D Bi-Sperner Problem: The 2D-BiSperner problem asks for a panchromatic grid cell or a violation of proper-coloring rules, using a succinct circuit to describe exponentially large grids.Proper colorings assign one color from {1−, 1+} and one from {2−, 2+} to each vertex, with prescribed boundary colors.
  • 6.1 The 2D Bi-Sperner Problem: 2D-BiSperner is PPAD-hard, providing the discrete source problem for the reduction to Gradient Descent/Ascent fixed points.The hardness proof maps approximate fixed points of a Lipschitz function to valid 2D-BiSperner solutions.
  • 6.2 From 2D Bi-Sperner to Fixed Points of Gradient Descent/Ascent: The reduction constructs a smooth function from the coloring circuit so that shared vertex colors induce corresponding horizontal or vertical gradient directions.The construction uses local cell information and smooth interpolation while preserving the gradient structure needed for correctness.
  • 6.2 From 2D Bi-Sperner to Fixed Points of Gradient Descent/Ascent: fCl is continuous and differentiable, Θ(1/δ)-Lipschitz, and Θ(1/δ^2)-smooth on [0, 1]^4, with δ = 1/(2^n − 1).These properties make the constructed function a valid input for the fixed-point problem.

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

The paper reduces a high-dimensional BiSperner problem to approximate fixed points of projected Gradient Descent/Ascent, establishing hardness while preserving polynomially bounded parameters. A novel smooth interpolation construction enables the reduction and yields unconditional black-box lower bounds.

  • Hardness result: An unconditional black-box lower bound requires time exponential in at least one of d, G, L, or 1/ε for algorithms accessing only f and ∇f.The corresponding white-box problem also rules out poly(d, G, L, 1/ε)-time algorithms unless FP = PPAD.
  • Smooth interpolation: Smoothly and efficiently interpolating corner functions across glued d-dimensional simplices is the central technical challenge.The novel smooth and efficient interpolation coefficients support this construction; the resulting function is O(d^15/δ)-Lipschitz and O(d^27/δ^2)-smooth.
  • HighD-BiSperner: HighD-BiSperner generalizes 2D-BiSperner on a d-dimensional grid with two signed colors assigned to each coordinate.Proper colorings impose coordinate-specific color restrictions, including prescribed colors on lower and upper boundaries.
  • HighD-BiSperner: A panchromatic cubelet contains all 2d signed colors, and HighD-BiSperner provides a polynomially checkable certificate using 2d vertices from one cubelet.The alternative certificate is a vertex violating a boundary condition.
  • PPAD reduction: γ-SuccinctBrouwer is PPAD-complete, and it reduces in polynomial time to HighD-BiSperner with N = Θ(d/γ^2).A panchromatic cell yields a solution to γ-SuccinctBrouwer under this grid-size choice.
  • Reduction to GDAFixedPoint: The main reduction maps HighD-BiSperner instances to GDAFixedPoint while maintaining 1/α = poly(d), G = poly(d), and L = poly(d).The construction defines a function by interpolating corner functions over simplices and uses the resulting fixed point to recover a panchromatic cubelet or a coloring violation.

8 Smooth and Efficient Interpolation Coefficients

The section constructs smooth and efficient interpolation coefficients (SEIC) in arbitrary dimensions, using smooth-step functions and cubelet-based representations. It proves that these coefficients exist with the required differentiability, sparsity, normalization, computability, and boundary properties.

  • SEIC properties: SEIC coefficients satisfy twice differentiability, nonnegativity, normalization, local sparsity, efficient support computation, and boundary-vertex properties.At most d + 1 coefficients can be nonzero at any x, and the relevant support can be computed in polynomial time.
  • Existence theorem: For every dimension d and polynomially bounded N, a family of SEIC functions satisfying properties (A)–(D) exists.
  • Smooth-step functions: Smooth-step functions provide the differentiable transitions used to construct the coefficients, including finite-order S and infinitely smooth S∞.Both functions are monotone, map 0 to 0 and 1 to 1, and S∞ has derivatives vanishing at the endpoints.
  • Single-dimensional construction: In one dimension, the construction defines each coefficient from shifted S∞ functions, yielding twice-differentiable coefficients with bounded first and second derivatives.The resulting construction satisfies the SEIC properties, and Figure 7 illustrates P3 for N = 5.
  • Multidimensional construction: The multidimensional construction introduces cubelet orientations, source and target vertices, canonical representations, and auxiliary Qv functions before assembling the SEIC coefficients.

9 Unconditional Black-Box Lower Bounds

The section derives unconditional black-box lower bounds by reducing Brouwer and Bi-Sperner instances to approximate fixed points of Gradient Descent/Ascent and local min-max problems. The reduction requires d + 1 oracle queries per objective value or gradient query, preserving exponential hardness up to this factor.

  • Brouwer lower bound: A 2-Lipschitz Brouwer function requires at least 2^d oracle calls to obtain a point with residual at most 1/(2c).
  • Bi-Sperner reduction: The Brouwer lower bound transfers to HighD-BiSperner, which therefore requires 2^d oracle calls when N = O(d).
  • Query simulation: Each oracle query returning f(x, y) and ∇f(x, y) can be implemented using d + 1 HighD-BiSperner queries.The same d + 1 coefficient values suffice for evaluating every coordinate and its gradient.
  • Final lower bound: Consequently, black-box algorithms for GDAFixedPoint and LR-LocalMinMax require at least 2^d/(d + 1) oracle queries.The argument assumes infinite-precision real-number operations and uses a black-box reduction from HighD-BiSperner.

10 Hardness in the Global Regime

The section establishes hardness in the global regime by reducing bounded-occurrence 3-SAT to local min-max and minimization problems, and by constructing black-box functions whose local minima encode satisfying assignments. These results show exponential query requirements even for polynomially bounded Lipschitzness and smoothness parameters.

  • Local min-max hardness: LocalMinMax is FNP-hard for ε ≤ 1/384 and δ ≥ 1, even on the hypercube [0, 1]^d.The reduction uses 3-SAT(3) and constructs a polynomial objective with Lipschitzness and smoothness proportional to the instance size.
  • Assignment recovery: The reduction converts a local min-max equilibrium into a satisfying assignment using the Lovász Local Lemma, exploiting that each clause overlaps with at most six others.
  • Minimization hardness: LocalMin is FNP-hard for ε ≤ 1/24 when δ is at least the feasible-set diameter, with a weaker parameter regime than LocalMinMax.The stated construction sets δ ≥ √n for the hypercube and derives satisfiability from sufficiently low objective value.
  • Black-box lower bound: A black-box LocalMin algorithm requires 2^d/d value-gradient queries for functions with G = Θ(d^15), L = Θ(d^22), ε < 1, and global radius δ.The construction interpolates Boolean oracle values over hypercube vertices using SEIC coefficients.
  • Interpolation recovery: At most d + 1 vertex queries suffice to recover a satisfying assignment from an approximate local minimum of the interpolated function.Only the vertices with nonzero interpolation coefficients need to be checked.

A Proof of Theorem 4.1

The section proves FNP-hardness of approximate stationary-point computation by reducing bounded-occurrence 3-SAT to a polynomial objective over [0, 1]^(n+m). Satisfying assignments correspond exactly to sufficiently accurate stationary points, while the constructed function has polynomial Lipschitzness and smoothness.

  • Reduction: 3-SAT(3) is reduced to ε-StationaryPoint by encoding each clause as a polynomial over real-valued variables.Each literal contributes either xi or 1 − xi, and the clause polynomial is their product.
  • Regularity parameters: The constructed objective is G-Lipschitz with G = Θ(√n + m) and L-smooth with L = Θ(n + m).
  • Hardness equivalence: A satisfying assignment exists if and only if the constructed function has a point with gradient norm below 1/24.This equivalence is stated for the constructed StationaryPoint instance over [0, 1]^(n+m).
  • Forward direction: The reduction maps a satisfying assignment to a zero-gradient point by setting clause auxiliary variables to zero.
  • Reverse direction: Conversely, an approximate stationary point implies every clause polynomial is below 1/24, from which the Lovász Local Lemma yields a satisfying assignment.

B.1 Proof of Theorem 5.1

The proof shows that approximate fixed points of projected gradient descent/ascent yield local min-max points, and conversely that local min-max points yield approximate fixed points. The argument uses projection geometry, smoothness, and carefully chosen approximation parameters.

  • Reduction from GDAFixedPoint to LR-LocalMinMax: Projection onto the feasible slice K and convex-set projection geometry bound the gradient inner product by (G + δ + α) · α.The bound combines Cauchy–Schwarz, the triangle inequality, the gradient norm bound G, and the α-approximate fixed-point condition.
  • Reduction from GDAFixedPoint to LR-LocalMinMax: Choosing δ sufficiently small makes the smoothness error and projection error fit within ε, yielding the local min-max guarantee.The proof uses L-smoothness together with the constraint δ < √(ε/L) and related parameter conditions.
  • Reduction from GDAFixedPoint to LR-LocalMinMax: An α-approximate fixed point of projected gradient descent/ascent satisfies the ε-local min-max inequalities in both variables.The proof establishes the minimizing inequality for feasible x near x⋆ and the analogous maximizing inequality for feasible y near y⋆.
  • Reduction from LR-LocalMinMax to GDAFixedPoint: Conversely, an (ε, δ)-local min-max equilibrium induces a projected-gradient displacement below α/2 in each variable.If the projection displacement exceeds δ, the proof moves to a point at distance δ and combines local optimality with smoothness to derive a contradiction.
  • Reduction from LR-LocalMinMax to GDAFixedPoint: The displacement bound follows from the inner-product estimate ⟨∇f(x⋆), x⋆−x̂⟩ < 3ε and the selected relationship between ε and α.The resulting projection distance is bounded as stated in the proof.

B.2 Proof of Theorem 5.2

The proof reduces GDAFixedPoint to Brouwer by constructing a Lipschitz map from projected gradient updates. Approximate fixed points of this map become approximate fixed points of gradient descent/ascent, establishing PPAD membership and totality.

  • Reduction to Brouwer: A polynomial-time reduction from GDAFixedPoint to Brouwer establishes totality and PPAD membership for GDAFixedPoint.Because Brouwer is total and belongs to PPAD, the reduction transfers both properties.
  • Reduction to Brouwer: The same reduction establishes totality and PPAD membership for LR-LocalMinMax through its reduction to GDAFixedPoint.The proof invokes the previously established polynomial-time reduction from LR-LocalMinMax to GDAFixedPoint.
  • Constructing the Brouwer map: The constructed map M is (L + 1)-Lipschitz when f is L-smooth.The Brouwer instance uses M as the map whose approximate fixed points are analyzed.
  • Transferring approximate fixed points: A γ-approximate fixed point of M is shown to be an α-approximate fixed point of projected gradient descent/ascent.The proof sets γ = α^2/4(G + 2...) and uses the feasible polytope’s bounded diameter together with projection inequalities.
  • Transferring approximate fixed points: The transfer argument bounds the projected update displacement using Claim B.2 and the choice γ = α^2/4(G + 2...).The same reasoning is applied symmetrically to the x and y coordinates.
  • Transferring approximate fixed points: Combining the two coordinate bounds shows that the original point is an α-approximate fixed point of FGDA.This completes the validity of the reduction from Brouwer to GDAFixedPoint.

C Missing Proofs from Section 8

This section proves differentiability and computational properties of the cubelet-based functions used in the construction. The key result is smooth behavior across cubelet boundaries, enabling the later hardness arguments.

  • Differentiability within cubelets: The functions Qc_v are shown to be continuous and twice differentiable within cubelets.The proof analyzes first- and second-order derivatives using the differentiability of the smoothing functions S and S∞.
  • Behavior across cubelet boundaries: At cubelet boundaries, Lemma C.2 ensures that the assembled functions P_v remain continuous and twice differentiable.The lemma matches values and derivatives for shared and non-shared vertices when crossing between neighboring cubelets.
  • Continuity of assembled functions: The coefficient P_v is continuous at cubelet intersections because the relevant Qc_v terms either vanish or match across the boundary.The proof partitions vertices according to which neighboring cubelets contain them.
  • Behavior across cubelet boundaries: The boundary analysis establishes differentiability by showing that one-sided limits agree or both derivatives vanish.These cases cover vertices shared by adjacent cubelets and vertices absent from one side.
  • Computational properties: The set R+(x) contains at most d + 1 vertices and can be computed in polynomial time.The construction sorts the coordinates of x and enumerates candidate vertices associated with the resulting order.

C.1.1 Proof of Lemma C.2

The proof of Lemma C.2 analyzes neighboring cubelets at a shared boundary and shows that their function values and derivatives match appropriately. This establishes smooth gluing across cubelets.

  • Shared vertices: For vertices shared by two neighboring cubelets, the corresponding Qc_v values and derivatives agree at the boundary.The canonical representations coincide, and the boundary coordinate contributes no derivative because S′(0) = S′(1) = 0.
  • Non-shared vertices: For vertices present in only one neighboring cubelet, the corresponding derivative terms vanish at the boundary.The proof uses the boundary values of the canonical coordinate and the vanishing derivatives of the smoothing functions.
  • First-order smoothness: First derivatives match across cubelet boundaries, including the coordinate normal to the shared face.For the boundary coordinate, the proof invokes S′(0) = S′(1) = 0.
  • Second-order smoothness: Second derivatives also match across boundaries because S′ and S′′ vanish at the endpoint values.The argument explicitly uses S′(0) = S′(1) = S′′(0) = S′′(1) = 0.
  • Conclusion of Lemma C.2: These boundary identities establish the cases required by Lemma C.2 and support continuity and twice differentiability of P_v.The proof handles shared vertices directly and reduces the remaining cases to the corresponding boundary lemmas.

C.2 Proof of Lemma 8.11

This section proves Lemma 8.11 by establishing technical bounds on the smooth step function and then combining them to control the gradient and Hessian of P_v(x).

  • Bounds on S∞: For x ≥ 1/d, the ratio S′∞(x)/S∞(x) is bounded by c · d^2.
  • Bounds on S∞: For x ≥ 1/d, the ratio |S′′∞(x)|/S∞(x) is bounded by c · d^4.
  • Bounds on S∞: The proof uses monotonicity and derivative formulas for S∞, S′∞, S′′∞, and S′′′∞ on small intervals.The preliminary analysis establishes nonnegativity and monotonicity properties for these derivatives.
  • Bounds on S∞: S∞ is increasing on [0, 1], with S∞(x) ≥ 2^-d whenever x ≥ 1/d.The proof derives this from S′∞(x) ≥ 0 and the bound h(x) ∈ [1/4, 1].
  • Gradient and Hessian bounds: A separated pair of consecutive coordinates supplies a vertex with a sufficiently large smooth-step contribution, enabling the required bounds over cubelet vertices.Among 0, p1, ..., pd, 1, two consecutive points differ by more than 1/(d + 1), which yields an exponentially small but controlled contribution.
  • Gradient and Hessian bounds: Combining the technical lemmas completes the gradient and Hessian bounds for P_v(x) stated in Lemma 8.11.

C.3 Proof of Lemma 8.12

The proof of Lemma 8.12 analyzes cubelet coordinates through source and target vertices, showing that suitable positive-weight corners have prescribed boundary coordinates.

  • Upper boundary: For coordinates near the upper boundary, a positive-weight vertex has coordinate i equal to the target value ti = 1.
  • Lower boundary: For coordinates near the lower boundary, a positive-weight vertex has coordinate i equal to the source value si = 0.
  • Parity cases: When N is even, the upper-boundary case instead identifies a positive-weight vertex with vi = si = 1.
  • Parity cases: The odd- and even-N cases are combined to establish the second statement of the lemma.

D Constructing the Turing Machine – Proof of Theorem 7.6

This section constructs polynomial-time Turing machines that compute the smooth-step function, cubelet coefficients, and P_v(x) and its gradient to prescribed accuracy.

  • Computational framework: The construction targets accuracy b = log(1/ε) and proves polynomial-time computability for fCl(x, y) and its gradient.
  • Computing S∞: S∞(x) and S′∞(x) can be computed to b-bit accuracy in time polynomial in b and the binary representation of x.
  • Computing cubelet coefficients: The machines compute at most d + 1 relevant vertices and their coefficients Q_v(x), using the cubelet containing x and sorted canonical coordinates.The relevant vertices are those with positive coefficients and can be computed in polynomial time with respect to b, d, and the input representation of x.
  • Precision control: The required intermediate precision for coefficient computation is b′ = b + Θ(log d) + Θ(log N).
  • Computing P_v: P_v(x) and ∇P_v(x) can be computed to b-bit accuracy in polynomial time for every vertex with P_v(x) > 0.
  • Projected Gradient Descent: Projected Gradient Descent on a convex projection set converges to a first-order stationary point in the stated smooth minimization setting.The theorem uses step size η = 1/L and bounds the required iterations using the initial objective gap.
Loading 2009.09623v1…