Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees Article Swipe

MAKE IMPACT

Aleksandar Armacki , Shuhua Yu , Pranay Sharma , Gauri Joshi , Dragana Bajović , Dušan Jakovetić , Soummya Kar · YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2410.13954

We study high-probability convergence in online learning, in the presence of heavy-tailed noise. To combat the heavy tails, a general framework of nonlinear SGD methods is considered, subsuming several popular nonlinearities like sign, quantization, component-wise and joint clipping. In our work the nonlinearity is treated in a black-box manner, allowing us to establish unified guarantees for a broad range of nonlinear methods. For symmetric noise and non-convex costs we establish convergence of gradient norm-squared, at a rate $\widetilde{\mathcal{O}}(t^{-1/4})$, while for the last iterate of strongly convex costs we establish convergence to the population optima, at a rate $\mathcal{O}(t^{-ζ})$, where $ζ\in (0,1)$ depends on noise and problem parameters. Further, if the noise is a (biased) mixture of symmetric and non-symmetric components, we show convergence to a neighbourhood of stationarity, whose size depends on the mixture coefficient, nonlinearity and noise. Compared to state-of-the-art, who only consider clipping and require unbiased noise with bounded $p$-th moments, $p \in (1,2]$, we provide guarantees for a broad class of nonlinearities, without any assumptions on noise moments. While the rate exponents in state-of-the-art depend on noise moments and vanish as $p \rightarrow 1$, our exponents are constant and strictly better whenever $p < 6/5$ for non-convex and $p < 8/7$ for strongly convex costs. Experiments validate our theory, showing that clipping is not always the optimal nonlinearity, further underlining the value of a general framework.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2410.13954

PDF

https://arxiv.org/pdf/2410.13954

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4403995417

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4403995417

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2410.13954

Digital Object Identifier

Title

Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2024

Year of publication

Publication date

2024-10-17

Full publication date if available

Authors

Aleksandar Armacki, Shuhua Yu, Pranay Sharma, Gauri Joshi, Dragana Bajović, Dušan Jakovetić, Soummya Kar

List of authors in order

Landing page

https://arxiv.org/abs/2410.13954

Publisher landing page

PDF URL

https://arxiv.org/pdf/2410.13954

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2410.13954

Direct OA link when available

Concepts

Nonlinear system, Stochastic gradient descent, Noise (video), Gradient descent, Computer science, Applied mathematics, Descent (aeronautics), Statistical physics, Mathematical optimization, Mathematics, Physics, Artificial intelligence, Artificial neural network, Meteorology, Image (mathematics), Quantum mechanics

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload