PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

Qihao Zhou

arXiv:2609.30877v1math.OCcs.LG

TL;DR

The paper asks whether SAPD+’s linear stochastic condition-number dependence is necessary for nonconvex-strongly-concave minimax optimization. It constructs a lower bound by concealing primal progress in small dual gradients, and establishes a matching lower bound under SAPD+’s Moreau-envelope criterion and primal-dual initialization gap.

  • Problem

    The paper asks whether the linear condition-number dependence in SAPD+’s stochastic complexity is necessary for nonconvex-strongly-concave minimax optimization.

    Source: §1 · p. 1

  • Method

    The construction conceals each next primal-chain coordinate behind a dual gradient of magnitude Θ(ε/√κ), using the Moreau-envelope criterion and primal-dual initialization parameter from SAPD+’s guarantee.

    Source: §1 · pp. 1–2

  • Results

    The lower bound matches SAPD+’s stochastic complexity for zero-respecting algorithms under the same Moreau-envelope criterion and primal-dual initialization gap.

    Source: §7 · p. 12

  • Takeaways & Limitations

    The linear-κ stochastic lower bound holds even with an exact primal oracle, and the same instance gives a primal-gradient lower bound under a primal-gap budget.

    Source: §7 · p. 12

    The tightness result covers general unbiased bounded-variance estimators and bounded dual boxes; extension to arbitrary randomized algorithms, differentiable sample-loss gradients, or an unconstrained dual domain remains open for this construction.

    Source: §7 · p. 12

Abstract

from arXiv · show

We study whether the linear condition-number dependence in the stochastic complexity of SAPD+ is necessary for nonconvex-strongly-concave minimax optimization. For jointly $L$-smooth objectives with dual strong-concavity parameter $\mu$, we prove a lower bound that matches the SAPD+ upper bound under the same Moreau-envelope stationarity criterion and the same primal-dual initialization gap. Specifically, when $\sigma\ge\varepsilon$, the worst-case complexity of zero-respecting algorithms is $\Theta(\kappa LG\sigma^2\varepsilon^{-4})$ in the stated accuracy regime, where $\kappa=L/\mu$, $G$ bounds the initial primal-dual gap, and $\sigma^2$ bounds the variance of a general unbiased first-order oracle. The lower bound is realized on a smooth problem class with a bounded dual box. Our construction routes each link of a nonconvex zero-chain through a dual gradient of magnitude proportional to $\varepsilon/\sqrt{\kappa}$, while an undiscovered primal coordinate prevents stationarity. It also yields the primal-gradient lower bound $\Omega(L\Delta(\sqrt{\kappa}\varepsilon^{-2}+\kappa\sigma^2\varepsilon^{-4}))$ after combination with the known deterministic bound, where $\Delta$ bounds the initial primal function gap.

1 Introduction

The paper asks whether SAPD+’s linear stochastic dependence on the condition number is necessary and gives a matching lower bound under the same stationarity criterion and initialization gap. Its construction conceals primal-chain progress in small dual gradients, and it also establishes a primal-gradient lower bound.

1 Introduction

  • Each chain link must be discovered through a dual gradient of size Θ(ε/√κ), while an undiscovered final primal coordinate has gradient larger than 2ε.A separable primal correction removes direct communication between neighboring primal coordinates; a variance budget σ² gives expected waiting time Θ(1 + κσ²/ε²) per link.Source: §1 · p. 2
  • The lower bound matches SAPD+ under the same oracle model, Moreau-envelope criterion, and initialization gap, without a logarithmic-factor loss.The matching result is proved for a class with bounded dual boxes and bounded initial primal-dual gap.Source: §1 · pp. 1–2
  • Combining the stochastic result with the known deterministic bound gives a primal-gradient lower bound of Ω(√κL∆ε−2 + κL∆σ²ε−4).The initial primal-gap budget is ∆.Source: §1 · p. 2
  • The construction combines a dual Hessian −µI with a separable primal correction, enabling controlled cross derivatives and transfer to SAPD+’s stationarity criterion with only an absolute accuracy change.The introduction situates this construction in relation to stochastic concealment in dual and lower-level variables.Source: §1 · p. 2

2 Preliminaries

