PaperlayerView exact revision on arXiv

Source-linked AI summary

Geometric Moment Contraction for Stochastic Nesterov Acceleration

Wei Biao Wu

arXiv:2609.31303v1stat.MLcs.LG

TL;DR

The paper addresses the challenge of certifying contraction for stochastic Nesterov dynamics, where a componentwise comparison can be conservative at large momentum. It develops power-Lyapunov and quadratic-certificate approaches, and exact quadratic calculations show that momentum changes transient and marginal behavior while leaving long-run covariance unchanged.

  • Problem

    The direct componentwise comparison is conservative when β is large, limiting its usefulness as a contraction certificate in that regime.

    Source: §5 · p. 14

  • Method

    A power of the quadratic energy establishes contraction for every fixed β < 1 and p > 1, alongside general quadratic and samplewise-sector Lyapunov certificates.

    Source: §5.2 · p. 18, §7 · p. 22, §7.1 · p. 23

  • Results

    The exact quadratic calculations show that momentum changes transient roots, marginal variance, and the nonzero-frequency spectrum, but the full average has long-run covariance H−1ΩH−1.

    Source: §12 · p. 48

  • Takeaways & Limitations

    Distinguishing transient acceleration from first-order statistical efficiency is essential when selecting momentum for online inference.

    Source: §12 · p. 48

    The explicit quadratic metric's (1 − β)^2 scaling is not intrinsic stability scaling and is not an optimum over all quadratic metrics.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

We study geometric moment contraction (GMC) of the constant-parameter stochastic Nesterov recursion \[ Y_k=\Theta_k+\beta(\Theta_k-\Theta_{k-1}),\qquad \Theta_{k+1}=Y_k-\gamma G(Y_k,X_{k+1}). \] Under mean strong monotonicity and stochastic $L^p$ Lipschitz continuity, an explicit Perron comparison proves synchronous $L^p$ contraction when $\beta\gamma L_p<(1-\beta)(1-q_{\gamma,p})$. This direct criterion includes infinite-variance gradients for $1<p<2$, but its small-step regime requires $\beta<\mu/(\mu+L_p)$. A complementary power-Lyapunov argument establishes a positive, generally much smaller, step-size interval for every fixed $\beta<1$ and every $p>1$, using only a finite $p$th gradient moment. At $p=2$, a simpler explicit certificate gives \[ 0<\gamma<\frac{2\mu(1-\beta)^2}{L_2^2(1-\beta+2\beta^2)}. \] Its quadratic high-momentum scaling is a limitation of the chosen metric, not a sharp stability boundary. We quantify this loss, provide a general mean-only quadratic $S$-procedure, and exploit endpoint Lyapunov inequalities under stronger samplewise sector information. Verified endpoint certificates can be orders of magnitude less conservative than the explicit metric.

1 Introduction

The paper studies synchronous contraction of the constant-parameter stochastic Nesterov recursion and its consequences for stationary behavior and inference. It develops finite-moment contraction criteria with distinct momentum and step-size guarantees, then relates their conservatism to broader certificates and exact benchmarks.

1 Introduction

  • With constant step size, iterates generally do not converge to the optimizer, so the paper studies the invariant law of the augmented state and synchronous coupling.Its focus is a complementary coupling result for the nonlinear augmented state and the statistical consequences of its dependence structure.Source: §1 · p. 2

1.1 Main contributions

  • The direct Perron criterion gives synchronous Lp contraction for every p > 1, including infinite-variance cases, but its small-step regime requires β < µ/(µ + Lp).For 1 < p < 2, the assumptions permit infinite gradient variance.Source: §1 · p. 2, §1.1 · p. 3
  • For p = 2, a quadratic energy yields a mean-square certificate for every momentum value, requiring strong monotonicity only of the mean field.Individual sample losses need not be convex; the displayed weight optimizes only the derived sufficient condition within its chosen family.Source: §1.1 · pp. 3–4
  • Contraction yields a unique causal stationary state, exponential physical dependence, and a central limit theorem for the observed orbit from every deterministic initial pair.An oP (n1/p) Gaussian approximation is obtained under an order-p > 2 contraction; a mean-square certificate alone does not supply that higher-moment coupling at the same step size.Source: §1.1 · p. 4
  • In the stated small-step regime, the stationary second moment is bounded at scale γ/(1 − β), while the additive quadratic model has momentum-invariant long-run covariance H−1ΩH−1.The paper also derives exact quadratic stability and variance formulas and a random-curvature benchmark with distinct high-momentum regimes.Source: §1.1 · p. 4

