PaperlayerView exact revision on arXiv

Source-linked AI summary

Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

Jiayi Song, Zi Xu

arXiv:2610.01662v1math.OCcs.LGstat.ML

TL;DR

Stochastic NC–C minimax lower bounds have not fully addressed algorithms that use same-sample queries for variance reduction. This paper constructs lower bounds for zero-respecting algorithms in that setting and also derives complementary NC–SC bounds. The NC–C stochastic ε^-6 barrier persists for the considered algorithm class.

  • Problem

    Existing stochastic NC–C lower bounds do not directly resolve whether the same complexity barrier holds for algorithms using coupled same-sample gradient evaluations for variance reduction.

    Source: §1 · p. 2

  • Method

    The paper constructs a mean-square-smooth stochastic oracle and uses a common chain-based construction to establish lower bounds across NC–C and NC–SC regimes.

    Source: §1 · p. 2, §8 · p. 26

  • Results

    The stochastic ε^-6 barrier persists for zero-respecting NC–C algorithms with same-sample oracle access, and complementary NC–SC bounds capture accuracy and conditioning dependences.

    Source: §8 · p. 26

  • Takeaways & Limitations

    The common chain separates value-function stationarity difficulty from delayed primal–dual information, showing that stronger stochastic regularity alone does not ensure improved minimax accuracy dependence within the considered class.

    Source: §8 · p. 26

    Whether the barriers extend beyond zero-respecting algorithms remains unresolved.

    Source: §8 · p. 26

Abstract

from arXiv · show

We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an $L$-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most $D_Y$, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most $\Delta$. The target accuracy $\varepsilon$ is measured by the gradient norm of the Moreau envelope of the constrained primal value function with parameter $1/(2L)$. Under an unbiased stochastic first-order oracle with variance at most $\sigma^2$ and mean-square smoothness, we prove the lower bound $\Omega\!\left(L^2D_Y\Delta\varepsilon^{-3}+L^3D_Y^2\Delta\sigma^2\varepsilon^{-6}\right)$. This result quantifies the dependence on accuracy, dual-domain radius, and oracle noise even when variance reduction is allowed. We also establish complementary lower bounds for nonconvex--strongly-concave minimax optimization. With dual strong-concavity parameter $\mu>0$ and condition number $\kappa:=L/\mu$, we obtain $\Omega\!\left(L\Delta\sqrt{\kappa}\,\varepsilon^{-2}+L\Delta\kappa\sigma^2\varepsilon^{-4}\right)$ under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant $\bar L$, we obtain $\Omega\!\left(L\Delta\sqrt{\kappa}\,\varepsilon^{-2}+\Delta\bar L\sigma\kappa^{3/2}\varepsilon^{-3}\right)$. Together, these results identify complexity barriers across the concave and strongly concave regimes, with the main nonconvex--concave bound remaining valid for algorithms that use variance reduction.

1 Introduction

The paper studies stochastic first-order lower bounds for nonconvex–concave minimax optimization, addressing whether the stochastic accuracy barrier persists when variance reduction is allowed. It extends the analysis to nonconvex–strongly-concave problems with complementary bounds under bounded variance and mean-square smoothness.

1 Introduction

  • Prior work gives deterministic NC–C complexity O(ε^-3) and stochastic O(ε^-6) under bounded variance and mean-square smoothness; some stochastic lower bounds exclude variance reduction and do not settle shared-sample coupled-query algorithms.Variance reduction improves stochastic accuracy dependence in single-level nonconvex optimization.Source: §1 · p. 2

1.2 Main results and contributions

  • The NC–C lower bound is the central contribution, covering zero-respecting algorithms that permit variance reduction.The contribution extends the algorithmic scope of existing lower bounds rather than introducing a new accuracy exponent.Source: §1 · p. 2, §1.2 · p. 3
  • A lower bound of Ω(L^2 D_Y ∆ ε^-3) holds for zero-respecting algorithms with an unbiased, bounded-variance, mean-square-smooth oracle; same-sample queries are permitted.A dual path delays coordinate revelation, while a Bernoulli gate preserves that delay and the value function under mean-square smoothness.Source: §1.2 · p. 3
  • A clipped stochastic dual potential that hides the next block with positive probability yields the stochastic term Ω(L∆κσ^2ε^-4), while a quadratic strongly-concave dual lift produces the deterministic propagation term.Source: §1.2 · p. 3
  • Ω(L∆√κ ε^-2 + ∆L̄σκ^3/2ε^-3) is established for NC–SC optimization under mean-square smoothness.The construction retains the delayed strongly-concave chain and uses a smooth stochastic potential whose sample gradients satisfy bounded variance and mean-square smoothness.Source: §1.2 · p. 3
  • The paper measures stationarity by the Moreau-envelope gradient norm of the constrained primal value function, including when that value function is nonsmooth.The envelope parameter is 1/(2L), and the required expected squared stationarity measure is at most ε^2.Source: §1 · p. 1, §1.2 · p. 3

