acceptodds
Under review as a conference paper at ICLR 2027

High-Probability Guarantees for SGD under -Heavy-Tailed Gradient Noise

Abstract

Stochastic gradient descent (SGD) is widely used to train machine learning models, but subsampling the training data introduces noise into its updates. The strength and applicability of high-probability guarantees therefore depend critically on how the tails of gradient noise are modeled. Reports of heavy-tailed gradient noise in deep learning motivate relaxing the bounded-noise and sub-Gaussian assumptions commonly used in high-probability analyses of SGD. We use Young functions from Orlicz space theory to describe noise tails in a common framework. We model SGD gradient noise by adopting a Young function that preserves the finiteness of all polynomial moments while allowing tails heavier than sub-Weibull, including lognormal distributions. The resulting class is called -heavy-tailed, with controlling the tail heaviness. We establish concentration inequalities for -heavy-tailed noise and combine them with a uniform bound on the difference between empirical and population gradients along the SGD trajectory to obtain high-probability bounds on optimization and population-risk stationarity for smooth nonconvex losses under trajectory assumptions. The bounds are not restricted to a particular learning-rate decay rule and make explicit the effects of noise tails and learning-rate schedules. Under the Polyak–Łojasiewicz condition, we bound the risk at the last iterate. We also analyze SGD with gradient clipping under the -heavy-tailed noise model.

Primary area:
learning theory
Keywords:
stochastic gradient descent, heavy-tailed gradient noise, high-probability bounds, Orlicz spaces

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_YKbkOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work studies the high-probability convergence and generalization guarantees for SGD under the β\beta-heavy-tailed condition, allowing tails heavier than sub-Weibull, while requiring all polynomial moments to remain finite. Under smoothness and trajectory assumptions, the authors derive high-probability bounds on the empirical and population gradient norms for smooth nonconvex objectives. Under additional PL conditions, the authors establish last-iterate optimization and excess population risk bounds. They further extend their analysis to SGD with gradient clipping.

Critical strengths

The paper considers an intermediate class of heavy-tailed distributions that is not covered by standard sub-Weibull assumptions but retains finite moments of all orders. This provides an interesting extension of existing high-probability analyses of SGD. The development of martingale concentration inequalities under this condition, particularly with predictable noise scales and variance proxies, is a useful technical contribution.

Critical weaknesses

The paper introduces a β\beta-heavy-tailed noise model that extends beyond sub-Weibull distributions, but its practical relevance to SGD remains unclear. Although the proposed Orlicz condition is mathematically motivated by lognormal-type distributions, the cited empirical evidence concerns intermediate-layer gradient magnitudes rather than centered stochastic gradient noise. Furthermore, the analysis assumes a uniform bound on the conditional Orlicz norm throughout the SGD trajectory, without establishing when this assumption holds in realistic learning settings. Consequently, it remains unclear whether the proposed framework captures practically relevant noise behavior or offers meaningful advantages over existing noise models.

Moreover, even the paper extends existing high-probability guarantees to a broader noise class, the resulting convergence rates do not demonstrate a clear advantage over existing analyses. The results in this work rely on restrictive conditions, including uniformly smooth per-sample losses, a trajectory-dependent gradient bound, and global PL conditions for the last-iterate guarantees. The additional tail-dependent factors may also substantially weaken the bounds. Overall, the paper does not convincingly establish that the extended noise model leads to fundamentally new insights or sharper guarantees for SGD.

Questions for authors
  1. Could the authors provide further justification or empirical evidence that centered stochastic gradient noise in practical learning problems satisfies the proposed β\beta-heavy-tailed condition, particularly the uniform conditional Orlicz norm bound along the SGD trajectory? Additionally, in what practical settings would this noise model offer meaningful advantages over existing sub-Weibull assumptions?

  2. How do the resulting convergence rates compare quantitatively with existing high-probability guarantees under sub-Weibull or finite-moment assumptions? In particular, are there regimes where the proposed analysis yields sharper or more informative bounds, rather than merely accommodating a broader class of noise distributions?