1.2 Positioning relative to the literature

  • The paper frames its contribution as explicit finite-moment coupling criteria and their inference consequences, not as new causal-process limit theorems or quadratic AR(2) calculations.It describes the work as a Nesterov-specific development of nonlinear autoregressive stability and inference in the sense of Chen and Wu [2016].Source: §1.2 · p. 6

2 Setup and the ordinary-SGD contraction module

  • The assumptions use mean strong monotonicity and stochastic Lp Lipschitz continuity; the mean field has a unique zero, and sample losses need not be convex.The contraction arguments also apply to the stated unconstrained extrapolated stochastic monotone-operator recursion, but not thereby to projected or proximal acceleration.Source: §2 · p. 8

3 Nesterov acceleration as an iterated random function

The paper rewrites Nesterov’s recursion in position–increment coordinates to expose its synchronous coupling structure. It also connects the resulting contraction analysis to a two-lag autoregressive framework, which supplies stationarity and dependence conclusions under a sufficient condition.

3 Nesterov acceleration as an iterated random function

  • The state (Y, S) is Markov, and the original iterates are recovered through an equivalent linear coordinate transformation.For two trajectories with shared innovations, the extrapolated-point difference satisfies yk = xk + βsk.Source: §3 · p. 9
  • Product Lp GMC measures synchronous contraction of the transformed state and is equivalent, up to fixed constants, to GMC of the original two-iterate state.The definition uses positive weights on the two state-coordinate differences.Source: §3 · pp. 9–10

3.1 Connection with Chen and Wu’s autoregressive framework

  • The AR(2) comparison gives a sufficient contraction condition; for scalar random-curvature dynamics its interval has a positive lower endpoint even though the exact region starts at zero.At β = 0.9, the autoregressive certificate covers 9/14 < γh < 19/14, while failure of a sufficient condition does not imply instability.Source: §3.1 · pp. 10–12
  • Under the AR(2) contraction condition, the Nesterov state has a unique causal stationary solution with a finite pth moment, geometric coupling to stationarity, and exponential physical dependence.Forward coupling also gives convergence from every deterministic initial pair.Source: §3.1 · p. 11
  • The lag-coefficient approach can fail for sufficiently small steps at fixed β > 0 because it discards the negative sign on the previous iterate.The position–increment and power-Lyapunov certificates preserve signed information, but are additional sufficient certificates rather than uniformly dominant ones.Source: §3.1 · p. 11

4 Direct Lp geometric moment contraction

A direct Perron comparison establishes product-Lp geometric moment contraction for synchronously coupled Nesterov trajectories, yielding a unique causal stationary solution. The componentwise comparison is conservative at high momentum because it discards stabilizing signed terms.

4 Direct Lp geometric moment contraction

  • The direct Perron theorem gives synchronous product-Lp geometric moment contraction and a unique causal stationary solution with finite pth moment.Backward iteration constructs the stationary solution, and forward coupling gives contraction from deterministic states.Source: §4 · pp. 12–13
  • The stationary state also satisfies classical geometric-moment-contraction and p-Wasserstein mixing bounds.The Wasserstein bound compares the k-step transition law with the invariant law.Source: §4 · pp. 13–14
  • As γ decreases, the direct condition eventually fails for every fixed β > 0 because the absolute-value comparison loses the stabilizing cross-term sign.The scalar quadratic specialization permits 0 < γh < 2(1−β) only when β < 1/2, whereas the exact Nesterov stability region is nonempty for every β < 1.Source: §4 · p. 14

5 Mean-square contraction for every momentum parameter

A signed quadratic energy provides mean-square contraction for every momentum parameter under a sufficient step-size condition, while a power-Lyapunov argument extends finite-moment contraction to every fixed β < 1. The latter removes the qualitative momentum restriction but may yield a very small step-size interval.