2 Problem setup

The setup defines nonconvex–(strongly)concave objective classes, a Moreau-envelope stationarity measure, and stochastic oracle and algorithm models. It also formalizes coordinate revelation through zero-chains.

2.1 Function classes and stationarity measures

  • The objective classes use closed convex primal and dual domains containing zero, joint L-smoothness, concavity in the dual variable, and a bounded initial value-function gap.The function-class definition covers the nonconvex–concave and nonconvex–strongly-concave settings.Source: §2.1 · pp. 4–5
  • For strongly concave dual objectives, the maximizer is unique and the value function is differentiable; the NC–C setup instead uses the Moreau envelope of the constrained value function.The envelope is continuously differentiable and supplies a stationarity measure for potentially nonsmooth value functions.Source: §2.1 · p. 5

2.3 Zero-chain framework

  • Zero-respecting algorithms restrict feasible iterates to coordinates revealed by oracle responses, and the zero-chain framework formalizes sequential coordinate revelation.A probability-p zero-chain constrains revelation probabilistically, with probability taken over oracle randomness.Source: §2.1 · p. 5, §2.2 · p. 6, §2.3 · p. 6

2.2 Oracle and algorithm classes

  • The stochastic first-order oracle returns function and gradient information, with mean-square smoothness requiring the same random sample at both query points.The oracle is defined for a differentiable objective over the primal–dual domain.Source: §2.2 · pp. 5–6

3 Common hard-instance components

The common hard-instance component is a smooth zero-chain whose decomposition supports both concave and strongly-concave saddle constructions. Its support structure limits how quickly oracle responses can reveal new coordinates.

3 Common hard-instance components

  • The common chain has smoothness, an unfinished-chain gradient barrier, and an initial gap bounded uniformly in its dimension.Its decomposition into H_m and a squared-norm term supports both concave and strongly-concave saddle realizations.Source: §3 · pp. 6–7

3.1 Construction of the common chain

  • The square-norm representation also yields an exact strongly-concave lift, whose maximizer is shown feasible.This connects the shared chain construction to a strongly-concave saddle realization.Source: §3 · p. 7, §3.1 · p. 8
  • If coordinates beyond r are zero, the chain gradient is supported through coordinate r+1, so its zero-chain structure reveals at most the next coordinate.The stated support bounds apply to the gradients of H_m and Q_m, respectively.Source: §3.1 · p. 8

4 The NC–C lower bound under mean-square smoothness

The section realizes a common chain as a concave saddle problem, using a long dual path for the deterministic obstruction and a Bernoulli-gated four-node path for the stochastic term.

4.1 A concave realization of the common chain

  • A long dual path realizes the deterministic obstruction as a jointly smooth, concave saddle problem with a compact convex dual domain and bounded initial value-function gap.The zero-chain reveal rule limits progress to one new coordinate per call, leaving the terminal primal coordinate unrevealed below the stated threshold.Source: §4 · p. 8, §4.1 · pp. 10–11

4.2 The stochastic contribution under mean-square smoothness

  • The stochastic term uses a Bernoulli-gated four-node path: when the gate is closed, internal dual edges reveal no new coordinate; when open, at most the next coordinate is exposed.A fresh gate draw is shared by all query points in a call.Source: §4 · p. 8, §4.2 · p. 12
  • Every zero-respecting algorithm needs enough successful shared-sample draws to reveal the terminal primal coordinate; finite batches cannot skip coordinates in the ordered path.The stochastic construction yields expected SOS above ε within the proposition’s call budget.Source: §4.2 · pp. 12–13