2 comments
AuthorsOpenReview ↗

Response to Reviewer YKbk

We thank the reviewer for their careful reading and valuable comments. We respond to each point below.

Weakness 1. Practical relevance, empirical evidence, and the uniform bound along the trajectory

We agree that experimental evidence that the centered gradient noise in actual training satisfies our condition is lacking. Sections 1 and 2 of the general response explain the motivation drawn from existing work and the extent of its empirical support. Regarding the uniform bound along the trajectory, Section 3 of the general response explains its relation to existing assumptions, the situations in which it holds and those in which it does not, and a direction for relaxing it.

Weakness 2. Advantage of the rates over existing analyses, strength of the assumptions, and the tail factor

Our paper concerns gradient noise that is regarded as β\beta-heavy-tailed rather than sub-Weibull. For such noise, the reference point for standard SGD is the high-probability guarantee available under bounded variance alone. Its dependence on the failure probability is polynomial (for example, 1/δ1/\delta from a bound in expectation and Markov's inequality), and an example shows that a logarithmic dependence cannot be obtained in general [1, Theorem 2.1]. For fixed TT, β\beta, and step sizes, our guarantee gives a better dependence on the failure probability as δ→0\delta\to 0. The reason is that the tail factor exp⁡(2log⁡1/β(T/δ))\exp(2\log^{1/\beta}(T/\delta)) raised by the reviewer, although larger than the logarithmic factors of the sub-Weibull analyses, grows more slowly than any positive power of 1/δ1/\delta. This is the benefit obtained from extending the noise model (Section 4 of the general response). When the noise can be regarded as sub-Weibull, the existing analyses are sharper, and our paper does not improve their rates.

The conditions listed by the reviewer, namely uniform smoothness of the per-sample losses, the trajectory-dependent gradient bound, and the global PL condition used for the last-iterate guarantees, are also used in the existing analysis under sub-Weibull noise [2]. They are therefore not specific to our noise model (see the Assumptions column of Table 2, line 757). We agree that they are restrictive. Among them, the trajectory-dependent gradient bound can be removed by clipping, as shown in Theorem 3.9.

Question 1. Empirical evidence, the uniform bound along the trajectory, and advantages over sub-Weibull assumptions

For the empirical evidence and the uniform bound along the trajectory, please see our response to Weakness 1 and Sections 2 and 3 of the general response referred to there. The noise model offers an advantage over sub-Weibull assumptions when the gradient noise is regarded as β\beta-heavy-tailed rather than sub-Weibull, for example when it has lognormal-type tails. The possibility of such tails has been suggested on the basis of the multiplicative structure of products of Jacobians across layers (Section 1 of the general response).

Question 2. Quantitative comparison with existing guarantees, and regimes with sharper bounds

The quantitative comparison has been added in Appendix A.1 (from line 709, Tables 2–4) and is explained in Section 4 of the general response. Under sub-Weibull noise, the existing analyses give sharper bounds, as stated in our response to Weakness 2. In comparison with standard SGD under bounded variance alone, however, there is a regime in which our bound is smaller. Under bounded variance alone, high-probability guarantees depend polynomially on the failure probability δ\delta. Theorem 3.1 additionally imposes Assumptions 2.2 and 2.5 and, for fixed TT, β\beta, and step sizes, gives a better dependence on the failure probability as δ→0\delta\to 0. This comparison is explained in Section 4 of the general response. For finite TT and δ\delta, which bound is smaller also depends on the hidden constants. For clipped SGD, our clipping result (Theorem 3.9) does not improve on the existing rates for clipped SGD under bounded variance (Section 4 of the general response).

We hope that these responses address the reviewer's concerns. We would be glad to answer any further questions.

References

  • [1] A. Sadiev et al. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. ICML 2023.
  • [2] S. Li and Y. Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. ICML 2022.

Thank you for the response and revision. However, my main concerns about the motivation for the proposed noise model and the limited novelty over existing work remain. I therefore maintain my original score.

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

This paper gives high-probability optimization and generalization bounds for nonconvex SGD under β\beta-heavy-tailed gradient noise, which is measured by the Orlicz function Ψβ(x)=exp⁡(log⁡β(x+1))−1\Psi_\beta(x)=\exp(\log^\beta(x+1))-1 with β>1\beta>1, allowing tails heavier than sub-Weibull. The authors establish concentration inequalities for β\beta-heavy-tailed noise and combine them with a uniform bound on the difference between empirical and population gradients along the SGD trajectory to obtain high-probability bounds on optimization and population-risk stationarity for smooth nonconvex losses under trajectory assumptions. They also consider the Polyak–Łojasiewicz condition and SGD with gradient clipping.

Critical strengths

The paper extends high-probability guarantees for nonconvex SGD from sub-Weibull noise to a strictly heavier Orlicz class that still has all polynomial moments and includes lognormal noise. The concentration argument is a Freedman-type bound for trajectory-dependent martingale noise, rather than an independent-sum inequality. This is the main technical improvement over Li and Liu (2022) and Madden et al. (2024), whose guarantees are established under sub-Weibull tails.

Critical weaknesses
  1. The population-gradient bound of the order (d+log⁡(1/δ))/n\sqrt{(d+\log(1/\delta))/n} is also obtained in Li and Liu (2022), where the factor exp⁡(2log⁡1/β(T/δ))\exp(2\log^{1/\beta}(T/\delta)) in this paper is replaced by log⁡θ−1(T/δ)log⁡(1/δ)\log^{\theta-1}(T/\delta)\log(1/\delta). Furthermore, [1] gives a high-probability bound of order O~(d/n)\widetilde O(d/n) on the squared population gradient for steps of order 1/t1/\sqrt{t} and T≍n2/(d2L2)T\asymp n^2/(d^2L^2). This paper fails to give a comprehensive comparison with these existing works.

  2. Assumption 2.2 is imposed on the sampling noise of finite-data SGD, but Remark 2.3 notes that this noise has finite support, so the assumption only enforces a uniform Orlicz scale. That scale excludes the infinite-variance α\alpha-stable noise cited as motivation, and the paper does not check the assumption experimentally.

[1] Lei, Yunwen. "Towards better generalization bounds of stochastic optimization for nonconvex learning." IEEE Transactions on Pattern Analysis and Machine Intelligence (2025).

Questions for authors
  1. Could the authors give a more comprehensive comparison with existing works such as Li and Liu (2022) and [1]?

  2. As far as I know, [1] gives better uniform convergence results compared with Lei & Tang, 2021. Would this help to improve the existing results? (such as Lemma A.7 and Theorem 3.3 in this paper)

  3. Given that Remark 2.3 says the finite-data sampling noise has finite support, what heavy-tail behavior does the uniform Orlicz scale in Assumption 2.2 encode, and does this scale include the infinite-variance α\alpha-stable noise discussed in the introduction?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Q83J (1/2)

We thank the reviewer for their careful reading and valuable comments. We respond to each point below.

Weakness 1. Comparison with Li and Liu [2] and Lei [1]

We added a comparison with Li and Liu [2] and Lei [1] in Table 2 of Appendix A.1 (line 757). Our contribution is to provide high-probability guarantees for standard SGD under gradient noise that is regarded as β\beta-heavy-tailed rather than sub-Weibull. When the noise can be regarded as sub-Weibull, the guarantee of Li and Liu is sharper, and our tail factor exp⁡(2log⁡1/β(T/δ))\exp(2\log^{1/\beta}(T/\delta)) is replaced there by powers of logarithms. The O~(d/n)\widetilde{\mathcal{O}}(d/n) bound of Lei [1, Theorem 7] is obtained from a uniform gradient bound based on the empirical second moment of the per-sample gradients. It holds under the trajectory condition ηt∥∇ℓ(wt;z)∥≤G0\sqrt{\eta_t}\lVert\nabla\ell(\boldsymbol w_t;z)\rVert\le G_0, which is stronger than our Assumption 2.5 and implies it, and in the underparameterized regime d≪nd\ll n. This uniform bound also holds under our assumptions, and with T≍(n/d)2T\asymp(n/d)^2 it yields the rate d/nd/n up to the tail factor and logarithmic factors (see our response to Question 2 for this improvement).

Weakness 2. Uniform Orlicz scale for finitely supported noise, relation to α\alpha-stable noise, and experimental verification

As the reviewer notes, Assumption 2.2 implies that all moments are finite, so infinite-variance α\alpha-stable noise is not covered. In the revision, we relate the motivation of the paper to lognormal-type tails rather than to α\alpha-stable noise (lines 042–047; Section 1 of the general response).

We also agree that, in the finite-data setting, the noise at each step has finite support and Assumption 2.2 is a condition on a uniform Orlicz scale (Remark 2.3, lines 212–226). We explain what this condition expresses in our response to Question 3.

Regarding experimental verification, we have not confirmed that the centered gradient noise in actual training satisfies this condition. The revision distinguishes the motivation for studying lognormal-type tails from empirical support (Sections 1 and 2 of the general response), and leaves the verification on actual gradient noise for future work.

AuthorsOpenReview ↗

Response to Reviewer Q83J (2/2)

Question 1. Comparison with Li and Liu [2] and Lei [1]

The comparison has been added in Table 2 of Appendix A.1 (line 757). Its content is explained in our response to Weakness 1.

Question 2. Improvement through the uniform convergence result of Lei [1]

We thank the reviewer for this helpful suggestion. Yes, using the bound of Lei [1, Theorem 2], the rate of Theorem 3.4 can be improved, in terms of dd and nn, from d/n\sqrt{d/n} to d/nd/n under certain conditions. Under the same assumptions, using the empirical second moment of the per-sample gradients, n−1∑i∥∇ℓ(w;zi)∥2n^{-1}\sum_i \lVert\nabla\ell(\boldsymbol w;z_i)\rVert^2, reduces the dependence on the worst-case gradient bound bR+b′bR+b^\prime over the ball of radius RR. Two conditions are required: (i) the underparameterized regime, in which the number of parameters dd is much smaller than the sample size nn (d/n≪1d/n\ll 1), and (ii) the empirical second moment of the gradients is much smaller than (bR+b′)2(bR+b^\prime)^2. Neither is guaranteed by our assumptions alone. In particular, (i) fails for the overparameterized models used in modern deep learning, in which the number of parameters exceeds the sample size. Regarding (ii), under ηt≍t−1/2\eta_t\asymp t^{-1/2}, the weighted average of the empirical second moment along the trajectory becomes small relative to the square of the gradient bound on the ball as the number of iterations grows. For the improved generalization bound to carry over to the final rate, the optimization error must also be reduced sufficiently, which requires a longer horizon than before. A longer horizon in turn increases the tail factor exp⁡(2log⁡1/β(T/δ))\exp(2\log^{1/\beta}(T/\delta)), so the overall bound does not necessarily improve. The conditions and the derivation are given in the main text (lines 322–323) and in Appendix A.10 (from line 1944).

Question 3. What the uniform Orlicz scale expresses, and its relation to α\alpha-stable noise

In the finite-data setting the noise is bounded, yet its distribution may still produce very large gradient deviations with small probability, as in the case of a truncated heavy-tailed distribution. For such distributions, it is meaningful for the analysis to reflect not only the almost-sure bound but also the frequency of large deviations. Our Orlicz condition controls the magnitude and the frequency of the deviations through the scale KK.

Bounded noise formally belongs to every tail class. However, the scale and the constants in the resulting guarantees depend on the class in which the noise is measured, so the choice of the assumption affects the guarantee. Madden et al. [3] make this point for bounded sub-Weibull noise (in the paragraph following their Remark 7), and Appendix A.9 (from line 1919) gives the corresponding calculation for our model.

As stated in our response to Weakness 2, infinite-variance α\alpha-stable noise is not covered by this assumption.

We hope that these responses address the reviewer's concerns. We would be glad to answer any further questions.

References

  • [1] Y. Lei. Towards better generalization bounds of stochastic optimization for nonconvex learning. IEEE TPAMI, 2025.
  • [2] S. Li and Y. Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. ICML 2022.
  • [3] L. Madden, E. Dall'Anese, and S. Becker. High probability convergence bounds for non-convex stochastic gradient descent with sub-Weibull noise. JMLR, 2024.

Thanks for the response. In Lemma A.31, what if we estimate νS(wt)\nu_S(\mathbf{w}_t) using the self-bounding property mentioned in [1]? Would this help to improve the result?

AuthorsOpenReview ↗

Response to Reviewer Q83J

Yes, we agree that the self-bounding property gives a more informative estimate of the second-moment term when the training loss is small, since it reflects the loss attained during training. However, as explained below, it does not change the order d/nd/n of the final rate.

Our current argument uses Lemma A.31 to obtain

\le \frac{\sum_{t=1}^T\eta_t\lVert\nabla\mathcal L_S(\boldsymbol w_t)\rVert^2}{\sum_{t=1}^T\eta_t} +\sigma_\beta^2,$$ where the gradient term is controlled by Theorem 3.1 and $\sigma_\beta^2$ is the uniform noise-variance bound defined in Lemma A.31. If we additionally assume that each per-sample loss is nonnegative, our smoothness assumption (Assumption 2.4) gives the self-bounding property $\lVert\nabla\ell(\boldsymbol w;z)\rVert^2\le 2b\ell(\boldsymbol w;z)$. Averaging over samples and iterations yields the alternative bound $$\frac{\sum_{t=1}^T\eta_t\nu_S(\boldsymbol w_t)}{\sum_{t=1}^T\eta_t} \le 2b\,\frac{\sum_{t=1}^T\eta_t\mathcal L_S(\boldsymbol w_t)}{\sum_{t=1}^T\eta_t}.$$ Compared with the bound of Lemma A.31 and the worst-case bound $\nu_S(\boldsymbol w)\le(bR+b')^2$, this estimate captures the benefit of a small training loss, as discussed in Lei [1, Remark 1]. We can use the smaller of the two displayed bounds in Appendix A.10, making the generalization bound more sensitive to the actual training trajectory. However, a smaller second moment improves only the second term of [1, Theorem 2]; the first term, $(bR+b')D_R/n$ with $D_R=d\log(Rn)+\log(1/\delta)$ as in Appendix A.10, is unaffected. Along the SGD trajectory, the radius $R$ grows with $\sum_t\eta_t$. This also happens in [1, Theorem 7], where the iterate norm grows as $T^{1/4}$ (Eq. (29) there) and the first term contributes $\sqrt T d^2/n^2$ up to constants and logarithmic factors. In both analyses, balancing this term against the optimization term gives the horizon $T\asymp(n/d)^2$ and the rate $d/n$, up to the tail and logarithmic factors in our case (see the sketch at the end of Appendix A.10). At this horizon the second-moment term is also of order $d/n$, so the self-bounding estimate can reduce this term but does not change the order $d/n$ of the final rate. We have added this self-bounding estimate as Remark A.32 in Appendix A.10 (lines 1998–2009 of the revised manuscript).
Reviewer_juR1OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers β\beta heavy-tailed noise, and develops its concentration bounds. Based on those developed tools, it derives, under the β\beta gradient noise model, high-probability convergence bounds for 1) SGD under nonconvex smooth functions in terms stationarity guarantees, 2) SGD under nonconvex smooth functions with PL condition in terms of last-iterate risk guarantees, and 3) SGD with gradient clipping under nonconvex smooth functions.

