PaperlayerView exact revision on arXiv

Source-linked AI summary

Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds

Wei Biao Wu

arXiv:2609.30499v2stat.MLcs.LG

TL;DR

Distance-dependent noise challenges ordinary SGD because smooth nonconvex objectives need not control how far iterates travel [p001, p003]. The paper analyzes single-sample SGD using descent and displacement arguments, then derives localized higher-moment confidence bounds [p057, p018]. Its refined bounds separate variance and rare-shock costs, with T^-1/3 stationarity under distance growth and T^-1/2 under objective-gap growth at polynomial failure probabilities [p058].

  • Problem

    Noise moments may grow with distance from initialization, and objective values on general smooth nonconvex problems need not control that distance.

    Source: §1 · pp. 1–2

  • Method

    The analysis combines descent with displacement control for second-moment results and uses predictable localization with higher-moment concentration for confidence bounds.

    Source: §1.1 · p. 3, §11 · p. 36

  • Results

    The refined bounds separate variance and rare-shock contributions, attaining T^-1/3 stationarity under distance growth and T^-1/2 under objective-gap growth when failure probability is T^-r for r ≤ p/2 − 1.

    Source: §11 · p. 36

  • Takeaways & Limitations

    Ordinary single-sample SGD attains the BG-0 stochastic complexity in the second-moment class, while the optimality claim does not extend automatically to the smaller mean-square-smooth class.

    Source: §11 · p. 36

    The root-T refinement requires objective-gap moment growth, which is not implied by ordinary smoothness or a bound on the objective alone.

    Source: §8 · p. 30

Abstract

from arXiv · show

Uniform noise-moment bounds exclude stochastic gradients whose variability increases with the iterate. We study ordinary, single-sample stochastic gradient descent for smooth, lower-bounded, possibly nonconvex objectives under distance-dependent conditional moments. Under second moments alone, a direct descent--displacement argument yields $T^{-1/3}$ expected average squared-gradient stationarity with a horizon-dependent stepsize. An explicit oracle-complexity corollary matches the known smooth Blum--Gladyshev (BG-0) lower bound, including the $Lb_2\Delta^3\varepsilon^{-6}$ and $L\Delta\sigma^2\varepsilon^{-4}$ stochastic terms, where $\Delta$ is the initial objective gap and $\sigma^2+b_2\|x-x_1\|^2$ bounds the variance. Thus unchanged SGD attains the minimax stochastic complexity in this second-moment class. For $p>2$, predictable localization and a Hilbert-space Fuk--Nagaev inequality yield a high-probability bound separating logarithmic variance and polynomial rare-shock contributions. The localization radius is derived from the recursion: no bounded-iterate assumption, clipping, normalization, momentum, or increasing batch size is needed. We also give increasing-confidence rates, an objective-gap-growth refinement recovering root-$T$ stationarity, and stochastic $L^p$-Lipschitz examples. The broad BG-0 optimality statement is distinguished from the smaller mean-square-smooth class, in which additional oracle structure permits faster algorithms.

1 Introduction

State-dependent noise can grow with distance from initialization, while objective values may not control the distance traveled or the noise scale [p001, p002, p003]. The paper analyzes ordinary SGD under these conditions, establishing second-moment stationarity and oracle-complexity results alongside higher-moment confidence bounds and their scope [p015, p034, p018, p019, p049, p050, p051, p054, p056].

1 Introduction

  • Distance-dependent moments can grow with the iterate, and smooth nonconvex objectives may have flat directions where objective values do not control that growth.Fresh independent observations ensure conditional unbiasedness but do not make the state-dependent noise scale uniformly bounded.Source: §1 · pp. 1–2

