Analysing heavy-tail properties of stochastic gradient descent by means of stochastic recurrence equations

Abstract In recent works on the theory of machine learning, it has been observed that heavy tail properties of stochastic gradient descent (SGD) can be studied in the probabilistic framework of stochastic recursions. In particular, Gürbüzbalaban et al. (2021) considered a setup corresponding to linear regression for which iterations of SGD can be modelled by a multivariate affine stochastic recursion Xₙ=AₙX₍-₁+Bₙ for independent and identically distributed pairs (Aₙ, Bₙ), where Aₙ is a random symmetric matrix and Bₙ is a random vector. However, their approach is not completely correct and, in the present paper, the problem is put into the right framework by applying the theory of irreducible-proximal matrices.