Critical strengths
  1. This paper considers a new noise model that is under-explored in the current stochastic optimization literature, and develops its concentration properties.
Critical weaknesses
  1. There lacks motivations in studying the proposed gradient noise. Maybe more discussions are needed on why this type of noise is of interest to the community?
  2. The β\beta heavy-tailed noise is stronger then existing literature on stochastic optimization under gradient noise with moment bounds for moment in (0,2](0, 2]. The paper does not provide a comparison with existing sota results in this regime, and demonstrate strength in terms of complexity bounds presented in this paper under the stronger assumptions.
Questions for authors

n.a.

2 comments
AuthorsOpenReview ↗

Response to Reviewer juR1

We thank the reviewer for their careful reading and valuable comments. We respond to each point below.

Weakness 1. Motivation

We agree that the original submission did not explain the motivation sufficiently, and we have added it to the revision (lines 042–047). Hodgkinson and Mahoney [1, Section 6] suggest that the tail of the stochastic gradient noise at fixed weights may be of lognormal type, on the basis of the multiplicative structure of products of Jacobians across layers [2]. Unbounded lognormal-type noise is outside the scope of the existing sub-Weibull analyses, whereas analyses under a bounded pp-th moment do not exploit the finiteness of all moments. Our work derives the high-probability guarantees available for standard SGD in this intermediate regime and identifies the resulting tail-dependent factor (see also Section 1 of the general response).

