Cyclic and randomized stepsizes invoke heavier tails in SGD than constant stepsize

Mert Gürbüzbalaban; Yuanhan Hu; Umut Şimşekli; Lingjiong Zhu

Publications · Journal article · Trans. Mach. Learn. Res. 2023

Cyclic and randomized stepsizes invoke heavier tails in SGD than constant stepsize

Mert Gürbüzbalaban, Yuanhan Hu, Umut Şimşekli, Lingjiong Zhu

Transactions on Machine Learning Research, 2023.

arXiv:2302.05516 Code OpenReview

In brief

A constant step-size already makes SGD’s iterates heavy-tailed; this paper shows that cyclic and randomized step-size schedules make them heavier still, with an explicit characterization of the tail index on quadratic problems. The schedule itself, not only the step-size-to-batch-size ratio, therefore shapes the tail behavior — and hence the solutions SGD tends to find.

Topics

Heavy tails in SGD

Cite

@article{gurbuzbalaban2023cyclic,
  title   = {Cyclic and randomized stepsizes invoke heavier tails in SGD than constant stepsize},
  author  = {Mert Gürbüzbalaban and Yuanhan Hu and Umut Şimşekli and Lingjiong Zhu},
  year    = {2023},
  journal = {Transactions on Machine Learning Research},
  note    = {arXiv:2302.05516},
}

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