1.1 Results and mechanism

  • The one-sample second-moment analysis gives a finite-horizon O(T^-1/3) expected stationarity rate and matches the BG-0 stochastic oracle lower-bound terms [Fazla et al. (2026, Theorem 1)].The oracle budget is for a uniformly randomized output, and the result uses the ordinary SGD update with one fresh oracle call per iteration.Source: §1.1 · p. 3, §1.2 · p. 4
  • A decreasing-stepsize single run gives near-T^-1/3 expected stationarity for every prefix and almost-sure convergence of gradient norms to zero.The stated schedule has a logarithmic loss, and the result controls weighted gradient and noise energies.Source: §1.1 · p. 3
  • For p > 2, predictable localization and refined Nagaev bounds separate logarithmic variance costs from polynomial rare-shock contributions.The localization radius is derived from the recursion rather than imposed as a bounded-iterate assumption.Source: §1.1 · p. 3, §1.2 · p. 5
  • Under distance growth, a fixed-horizon run attains O(T^-1/3) stationarity with failure probability T^-r for 0 < r ≤ p/2 − 1.For example, fourth moments permit failure probability T^-1 at this rate; these are individual fixed-horizon events, not simultaneous events for a decreasing-stepsize run.Source: §1.1 · p. 3
  • Objective-gap moment growth supports root-T stationarity at failure probability T^-r for r ≤ p/2 − 1, under its additional feedback condition.This condition is distinct from distance growth and is not implied by the two-point stochastic Lipschitz condition alone.Source: §1.1 · p. 3

1.2 Relation to existing work

  • The BG-0 complexity comparison concerns the broad second-moment oracle class, not the smaller mean-square-smooth class with faster variance-reduced methods.The paper distinguishes its ordinary-SGD result from methods using additional oracle structure [Fazla et al. (2026)].Source: §1.2 · p. 4
  • Unlike clipping-based or batched normalized-momentum approaches, the higher-moment results retain the ordinary update and its polynomial rare-shock confidence cost.The Nagaev analysis derives deterministic conditional envelopes by closing a displacement bound rather than assuming bounded iterates.Source: §1.2 · p. 5

2 Setup and moment assumptions

The setup assumes a smooth lower-bounded objective and an unbiased stochastic-gradient recursion, with noise moments allowed to grow with distance from initialization [p066, p067, p068, p070, p071]. Independent-sample stochastic Lipschitz conditions can verify such growth, and finite-horizon integrability supports the subsequent bounds [p075, p090, p091, p095, p097].

2 Setup and moment assumptions

  • The objective has an L-Lipschitz gradient and a finite lower bound, and the recursion uses a deterministic stepsize with conditionally centered errors.The lower bound need not be attained, and no minimizer set is required.Source: §2 · pp. 5–6
  • The second-moment assumption bounds conditional error variance by an affine function of squared distance from initialization; the p > 2 version adds conditional higher-moment growth.The expectation results need only marginal second-moment growth, whereas confidence results require the stronger conditional bounds.Source: §2 · p. 6

2.1 Independent samples and stochastic Lipschitz continuity

  • An independent-sample stochastic Lp-Lipschitz oracle with a finite moment at one reference point implies distance-dependent moment bounds for its centered error.The increment condition alone does not bound absolute noise over an unbounded parameter space; a finite single-point moment is also needed.Source: §2.1 · pp. 6–7

2.2 Integrability and elementary objective bounds

  • Under the assumptions, iterates, gradients, and errors are integrable at every finite horizon, but the induction does not assert a uniform-in-time bound.For an unbiased iid oracle, centered and uncentered distance-growth bounds can also be related using objective smoothness.Source: §2.2 · pp. 7–8

3 A second-moment stationarity theorem

The second-moment theorem establishes expected stationarity and controls displacement using only marginal second-moment growth. Its corollaries give a one-sample T^-1/3 rate, explicit oracle complexity matching the smooth BG-0 lower bound, and a decreasing-stepsize single-run result.

3 A second-moment stationarity theorem

  • With α = a0T^-2/3, one-sample SGD achieves O(T^-1/3) expected average squared-gradient stationarity under marginal second-moment growth.The theorem also controls maximum displacement; the maximal bound uses the same stepsize restriction as the marginal bound.Source: §3 · pp. 9, 11

3.1 Oracle complexity and BG-0 optimality

  • In the small-accuracy stochastic regime, the one-sample bound matches both stochastic terms of the smooth BG-0 lower bound, making ordinary SGD minimax optimal; for fixed b² > 0, L, Δ > 0, its worst-case order is Θ(ε^-6).The match is in dependence on L, b², Δ, and σ², with the usual deterministic LΔ/ε² overhead.Source: §3.1 · p. 13
  • The BG-0 optimality claim does not automatically extend to the smaller mean-square-smooth class, where additional oracle structure permits faster algorithms.The best rate for unchanged single-sample SGD in that smaller class remains a separate algorithm-specific question.Source: §3.1 · p. 13