5 Mean-square contraction for every momentum parameter

  • The signed slow-coordinate energy yields geometric mean-square contraction and a unique causal stationary law with finite second moment for every 0 < β < 1 under the theorem’s step-size condition.The proof retains signed coupling terms lost by componentwise comparison.Source: §5 · pp. 14–16

5.1 Optimality within a natural quadratic family

  • The derived sufficient bound is maximized at t = β^2, but this is not an optimum over all quadratic metrics or the exact contraction region.The optimization is restricted to the slow coordinate and the specified energy family.Source: §5.1 · p. 17

5.2 Finite pth moments at arbitrary fixed momentum

  • The power argument handles 1 < p < 2 without assuming a second moment by applying the power-remainder bound at the zero-step momentum update.This preserves increment damping before bounding the stochastic-gradient remainder.Source: §5.2 · pp. 18–20
  • For every fixed β < 1 and p > 1, a power of the quadratic energy gives a positive step-size interval using only a finite pth moment.For (µ, Lp) = (1, 1.5) and p = 1.4, the bound is approximately 1.51 × 10^-8 at β = 0.8 and 1.54 × 10^-10 at β = 0.9; it is an existence result, not a practical tuning rule.Source: §5.2 · pp. 18–20

6 Verification in statistical learning models

The paper verifies its stochastic-gradient assumptions in several learning models, illustrating finite-moment contraction with random-design least squares, ridge-regularized logistic regression, and additive heavy-tailed noise.

6 Verification in statistical learning models

  • The stated stochastic-gradient assumptions can be checked without bounded gradients, and the examples illustrate where the fractional-moment theorem applies.The examples cover random-design least squares, ridge-regularized logistic regression, and additive heavy-tailed gradient noise.Source: §6 · p. 20

6.1 Random-design least squares

  • For Gaussian random-design least squares, the direct mean-square criterion’s small-step momentum range is β < 1/(1 + √(d + 2)), approximately 0.333, 0.224, and 0.122 at d = 2, 10, and 50.This criterion does not cover momenta 0.8–0.95 in these examples; for 1 < p < 2, the condition permits Zε to have infinite variance.Source: §6.1 · pp. 20–21

6.2 Ridge-regularized logistic regression

  • Ridge regularization is essential for global strong monotonicity in stochastic logistic regression; without it, logistic risk may be only locally strongly convex [Bach, 2014].When the covariate is almost surely bounded, the samplewise sector condition also makes the endpoint LMI available.Source: §6.2 · p. 21, §6.1 · p. 21

6.3 Additive heavy-tailed gradient noise

  • Additive heavy-tailed gradient noise needs no variance when 1 < p < 2, while multiplicative-noise least squares can produce heavy stationary tails even from light-tailed additive errors [Gürbüzbalaban et al., 2021, Hodgkinson and Mahoney, 2021, Damek and Mentemeier, 2026].The additive-noise setting separates heavy-tailed innovations from memory controlled by the deterministic Jacobian.Source: §6.3 · pp. 21–22

7 Pathwise sector conditions and an endpoint LMI

Samplewise Hessian-sector information supports pathwise contraction through endpoint Lyapunov tests. Under mean-only information, a separate quadratic S-procedure provides a sufficient certificate for mean-square contraction.

7 Pathwise sector conditions and an endpoint LMI

  • Under a samplewise Hessian sector, endpoint Lyapunov inequalities certify pathwise geometric moment contraction in a common quadratic norm.With a finite pth moment at the optimizer, the stationary state has a finite pth moment and the contraction implies Lp GMC.Source: §7 · pp. 22–23

7.1 A general quadratic certificate using mean-only information

  • The mean-only quadratic S-procedure gives conditional contraction and a unique causal stationary law with finite second moment when its semidefinite certificate holds.The certificate is sufficient, not an exact characterization; a numerical search failure does not establish infeasibility or instability.Source: §7.1 · pp. 23–24

8 Stationary moments and invariant-mean bias

The section bounds stationary moments and invariant-mean bias at p=2 under a specified small-step regime. The admissible step size depends on momentum, while the bias is O(γ) for fixed β under an additional Jacobian condition.