Weakness 2. Comparison with existing results under bounded-moment assumptions

As the reviewer notes, our assumption is stronger than a bounded pp-th moment with p∈(1,2]p\in(1,2]. Since our main results concern standard SGD, we first discuss p=2p=2, the bounded-variance case, in which the comparison is for the same algorithm.

Under bounded variance alone, high-probability bounds for standard SGD depend polynomially on the failure probability δ\delta (for example, 1/δ1/\delta from a bound in expectation and Markov's inequality), and an example shows that such a dependence cannot be avoided in general [3, Theorem 2.1]. Theorem 3.1 additionally imposes Assumptions 2.2 and 2.5 and, for fixed TT, β\beta, and step sizes, yields a dependence on the failure probability that grows more slowly than any positive power of 1/δ1/\delta as δ→0\delta\to 0. This is the benefit obtained from the stronger assumption. A detailed comparison is given in Section 4 of the general response.

For p<2p \lt 2, which allows infinite variance, the existing high-probability guarantees are for clipped SGD [3, 4]. Because the update rule differs, they are not directly comparable with our main results for standard SGD. For reference, we added a comparison of our clipping result (Theorem 3.9) with these results in Table 3 of Appendix A.1 (line 811).

We hope that these responses address the reviewer's concerns. We would be glad to answer any further questions.

References

  • [1] L. Hodgkinson and M. Mahoney. Multiplicative noise and heavy tails in stochastic optimization. ICML 2021.
  • [2] B. Hanin and M. Nica. Products of many large random matrices and gradients in deep neural networks. Communications in Mathematical Physics, 2020.
  • [3] A. Sadiev et al. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. ICML 2023.
  • [4] T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. NeurIPS 2023.

i thank the authors for the replies. 1) the newly added motivation part is helpful. 2) for standard sgd, the improvement of failure probability dependence from polynomial to subpolynomial is meaningful but not substantial. 3) for clipped sgd, my major concern still stands, i.e., stronger assumptions does not bring benefits in complexity so this would weaken the contribution of the analysis. therefore, i would like to keep my current score 2.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response to All Reviewers and the AC (1/2)

