acceptodds
Under review as a conference paper at ICLR 2027

Nagaev Bounds for Nonconvex Momentum: Finite Moments and Temporal Dependence

Abstract

Momentum can smooth individual gradient errors without removing the confidence cost of rare shocks along an optimization trajectory. For ordinary nonconvex momentum under conditional second and th moments, , we prove a bound on average squared-gradient stationarity that separates a logarithmic variance term from a polynomial rare-shock term. A quadratic construction matches the polynomial component in its powers of horizon, confidence and stepsize over the stated moment class, allowing the noise law to depend on horizon and confidence. Both bounds have constants uniform in momentum within an explicit stepsize region. We then replace conditional moment envelopes by a budget for accumulated noise energy. This gives stationarity at fixed momentum and confidence under a uniform second-moment bound, including state-dependent martingale noise with unbounded conditional variance. A predictable correction extends the analysis to additive causal noise, covering polynomial linear filters with exponent under finite moments. Exact calculations and simulations explain the common mechanism: pointwise smoothing can coexist with a persistent normalized shock response. They also test fixed-law tails and the scope of the random-volatility and causal extensions.

Primary area:
optimization
Keywords:
stochastic momentum, nonconvex optimization, heavy-tailed noise, high-probability bounds, temporal dependence, martingale concentration, Nagaev inequalities

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_rozoOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies average squared-gradient stationarity for ordinary stochastic gradient descent with momentum under finite-moment noise. Its main theorem separates a logarithmic variance contribution from a polynomial rare-shock contribution, with constants independent of dimension and momentum within an explicit step-size region. A scalar quadratic construction matches the polynomial term over a noise class whose law may depend on the horizon and confidence level.

Critical strengths
  1. The main proof isolates the effect of momentum cleanly. The virtual iterate reduces the update to a form suitable for descent, while the proof retains the filtered-noise energy rather than immediately replacing it by raw noise energy. Lifting the noise into a product Hilbert space gives the factor (1−β)/(1+β)(1-\beta)/(1+\beta); together with the step-size condition, this controls the apparently singular momentum coefficient.
  2. The lower bound and experiments help interpret the result without overstating it. Theorem 2.2 matches the polynomial component in horizon, confidence, and step-size dependence. The abstract explicitly allows a horizon- and confidence-dependent noise law, and the paper distinguishes that construction from its separate fixed-law simulations.
Critical weaknesses
  1. The extensions contribute less to the convergence rate than the main confidence split. At fixed momentum and confidence, the second-moment consequence of Theorem 3.1 yields the familiar T−1/2T^{-1/2} stationarity order, with an energy allowance proportional to 1/δ1/\delta. Its distinctive value is the route through realized and predictable energy and the refined dependent-noise allowances. The paper could make that distinction more explicit relative to a Markov conversion of an expectation bound. 2, The demonstrated practical scope is limited. The matching construction establishes a worst-case moment-class obstruction, not a matching asymptotic result for one fixed noise law. The causal theorem treats additive stationary errors; the state-dependent application uses a bounded amplitude multiplying martingale noise. The experiments make these regimes concrete, including a vector learning problem, but use constructed or injected noise.
Questions for authors
  1. Could you summarize exactly what the second-moment consequence of Theorem 3.1 adds to an expectation-plus-Markov argument under the same assumptions, separating rate improvements from the usefulness of the energy formulation?
  2. Is the dependence on LβL_\beta in the energy result necessary, or can additional control of filtered energy recover momentum-uniform constants for some random-volatility models?
  3. How does the rare-shock term compare with the variance term at experimentally relevant horizons for a fixed law with finite ppth moment?
Reviewer_uRm5OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies high-probability bounds for the average squared gradient norm of ordinary stochastic gradient descent with momentum (SGDM). The authors show that under conditional unbiasedness and second and pp-th order moment bounds for pp > 2, SGDM satisfies a nonconvex stationarity guarantee that decomposes into a term involving the variance of the stochastic gradient and a polynomial term capturing the effect of rare, large gradient errors. A quadratic construction matches the polynomial dependence on horizon, confidence, and stepsize over a distribution class that permits the noise law to depend on T,δT, \delta. The authors additionally extend this analysis to martingale noise with unbounded conditional variance and additive stationary causal noise. Synthetic experiments further illustrate the theoretical findings.