8 Stationary moments and invariant-mean bias

  • The stationary moment theorem is stated for p=2 and fixed β<1, with constants that may deteriorate as β approaches 1.The theorem’s step-size restriction is also β-dependent.Source: §8 · p. 24
  • For fixed β<1, the p=2 theorem provides a stationary mean-square bound for γ below an explicit threshold, whose admissible range depends on β.The range is not uniform as β approaches 1.Source: §8 · p. 24
  • Under a globally Lipschitz Jacobian and the corollary’s other assumptions, the invariant-mean bias has an explicit bound of order O(γ) for fixed β.The averaged-iterate CLT is centered at θ∞(γ, β), separating statistical n^-1/2 fluctuation from the algorithmic O(γ) invariant bias.Source: §8 · p. 26

9 Physical dependence and initialization-robust limit theory

Under the stated contraction conditions, the Nesterov state has exponential physical dependence, supporting moment and almost-sure results, central limit theorems, and Gaussian approximation. These results extend to every deterministic initial pair, with higher-moment Gaussian approximation requiring more than a mean-square certificate alone.

9 Physical dependence and initialization-robust limit theory

  • The stated contraction hypotheses yield exponential physical dependence for the Nesterov state.The proposition covers order-p contraction for p>1, specified p=2 conditions, or pathwise contraction with a finite pth anchor moment.Source: §9 · p. 27
  • Moment and almost-sure results for averaged iterates transfer to every deterministic initial pair.The section applies established causal-process probability theorems; it does not claim new general strong laws.Source: §9 · pp. 27–28
  • The p=2 contraction conditions give an initialization-robust central limit theorem, including a joint CLT for finitely many parameter pairs driven by the same data stream.The functional central limit theorem also holds from every deterministic initialization.Source: §9 · pp. 28, 30
  • An order-p>2 contraction supports an oP(n^(1/p)) Gaussian approximation from every deterministic initial pair, but a mean-square certificate alone does not provide that higher-moment coupling at the same step size.A verified samplewise common norm permits every finite anchor moment at the same certified step.Source: §9 · pp. 29–30

10 Exact additive-quadratic theory

For additive quadratics, the paper gives exact stability and stationary-process results, including the long-run covariance and a stable limit under infinite-variance innovations. It also distinguishes these exact scalar benchmarks from sufficient contraction criteria and identifies conditions not implied by GMC alone.

10 Exact additive-quadratic theory

  • Under the quadratic stability condition and a logarithmic innovation moment, the recursion has a unique causal strictly stationary solution; a finite pth innovation moment gives a finite pth stationary moment and pathwise geometric contraction.The stationarity claim needs only the logarithmic moment; the finite pth moment is an additional condition for the pth-moment conclusion.Source: §10 · p. 30
  • For each eigenvalue h, the scalar Schur condition reduces to γh < 2(1+β)/(1+2β), yielding the exact quadratic stability test when imposed across eigenvalues.The deterministic part of the recursion is Schur stable if and only if the stated eigenvalue conditions hold.Source: §10 · pp. 30–31
  • The small-step and high-momentum limits do not commute: the fixed-β small-step expansion is nonuniform as β approaches 1.Neither the explicit stationary bound nor the fixed-β expansion is asserted uniformly near unit momentum.Source: §10 · pp. 31–32
  • Throughout the quadratic stability region, the long-run covariance is H^-1ΩH^-1 and is independent of both γ and β.Momentum can change transient roots and one-time stationary variance without changing the first-order asymptotic covariance of the full iterate average.Source: §10 · p. 32

10.1 A stable limit under infinite-variance innovations

  • Under the innovation domain-of-attraction assumption, the quadratic recursion has a stable limit for partial sums, and the same limit holds from every deterministic initial pair.The result uses the exact linear filter representation.Source: §10.1 · p. 33
  • For general nonlinear Nesterov recursions, fractional-moment GMC alone does not imply a stable limit; further conditions include joint regular variation, anti-clustering, and a negligible-small-jump condition.The quadratic theorem reduces these issues to the innovation domain-of-attraction assumption through the exact linear filter.Source: §10.1 · p. 33

