- 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 -th central moment, where . Theorem 1 establishes a high-probability bound on the average squared gradient norm with dependence , suppressing problem-dependent constants. Theorem2 established an algorithm-specific lower bound showing that the joint dependence on and 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
- 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.
- 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.
- 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
-
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.
-
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.