Critical strengths
  1. Theorem 2.1 establishes an interesting decomposition of the stationarity bound into a logarithmic variance-dependent term and a polynomial term capturing the effect of rare, large gradient errors. Theorem 2.2 further provides a matching lower bound for the polynomial dependence on horizon, confidence, and stepsize, demonstrating that this confidence cost cannot generally be eliminated for ordinary SGDM under the stated assumptions. I believe this provides a meaningful theoretical contribution to understanding the limitations of momentum under heavy-tailed gradient noise, especially considering no changes are made procedurally.

  2. The extensions to martingale noise with unbounded conditional variance and additive stationary causal noise are also interesting. In particular, Theorem 3.1 replaces uniform conditional variance bounds with an accumulated noise-energy condition, while Theorem 4.2 accommodates temporally dependent noise through a martingale–coboundary decomposition. These results broaden the scope of the analysis beyond conventional conditional moment assumptions and provide potentially useful directions for understanding SGDM under more general stochastic-gradient models.

Critical weaknesses

W1. Although the theoretical guarantees appear mathematically sound, their implications are not sufficiently explained. In particular, the momentum-uniform constants in Theorem 2.1 must be interpreted together with the stepsize restriction α≤(1−β)/(8L)\alpha \leq (1-\beta)/(8L), which becomes increasingly restrictive as β→1\beta \to1. The paper does not clearly explain how this affects the comparison between SGD and SGDM, or what the results establish about the benefits and limitations of momentum beyond the persistence of the polynomial confidence cost. I believe a more explicit discussion of these distinctions is important for understanding the significance of the main contribution.

W2. The additional extensions introduce several technical conditions without sufficiently motivating their necessity or explaining their practical implications. For example, the usefulness of Theorem 3.1 depends on establishing a sufficiently informative accumulated noise-energy bound, while the causal-noise results impose different dependence conditions for fixed-confidence and shrinking-confidence guarantees. The distinctions between these results, their assumptions, and their improvements over existing guarantees are not clearly communicated. Additionally, the proofs would benefit from a clearer explanation of the key technical arguments and the intuition motivating them. Given that the primary contribution of this paper is theoretical, I believe these presentation issues substantially detract from the accessibility and significance of the results.

Questions for authors

Q1. Can the authors provide an explanation of what Theorems 2.1, 3.1, and 4.2 each add, distinguishing improvements in confidence dependence from extensions of the admissible noise class? In particular, why are these technical conditions required and in what settings are they particularly useful practically? This would help me understand the theoretical contributions and their implications more clearly.

Q2. What conclusion about momentum follows after accounting for the stepsize restriction, rather than considering only the constants in the bound? A concise explanation of this would clarify the interpretation of momentum uniformity. Additionally, how does this compare against SGD?

Reviewer_NBiPOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper presents high-probability guarantees for momentum-based SGD methods along with lower bounds. The paper presents simulations to explain some of the observations made in the theory.

Critical strengths
  • The paper considers an interesting problem and presents results under multiple settings.
  • The paper provides high-probability guarantees along with lower bounds for SGDM.
  • The experiments are conducted to test the theory.
Critical weaknesses

The paper is unreadable. In my opinion, in its current form, the paper cannot be accepted. Here, I list my major concerns:

  • The paper consistently utilizes terms like rare shock, rare gradients, worst-case variance envelope, among others, without defining them. I looked into the past papers the authors have cited and found no reference to this language. It is impossible to make sense of the paper if it takes extensive effort to understand every statement in the paper.

  • The contributions of the paper are not clear. The contributions are written in a difficult-to-understand language; the paper does not clarify what the past literature misses that the paper addresses.

  • The Introduction jumps from one topic to another just to complete a checklist of topics. It is not at all clear what story the paper is trying to sell.

Questions for authors

I would say the paper needs a complete rewrite and a complete proofread to make sure the paper actually makes a worthy contribution to the field.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.