  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.
