Cyclic and Randomized Stepsizes Invoke Heavier Tails in SGD than Constant Stepsize
This work addresses the theoretical gap in understanding why non-constant stepsizes often outperform constant ones in deep learning, offering insights for practitioners optimizing SGD schedules.
The paper investigates how cyclic and randomized stepsizes in SGD affect the tail behavior of iterates, showing that these schedules can produce heavier tails than constant stepsize, which is linked to improved generalization performance. It provides theoretical results on tail-index variation and validates them with linear regression and deep learning experiments.
Cyclic and randomized stepsizes are widely used in the deep learning practice and can often outperform standard stepsize choices such as constant stepsize in SGD. Despite their empirical success, not much is currently known about when and why they can theoretically improve the generalization performance. We consider a general class of Markovian stepsizes for learning, which contain i.i.d. random stepsize, cyclic stepsize as well as the constant stepsize as special cases, and motivated by the literature which shows that heaviness of the tails (measured by the so-called "tail-index") in the SGD iterates is correlated with generalization, we study tail-index and provide a number of theoretical results that demonstrate how the tail-index varies on the stepsize scheduling. Our results bring a new understanding of the benefits of cyclic and randomized stepsizes compared to constant stepsize in terms of the tail behavior. We illustrate our theory on linear regression experiments and show through deep learning experiments that Markovian stepsizes can achieve even a heavier tail and be a viable alternative to cyclic and i.i.d. randomized stepsize rules.