Algorithmic stability of heavy-tailed stochastic gradient descent on least squares

Anant Raj; Melih Barsbey; Mert Gürbüzbalaban; Lingjiong Zhu; Umut Şimşekli

Publications · Conference paper · ALT 2023

Algorithmic stability of heavy-tailed stochastic gradient descent on least squares

Anant Raj, Melih Barsbey, Mert Gürbüzbalaban, Lingjiong Zhu, Umut Şimşekli

Algorithmic Learning Theory (ALT), pp. 1292–1342, 2023.

Publisher page arXiv:2206.01274

In brief

On least-squares problems SGD’s iterates can become heavy-tailed, and here everything is explicit enough to compute how that affects algorithmic stability. The paper derives stability bounds as a function of the tail index of the iterates and, since stability governs generalization, links the tail behavior of SGD directly to how well it generalizes.

Topics

Heavy tails in SGD

Cite

@inproceedings{raj2023leastsquares,
  title   = {Algorithmic stability of heavy-tailed stochastic gradient descent on least squares},
  author  = {Anant Raj and Melih Barsbey and Mert Gürbüzbalaban and Lingjiong Zhu and Umut Şimşekli},
  year    = {2023},
  booktitle = {Algorithmic Learning Theory (ALT)},
  pages   = {1292--1342},
  url     = {https://proceedings.mlr.press/v201/raj23a.html},
  note    = {arXiv:2206.01274},
}

Relatedsame topics

Algorithmic stability of stochastic gradient descent with momentum under heavy-tailed noise (arXiv, 2025)
Heavy-tail phenomenon in decentralized SGD (IISE Trans., 2025)
Rényi differential privacy for heavy-tailed SDEs via fractional Poincaré inequalities (arXiv, 2025)
Differential privacy of noisy (S)GD under heavy-tailed perturbations (arXiv, 2024)
Algorithmic stability of heavy-tailed SGD with general loss functions (ICML, 2023)

← All publications · Research program · Mert Gürbüzbalaban