10.2 Rigidity and an exact random-curvature benchmark

  • The exact scalar random-curvature analysis characterizes L2 GMC by an if-and-only-if boundary, distinct from the sufficient coefficient-sum condition.The sufficient condition’s boundary is not asserted to coincide with the exact signed-covariance boundary.Source: §10.2 · pp. 34–35
  • At β=0, the scalar random-curvature boundary is 2μ/L2; at β=1, a nonempty mean-square stable interval exists exactly when L2<3μ^2.The β=1 statement is specific to this scalar model.Source: §10.2 · p. 35

11 Numerical illustrations and checked certificates

The numerical illustrations distinguish sufficient bounds, exact model-specific boundaries, verified matrix certificates, and observed rates. Across deterministic and stochastic examples, they compare certificate conservatism, demonstrate synchronous forgetting, and examine full-orbit and stationary variance behavior.

11 Numerical illustrations and checked certificates

  • The experiments distinguish sufficient conditions, exact model-specific boundaries, verified matrix certificates, and observed Monte Carlo rates.No experiment is presented as a benchmark for large-scale neural-network training.Source: §11 · p. 36

11.1 What is lost by the explicit metric?

  • With μ=L=h=1, the exact Schur boundary is 2(1+β)/(1+2β), while the explicit metric misses stable points; the mean-only scalar boundary can remain positive as β approaches one.For μ=1, L=1.5, the scalar boundary tends to 2/9 while the explicit slow-coordinate bound tends to zero; for L=3, the scalar boundary decays linearly in 1−β, not quadratically, and is not a sufficient region for nonlinear models.Source: §11.1 · p. 36, Figure 2 · p. 38, Figure 3 · p. 38

11.2 Endpoint and mean-only quadratic certificates

  • 0.923076 versus 0.024024 at [1,1.5], β=0.8, and 0.434862 versus 0.001292 at [1,3], β=0.9, are verified endpoint steps versus explicit bounds.A mean-only certificate at (1, 1.5, 0.8, 0.03) gives squared factor 0.999, also beyond the explicit bound; search failures do not prove infeasibility, and smaller steps are not necessarily certified.Source: §11.2 · pp. 39–41

11.3 Certified and observed forgetting in a nonlinear sector model

  • At γ=0.9, the nonlinear samplewise-sector model has a verified worst endpoint squared factor of 0.8665990, beyond the slow-coordinate interval.At γ=0.015, the endpoint certificate gives squared factor 0.8252862 versus 0.9979116 for the explicit metric; the observed Euclidean squared-separation fit is 0.78156 per step, not directly comparable across norms.Source: §11.3 · pp. 41–42

11.4 A genuinely mean-only random-curvature experiment

  • The mean-only random-curvature recursion has exact second-moment spectral radius 0.8258465, versus the explicit theorem’s squared factor 0.9979116.The sample slopes include a negative value with positive probability, so the experiment has no positive samplewise curvature lower bound.Source: §11.4 · p. 42

11.5 Fractional moments with infinite-variance innovations

  • With infinite-variance Pareto innovations and finite 1.4th moment, the experiment checks the direct fractional-moment theorem at permitted small momentum.It does not numerically validate the theorem’s tiny large-momentum interval.Source: §11.5 · p. 43, Figure 9 · p. 44

11.6 The full-orbit central limit theorem from separated initial pairs

  • The full-orbit normal approximation is illustrated from three separated initial pairs, retaining every iterate and showing only small deterministic standardized shifts.The shifts are −0.0225, 0, and 0.0225; coverage uses the known asymptotic long-run variance, not an estimated standard error.Source: §11.6 · p. 44, Table 3 · p. 44, Figure 10 · p. 45

11.7 Marginal variance versus long-run variance

  • The exact long-run variance is one for every displayed momentum, although the marginal variance changes substantially.Empirical long-run estimates vary by a few percent from Monte Carlo variation and finite-batch effects; the result concerns zero frequency, not the full spectrum.Source: §11.7 · pp. 45–46, Figure 11 · p. 46, Figure 12 · p. 47

12 Discussion and extensions

The discussion distinguishes certified contraction from true stability and separates momentum’s transient effects from its first-order statistical efficiency. It also identifies scope boundaries and directions for improving the theory.