4.3 Proof of the NC–C lower bound

  • Theorem 4.8 gives a hard NC–C instance whose unbiased oracle has bounded variance and mean-square smoothness, and whose outputs remain above the target stationarity level through the stated call budget.The theorem covers randomized zero-respecting algorithms with shared-sample oracle access.Source: §4.3 · pp. 13–14

5 A delayed dual chain for the NC–SC lower bounds

The NC–SC construction delays access to each primal coordinate with a dual path, then scales that chain to obtain a deterministic lower bound.

5 A delayed dual chain for the NC–SC lower bounds

  • A dual path of length n between consecutive primal coordinates creates the condition-number factor; choosing n = Θ(√κ) gives the stated scaling.The initial-gap budget fixes the number of chain blocks.Source: §5 · p. 14

5.1 Construction of the delayed chain

  • The delayed chain is jointly smooth and strongly concave in the dual variable, and each oracle response reveals at most one new coordinate.Fewer than m(n + 1) batch calls leave the final primal coordinate zero.Source: §5.1 · p. 15

5.2 Scaling and the deterministic lower bound

  • A fixed deterministic NC–SC instance keeps every zero-respecting algorithm’s gradient norm at least 16ε through the stated oracle-call budget.The instance is deterministic and the residual guarantee holds for the prescribed algorithm class.Source: §5.2 · p. 15

6 The bounded-variance NC–SC lower bound

The section constructs a strongly concave lift of a common chain and uses Bernoulli delays to establish a bounded-variance oracle lower bound for zero-respecting algorithms. The query threshold scales with both the deterministic chain length and the delay from stochastic gating.

6.1 A strongly-concave lift of the common chain

  • The mean objective realizes the common chain, while a clipped sample perturbation preserves its mean and bounds the perturbation derivative.The resulting objective is jointly L-smooth and μ-strongly concave in y, with a unique dual maximizer and bounded initial gap.Source: §6.1 · p. 17

6.2 From Bernoulli delays to an oracle lower bound

  • Shared-sample batches reveal at most the next block, and the chain keeps the value-function gradient large until the terminal block is revealed.The Bernoulli delay bounds progress, giving the stochastic hardness threshold used in the theorem.Source: §6.1 · p. 17, §6.2 · pp. 18, 20
  • The query threshold scales as LΔ/ε² times a factor proportional to 1+κσ²/ε², yielding deterministic and stochastic hardness contributions.The theorem selects a fixed instance whose expected residual remains above ε for algorithms below the stated threshold.Source: §6.2 · pp. 18–19

7 The mean-square-smooth NC–SC lower bound

The section adds mean-square smoothness to the NC–SC setting and gates a common chain through a shared Bernoulli sample. Its theorem combines deterministic and stochastic query thresholds for zero-respecting algorithms across finite shared-sample batch sizes.

7.1 A Bernoulli-gated strongly-concave construction

  • The construction gates a common chain with a shared Bernoulli sample; the random term affects only the y-gradient, while a deterministic quadratic supplies strong concavity.The resulting oracle is unbiased, has variance at most σ², and satisfies the stated same-sample mean-square smoothness condition.Source: §7 · p. 20, §7.1 · p. 21

7.2 Scaling and completion of the lower bound

  • The scaling combines the deterministic condition-number threshold with a stochastic threshold set by the chain length and Bernoulli probability.The deterministic instance also belongs to the mean-square-smooth class when the smoothness constant satisfies L̄ ≥ L.Source: §7.2 · pp. 23–24
  • Theorem 7.6 establishes a lower bound for every zero-respecting randomized algorithm using shared-sample batch calls, with a fixed instance chosen independently of the algorithm.The theorem applies under its stated condition-number and stochastic accuracy conditions, and covers every finite batch size.Source: §7.2 · p. 25

8 Conclusion

The conclusion emphasizes that the NC–C stochastic ε^-6 barrier persists for zero-respecting algorithms with same-sample access, while complementary NC–SC results capture accuracy and conditioning dependence. It identifies extension beyond zero-respecting algorithms as an open next step.