The preliminaries define the notation, admissible problem and oracle classes, zero-respecting algorithms, and the criterion used to compare the lower bound with SAPD+. The comparison class adds bounded dual boxes and an initial primal-dual gap budget.

2 Preliminaries

  • The notation uses Euclidean vector norms and spectral matrix norms, and O(·), Ω(·), and Θ(·) hide absolute constants while eO(·) also hides logarithmic factors.The preliminaries also define support, standard basis vectors, and vector concatenation.Source: §2 · p. 2

2.1 Smoothness and primal-gap class

  • The primal-gap class assumes joint L-smoothness, µ-strong concavity in y, a nonempty closed convex dual set containing the origin, and a primal function bounded below.These assumptions ensure a unique maximizer y*(x), making Φ differentiable with gradient ∇Φ(x) = ∇xf(x, y*(x)); κ = L/µ.Source: §2.1 · pp. 2–3

2.2 Oracle model and algorithms

  • The oracle returns unbiased gradients with variance at most σ² using fresh independent samples, and permits estimators not arising from differentiable sample losses or mean-squared-smoothness assumptions.Zero-respecting algorithms start at the origin and restrict queries and outputs to coordinates appearing in prior oracle supports; queries may be adaptive and internally randomized.Source: §2.2 · p. 3

2.3 The class and criterion for the SAPD+ comparison

  • For the SAPD+ comparison, problems in M(L, µ, G) satisfy Assumptions 1–3, with Y a bounded box containing the origin, f twice continuously differentiable on an open neighborhood of R^dx × Y, and G0 ≤ G.Source: §2.3 · p. 4

3 Related Work

Prior work establishes deterministic condition-number bounds and stochastic lower bounds, but uses differing oracle, domain, and stationarity settings. The paper distinguishes its strongly concave construction from related nonconvex-concave and bilevel lower bounds.

Algorithms for nonconvex-strongly-concave minimax optimization

  • Accelerated proximal-point methods attain eO(√κ) deterministic dependence under their respective guarantees, while SAPD+ combines an inexact proximal-point framework with stochastic accelerated primal-dual updates.The SAPD+ comparison uses its Moreau-envelope guarantee for a uniformly selected outer iterate and matches its primal-dual gap parameter.Source: §3 · pp. 4–5

Lower bounds

  • For zero-respecting algorithms, prior stochastic minimax lower bounds use a κ^(1/3) term and a projected-gradient mapping on a constrained primal domain, unlike this paper’s linear-κ bound for ∥∇Φ∥ on an unconstrained primal domain.The comparison concerns stochastic condition-number dependence within this algorithmic framework.Source: §3 · p. 5

Recent nonconvex-concave lower bounds

  • Wu et al. [10] use dual-path clipping and Bernoulli concealment for nonconvex-concave lower bounds, but their results do not impose uniform strong concavity.This construction uses two dual variables per primal link and a diagonal dual Hessian −µI to obtain a strongly concave realization with controlled smoothness and gap.Source: §3 · p. 5

Bilevel and nonconvex-Polyak–Łojasiewicz problems

  • Bilevel lower bounds [4] and [3] conceal lower-level information, but distinct upper- and lower-level objectives do not directly establish the minimax bound, which requires the lower-level objective to be the negative of the upper-level objective.Pan and Li [9] give a deterministic result under nonconvex-Polyak–Łojasiewicz regularity, not the stochastic strongly concave bound considered here.Source: §3 · p. 5

4 Main Results

The main results match SAPD+’s stochastic upper bound with a lower bound for zero-respecting algorithms under the same comparison framework. The construction also yields a primal-gradient lower bound, while the exact optimality claim for SAPD+ is confined to the stochastic regime.

Theorem 1

  • The lower bound matches SAPD+’s upper bound for the stochastic condition-number dependence among zero-respecting algorithms over M(L, µ, G).The comparison uses the same oracle model and Moreau-envelope criterion, without a logarithmic-factor loss.Source: §4 · p. 6
  • The upper bound is attained by SAPD+ with a uniformly selected outer iterate, while the lower bound holds even when the primal oracle component is deterministic.The comparison uses the initial primal-dual gap and stationarity criterion from the SAPD+ guarantee.Source: §4 · p. 6