3.2 A single run with decreasing stepsizes

  • A single decreasing-stepsize run achieves a rate arbitrarily close to T^-1/3 for every prefix and converges to stationarity almost surely.The finite-time rate is for average squared-gradient energy; the last-iterate statement is qualitative, not a finite-time rate.Source: §3.2 · pp. 15–16

4 The probability input and predictable stopping

The probability input is a maximal Hilbert-space Fuk–Nagaev inequality for martingale differences, combining logarithmic variance and polynomial rare-shock allowances. Predictable stopping preserves the same moment budgets, enabling its use without conditioning on future events.

4 The probability input and predictable stopping

  • With probability at least 1 − u, the maximal martingale sum is bounded by a logarithmic variance term plus a polynomial rare-shock term.The inequality applies to martingale differences in a separable Hilbert space for p > 2.Source: §4 · p. 16
  • Predictable stopping preserves the original maximal bound and moment budgets, including the increment that produces an exit.No conditioning on a future no-exit event is involved.Source: §4 · p. 16
  • The centered-energy lemma bounds an upper deviation of nonnegative noise energy, not a centered two-sided Gaussian-plus-polynomial deviation.For p > 4, no logarithm multiplies the Ts^2 variance baseline.Source: §4 · pp. 17–18

5 A deterministic-envelope lemma for plain SGD

This section turns deterministic conditional moment envelopes into simultaneous trajectory and stationarity bounds for plain SGD. An energy-stopped refinement uses accumulated squared-gradient energy to reduce the variance budget of the adaptive transform.

5 A deterministic-envelope lemma for plain SGD

  • The deterministic-envelope results are concentration ingredients for plain SGD, not new concentration theorems, and retain the smoothness cap α ≤ L^-1.The auxiliary ingredients are a raw-energy lift and objective-level localization.Source: §5 · p. 18
  • Under deterministic conditional envelopes and α ≤ L^-1, Proposition 5.1 gives four simultaneous trajectory bounds with probability at least 1 − δ.The proof uses pathwise descent and predictable stopping, then removes the objective stop by a first-exit argument.Source: §5 · pp. 18–19

5.1 Stopping objective plus accumulated gradient energy

  • The refinement's constants depend only on p and are conservative; its purpose is confidence-factor placement rather than numerical optimization.The stopped indicators are predictable and retain the possible exit-producing update.Source: §5.1 · pp. 20–21
  • Proposition 5.2 stops the objective gap plus accumulated squared-gradient energy, yielding an explicit bound valid without LαT ≥ 1.The energy stop makes the adaptive transform's variance budget depend on accumulated gradient energy rather than only a maximum gradient norm.Source: §5.1 · p. 20

6 Nagaev bounds under distance-dependent moments

The distance-dependent Nagaev results derive a localization radius from the recursion and combine trajectory control with stationarity under conditional moment growth. An energy-refined result sharpens the variance baseline, while admissibility and confidence costs constrain the bounds.

6 Nagaev bounds under distance-dependent moments

  • Theorem 6.1 gives a high-probability distance-dependent Nagaev bound with a localization radius derived from the recursion, not imposed on the optimizer.Its numerical constants are dimension-independent, although moment parameters may depend on dimension.Source: §6 · p. 22

6.1 Proof of Theorem 6.1

  • The localization proof uses a stopped auxiliary recursion and a first-exit argument to show it agrees with the original process throughout the run.This is a pathwise argument, not conditioning a martingale inequality on a future no-exit event.Source: §6.1 · pp. 22–23

6.2 A sharper variance baseline and feedback condition

  • The energy-refined theorem places the leading variance baseline at Lασ^2 and the logarithmic fluctuation term at σ^2ℓ/T, while retaining a polynomial rare-shock term.Its cubic feedback-condition component has no variance logarithm, and LαT ≥ 1 absorbs a short-run transform term.Source: §6.3 · pp. 24–25, §6.2 · p. 24