8 Conclusion

  • The main NC–C result preserves the ε^-6 stochastic barrier under mean-square smoothness while extending the lower bound to zero-respecting algorithms with same-sample access.The conclusion frames the contribution as broader algorithmic scope, not a new accuracy exponent.Source: §8 · p. 26
  • The common product-weighted chain separates value-function stationarity difficulty from delayed revelation of primal–dual information.The conclusion says this construction supports hard instances across concavity and stochastic-regularity regimes, and that stronger stochastic regularity alone does not guarantee improved minimax accuracy dependence.Source: §8 · p. 26
  • Whether the barriers extend beyond zero-respecting algorithms remains an open question.Resolving it would clarify whether the observed complexity is intrinsic to stochastic minimax optimization or tied to coordinate-revelation restrictions.Source: §8 · p. 26

A.2 Proof of Lemma 3.2

The appendix establishes a stationarity barrier for the common chain, shows how its gradient support propagates by at most one coordinate, and derives an endpoint reduction by eliminating interior coordinates.

A.2 Proof of Lemma 3.2

  • If the terminal coordinate remains at or below 1/2, the chain’s gradient cannot fall below the stated barrier.The proof assumes a smaller gradient and derives a contradiction using the first index at which the chain variable crosses its threshold.Source: §A.2 · p. 29

A.3 Proof of Lemma 3.3

  • When coordinates after r are zero, the chain gradient has no nonzero component after r+1, so propagation reaches at most the next coordinate.The derivative at coordinate r+1 can be nonzero, providing the one-coordinate propagation used in the oracle lower bound.Source: §A.3 · p. 30

B.1 Proof of Lemma 4.1

  • Eliminating interior coordinates by minimizing their difference energy yields a linear interpolation and an endpoint Schur complement.The resulting endpoint energy is (a−b)²/(n−1).Source: §B.1 · p. 30

B.2 Proof of Lemma 4.2

These proofs verify the construction’s smoothness and oracle properties, then establish strong concavity, a feasible maximizer, and an initial-gap bound.

B.2 Proof of Lemma 4.2

  • The construction is shown to be jointly smooth and concave in the dual variable, with unrevealed coordinates excluded by the zero-chain support argument.Source: §B.2 · p. 31

B.3 Proof of Lemma 4.5

  • The Bernoulli sample gradient is unbiased with variance calibrated by p, and shared centered multipliers cancel cross terms to establish mean-square smoothness.Source: §B.3 · pp. 31–32

C.1 Proof of Lemma 5.1

  • Derivative bounds establish joint smoothness on the feasible domains.Source: §C.1 · p. 32
  • The dual objective is 1/(2n^2)-strongly concave, and its unconstrained block maximizer lies in the feasible domain, yielding the stated value function and initial-gap bound.Source: §C.1 · p. 33

C.2 Proof of Lemma 5.2

The proof establishes a zero-chain barrier for the value function: the coordinate order delays revelation, so a zero-respecting algorithm cannot reach the terminal coordinate quickly.

C.2 Proof of Lemma 5.2

  • When xm ≤ 1/2, the value-function argument rules out a gradient norm below cd.Source: §C.2 · p. 33
  • Tridiagonal dual blocks expose only the next dual coordinate, and the other endpoint does not bypass the primal-dual path.Source: §C.2 · p. 33
  • Fewer than m(n + 1) calls leave terminal coordinate xm unrevealed, forcing a zero-respecting final output to have bxm = 0.Source: §C.2 · p. 34

D.1 Proof of Lemma 6.1

These proofs verify the strongly concave construction and its stochastic-oracle properties, including blockwise information limits and a constant-sample mean-square-smooth instance.

D.1 Proof of Lemma 6.1

  • Completing the square identifies a unique dual maximizer under µ-strong concavity, while the exact value-function formula supports the smoothness argument.Source: §D.1 · pp. 34–35

D.2 Proof of Lemma 6.2

  • With a shared draw, a batch reveals at most the next block; failed draws reveal none, independently of finite batch size.Source: §D.2 · p. 36

E.1 Proof of Lemma 7.1

  • The instance verification establishes mean-square smoothness, strong concavity, joint smoothness, and a bounded initial gap.Source: §E.1 · pp. 37–38

E.2 Proof of Lemma 7.5

  • A deterministic instance represented as a constant-sample oracle satisfies the same mean-square-smooth class requirements.Source: §E.2 · p. 38

Related papers

Loading 2610.01662v1…