We thank the all reviewers for their careful reading and constructive comments. Here we respond to the concerns shared by several reviewers. Line numbers refer to the revised manuscript, in which the changes are shown in blue.

1. Motivation for studying β\beta-heavy-tailed noise (Reviewer juR1, Weakness 1; Reviewer Q83J, Weakness 2)

The original submission did not explain the motivation sufficiently, and the revision now states it as follows (lines 042–047 and 131–132). Hodgkinson and Mahoney [1, Section 6] suggest that the tail of the stochastic gradient noise at fixed weights may be of lognormal type. This suggestion rests on the multiplicative structure by which derivatives propagate across layers as products of Jacobians, and Hanin and Nica [2] establish the asymptotic lognormality of Jacobian norms in randomly initialized ReLU networks (lines 123–128). Lognormal-type noise does not satisfy the sub-Weibull condition, so the existing sub-Weibull rates do not apply directly. Conversely, analyses that use only a bounded pp-th moment do not exploit the finiteness of all moments, which is a property of lognormal-type tails, and may therefore yield weaker bounds.

Our contribution is to derive high-probability guarantees for standard SGD in this intermediate regime and to identify the factor exp⁡(2log⁡1/β(T/δ))\exp(2\log^{1/\beta}(T/\delta)) induced by β\beta-heavy-tailed noise. For standard SGD, the dependence on the failure probability δ\delta lies between the polylog(1/δ)\mathrm{polylog}(1/\delta) dependence of sub-Weibull analyses and the polynomial dependence on δ\delta that arises under bounded variance alone (see Section 4 below).