6.3 Trajectory control and admissibility

  • The Nagaev bounds require an explicit feedback condition whose admissibility can tighten as failure probability decreases; their localization radii may grow with T.The second-moment and finite-p results have different moment assumptions and confidence costs; neither imposes one fixed compact set uniformly over all horizons.Source: §6.3 · p. 25

7 Stepsizes, confidence levels, and output criteria

The section gives sufficient finite-horizon stepsize recipes and confidence-dependent stationarity guarantees for ordinary SGD. It also clarifies the sampled-output criterion and the oracle budget used to attain it.

7.1 A direct finite-horizon stepsize recipe

  • The sufficient stepsize recipes make growth and confidence restrictions explicit, but their constants are conservative worst-case certificates rather than practical stability boundaries.Reducing the failure probability can require a smaller stepsize; adaptive estimation of growth parameters is outside the analysis.Source: §7.1 · p. 25
  • The analysis also gives an interpolating finite-horizon high-probability bound, with a stated lower bound on its success probability.The supplied corollary passages do not provide the bound's full expression.Source: §7.1 · p. 26

7.2 Fixed confidence

  • The fixed-confidence schedule yields A_T = O(T^-1/3) with probability at least 1−δ for every positive integer horizon.The finite-p assumption is needed for the confidence decomposition, not for the T^-1/3 exponent, which is also available under second moments alone.Source: §7.2 · p. 26

7.3 Polynomially increasing confidence without a logarithmic rate loss

  • For 0 < r ≤ p/2−1, A_T = O(T^-1/3) holds with failure probability T^-r; this is a fixed-horizon guarantee, not a time-uniform event.With fourth moments, failure probability T^-1 is possible at this rate; first-moment Markov conversion instead gives an O(T^2/3) certificate.Source: §7.3 · p. 27

7.4 Stationarity criteria and oracle complexity

  • Corollary 3.4 supplies a parameter-explicit oracle budget for squared-gradient stationarity, with exactly one oracle call per update.The expectation guarantee implies the first-moment stationarity criterion used in the external BG-0 lower bound.Source: §7.4 · p. 28

8 Objective-gap moment growth and a root-T refinement

The section strengthens distance-growth results by assuming conditional moments grow with the objective gap. Under this additional structure, it derives finite-moment confidence bounds and recovers root-T stationarity in specified regimes.

8 Objective-gap moment growth and a root-T refinement

  • A sufficiently small fixed stepsize α = a0T^-1/2 gives fixed-confidence stationarity of root-T order for sufficiently large T under objective-gap moment growth.The transient and variance terms are O(T^-1/2), while the polynomial term is o(T^-1/2).Source: §8 · pp. 29–30
  • Objective-gap moment growth is an additional assumption: ordinary smooth nonconvexity and an objective bound alone do not imply it.For an unbounded minimizer set, the set-valued verification requires uniform noise-moment control on that set.Source: §8 · pp. 28, 30
  • The objective-gap second-moment condition is a special case of the ABC condition; the refinement adds a specified pth-moment growth assumption and a variance/rare-shock confidence bound.A geometric sufficient condition is also given, including a quadratic-growth route relative to a minimizer.Source: §8 · pp. 30–31

8.1 Refined gap-growth confidence bounds

  • The increasing-confidence corollary states fixed-horizon probability guarantees, not simultaneous guarantees for one decreasing-stepsize run.Its root-T range uses the unadjusted stepsize; beyond that range the sufficient rate is adjusted.Source: §8.1 · p. 31
  • For 0 < r ≤ p/2−1, the unadjusted α = a0T^-1/2 schedule gives root-T stationarity with failure probability T^-r.For the wider range 0 < r < p−1, the corollary gives an increasing-confidence rate with a confidence-dependent stepsize.Source: §8.1 · p. 31

9 Examples and the necessity of noise-sensitive stability

The examples show how distance-dependent noise moments arise in stochastic-gradient models and why smoothness or objective values alone may not provide stability. They also illustrate when objective-gap growth supplies stronger stationarity guarantees and why a stepsize cap based only on objective smoothness can fail.

9.1 Random affine gradient errors

  • Affine gradient errors have moments growing with distance, and a nonzero matrix-noise direction makes a global moment envelope impossible.The affine-noise oracle remains unbiased with objective Ef(x, Z) = F(x).Source: §9.1 · p. 32

