Summary of Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: a Unified Framework and High-probability Guarantees, by Aleksandar Armacki et al.
Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees
by Aleksandar Armacki, Shuhua Yu, Pranay Sharma, Gauri Joshi, Dragana Bajovic, Dusan Jakovetic, Soummya Kar
First submitted to arxiv on: 17 Oct 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Optimization and Control (math.OC)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary This paper studies high-probability convergence in online learning with heavy-tailed noise. To address this challenge, the authors propose a general framework for nonlinear stochastic gradient methods (SGDs), which encompasses various popular nonlinearities like sign, quantization, and clipping. By treating the nonlinearity as a black box, they establish unified guarantees for a broad range of nonlinear methods. The results show convergence to the population optimum at a rate of (t^{-1/4}) for symmetric noise and non-convex costs, and to a neighbourhood of stationarity with a constant size that depends on the mixture coefficient, nonlinearity, and noise. The authors’ framework outperforms existing methods by providing guarantees for a broad class of nonlinearities without assumptions on noise moments, with exponents that are constant and strictly better in certain cases. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary This paper looks at how to make sure online learning works well even when there’s heavy-tailed noise. Heavy-tailed noise means the noise is very unlikely to be extreme but can still cause problems. The authors create a new way to make SGD work with nonlinear methods, which are helpful for dealing with this kind of noise. They show that their method can help convergence happen faster and more reliably than other methods. This is important because it means we can use online learning even when the data is noisy. |
Keywords
» Artificial intelligence » Online learning » Probability » Quantization