We note that the existing high-probability guarantees under a bounded pp-th moment with 1<p<21 \lt p \lt 2, which allows infinite variance, are for clipped SGD [3, 4]. They are therefore not directly comparable with our results for standard SGD.

2. Practical relevance (Reviewer YKbk, Weakness 1 and Question 1; Reviewer Q83J, Weakness 2)

As the reviewers point out, we have not verified that gradient noise is β\beta-heavy-tailed for the architectures and training procedures used in deep learning practice. As Reviewer YKbk notes, Chmiel et al. [5] report observations on the magnitudes of gradients with respect to intermediate-layer outputs (lines 127–128). The result of Hanin and Nica [2] concerns networks at initialization. It suggests that gradient noise may be of lognormal type, but it is not conclusive. Empirical verification, or a theoretical derivation, of the β\beta-heavy-tailed property of gradient noise for practical architectures and training procedures is left for future work.

3. Justification and limitations of the uniform bound on the Orlicz scale along the trajectory (Reviewer YKbk, Weakness 1 and Question 1)

Assumption 2.2 allows the conditional Orlicz scale to vary with time and with the history, and assumes the existence of a common upper bound KK (lines 203–206). Bounding the noise by a constant that is independent of the iterate is common to the analyses under bounded variance [6], sub-Weibull noise [7, 8], and a bounded pp-th moment [4].

