Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance Article Swipe

MAKE IMPACT

Hongjian Wang , Mert Gürbüzbalaban , Lingjiong Zhu , Umut Şimşekli , Murat A. Erdogdu · YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2102.10346

Recent studies have provided both empirical and theoretical evidence illustrating that heavy tails can emerge in stochastic gradient descent (SGD) in various scenarios. Such heavy tails potentially result in iterates with diverging variance, which hinders the use of conventional convergence analysis techniques that rely on the existence of the second-order moments. In this paper, we provide convergence guarantees for SGD under a state-dependent and heavy-tailed noise with a potentially infinite variance, for a class of strongly convex objectives. In the case where the $p$-th moment of the noise exists for some $p\in [1,2)$, we first identify a condition on the Hessian, coined '$p$-positive (semi-)definiteness', that leads to an interesting interpolation between positive semi-definite matrices ($p=2$) and diagonally dominant matrices with non-negative diagonal entries ($p=1$). Under this condition, we then provide a convergence rate for the distance to the global optimum in $L^p$. Furthermore, we provide a generalized central limit theorem, which shows that the properly scaled Polyak-Ruppert averaging converges weakly to a multivariate $α$-stable random vector. Our results indicate that even under heavy-tailed noise with infinite variance, SGD can converge to the global optimum without necessitating any modification neither to the loss function or to the algorithm itself, as typically required in robust statistics. We demonstrate the implications of our results to applications such as linear regression and generalized linear models subject to heavy-tailed data.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2102.10346

PDF

https://arxiv.org/pdf/2102.10346

OA Status

green

Cited By

10

References

40

Related Works

10

OpenAlex ID

https://openalex.org/W3132170983

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W3132170983

Canonical identifier for this work in OpenAlex

DOI

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

Digital Object Identifier

Title

Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2021

Year of publication

Publication date

2021-02-20

Full publication date if available

Authors

Hongjian Wang, Mert Gürbüzbalaban, Lingjiong Zhu, Umut Şimşekli, Murat A. Erdogdu

List of authors in order

Landing page

https://arxiv.org/abs/2102.10346

Publisher landing page

PDF URL

https://arxiv.org/pdf/2102.10346

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/2102.10346

Direct OA link when available

Concepts

Hessian matrix, Mathematics, Applied mathematics, Stochastic gradient descent, Rate of convergence, Diagonal, Iterated function, Convergence (economics), Convex function, Noise (video), Regular polygon, Mathematical analysis, Computer science, Computer network, Image (mathematics), Economic growth, Machine learning, Artificial neural network, Channel (broadcasting), Geometry, Economics, Artificial intelligence

Top concepts (fields/topics) attached by OpenAlex

Cited by

10

Total citation count in OpenAlex

Citations by year (recent)

2024: 3, 2023: 2, 2022: 2, 2021: 3

Per-year citation counts (last 5 years)

References (count)

40

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload