Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance

Abstract

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 $\alpha$-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.

References in corpus (11)

• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• Multiplicative noise and heavy tails in stochastic optimization
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• Features modeling with an $\alpha$-stable distribution: Application to pattern recognition based on continuous belief functions
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• Asymptotic Optimality in Stochastic Optimization
• From low probability to high confidence in stochastic convex optimization
• Optimal Mean Estimation without a Variance
• Fractional moment-preserving initialization schemes for training deep neural networks

Cited by in corpus (4)

• Catoni-style confidence sequences for heavy-tailed mean estimation
• Global Convergence and Stability of Stochastic Gradient Descent
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails
• Accelerated Stochastic Gradient Method with Applications to Consensus Problem in Markov-Varying Networks