In the finite-data setting, as noted in Remark 2.3 (lines 212–226), the noise at each step is bounded, and its magnitude is controlled by the norm of the iterate. Since the Orlicz scale of bounded noise is controlled by its bound, Assumption 2.2 holds as long as the iterates remain in a bounded region. The assumption therefore amounts to requiring that the optimization trajectory remain bounded. For example, it holds regardless of the trajectory when the per-sample gradients are bounded uniformly in the iterate, as in logistic regression with bounded features. It also holds when the iterates are restricted to a bounded set, as in projected SGD.

In contrast, when the noise magnitude grows with the norm of the iterate, as for the squared loss, and standard SGD is run without projection, boundedness of the trajectory is not guaranteed, and neither is the assumption. Training deep neural networks without projection falls into this case, and our paper does not establish the assumption there.

One way to relax this restriction is localization, as in [3], where the assumption is imposed only on a bounded set and the probability that the iterates leave this set is controlled separately. Our Freedman-type inequality (Proposition A.23) admits a similar extension. However, such an extension requires additional modeling of the probability that the iterates leave the set, and the validity of that modeling becomes a new issue. We do not pursue this direction here and restrict our analysis to the uniform bound. The refinement by localization is stated as future work in the Conclusion (lines 466–473).

AuthorsOpenReview ↗

General Response to All Reviewers and the AC (2/2)