9.2 Nonconvex flat directions: distance growth without gap growth

  • On a minimum-level flat direction, the objective gap stays zero while noise moments grow with distance, so no global gap-growth inequality holds.This bounded, noncoercive example separates distance growth from objective-gap growth.Source: §9.2 · pp. 32–33

9.3 A nonconvex coercive example with gap growth

  • A nonconvex objective with quadratic growth satisfies the gap-growth condition, and sufficiently small steps of order T^-1/2 yield fixed-confidence root-T stationarity.The verification does not use convexity.Source: §9.3 · p. 33

9.4 Random-design regression with a nonconvex penalty

  • Unbounded random-design regression with a nonconvex penalty satisfies stochastic Lipschitz continuity without bounded design or response, coercivity, or a smallest-eigenvalue bound.The example can be genuinely nonconvex.Source: §9.4 · pp. 33–34

9.5 A smoothness-only stepsize cap is insufficient

  • A one-dimensional strongly convex objective can have SGD iterates diverge on every sample path despite an unbiased Lp-Lipschitz oracle and α ≤ (8L)^-1.Mean-square contraction instead holds exactly when 0 < α < 2/(1 + c^2); this illustrates noise-sensitive stability, not a rate lower bound.Source: §9.5 · p. 34

9.6 An unbounded minimizer set with controlled noise

  • A nonconvex objective with an unbounded, nonunique minimizer set can still satisfy both gap-growth theorems when noise is controlled along that set.The example needs neither coercivity nor a unique minimizer.Source: §9.6 · p. 34

10 An additive rare-shock lower bound

The section constructs an additive-noise example showing that unchanged SGD cannot have a variance-only logarithmic confidence certificate uniformly over the finite-p class. Its rare-shock law depends on the horizon and confidence, so the result does not establish a fixed-law tail asymptotic or a lower bound on the feedback stepsize.

10 An additive rare-shock lower bound

  • The additive oracle has stochastic Lipschitz constant λ independent of the noise law, while its centered error has b2 = bp = 0.Thus the example lies in a subclass covered by the main theorem.Source: §10 · p. 36
  • A horizon- and confidence-dependent centered additive-noise law shows that a logarithmic variance term alone cannot cover unchanged SGD's polynomial confidence scale uniformly.The construction is not a fixed-law tail asymptotic and does not force the distance-feedback stepsize.Source: §10 · pp. 35–36

11 Discussion and scope

The discussion distinguishes expectation stability, finite-horizon confidence, and oracle complexity, and states the scope of the resulting guarantees. It also identifies questions left open by the analysis.

11 Discussion and scope

  • Under marginal second-moment growth, descent–displacement analysis gives finite-horizon BG-0 stochastic complexity and expected squared maximum displacement 20αT∆ + 10hTσ^2.The decreasing-stepsize extension controls total weighted gradient and noise energies and gives near-T^-1/3 expectation rate with almost-sure gradient-norm convergence.Source: §11 · p. 36
  • For p>2, centered-noise energy and stopped objective-plus-gradient energy yield variance cost Lασ^2 + σ^2ℓ/T while retaining a polynomial rare-shock term.The refined rates are T^-1/3 under distance growth and T^-1/2 under objective-gap growth at failure probability T^-r for r ≤ p/2 − 1; simplified statements require LαT ≥ 1.Source: §11 · p. 36
  • The BG-0 second-moment oracle model differs from common-sample two-point stochastic smoothness, whose additional structure permits faster variance-reduced methods.Objective-gap growth can accommodate unbounded nonunique minimizers if noise is controlled along the minimizer set.Source: §11 · p. 36
  • Finite-time guarantees cover average squared gradients, maximal displacement, and randomized-output conversions, but not a finite-time last-iterate rate or convergence to a specified point.Shrinking-confidence guarantees apply to individual fixed-horizon runs, and the finite-p confidence exponents are not minimax claims.Source: §11 · pp. 36–37
  • Open questions include an exactly log-free horizon-free stationarity rate, plain-SGD analysis using stochastic two-point regularity, and data-driven estimation of state-dependent noise coefficients.A confidence sequence for one decreasing-stepsize run requires an additional uniform-in-time argument.Source: §11 · p. 37

Related papers

Loading 2609.30499v2…