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

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

Journal article, 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},
}