4. Comparison with existing work (Reviewer juR1, Weakness 2; Reviewer Q83J, Weakness 1 and Questions 1 and 2; Reviewer YKbk, Weakness 2 and Question 2)

We added comparison tables in Appendix A.1 (from line 709), namely Table 2 for SGD, Table 3 for clipped SGD, and Table 4 for the dependence of the SGD guarantees on the failure probability. The main text now refers to them (lines 116–117). Since standard SGD and clipped SGD use different update rules, we compare each with the existing results for the same algorithm.

For standard SGD, our guarantees carry the tail factor exp⁡(2log⁡1/β(T/δ))\exp(2\log^{1/\beta}(T/\delta)) in place of the powers of logarithms in the sub-Weibull analyses [7, 8]. They therefore do not improve the rate when the noise can be regarded as sub-Weibull. On the other hand, for fixed TT, β\beta, and step sizes, the dependence of our bound on the failure probability, exp⁡(2log⁡1/β(T/δ))log⁡(e/δ)\exp(2\log^{1/\beta}(T/\delta))\log(e/\delta), is heavier than the polylog(1/δ)\mathrm{polylog}(1/\delta) dependence of the sub-Weibull analyses and lighter than any positive power of 1/δ1/\delta as δ→0\delta\to 0. Under bounded variance alone, a bound in expectation combined with Markov's inequality gives a bound proportional to 1/δ1/\delta, and an example shows that a polynomial dependence on δ\delta cannot be avoided in general for standard SGD [3, Theorem 2.1]. In this sense, our guarantees lie between the two. For tails beyond sub-Weibull, they give standard SGD a better dependence on the failure probability than is available under bounded variance alone. The differences in assumptions from the sub-Weibull analyses are listed in Table 2 (line 757), and the dependence on the failure probability is compared in Table 4 (line 844). Under infinite variance, the argument based on bounded variance is not available. The existing high-probability guarantees in that case are for clipped SGD and are not directly comparable with standard SGD, so we list them separately in Table 3 (line 811).

For clipped SGD, our analysis makes explicit how the tail parameter β\beta enters the threshold τ=8Kexp⁡(log⁡1/β(8T/δ))\tau=8K\exp(\log^{1/\beta}(8T/\delta)). Under this threshold, it gives a stationarity guarantee that requires neither the trajectory-dependent gradient bound (Assumption 2.5) nor the smoothness-based upper bound on the step size. It does not aim to improve the rates of the existing analyses of clipped SGD.

In addition, following the suggestion of Reviewer Q83J, we examined when the uniform gradient bound of Lei [9] can sharpen our generalization bounds, and added this discussion to the main text (lines 322–323) and to Appendix A.10 (from line 1944). The conditions for its applicability and the comparison of the bounds are given in Appendix A.10.

This concludes our response to the concerns shared by several reviewers. We respond to the individual comments in our replies to each reviewer. The revision also corrects typographical errors and makes minor wording changes, which do not affect the claims or the results of the paper.

References

  • [1] L. Hodgkinson and M. Mahoney. Multiplicative noise and heavy tails in stochastic optimization. ICML 2021.
  • [2] B. Hanin and M. Nica. Products of many large random matrices and gradients in deep neural networks. Communications in Mathematical Physics, 2020.
  • [3] A. Sadiev et al. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. ICML 2023.
  • [4] T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. NeurIPS 2023.
  • [5] B. Chmiel et al. Neural gradients are near-lognormal: improved quantized and sparse training. ICLR 2021.
  • [6] S. Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 2013.
  • [7] S. Li and Y. Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. ICML 2022.
  • [8] L. Madden, E. Dall'Anese, and S. Becker. High probability convergence bounds for non-convex stochastic gradient descent with sub-Weibull noise. JMLR, 2024.
  • [9] Y. Lei. Towards better generalization bounds of stochastic optimization for nonconvex learning. IEEE TPAMI, 2025.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.