acceptodds
Under review as a conference paper at ICLR 2027

Convergence and Reliability Limits of Standard Nonconvex SGD under Heavy-Tailed Noise

Abstract

Whether standard SGD converges for smooth nonconvex objectives under heavy-tailed gradient noise remains unresolved under the basic combination of standard -smoothness and a bounded -th central moment of the stochastic-gradient noise. We resolve this question and further characterize the high-probability reliability limit of the standard SGD recursion. We study smooth nonconvex optimization under unbiased stochastic gradients whose noise has a bounded -th central moment with . We first prove that, under a confidence-calibrated learning rate, it holds with at least probability. We then characterize the corresponding limitation of standard nonconvex SGD for optimization with heavy-tailed noise. For any deterministic learning rate schedule satisfying , we establish a high-probability lower bound as in the nontrivial regime. Such a result shows that standard nonconvex SGD cannot attain the rate achieved by gradient clipping under heavy-tailed noise, which cannot be removed by learning rate tuning alone.

Primary area:
optimization
Keywords:
Reliable training, Stochastic gradient descent, Heavy-tailed gradient noise, High-probability convergence, Robust learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_HuZ3OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies standard nonconvex SGD under Lipschitz smoothness and heavy-tailed gradient noise characterized by bounded conditional α\alpha-th central moment, where α∈(1,2]\alpha\in(1,2]. Theorem 1 establishes a high-probability bound on the average squared gradient norm with dependence O(T−1+δ−1/αT−(α−1)/α)O\left(T^{-1}+\delta^{-1/\alpha}T^{-(\alpha-1)/\alpha}\right), suppressing problem-dependent constants. Theorem2 established an algorithm-specific lower bound showing that the joint dependence on TT and δ\delta is unavoidable for deterministic learning-rate schedules in the nontrivial regime (i.e., exclude stochastic gradient normalization in learning rate design). These results distinguish probabilistic convergence from finite-second-moment guarantees and clarify the potential benefit of clipping or normalization under heavy-tailed gradient noise. Experiments on three image-classification tasks show that injected heavy-tailed noise increases early instability, while SGD eventually achieves comparable performance. Synthetic tests illustrate the predicted iteration–confidence scaling, and additional comparisons demonstrate benefits from larger batches, clipping, and normalization.

Critical strengths
  1. Convergence of SGD under heavy-tailed gradient noise is an important research problem of interest. The analysis covers standard SGD without clipping, bounded stochastic gradients, or finite variance. It carefully distinguishes the failure of expected squared-gradient bounds from the possibility of high-probability convergence.
  2. Theorem 2 on matching upper and lower bounds is novel and main contribution of the work. The joint characterization of iteration and confidence dependence is a significant contribution. The lower bound covers arbitrary deterministic schedules, showing that deterministic learning-rate tuning alone cannot improve the worst-case rate.
  3. Analytical novelty The stopping-time argument handles potentially infinite second moments, while the minibatch and distributed extensions broaden the results. The appendix includes clipping and normalization comparisons.
Critical weaknesses
  1. Limited (experimental) evidence under naturally occurring heavy-tailed gradient noise. The image classification experiments use artificial noise, providing limited evidence for practical training. Language exhibits heavy-tailed word frequency statistics commonly described by Zipf’s law. More directly, Zhang et al. [1] report empirical evidence of heavy-tailed gradient noise in BERT training. The authors should include a BERT experiment with gradient-noise diagnostics and run comparisons of SGD, clipping, and normalization; a synthetic Zipf experiment would complement this evaluation.

  2. Technical novelty and lower-bound construction need clearer presentation in main context. The paper compares assumptions and guarantees with prior work and supplies full proofs, but gives limited main-text intuition about which proof ingredients are new. In particular, authors should explain the intuition behind their lower-bound examples: insufficient cumulative step sizes can prevent the gradients from becoming small, while rare, large noise perturbations can produce effects that persist over subsequent iterations. A focused comparison with existing lower-bound constructions would help readers assess the technical contribution.

References

[1] Zhang, J., et al. (2020). Why are Adaptive Methods Good for Attention Models? NeurIPS.

Questions for authors

All concerns in the weakness section should be addressed before the work is ready for acceptance.

Reviewer_Rub8OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

In this paper, the authors present an improved high-probability convergence analysis of SGD in the nonconvex setting, compared to prior works. In addition to the upper bound, they establish matching lower bounds in TT and δ\delta terms for SGD with deterministic step-size schedules. The authors also provide experiments to support their theoretical findings.

Critical strengths

The main strength of this paper is the improvement over existing convergence guarantees. Indeed, the most closely related results reviewed by the authors in Table 1 are weaker than those established in this work: either they rely on stronger assumptions that restrict the class of optimization problems or stochastic oracles under consideration, or they provide worse convergence bounds (e.g., Scaman and Malherbe, 2020).

Moreover, the lower-bound result nicely complements the upper bound. However, as the authors themselves acknowledge, Theorem 2 applies only to SGD with predetermined step-size schedules, since the proof technique does not extend to adaptive step-size choices.

Moreover, I went through the proofs and did not find any technical flaws. These proofs are interesting and may be useful to the research community.

Critical weaknesses

None

Questions for authors

I have not found any critical issues. However, I could mention some minor shortcomings.

First, I humbly recommend proofreading the manuscript for typos and removing unnecessary equation numbering. For example, there are typos such as “Can standard nonconvex SGD be guaranteed to converge with high-probability form uunder...” on page 2 and “Consider the H”older’s inequality...” on page 21. Moreover, all equations in the appendix are numbered, although many of them are never referenced. I believe that numbering only the equations that are actually referenced would improve the readability of the proofs.

Second, I would like to comment on the main idea of the paper. In my opinion, the idea itself is not particularly novel. Based on the existing literature, it was already known that high-probability convergence of SGD suffers from a polynomial dependence on 1δ\frac{1}{\delta}, as discussed, for example, in Sadiev et al. (2023). Despite the improved upper bound and the matching lower-bound result, I do not think the paper changes our conceptual understanding of SGD in the setting of the heavy-tailed stochasticity. For this reason, I have decided to maintain my current score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.