Summary of Large Deviations and Improved Mean-squared Error Rates Of Nonlinear Sgd: Heavy-tailed Noise and Power Of Symmetry, by Aleksandar Armacki et al.
Large Deviations and Improved Mean-squared Error Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry
by Aleksandar Armacki, Shuhua Yu, Dragana Bajovic, Dusan Jakovetic, Soummya Kar
First submitted to arxiv on: 21 Oct 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Optimization and Control (math.OC); Probability (math.PR)
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 The paper presents a general framework for nonlinear stochastic gradient methods in the online setting, focusing on large deviations and mean-squared error (MSE) guarantees. The proposed approach treats the nonlinearity as a black box, allowing for unified guarantees across a broad class of bounded nonlinearities, including sign, quantization, normalization, and clipping. The authors provide strong results for various step-sizes in the presence of heavy-tailed noise with symmetric probability density function, positive in a neighbourhood of zero and potentially unbounded moments. Specifically, they establish large deviation upper bounds for non-convex costs, showing an asymptotic tail decay on an exponential scale, as well as optimal MSE rates for both non-convex and strongly convex costs. Finally, the authors demonstrate almost sure convergence of the minimum norm-squared of gradients. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper explores a new approach to nonlinear stochastic gradient methods in online learning, aiming to provide guarantees for large deviations and mean-squared error (MSE). The key innovation is treating the nonlinearity as a black box, enabling unified results across various types. This framework handles heavy-tailed noise with symmetric probability density function, positive near zero, and potentially unbounded moments. The authors show how this approach leads to improved guarantees for non-convex costs and provides optimal MSE rates. |
Keywords
» Artificial intelligence » Mse » Online learning » Probability » Quantization