Theorem 2

  • Theorem 2’s lower-bound instance has a bounded dual box and an oracle with variance at most σ^2.The construction’s cross derivatives are controlled, rather than requiring the largest values permitted by joint smoothness.Source: §4 · p. 6

Comparison with prior lower bounds

  • The stochastic term has linear dependence on κ, improving on Li et al.’s κ^1/3 lower-bound dependence under the domain and stationarity distinctions discussed in Section 3 [5].The κ^1/3 comparison is qualified by differences in domain and stationarity measure.Source: §4 · p. 6

Theorem 2 and Corollary 1

  • For σ ≥ ε, the primal-gradient lower bound includes the stochastic term Ω(κL∆σ^2ε^-4).The combined lower bound uses the known deterministic bound for its first term; the stochastic term dominates when σ^2 is at least of order ε^2/√κ.Source: §4 · p. 7

Scope

  • Theorem 1 addresses σ ≥ ε; Theorem 2 covers σ ≥ 0 but does not claim SAPD+ has optimal deterministic complexity.The paper separately records a construction-specific upper bound in Appendix F.Source: §4 · p. 7

5 The Dual Probability Zero-Chain

The proof builds a nonconvex chain whose undiscovered final coordinate prevents stationarity, hides each link behind a dual signal, and counts successful discoveries to obtain the lower bound.

5.1 Step 1: A chain that certifies nonstationarity

  • An undiscovered final primal coordinate keeps the primal gradient above the stationarity threshold, so the algorithm must discover the chain’s last link.The proof uses a chain with Θ(L∆/ε²) links and gradient larger than 2ε while the final coordinate remains undiscovered.Source: §5 · p. 7, §5.1 · p. 8

5.2 Step 2: Realizing each link through the dual variables

  • The primal function is separable, while maximization over the dual variables reconstructs the chain links and cancels the separable correction.The constructed objective is in the stated smooth, strongly concave problem class and has a bounded dual box.Source: §5.2 · pp. 8–9

5.3 Step 3: Concealing the next dual link

  • A Bernoulli oracle conceals only part of the frontier dual gradient; the primal gradient is returned exactly, and the oracle remains unbiased with bounded variance.When σ = 0, the oracle is deterministic.Source: §5.3 · p. 9

5.4 Step 4: Counting discoveries

  • Each new primal coordinate after the first requires a distinct earlier Bernoulli success, yielding a bound on how many links can be discovered.The discovery invariant also holds for adaptive queries that reset previously discovered coordinates to zero.Source: §5.4 · p. 10

5.5 Proof of Theorem 2

  • The proof combines oracle validity, initial nonstationarity, and the discovery bound to establish the primal-gradient lower bound.The initial point has gradient norm 2√e ε > ε.Source: §5.3 · p. 9, §5.5 · p. 10, §5.4 · p. 10

6 Matching the SAPD+ Guarantee

The proof transfers the primal-gradient lower bound to SAPD+’s Moreau-envelope criterion by comparing stationarity at the algorithm’s output. It then matches the SAPD+ upper bound in the stated regime.

6.1 Comparing stationarity at the same point

  • The construction’s controlled cross derivatives transfer the lower bound to Moreau-envelope stationarity with only an absolute factor, without adding a proximal computation to the oracle.The comparison is made at the algorithm’s output.Source: §6.1 · p. 11, §6 · p. 11

6.2 Proof of Theorem 1

  • In the stated regime, the SAPD+ upper bound is O(κLGσ²ε−4), matching the lower bound under the same criterion and initialization gap.The constructed problem belongs to the class with primal-dual gap budget G.Source: §6.2 · p. 12

7 Conclusion

The paper establishes tight stochastic condition-number dependence for zero-respecting algorithms under SAPD+’s criterion and initialization budget. Its conclusion also identifies the bounds of that result and open extensions.

7 Conclusion

  • A dual gradient of magnitude Θ(ε/√κ) carries the information needed for primal progress, yielding a linear-κ stochastic lower bound even with an exact primal oracle.The same instance gives a primal-gradient lower bound under a primal-gap budget.Source: §7 · p. 12
  • The tightness result covers general unbiased bounded-variance estimators and problem classes with bounded dual boxes, but not arbitrary randomized algorithms or unconstrained dual domains.Extending the construction to stochastic gradients of differentiable sample losses remains open.Source: §7 · p. 12
  • A matching primal-gradient upper bound under only a primal-gap budget requires a separate argument.Source: §7 · p. 12

