- 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 -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 -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
-
Could the authors provide further justification or empirical evidence that centered stochastic gradient noise in practical learning problems satisfies the proposed -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?
-
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
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.
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 β-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/δ 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 T, β, and step sizes, our guarantee gives a better dependence on the failure probability as δ→0. The reason is that the tail factor exp(2log1/β(T/δ)) raised by the reviewer, although larger than the logarithmic factors of the sub-Weibull analyses, grows more slowly than any positive power of 1/δ. 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 β-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 δ. Theorem 3.1 additionally imposes Assumptions 2.2 and 2.5 and, for fixed T, β, and step sizes, gives a better dependence on the failure probability as δ→0. This comparison is explained in Section 4 of the general response. For finite T and δ, 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