12 Discussion and extensions

  • The certificates have distinct scopes: the direct Perron criterion restricts momentum, while power-Lyapunov contraction covers each fixed β < 1 with a potentially very small interval.The explicit quadratic mean-square theorem also covers every fixed momentum, but its step interval is conservative; no sufficient certificate is identified with the true nonlinear stability boundary.Source: §12 · p. 47
  • The scalar random-curvature model has a phase transition at L2/µ = 3, but does not resolve worst-case nonlinear or multivariate stability.Its favorable behavior at β = 1 does not extend the general GMC theorems to unit momentum.Source: §12 · p. 47
  • The statistical conclusions require contraction conditions: the central limit theorem needs second-moment contraction, while the sharper Gaussian coupling needs a higher moment and its own condition.Both center at the invariant mean, which may differ from the optimizer at a fixed nonzero step, and concern initialization robustness rather than limits conditional on an arbitrary random environment.Source: §12 · p. 47
  • Useful all-momentum regions under only a fractional moment and better high-momentum scaling remain quantitative open questions.The discussion points to optimizing a mean-only metric, richer quadratic constraints, or multistep contraction as possible routes.Source: §12 · p. 48
  • Proximal or projected extensions require checking nonexpansiveness in the augmented contraction metric, while nonconvex extensions need additional recurrence and communication assumptions for global uniqueness.A look-ahead coefficient ν ∈ [0, 1] interpolates between heavy ball and Nesterov, but its optimal certificates need not interpolate linearly.Source: §12 · p. 48
  • The full-average long-run covariance remains H−1ΩH−1, although momentum changes transient roots, marginal variance, and the nonzero-frequency spectrum.The small-step expansion is nonuniform near unit momentum, which matters when choosing momentum for online inference.Source: §12 · p. 48

A Power inequalities and proof of Proposition 2.3

The appendix justifies the power-remainder inequalities used in the ordinary-SGD module, including the noninteger-moment regime. These inequalities support Proposition 2.3’s contraction bound and step-size conclusions.

A Power inequalities and proof of Proposition 2.3

  • The ordinary-SGD module uses power-remainder inequalities to handle noninteger p and permit infinite variance.The appendix records the analytic inequalities underlying that part of the geometric moment contraction argument.Source: A Power inequalities and proof of… · p. 49
  • For 1 < p < 2, the Euclidean remainder is bounded by 2^(2−p)|y|^p after its linear inner-product term.The stated constant is a convenient valid upper bound, not the best one for fixed p.Source: A Power inequalities and proof of… · p. 49
  • For p ≥ 2, the proof justifies a scalar expected-remainder step through concavity and Jensen’s inequality rather than substituting an Lp norm into the negative linear term.The argument treats a = 0 separately as the linear case.Source: A Power inequalities and proof of… · p. 49
  • Applying the power inequalities in the respective p regimes yields Proposition 2.3’s bound after taking pth roots, with step-size characterizations following by monotonicity.For 1 < p < 2, the proof invokes Lemma A.1(ii).Source: A Power inequalities and proof of… · p. 50

B Additional details for the iterated-random-function construction

The appendices provide supporting constructions and calculations for the paper’s contraction and quadratic analyses. They give a stationary-solution construction, verify the all-momentum energy algebra, record further scalar formulas, and establish a covariance-operator positivity fact.

B Additional details for the iterated-random-function construction

  • A contracting complete product Lp metric yields a unique causal stationary solution with finite pth moment and forward synchronous coupling decaying at rate r^k.The backward construction requires finite displacement from one deterministic anchor; the limiting solution is anchor-independent.Source: B Additional details for the… · p. 50

C Algebraic verification of the all-β energy

  • The coefficients in the all-β energy theorem and Proposition 5.3 follow by conditional expectation, substitution, and use of the stated inequalities.The appendix collects the exact transformations behind Theorem 5.1.Source: C Algebraic verification of the all-β… · pp. 50–51

D Further quadratic formulas

  • The scalar quadratic formulas show that zero-frequency spectral density is invariant, while both γ and β alter the spectrum at nonzero frequencies.The zero-frequency value is σ²/h² and is relevant to full iterate averaging.Source: D Further quadratic formulas · p. 51

E A positivity fact for the covariance operator

Related papers

Loading 2609.31303v1…