AI Assistance Acknowledgement

The author acknowledges AI assistance with drafting and states that all content, including proofs, was verified by the author.

AI Assistance Acknowledgement

A Properties of the Nonconvex Chain

The construction builds a smooth nonconvex chain whose undiscovered terminal coordinate ensures a large gradient, then embeds its primal identity in a bounded, strongly concave dual problem.

A Properties of the Nonconvex Chain

  • The chain satisfies |ψ′′(t)| < 32.5 and has function gap F_T(0) − inf_u F_T(u) ≤ 12T.These bounds support the smoothness and gap control used for the construction.Source: A Properties of the Nonconvex Chain · p. 14
  • When |u_T| < 1, the chain has gradient norm greater than 1 because all partial-derivative contributions are nonpositive and one is below −1.The proof handles the first index with |u_i| < 1, including the initial-coordinate case.Source: A Properties of the Nonconvex Chain · p. 14

B.1 Primal identity; B.2 Joint smoothness, strong concavity, and the gap

  • Maximizing over the dual variables recovers the primal identity, and the constrained maximizer lies inside the box.The resulting objective meets the stated smoothness, strong-concavity, lower-boundedness, and gap requirements, with f ∈ M(L, μ, 1.14Δ).Source: §B.1 · pp. 14–15, §B.2 · p. 16

C Proof of the Chain Invariant

The chain invariant ties discovery of dual links to primal-coordinate progress. The paper also specializes SAPD+ to the matching stationarity and initialization criteria and gives a zero-respecting implementation.

C Proof of the Chain Invariant

  • Before the frontier reaches T, no dual link beyond the current primal frontier can be discovered.The invariant follows from the oracle's support restrictions and is preserved whether the current frontier link has already been discovered or not.Source: C Proof of the Chain Invariant · pp. 16–17
  • Each increase in the discovered primal frontier requires an earlier successful Bernoulli trial, yielding the chain invariant.A link cannot be discovered before its primal coordinate or on the call that reveals that coordinate.Source: C Proof of the Chain Invariant · p. 17

D Specialization of the SAPD+ Upper Bound

  • The SAPD+ specialization yields outer iterates meeting envelope accuracy δ, without requiring a gradient-norm evaluation to select the output.Setting δ = ε gives the stated specialization; the implementation uses a constant number of full-oracle calls per inner iteration and preserves zero coordinates until their oracle coordinates appear.Source: D Specialization of the SAPD+ Upper… · pp. 17–18

E A Matching Primal-Gradient Result

The section establishes a matching primal-gradient complexity result and analyzes a construction-specific procedure, separating its coordinate-discovery stage from its final stationarity step.

E A Matching Primal-Gradient Result

  • For the primal-gradient criterion, the lower and upper call bounds both scale as κLGσ²ε^-4.The lower-bound instance forces E ∥∇Φ(ˆx)∥ > 2ε for Ω(κLGσ²ε^-4) calls; SAPD+ attains the result by running to envelope accuracy ε/2.Source: E A Matching Primal-Gradient Result · p. 18

F A Matching Bound for the Construction

  • The construction-specific upper bound is not uniform over F(L, μ, Δ), and its procedure is given the explicit construction and parameters.The procedure must discover all primal coordinates and then return an explicit point with small primal gradient; discovery alone does not imply stationarity.Source: F A Matching Bound for the Construction · p. 19

F.1 Discovering the coordinates

  • After a geometric number of trials with success probability p, a dual frontier query reveals the link needed to expose the next primal coordinate.The discovery procedure uses the same primal query until the dual link is found, then queries at a dual coordinate to reveal the next primal coordinate.Source: §F.1 · p. 19

F.2 Returning an approximate stationary point

  • The procedure truncates discovery at a deterministic call budget and returns either the constructed small-gradient point or zero.The output is legal in either case; the proof uses the discovery-call bound and Markov’s inequality to establish the stated construction-specific result.Source: §F.2 · p. 20
Loading 2609.30877v1…