Cyclic and Randomized Stepsizes Invoke Heavier Tails in SGD than Constant Stepsize
Authors: Mert Gurbuzbalaban
Yuanhan Hu
Umut Simsekli
Lingjiong Zhu
Venue: Accepted by TMLR ()

Abstract: 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.

Published in Transactions on Machine Learning Research (08/2023)
Cyclic and Randomized Stepsizes Invoke Heavier Tails in SGD than Constant Stepsize
Mert Gürbiizallaaa
mg1366@rutgers.edl
Deportment of Management Science and Information Systems
Rutgers Business School, Piscataway, NJ, USA &
Center for Statistics and Machine Learning Princeton University, Princeton, NJ, USA.
Yuanhan Hu
yuanhan.hu@ruuteer..
Deportment of Management Science and Information Systems Rulgers Business School, Piscolaway, NJ, USA
Umut Şimşekli
wmw.ssimeekliiinri....
Inria, CNRS, Ecole Normale Supérieure PSL Research University, Paris, Fronce
Lingjiong Zhu
aluu@malth edu
Department of Mathematics Florida State University, Tallahassee, FI, USA.
Reviewed on OpenReview: https: // openreview. net/ forum? id= LNB5EHn8uC
Abstract
Cyclic and randomized stepsizes are widely used in the deep learning practice and can of- len outperform standard slepsize choices such as constant slepsize SGD. Despite their empirical success, not much currently known about when and why they can theoretically improve the generalization performance. We consider general class of Markovian stepsizes for learning, which contain ii.d. random stepsize, cyclic stepsize as well as the constant stepsize 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 gener- alization, 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 achieve even heavier tail and be viable alternative to cyclic and i..d. randomized stepsize rules.
1 Introduction
Stochastic optimization problems are ubiquitous in supervised learning. In particular, the learning problem in neural networks can be expressed as instance of the stochastic optimization problem
mingerd Es-Dif(x, 2)],
(1)
where x E 2d are the parametors, 2 E Z is the random data which is assumed to obey an unknown probability distribution D, and is the loss of misprediction with parameters x corresponding to data z. Since the population distribution D is unknown, in practice, we often approximately solve the empirical
version of [
mingeRd F(x):= : Σ i=1 f((z), where f((x) = f(z, 2))
(2)

---

Published in Transactions on Machine Learning Research (08/2023)
based on dataset (21, 22....,,.) 2n) E 2 which consists of independent identically distributed (i.i.d)) samples
from data. Stochastic gradient descent (SGD) methods are workhorse methods for solving such problems
due to their scalability properties and their favorable performance in practice [Bottou 2010 2012). SGD
with batch-size b consists of the updates
Ik+1 = Ikk - -1++1 ff (xx)
(3)
where Mh+11 is the stepsize and Vf(x)) == # (zxx is the stochastic gradient at k-th iterate with Ot being a set of data points with cardinality [S2x] = b (see Sec. 2 for details).
Understanding the generalization behavior of SGD, i.e. how solution found by SGD performs on unseen data has been a major question of research in the last decades (see e.g. Keskar & Socher (2017): Hardt et al. (0166); Lei & Ying [2020); Lin et al. (2016)). Recent empirical and theoretical studies have revealed an interesting phenomenon in this direction. Heavy tails in fact can arise in SGD iterates due to multiplicative noise and the amount of heavy tails (measured by the so-called "tail-index") )) is siguificantly correlated with the generalization performance in deep learning practice (Gürbizbalaban et all 2021 Hodgkinson & Mahoney 2021). This phenomenon is not specific to deep learning in the sense that it arises even in surprisingly simple settings such as linear regression (when the loss is a quadratic) with Gaussian input data. This raises the natural question of how the choice of the stepsize sequence {nk affects the tail-index and generalization properties which will be the main topic of study in this work.
The stepsize sequence }m can be chosen in various ways in deterministic or a randomized fashion. Constant stepsize as well as varying stepsizes are proposed in the literature (Robbins & Monro 1951 Kiefer & &Wolfowizz/ 1952 Smith 2017; Bottou et al. 2018). For constant stepsize and for (least squares) linear regression problems where the loss I is a quadratic, Gürbüzbalaban et al. (2021) showed that the tails are monotonic with respect to the stepsize and the batch-size and there exists a range of stepsizes for which there cxists stationary distribution with infinite variance. In a very recent work, Güürbüzbalaban et al.) (2022) showed that even heavier tails can arise in the decentralized stochastic gradient descent with constant stepsize and this correlates with generalization. However, other (non-constant) choices of the stepsize can often outperform constant stepsize. MMsso (2020) suggests that in the small learning rate regime, uniformly- distributed random learning rate yields better regularization without extra computational cost compared to constant stepsize. Also, cyclic stepsizes where the stepsize changes in cyclic fashion (obeying lower and upper bounds) have been numerically demonstrated to be very useful for some problems. Among this line of work, |Smthh (2017) argued that cyclic stepsizes require less tuning in deep learning and can lead to often better performance. Smith (2015) suggests that experiments with sinusoidal learning rates versus cyclic stepsize with equal grid points lead to similar results. Smith & Topin (2017) demonstrates that the cyclical learning rate can produce greater testing accuracy than traditional training despite using large learning rates for different network structures and datasets. Huang et al. (2017) argues that cyclic stepsize allows to train better models compared to constant stepsize. Kalousek (2177) studies a steepest descent method with random stepsizes and shows that it can achieve faster asymptotic rate than gradient descent without knowing the details of the Hessian information. /Zhang et al. (2020b) suggests cosine cyclical stepsize for Bayesian deep learning. Gulde et al. (2020) investigates cyclical learning rate and proposes method for defining a general cyclical learning rate for various deep reinforcement learning problems. They show that using cyclical learning rate achieves similar or even better results than highly tuned fixed learning rates. Wang et al. (2023) applies the cyclical learning rate to train transformer-baser neural networks for neural machine translation. They show that the choice of optimizers and the associated cyclical learning rate policy can have a significant impact on performance. Alyah et al. (2018) argues that with a cyclical learning rate, the neural networks will have better results with similar or even smaller number of epochs on unbalanced datasets without extra computational cost compared to constant stepsize. In addition, due to their popularity, cyclic stepsizes are also part of popular packages such as PyTorch!] [
Despite the empirical success of randomized stepsize and cyclical stepsize rules, to our knowledge, the effect of the stepsize scheduling (cyclic, randomized versus constant etc.) on the generalization performance is not well st udded from a theoretical slandpoint except numerical results that highlight the benefits of randomized
SSee e.g. the "CyelieL.R package' available the website http://wwwpppoooooo////////////p scheduler. wyw.lierr.yyIic.......
2

---

Published in Transactions on Machine Learning Research (08/2023)
and cyclic stepsize rules compared to constant stepsize choice. While studying the generalization itself as a function of the stepsize sequence appears to be a difficult problem; building on the literature which demonstrates that tail-index is correlated with generalization (see e.g. Şimşekli et al. (2020) Barsbey et al.
2021);; 5 Simsekli et al. 2019 Gürbüibalaban et al.] (2021)), ), we study tail-index as a proxy to generalization performance and demonstrate how the tail-index depends on the stepsize scheduling, highlighting the benefits of using cyclic and randomized stepsizes compared to constant stepsize in terms of the tail behavior.
Contributions. We propose general class of Markovian stepsizes for learning, where the stepsize sequence Tis evolves according to a finite-state Markov chain where transitions between the states happen with certain probability p E [0, 1]. This class recovers i.i.d. random stepsize, cyclic stepsize as well as the constant stepsize as special cases. For losses that have quadratic growth outside a compact set in dimension one, one can infer from the results of Mirek (2011) that SGD iterates with Markovian stepsizes will be heavy-tailed (see Thm. 15 and Thm. [] However, the assumptions involved are highly nontrivial to check and do not hold for dimension two or higher even for linear regression ?
Furthermore, these results do neither specify how the tail-index depends on quantities of interest such as the batch-size, dimension nor compare the tails with that of the constant stepsize. Hence, to get finer characterizations of the tail-index and further intuition about the tails, we focus on linear regression as a case study throughout this paper and obtain explicit characterizations that provides further insights as well as theoretical support for the use of cyclic and randomized stepsizes in deep learning practice. We find that even in the linear regression setting, there are significant technical challenges. Here, viewing SGD as an iterated random recursion, we make novel technical contributions in analyzing the iterated random recursions with cyelic and Markovian structure with finite state space. We borrow the idea of regeneration times from probability theory, and consider iterates at those regeneration times to utilize the hidden renewal structure of the underlying iterated random recursions (sce Sec. g for further details). As result, we are able to study and characterize the tail-index of the SGD iterates with cyclic stepsizes (Thm. 5). Markovian stepsizes (Thm. 2 as well as i..d. random stepsizes (Thm.
For cyclic, Markovian and i.i.d. stepsizes, under Gaussian data assumptions for lincar regression, we also give a sharp characterization of the tail-index and provide a formula for the range of stepsizes in which SGD iterates admit stationary distribution with an infinite variance (Lem. Prop. 7 Lem. [1] Prop. g
Lem. Prop. 0 in the Appendix). We provide non-asymptotic bounds moment bounds for SGD iterates and provide non-asymptotic convergence rates to the stationary distribution in the Wasserstein metric (Thm. 16
Thm. 21 Thm. 14 in the Appendix). These results are obtained by using various technical inequalities, synchronous coupling, and spherical symmetry of Gaussian distributions and are deferred to the Appendix duc to space considerations.
In Sec. 4 we compare the tail-indices among these stepsize rules theoretically for linear regression. We show that i.i.d. random stepsizes (where Th are i.i.d. with the same distribution as 17) centered around an expected value o and positive range R has heavier tail compared to constant stepsize with r (Prop. D as well cyelic stepsize centered around on uniform grid with the same range (Prop. 2). Our results show that coarser the grid for the stepsize or wider the stepsize range R, heavier the tails become in a sense that we will precise (Thm. 13 Thm. 19] Thm. 20).. We prove that reducing the batch-size or increasing the dimension also leads to heavier tails, provided that the tail-index is not too small (Thm. 7 Thm. 4 Thm. 12). These results are obtained by employing delicate analysis leveraging convexity and Jensen's inequality. When the transition probability p E (0. 1/2) and there are two states, we completely work out the distribution of the regeneration time and the sample path of the Markov chain till the regeneration time to show that Markovian stepsizes can achieve even heavier tail with respect to cyclic and i.i.d. stepsizes and the tail gets heavier if p gets smaller (Prop. 5). We also discuss in Appendix B.4 how our comparisons can be extended to general state spaces. Since smaller tail-indices are correlated with better generalization in deep learning practice, our results shed further light into why random and eyclic stepsizes could perform better than constant. stepsize in some deep learning settings. In Sec. 5 we illustrate our theory on linear regression experiments and show through deep learning experiments that our proposed Markovian stepsizes can be a viable alternative to other standard choices in the literature, leading to the best performance in some cases.
Inn Mirek 2011), is required that the Hesslans of the component functions f(x, have certain orthogonality properties which does not typically hold in linear regression or more generally in statistical learning.
3

---

Published in Transactions on Machine Learning Research (08/2023)
2 Technical Background and Literature Review
Hcavy-tailed power-law distributions. A real-valued random variable X is said to be heavy-tailed if the right tail or the left tail of the distribution decays slower than any exponential distribution. A real-valued random variable X is said to have heavy right tail if lim P(X 2 z)ee = 20 for any с >> O, and a real-valued random variable X is said to have heavy left tail if si P(X S -z)eekl = oc for any > O. Similarly, an R4-valued random vector X is said to have heavy tail if u X has heavy right tail for some vector E gd-1, where gd-1 == {u E Rd |||]| = 1} is the unit. sphere in R2, Heavy tail distributions include a-stable distributions, Pareto distribution, log-now normooaall distribution and Weilbull distribution. An important class of the hcavy-tailed distributions is the distributions with power-law decay, which is the focus of our paper. That is, P(X 2 x) ~ o0 as x - do for some oo > 0 and a > 0, where a is known as the tail-index, which determines the tail thickness of the distribution. Similarly, the random vector X is said to have power-law decay with tail-index a if for some u E S we have P(u" x 2 x) ~ co(u)æ for some constant (u) that may depend on the direction u and for some a > 0.
Tail-index in SGD with constant stepsize. It is possible to show that SGD iterates are heavy-tailed with polynomially-decayy.
tails admitting unique stationary distribution, when the loss is strongly convex outside a compact set (Hodgkinson & Mahoney 2021] or when the loss has linear growth for large x (Mirek 2011: Gürbiizallaaan et al. 2021] | (see Thm. g in the Appendix for details), however in these results verifying the assumptions behind are highly non-trivial; and the dependence of the tail-index to the parameters of SGD such as the stepsize is not explicilly given. This motivates the study of least square problems (when / is a quadratic) where more precise characterizations of the tail-index can be obtained (see e.g. (Gürbizballbaa Gürrbizbalaban ct al. 2022) It is also known that slow algorithms that can generalize well subject to heavier lails can be slower for optimization purposes. For example, heavier tails in the gradients and iterates can often result in slower convergence rates in the training process in different optimization settings Şimsşkli et al. (2019); Wang et al. (2021), where clipping the gradients and robust ver- sions of stochastic gradient descent have been proposed for achieving faster convergence Zhang et al.] (2020a): Gorbunov et al. (2022). Therefore, we believe understanding the heavy-tailed of the iterates can be ben- eficial for understanding both optimization and generalization performance of an algorithm, and least square problems serve as fundamental case where stronger results can be obtained due to their special structure.
ct al. 2021 Raj ct al. 2023a b
Consider the least squares problem minzeR 2 Al y/l², where A is an n x d matrix, with i.i.d. entries, y E RD and x E Rd. This problem can be written in the form of (2 as
F(x)
- T fx(x), where f(x)) =
a x. Ui)
T
2
(4)
where of is the i-th row of the data matrix A. Using the fact that Vf((x)) = a; (af x - W:). we can rewrite
SGD iterations 3 as
Fx+1 = (7)+1/b) H2+1) IE + 9
(5)
2....,u. bk) and [2g b. Here, for simplicity, throughout the paper, we assume that we are in the streaming regime (also called the one-pass setting (Frostig et al.) 2015 Jain et al.) 2017 Gao et al. 2022) where cach sample is used once and is not recycled. We also make the following assumptions on the data throughout the paper:
where Ha = Eiea, aza and 9k The Eien, Di with Ω = (b(k: - +)++11 11, +
(A1) as's are i.i.d. with a continuous density supported on Rd with all the moments being finite.
(A2) ye are i.i.d. with continuous density whose support is It with all the moments finite.
Assumptions (A1) and (A2) are satisfied in a large variety of cases, for instance when a; and y are Gaussian distributed. When the stepsize п) =) is constant, and H₃ are i.i.d., 2g converges to Foo, where Foe has a heavy tail distribution with a tail-index that can be characterized [Gürbüzbalas laban el al. (021).. However, to the best of our knowledge, cyclic stepsizes or Markovian stepsizes are not studied in the literature in terms of the tail behavior that they result in the SGD iterates which will be the subject of this work. We also note that decaying stepsize rules where 776- -> are also widely used and they can ensure convergence of the SGD iterates Sebbouh et al. 2021 Gower et al. 2019 However, in this case, the iterates often converge to limit point.
4

---

Published in Transactions on Machine Learning Research (08/2023)
almost surely and therefore the stationary distribution of the iterates will typically be degenerate Dirac mass where characterixing the tail-index of the iterates will no longer be meaningful at stationarity. There- fore, in our analysis, we will assume that the stepsize is bounded away from zero, often lying on finite grid.
3 Main Results
Stochastic Gradient Descent with Markovian Stepsizes. We consider Markovian stepsizes with finito state spaces. The discussions with general state spaces will be provided Section B.4. in the Appendix. Let us consider the finite state space
{m, 12, Tm: 1m = (e1, (2.............................. ................................ -1, CK. CK-1, )
(6)
where m = 2K - and (et, c2,... ..) the stepsize grid. We assume the stepsize goes from ?h1 to 1/2 with probability 1 and it goes from т₁ to 7K-1 with probability 1. In between, for any i= ........ K 1, K + ,,...; m. the stepsize goes from 7) to M7+1 with probability p and from 1J to 7/-1 with probability 1 1 p with the understanding that 1m++1 == ?/. Therefore, p reduces to the case of cyclic stepsizes. We assunne is not the same for every i; otherwise this setting reduces to the case of constant stepsizes.
We first observe that SGD is an iterated random recursion of the form
Fk (A(IA-1,1)))
where the map V : Rd x R + Rd, hides the dependence on 24 which are random and i.i.d. and Te are Markovian with the finite state space (G). To the best of our knowledge, there is no general stochastic linear recursion theory for Markovian coefficients, except for some special cases, e-g. with heavy-tailed coefficients [Hay et al., 2011). However, we will show that in the case of finite-state space, it is possible to use the idea of regencration times from probability theory to analyze the iterated random recursion. The key idea is to introduce the regeneration times rk, which are defined as ro 0 and for any k 2 1:
Tk = inf ( > Tk-1 flj 100
(8)
That is, Te are the random times that the stepsizes start at yo at A = 0. It is easy to see that {ru- rA- JAEN are ii.d. with the same distribution as Ty. By iterating we have
Tress w/2 (Tre)
(9)
where the superscript (r) refers to the random choice of stepsizes and also happens to be the first letter of "regeneration". Since Qg are i.i.d. over k, by the definition of the regeneration time, it follows that (((r) are i.i.d. over k. We denote that v((r has the common distribution as w(r)) If we assume that the random map v(() is Lipschitz on average, i.e. E[ < oo with (()) ;= supa.yeRd
with v ((2 (-) = Mresi (... D +2 +2 (Wr++1('s (rr (+ Tret
[1)())()) ((()()))(((()))
(w)) and is mean- contracvnr,,,,ve, i.c. if (log(L(r) [
then it can be shown under further technical assumptions that the distribution of the iterates converges to a unique stationary distribution To geometrically fast (Diaconis & Freedman 1999).
The following result can be obtained in dimension d = 1, which follows directly from Mirek (011) by adapting it to our setting (see also Buraczewski et al. (2016)). ). Mirek (201I) also considers higher dimensions; but for d > 1, the assumptions required are not satisfied for quadratic losses nor for least square problems.
Theorem 1 (Adaptation of Mirek 2011 ). Assume stationary solution to 12 erists, d = 1, and:
(1) There erists a random variable (r) and random variable Bb7) > 0 such that a.s. (x)))
M x| < B(r) for every x where || denotes the absolute value;
(i) The conditional law of log [r]r given M(r) #0 0 is non non-arithmmetic; i.e. its support is not equal to aZ for any scalar a where Z is the set of integers;
(ii) There erists a1 > such that 1BI = 1, " < co and ( " log* |M < 0o, where log" + (a:) = max(log(z))00
5

---

Published in Transactions on Machine Learning Research (08/2023)
Then, there erists some conslant Co
(r) O such that lime- 1a P( -))
For linear regression, vp()) is a composition of affine maps and stays affine (see our discussion in the proof of Thm. 2); therefore Thm. is applicable in dimension one, More generally, Thm. | can be applicable to the restricted class of smooth losses that can be non-convex on compact while having a quadratic structure outside the compact (so that the gradient is affine up to a constant), and says that. heavy tails arises in SGD in this setting but does not precise the tail-index (r)) and this result works only in dimension d = 1. This motivates the study of more structured losses in high dimensional settings where more insights can be obtained. When the objective is a quadratic, we will provide a more detailed analysis.
For Markovian stepsizes, observe that the SGD iterates are given by (5) where (Hx, 9k) is i..d sequence and 1/s is stationary Markov chain with finite state space independent of (H&, )R) Next, we will show that one can fully characterize the tail-index when the stepsizes follow a Markov chain with a finite state space using a renewal argument based on regeneration times. Let us introduce
E M M22 ........0 1/))) 1/K
h (s) = limg-+oc
(10)
where
M = (1- (1ra41/ / Hress) (1 (#re41 11) ( ... (1
and rh 's are regeneration times defined in We also define
M M
(r) k- M
and
( = lime-1o0 (2k)- log largest eigenvalue of (T T (T²*))
We have the following result that characterizes the tail-index for the SGD with Markovian stepsizes. Theorem 2. Consider the SGD iterations (5) with Markovian stepsizes in fonite-state space. If p(r) < O and there cxisls unique posilive (r) such that (((r) (a!))= = then (5) admils a unique stationary solution vh and the SGD ilerations with Markovian slepsizes converge to xo in distribution, where the distribution of xlx satisfies lim ta ( P(u" (r) ea(: for any E Sd-1, for some positive and continuous
function egtr) on gd-1.
Proof. We recall from (5 that the SGD iterates are given by 2k+1 = (I- Me+1 HK+1) I + qk+1, where (Hk, (k) is an i.id. sequence and 7Jk is a stationary Markov chain with finite state space independent of (HKy Ts Ke)E We recall from { the regeneration times Tk such that To = O and for any & 2 1: _k == inf li > Pk-1:1 = no). That is тa are the random times that the stepsizes start at To at k = 0. It is easy to see that (ra -TK-IJkN are i..d. with the same distribution as ri. It follows that Trasi M ( Fr + 1 where M and d are defined as:
k+1 = (I- (Tren bonesn/b/)t /6) (1-
... ..- (Tr Hb)
(r) Pkt1
-I- (Tei /b) (I (Arx /b) H)) 11-1)))) ... (I (1++1/b) H4;
4+1
Since T% regeneration times, one can casily check that (Mr(") 9% are i.i.d. in k. The rest of the proof follows from Theorem 4.4.15 in Buraczewski et al. (2016) which goes back to Theorem 1.1 in Alsmeyer &
Mentemeier (2022) and Theorem 6 in Kesten [1973). J. See also Goldic (1991): Buraczewski et al. 2015). The proof is complete.
Remark 1. It is possible to exlend some of our results given in Thm. 2 for linear regression to problems where the loss function is a conver quadratic up to an error term outside a compact set. Smoothed Lasso problems where the penalty term a smooth version of the &, penalty would be an ezample. In this more general case, while it is not possible to provide formala for the tail-inde ezactly, one can still provide lower and upper bounds the ind-i..ex. The details can be found in Appendia F.
6

---

Published in Transactions on Machine Learning Research (08/2023)
In general, there is no simple explicit formula for (s) to evaluate at), However, we easily obtain the following bound using the sub-maltiplicatiiig of the norm of matrix products:
h (s) - (s) : II | (w.b) = E II En 1 (n/bb)H11()
(11)
where Ey denotes the expectation taken over Hi which i..dd distributed as H, and which are independent of (me)keN, where rı is the regeneration time defined in D. We define the lower bound a(r) for the tail-index (r)) as the unique positive value such that h(r) (ā(r) 1, provided that p(r) := |E Eh [log | <. In the following, we show that the lower bound a(r) for the fail-index increasing in batch-size.
Theorem 3. g0) is strictly increasing in batch-size provided that a 2 1.
Our proof of Theorem is based on the fact that the function (s) is strictly decreasing in b for 8 2 1 which follows from Jensen's incquality and convexity of the function || I| for s 2 1. The function || 11 is not convex for < 1; this is the reason why the condition d(r) > is needed in Theorem 3 within our
analysis. Note also that the tail-index (+)) is the unique positive value such that h(r) (a(r) 1 provided
that p(r) < O. In general, there no simple closod-fore form expression for (s) that is defined in 10
However, when the input data a are Gaussian,
able to obtain more explicit expression for (s).
(A3) a2 ~ NO0, Ta) are Gaussian distributed for every i.
Under (A3), we can obtain more explicit expression (see Lem. 11 and Lem. 12 in the Appendix) to characterize the tail-index (t)) Under (A3), obtain the following result that shows the tail-index a()) is increasing in batch-size b and decreasing in dimension d.
Theorem 4. Assume (A3) holds and p(+) < 0. Then: (i) The lail-indez ( is striclly increasing in batch-size b provided that a!r) 2 1; (ūi) The tail-inder a1 is strictly decreasing in dimension d.
Stochastic Gradient Descent with Cyclic Stepsizes. As a special case of the Markovian stepsizes, we consider the stochastic gradient descent method with cyclic stepsizes. More specifically, we assume that 7 takes values on a grid (c1,c2..... c in a cyclic manner satisfying ( and the length of the cycle is m = 2K - 2. In other words Mmk4+ = 7h, i == 1,2,..., m, for any k = 0, 1,....... Note that we can view cyclic stepsizes as a special case of Markovian stepsizes with transition probability p=1
As special case of the Markovian stepsizes, the SGD (3) can be iterated and we can consider:
D(k+ 1) = 1 k+1 (Ikm);
(12)
where w/(r) := (( (-.. V 2m ( 4 kmm+1 (- 11m+1), 22mm-2)...... 7)++))m) are i.id. over k. This is basi- cally the map that corresponds to consecutive m iterations of SGD, which demonstrates an i.idd structure. We denote (m(m) as the common distribution of (()) where the superscript (m) highlights the dependence on the cycle length m. In this case, an analoguc of Thm. Caan be obtained in dimension one (see Thm. 15 in the Appendix); but as before in the rest of the discussion, we focus on the quadratic case to have finer results for the tail-index We recall the SGD iterates from (5), where we consider the stepsize 77 to be deterministic and cyclic with a cycle length Next, let us introduce
= limp-1oo [E [E| M(m) ... 11) 1/k
(13)
where
M( := :I (I- (1mm (0mmbb)F H)m) (I (mm-1/ H .)... (I- (n/ () H(
(-- 1)=1m)))
(14)
is the product of consecutive iteration matrices. We also define
(m)) = lim (2k)) log largest eigenvalue of (TT())) T (TTTT)) m(m)) = M mm()) M(m)

---

Published in Transactions on Machine Learning Research (08/2023)
We can iterate the SGD from 5 to obtain 2((+1)m M Mfn (m) 2km 96+11 where M (m) is defined in and (m) Σ E (I 1m (m)+))mm) (I- m14+1m-- H ((++)))m ((++))m-)) ... (I-- th4s H441) 9:- We have the following result that characterizes the tail-index.
Theorem 5. Consider the SGD iterations ( with cyclic stepsizes {mk where the length of the cycle is
m. If pl)) < 0 and there erists a unique positive (m) such that h/m) (a!m) =1, then ( admits a unique
stationary solution xxc.) and the SGD iterations with cyclic stepsizes converye to I (m)) the distribution of (mm satisfies lim to (m) P(u" ( > t) = E for any u gd-1, for some positive and continuous function Caim) gd-1.
(m) in distribution, where
Proof. This follows immediately from Theorem 2 by noting that Markovian stepsizes reduce to the cyclic stepsizes in the special case when p= 1.
Determining the exact value of the tail-index (m) for the stationary distribution anni seems to be a hard problem; nevertheless, we can characterize a lower bound for the tail-index to control how heavy tailed SGD iterates can be by following a similar approach our discussions for the Markovian stepsizes. We start by noticing that (s) = if and only if (b(m) 1/m 1. In general, there is no simple explicit formula for (s). However, we have the following bound due to the sub-multiplicativity of the norm of matrix products:
(s) 1/m S (s)
(M
Th 1/m
Let @(m) be the unique positive value such that (mm))) (a(m)) = provided that p(m) := Ei= EE -11--110 []] < 0. This provides lower bound for the tail-index (!"), Next, we show that the lower bound ((m) for tail-index is increasing in batch-size. We next state analogues of Thm. and 4 in the cyclic stepsize setting, the proofs are similar, with the only difference that regeneration times (the time it takes to revisit a particular stepsize) are random for Markovian stepsizes, whereas they are deterministic for cyclic stepsizes. The proofs are given in the appendix for the sake completeness.
Thm.
Theorem 6. (m)) is striclly increasing in batch-size b provided that a(m) 2 1.
Under (A3), we can get a more explicit formula for h(m) and pmm) (see Lem. 9 Lem. 10 in the Appendix) and hence can obtain further properties of the tail-index (m)) Under (A3), obtain the monotonic dependence of the tail-index (m)) on the batch-size b and the dimension d.
Theorem 7. Assume (A3) holds and pl O. Then: (1) The tail-indez (m) is strictly increasing in
batch-size b provided (m) 2 1. (ii) The tail-inder mm) is strictly decreasing in dimension d.
4 Comparisons of Tail-Indices
In this section, we compare the tail-indices of SGD with constant, i.i.d., cyclic and Markovian stepsizes. The i..d. stepsizes can be considered as a special case of the Markovian stepsizes and in Sec. B.2 in the Appendix, we study the SGD with i.idd. stepsizes in detail. Under Assumption (A3), we compare the tail-index a of the SGD with i.i.d. stepsizes (where 7ik = = has the same distribution for every k) with the SGD with constant stepsize (where stepsize is fixed at E[n]).
Proposition 1. Assume (A3) holds and < 0. Then the tail-inder a with iid. stepsize is strictly less than the tail-inder ar with constant stepsize E[n] provided a 2 1.
In Prop. I we showed that the tail-index a is strictly less than the tail-index a, with constant stepsize E/n]. Under (A3), we can also compare the tail-index (m) of the SGD with cyclic stepsizes and the tail-index a of the SGD with i.i.d. uniformly distributed stepsizes such that P(n = 1/.) = 1, for any Isis m. Then, we have the following result which says i.i.d. stepsizes have heavier tail.
Proposition 2. Assume (A8) holds. The inil-index a for the SGD with ii.d stepsizes such that P(n = 17)) = m for any S < m is smaller than the tail-inder (m) for SGD with cyclic stepsizes.
8

---

Published in Transactions on Machine Learning Research (08/2023)
Next, compare the the tail-index (T)) with cyclic stepsizes and the tail-index ae with constant stepsize I Ei 1/-- When the batch-size is not too large relative to the dimension (i.e. when d 2 b + 3), we can show that cyclic stepsizes lead to heavier tails under (A3). The proof is based on exploiting log- oog-ooivy properties of the (-) function when the batch-size in this regime.
Proposition 3. Assume (A3) holds and d 2 b+3. 3. Then the toil-indez (m)) with cyclic slepsizes is striclly smaller than the
ae with constant stepsize +. mm provided that 's are sufficiently small.
In general, for SGD with Markovian stepsizes, the regeneration time is hard to analyze. Next, we consider the simplest example of a Markov chain, i.e., a homogeneous Markov chain with two-state space {n, nu such that P(n = n/.1% = 7) = p and Pm( = ?h 1/0 = 9aa) = p- This Markow chain exhibits a unique stationary distribution P(no = ne) = Pn = 7/) = 2- We notice that the special case = 1 reduces to the cyclic stepsizes. Indeed, we have the following monotonicity result of the tail-index depending on the parameter p.
Proposition 4. Consider the two-state Markoe chain, iee. P(n = Th Mo = m) = and P(n = ml = nh)) and assume that E E,, where
= { pE [0,1] 10 (1- p)) max EH [I(
T H
G1
EH
||
Tu H ei
<
<1
(15)
Then, the toil-inder (r) is increasing in p E P. In particular, (r) S (m))
Prop. 4 shows that Markovian stepsizes lead to heavier tails than cyclic stepsizes. In Prop. 2 we showed that SGD with i.i.d. stepsizes lead to heavier tail than the SGD with cyclic stepsizes, which has heavier tail than the SGD with constant stepsizes (Prop. B. The next result states that Markovian stepsizes may lead to heavier tails than i.i.d. stepsizes depending on whether p is greater or less than 2.
Proposition 5. Under the setting of Propositions 9 and 4 we have a < a()) < a a for any 2 and we have (r) < a < al)) < Or for any p 2. where Oce, a, alm), a(r)) denote the lail-inder for SGD with constant, d.i.d, cyclic and Markovian stepsizes respectively.
1 < p < 1
5 Numerical Experiments
In this section, we present the numerical experiments including the tail-index estimation of linear regression using uniform stepsize and Markovian stepsize and the performance of uniform, Markovian, cyclic and constant stepsize deep learning settings.
Linear regression (least squares). In the following experiments, we investigate the relationship between the tail-index and the stepsize choice. We consider the following model: w N (0, @2) x, ~ N o?.). and yi ww, x2 N (zT w, og), where w, xj E Rd, yı E E for i I,.... n, and a, 02 By > 0. In the experiments, we set d = 100, take a o = 1, 3, and generate {æ,, V by simulating the statistical model. To estimate the stationary measure, we iterate SGD for 1000 iterations and repeat this for 10000 runs. At each run, we take the average of the last 500 SGD iterates; in the Appendix (Cor. 1 and we argue that the average follows an a-stable distribution under some assumptions. This enables us to use advanced estimators (Mohammadi et al., 2015) specific to a-stable distributions. For constant stepsize schedules, we set the stepsize to be constant n during the training process. For i.i.d. uniformly distributed stepsize, cyclic stepsize, and Markovian stepsize, the interval of stepsize is set as [n - R R).
To compare different stepsize (learning rate) schedules, we calculate the tail-index for the linear regression experiment in Fig. [[a] In this experiment, set batch-size 10 for all stepsize schedules, R 0.05 and K = 10 for uniform, cyclic, and Markovian stepsize schedules. For Markovian stepsize, we sct p 0.6. We can conclude from the figure that the tail-index of all these slepsize schedules will decrease when the mean of stepsize i increases, meanwhile the tail-index of SGD with i.i.d. uniformly distributed stepsize is smaller than the tail-index of cyclic stepsize schedule, which validate our Prop. 2 We can also obscrve that the tail-index of Markovian stepsize is smaller than the cyclic stepsize schedule, which is predicted by our Prop. 5
9

---

Published in Transactions on Machine Learning Research (08/2023)
2.0
2.0
p-0.8
1.3
p
irdex
1.6
inex
1.6
p (cyclic F)
1.4
1.4
1.2
Comalant
1.2
1.0
Cyclc
Markovann =.b.b
0.24
0.16
0.18
0.20
0.24
0.16
0.18
0.20
0.22
Mean of lestnnn rete
Meen of learning rate
(a) Different stepsize schodules
(b) Markovian with parameter
Figure 1: Center of the stepsize interval (f) vs. tail-index for linear regression. (Left panel) Comparison of constant, uniform, cyclic and Markovian stepsizes with p p= 0.6 with batch-size = 10, and the stepsize grid parameters R = 0.05 and 10. (Right panel) Comparison of Markovian stepsizes with different transition probabilities p when the mean of the learning rate f is varied, with batch-size b 10, 0.05.
2.0
2.0
R=
A=
1.6
0.03
188
R 0.03
1.8
A 0.033
0.04
Irdex
1.6
0.05
R 0.05
1.6
A 0.05
1.4
1.4
1.2
1.2
1.2
1.0
0.14
0.16
0:18
0.20
0.22
0.24
0.19
0.18
0.20
0.22
0.14
9.16
0.18
0.20
0.22
Mean of learning rate
Meon of learning rate
Mean of learning rate
(a) i..d. stepsize
(b) Cyclic stepsize
(c) Markovian stepsize
Figure 2: Tail-index corresponding to different range values (R) as a function of the mean stepsize f for linear regression, for i.idd random stepsizes (left panel), for cyclic stepsize (middle panel) and for Markovian stepsizes with p = 0.6 (right panel). We fix K 10 and vary from to 0.05.
In the next sets of experiments, we will investigate the influence of different values of parameters on the tail-index for different stepsize schedules. In the first experiment, we test different transition probability p for Markovian stepsize. The result shown Fig. [(b] where the values of p is varied from 0.6 to 1 where we batch-size 10, R 0.05. When p = 1, the Markovian stepsize schedule will degencrate stepsize. We observe that with smaller p value, the tail-index of Markovian stepsize will become smaller. test different range R values for i.i.d. uniformly distributed, cyclic and Markovian stepsize schedules where set the batch-size b = 10 and 0.6 for Markovian stepsize. To vary R = (K 1)6/2, we keep K = 10 as constant and vary from 0 to 0.05. As shown in Fig. 2 the tail-index of all schedules will decrease when the range R increases. These results validate our Thm. 19 and Thm. 13 in the Appendix. Finally, in Fig. 3 we test different batch-size values from 5 to 15 where we set range 0.05 and for Markovian slepsize p = 0.6. We observe that the tail-index of every stepsize schedule is strictly increasing in batch-size, which consistent with our theory (Thm. and Thm. 12 the Appendix).
cyclic
This result validates Prop. 4 In another experiment,
Deep Learning. In our second set of experiments, investigate the performance of uniform stepsize, Markovian stepsize, cyclic stepsize, and constant stepsize beyond the lincar regression setting. Here we consider the 3-layer fully connected network with the cross entropy loss on the MNIST datasel. We train the models using SGD with batch-size = 20. Similar to the linear regression setting, we test different stepsizes centered at i where we vary 7 while keeping the range of stepsize fixed with R 0.05 and cyelic and Markovian stepsize schodules. We display the results of the deep learning experiment in Table Following the literature (Chen et al. 2018), we measure generalization in terms of the difference between the
100 for
10

---

Published in Transactions on Machine Learning Research (08/2023)
2.0
2.0
2.0
1.8
1.8
neex
1.6
batch
1.6
batch 15 batch
1.6
batch 15
betch
1.4
batch 10
Tal
batch
=
Tall
batch =
1.2
1.0
1.0
0.14
0.16
0.18
0.20
0.22
0.24
0.16
0.18
0.20
0.22
0.14
0.16
0.18
0.20
0.27
Mean of leerning rate it
Meen of learning rate
Mean of learning rate
(a) Uniform stepsize
(b) Cyclic stepsize
(c) Markovian stepsize
Figure 3: Tail-index of batch-size value for linear regression for uniform stepsize (left panel), cyclic stepsize (middle panel) and Markovian stepsize with = 0.6 (right pancl). We test different batch-size values E (5, 10, 15} with range parameter = 0.05 and K = 10.
training and test loss; the smaller difference is the better generalization. As an alternative but correlated metric, we also consider the difference between test and training accuracy for quantifying the generalization performance. For different center stepsize f). we can observe that uniform, cyclic, and Markovian stepsize schedules lead to a smaller tail-index compared to the constant stepsize. While the tail-index and heavy tail are well correlatod according to existing theorctical and numerical results (Şimşekli al. 2020: Barsbey let al.] 2021; Raj al. 2023a b Gürbüzbalaban et al. 2021], the relationship is not perfect straight line. For example, generalization power in the sense of smaller error difference and accuracy difference. But for all the other cases where Í 0.08, 0.09, Markovian stepsize schedule with = 0.5 has both the smallest tail-index and best, generalization performance.
see that for 0.06 case, the smallest tail-index does not lead to the better
As a larger-scale deep learning experiment, we next consider the VGG-11 architecture that has 8 convolutional layers and fully-connected layers and we use the CIFAR10 dataset. For the stepsize grid parameters, we use R= 0.03 and K 100 and take batchsize b = 25. We use SGD for training and compare different. stepsize schedules in Table for different choices of the mean stepsize f) similarly to the previous experiment. We observe that i.idd stepsize has the heaviest tails (with the lowest tail index) in all cases, and the constant stepsize has the lightest tails (with the highest tail index) whereas the cyelic and Markovian stepsizes are in between except when f = 0.12. As a general trend, these results are roughly inline with our results given in Prop. that compares the tails of different stepsizes schedules under some assumptions. In Figure 2 we also see that the heaviest tails led to the best generalization in terms of accuracy, except for the n 0.11 case. It would be interesting to investigate how the tails are related to generalization and optimization performance further as part of future work.
To summarize, our results suggest that good performance associated to cyclic, randomized and Markovian stepsize can be due to the incurrence of heavier tails compared to constant stepsize in the deep learning settings. While deep learning sctting is significantly more complicated than the lincar regression sctting we considered in our theoretical results, our results ofler theoretical support into why alternative stepsizes (randomized, cyclic) can be successful and offers new Markovian stepsize rules that can perform better in some cases.
6 Conclusion
In this work, we proposed Markovian stepsizes which recovers uniformly random, cyelic and constant stepsizes as special cases. We developed proof techniques where we show that uniformly random, cyclic and Markovian stepsizes can lead heavier tails in the distribution of SGD itcrates. Since smaller tail-indices are correlated with better generalization in deep learning practice, our results shed further light into why random and cyclic stepsizes perform better than constant stepsize in deep learning. We also showed that proposed
11

---

Published in Transactions on Machine Learning Research (08/2023)
Schedule
Train Err
Test Err
Error diff
Train Acc
Test Acc
Ace diff
Tail-index
Constant
3.81E-07
0.0055
5.54E-03
100%
98.39%
1.61%
1.95
Uniform
1.70E-07
0.0067
6.69IE-03
100%
98.38%
1.62%
1.93
Cyclic
0.06
3.27E-07
0.0065
6.50EB-03
100%
98.33%
1.67%
1.98
Markovian p=0.6
2.97E-07
0.0062
6. 1616-03
100%
98.36%
1.64%
1.90
Markovian p=0.5
2.79E-07
0.0068
6.84E-03
100%
98.34%
1.66%
1.90
Constant
0.00194
0.0332
3. 13E-02
99.55%
97.64%
1.91%
1.95
Uniform
0.00221
0.0346
3.24E--2
99.59%
97.63%
1.96%
1.94
Cyclic
0.08
0.01490
0.0346
1.97E-02
94.99%
93.17%
1.82%
1.78
Markovian p=0.6
0.00055
0.0198
1.93E-02
99.76%
97.80%
1.96%
1.89
Markovian p=0.5
2.10E-07 00
0.0071
7.14E-03
100%
98.35%
1.65%
1.69
Constant
0.00154
0.0366
3.50EE02
99.61%
97.71%
1.90%
1.85
Uniform
0.00208
0.0283
2.62F-02
99.49%
97.48%
2.01%
1.77
Cyclic
0.09
0.00294
0.0316
E-87E-02
99.18%
97.22%
1.96%
1.62
Markovian p=0.6
0.00433
0.0266
2. 2.22E-02
99.04%
97.05%
1.99%
1.69
Markovian 0.5
0.00168
0.0217
2.00E-02
99.38%
97.52%
1.86%
1.51
Table 1: 3-layer fully connected network on the MNIST dataset. We vary the mcan of the stepsize f) and
compare the stepsize schedules, where in the third to nineth columus we report the training error, lest error, difference between the test and training errors, training accuracy, test accuracy, difference between the test and training accuracy and the tail-index respectively.
Schedule
Train Err
Test Err
Error diff
Train Acc
Test Acc
Acc diff
Tail-index
Constant
3.49E-08
0.012
1.18E-02
85.15%
14.85%
1.83
Uniform
3.38E-08
0.011
1.15E-02
85.19%
14.81%
1.80
0.10
Cyclic
3.81E-08
0.011
1.14E-02
84.69%
15.31%
1.82
Markovian p=0.7
2.81E-08
0.012
1.18E-02
1
85.05%
14.95%
1.83
Constant
5.59E-08
0.011
1.14E-02
85.21%
14.79%
1.84
Uniform
3.391-08
0.012
1.20F-02
84.77%
15.23%
1.79
0.11
Cyclic
2.74F-08
0.012
1.17F-02
84.91%
15.09%
1.82
Markovian p=0.7
3.24E-08
0.012
1.16E-02
85.13%
14.87%
1.79
Constant
3.99F-08
0.012
1.18F-02
85.33%
14.67%
1.80
Uniform
6.85E-08
0.012
1.21E-02
85.41%
14.59%
1.76
Cyclic 0.12
4.25E-08
0.012
1.16E-02
85.15%
14.85%
1.80
Markovian p=0.7
3.02E-08
0.013
1.29E-02
84.57%
15.43%
1.81
Table 2: VGG11 network on the CIFAR10 dataset. We vary the mean of the stepsize f and compare the stepsize schedules, where in the third to nineth columns report the training error, test error, difference between the test and training errors, training accuracy, test accuracy, difference between the test and training accuracy and the tail-index respectively.
12

---

Published in Transactions on Machine Learning Research (08/2023)
Markovian stepsizes can be viable alternative to other standard choices in the literature, leading to the best performance in some cases.
Acknowledgments
Mert Gürbüzbalaban and Yuanhan Hu acknowledge Rutgers Business School for creating a supportive re- search atmosphere, most of this work was completed when Yuanhan Hu was Ph.D. student at the Rutgers Business School. Mert Gürbizzalabaa and Yuanhan Hu's research supported in part by the grants Of- fice of Naval Research Award Number N00014-21-1-2244, National Science Foundation (NSF) CCF-1814888, NSF DMS-2053485. Umut Çimşekli's research is supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' d'avenir" " program, reference ANR- 19- P----0000001 (PRAIRIE 3IA Institute) and the European Research Council Starting Grant DYNASTY 101039676. Lingjiong Zhu grateful to the partial support from Simons Foundation Collaboration Grant and the grant NSF DDSS-205445 from the National Science Foundation.
References
Gerold Alsmeyer and Scbastian Mentemeier. Tail behaviour of stationary solutions of random difference equations: the case of regular matrices. Journal of Difference Equations and Applications, 18(8):1305 1332, 2012.
Basel Alyafi, Fakrul Islam Tushar, and Zafar Toshpulatov. Cyclical learning rates for training neural networks with unbalanced data sets. Jmd in medical image analysis and opplicationspatteen. recognition module, 2018.
Melih Barsbey, Milad Sefidgaran, Murat Erdogdu, Gacl Richard, and Umut Simsokli. Heavy tails in SGD and compressibility of overparametrized neural networks. In Advances in Neural Information Processing Systems, volume 34, pp.
2021.
Heiko Bauke. Parameter estimation for lower-law distributions by maximum likelihood methods. The European Physical Journal B, 58(2):167-173, 2007.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMP- STAT'2010: 19th International Conference on Computational Statistics, Paris France, August 22-27, 2010 Keymole, Invited and Contribuled Papers, pp. 177-186. Springer, 2010.
Léon Bottou. Stochastic gradient descent tricks. Tn Neural Networks: Tricks of the Trade: Second Edition, pp. 421 436. Springer, 2012.
Léon Botton, Frank E Curtis, and Jorge Nocodal. Optimization methods for largo-scale machine learning. SIAM Review, 60(2):223 311, 2018.
Dariusz Buraczewski, Ewa Damck, Yves Guivarc'h, and Scbastian Mentemeier. On multidimensional Man- delbrot cascades. Journal of Difference Equalions and Applicalions, 20(11):1523 1567, 2014.
Dariusz Buraczewski, Ewa Damek, and Tomasz Przebinda. On the rate of convergence in the Kesten renewal theorem. Electronic Journal of Probaiblity, 20(22):1 35, 2015.
Dariusz Buraczewski, Exwa Damek, and Thomas Mikosch. Stochastic Models with Power-Taw Tails. Springer, 2016.
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence tradc-off of iterative optimization algorithms. arXiv preprint ar Xiv: 1804. 01619, 2018.
Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-law distributions in empirical data. SIAM Review, 51(4):661-703, 2009.
Persi Diaconis and David Freedman. Iterated random functions. SIAM Review, 41(1):45 76, 1999.
13

---

Published in Transactions on Machine Learning Research (08/2023)
Roy Frostig, Rong Ge, Sham M Kakade, and Aaron Sidford. Competing with the empirical risk minimizer in single pass. In Conference on Learning Theory, pp. 728-763, 2015.
Xueleng Gao, Mert Gürbizballban, and Lingjiong Zhu. Global convergence of stochastic gradient Hamil- tonian Monte Carlo for nonconvex stochastic optimization: Nonasymptotic performance bounds and momentum-basoe accelcration. Operations Research, 70(5):2931-220) 2022.
Charles M Goldie. Implicit renewal theory and tails of solutions of random equations. Annals of Applied Probability, 1(1):126-166, 1991.
Michel L Goldstein, Steven A Morris, and Gary G Yen. Problems with fitting to the power-law distribution. The European Physical Journal B- Condensed Malter and Compler Systems, 41(2):255 258, 2004.
Eduard Gorbunov, Marina Danilova, David Dobre, Pavel Dvurechenskii, Alexander Gasnikov, and Gauthier Gidel. Clipped stochastic methods for variational inequalities with heavy-tailed noise. In Advances in Newral Information Processing Systems, volume 35, pp. 31319-31332, 2022.
Robert Mansel Gower, Nicolas Loizon, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In International Conference on Machine Learning, pp. 5200- 5209. PMLR, 2019.
Ralf Gulde, Marc Tuscher, Akos Csiszar, Oliver Riedel, and Alexander Verl. Deep reinforcement learning using cyclical learning rates. In 2020 Third International Conference on Artificial Intelligence for Industries (AI4I), pp. 32-35. IEEE, 2020.
Mert Gürbiizaalaban, Umut Şimsckli, and Lingjiong Zhu. The heavy-tail phenomenon in SGD. In Interna- lional Conference on Machine Learning, 2021.
Mert Gürbüzbalaban, Yuanhan Hu, Umut Şimşekli, Kun Yuan, and Lingjiong Zhu. Heavy-tail phenomenon in decentralized SGD. XrXiv preprinl Xix:2205.00688) 2022.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1233 PMLR, 2016.
Hamed Haselimashhadi. A unified class of penalties with the capability of producing differentiable al- ternative to & norm penalty. Communications in Statistics Theory and Methods, 48 48(22):5530-5544 2019.
Diana Hay, Reza Rastegar, and Alexander Roitershtein. Multivariate linear recursions with Markov- dependent coefficients. Journal of Multivoriate Analysis, 102(3):521 527, 2011.
Liam Hodgkinson and Michael W Mahoney. Multiplicative noise and heavy tails in stochastic optimization. In International Conference on Machine Learning, 2021.
Gao Huang, Yixuan Li, Geoff Pleiss, Zhuang Liu, John E. Hopcroft, and Kilian Q, Weinberger. Snapshot ensembles: Train 1, get M for free. In International Conference on Learning Representations, 2017.
Pratock Jain, Sham M Kakade, Rahul Kidambi, Pranecth Netrapalli, and Aaron Sidford. Accelerating stochastic gradient descent. Proc. STAT, volume 1050, pp. 26, 2017.
Zdenčk Kalousck. Steepest descent method with random step lengths. Foundations of Computational Math- emalics, 17:359 422, 2017.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from Adam to SGD. arXiv preprint arXio:1712.00622 2017.
Harry Kesten. Random difference equations and renewal theory for products of random matrices. Acta Mathematica, 131:207-246 1973.
Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maxinum of a regression function. The
Annals of Mathematical Stalistics, 23(3):662-46) 1952.
14

---

Published in Transactions on Machine Learning Research (08/2023)
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pp. 980995819. PMM.R 2020.
Junhong Lin, Raffaello Camoriano, and Lorenzo Rosasco. Generalization properties and implicit regulariza- tion for multiple passes SGM. In International Conference Machine Learning, pp. 2340- 2348. PMLR, 2016.
Mariusz Mirek. Heavy tail phenomenon and convergence stable laws for iterated Lipschitz maps. Probo- bility Theory and Related Fields, 151(3-4):705-734, 2011.
Mohammad Mohammadi, Adel Mohammadpour, and Hiroaki Ogata. On estimating the tail index and the spectral measure of multivariate a-stable distributions. Metrika, 78(5):549 561, 2015.
Daniele Musso. Stochastic gradient descent with random learning rate. arXiv preprint orXiv:2003.06998 2020.
Anant Raj, Melih Barsbey, Mert Gürbüzbalaban, Lingjiong Zhu, and Umut Şimgekli. Algorithmic stability heavy-tailed stochastic gradient descent on least squares. In International Conference on Algorithmic Learning Theory, 2023a.
Anant Raj, Lingjiong Zhu, Mert Gürbützbalaban, and Umut Şimgekli. Algorithmii stability of heavy-tailed SGD with general loss functions. In International Conference on Machine Learning, 2023b.
Herbert Robbins and Sutton Monro. A stochastic approxination method. The Annals of Malhemalical Statistics, 22(3):400-400 407, 1951.
Othmane Sebbouh, Robert M Gower, and Aaron Defazio. Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. In Conference on Learning Theory, pp. 3935-3971. PMLR, 2021.
Umut Şimşekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. In Advances in Neural Information Processing Systems, volume 33, pp. 5138-5155 5151, 2020.
Umut Şimşekli, Mert Gürrbüzbalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On the heavy- tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint arXiv:1912.00015 2019.
Leslie N. Smith. No more pesky learning rate guessing games. arXin:1506.011 11350000118880 2015.
Leslie N. Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 464 472, 2017.
Leslie N Smith and Nicholay Topin. Exploring loss function topology with cyelical learning rates. arXiv preprint Xix: 04283, 2017.
Cédric Villani. Optimal Transport: Old and New. Springer, Berlin, 2009.
Hongjaan Wang, Mert Gurbuzbalaban, Lingjiong Zhu, Umut Simsekli, and Murat A Erdogdu. Convergence rates of stochastic gradient descent under infinite noise variance. In Advances in Neural Information Processing Systems, volume 34, pp. 18866-18877, 2021.
Weixuan Wang, Choon Meng Lee, Jianfeng Lin, Talha Colakoglu, and Wei Peng. An empirical study of cyclical learning rate on neural machine translation. Natural Language Engineering, 29(2):316 336, 2023.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A thcoretical justification for adaptivity. In International Conference on Learning Representations, 2020a.
Ruqi Zhang, Chunyuan Li, Jianyi Zhang, Changyou Chen, and Andrew Gordon Wilson. Cyclical stochasitc gradient MCMC for Bayesian deep learning. In International Conference on Learning Representations, 2020b.
15


Reviews:
[{"review_id": "FMzS77AjEG", "reviewer": "Reviewer_oJUY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is easy to follow. The studied problem is important and interesting. However, I have following concerns:\n\n1. The theoretical analysis is based on linear regression, which is quite special. Is it possible to generalize the analysis to the general strongly-convex loss functions?\n\n2. Assumption (A3) requires the data comes from zero-mean Gaussian distribution, which in my opinion is a bit strong.\n\n3. SGD usually uses a decreasing stepsize to ensure convergence, e.g., [1,2]. However, this paper does not compare the Markovian stepsizes with the commonly used decreasing stepsizes.\n\n4. In the experimental part, I think the authors should perform experiments on convolutional neural networks such as the VGG networks rather than the simple 3-layer fully connect networks.\n\n[1] Sebbouh, Othmane, Robert M. Gower, and Aaron Defazio. \"Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball.\" Conference on Learning Theory. PMLR, 2021.\n[2] Gower, Robert Mansel, et al. \"SGD: General analysis and improved rates.\" International conference on machine learning. PMLR, 2019.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers a general class of Markovian stepseizes in SGD. The authors study the tail-index of the SGD isterates for linear regression and compare the tail-indices among cyclic, Markovian and i.i.d. stepsizes. The authors also compare these stepsizes in both linear regression experiments and deep learning experiments.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors should address all concerns mentioned in the previous part. In addition, the writing can be polished. Some formulas appear more than once in the paper. For example, the updating formula (10) and (16) are the same except the assumption on the H_k and q_k. The authors may reorganize the paper and avoid redundant formulas.\n\nMinor:\nWhat does \"MC\" in table 1 stand for?", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kVpDiYJIy3", "reviewer": "Reviewer_Ft9k", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, my impression is that this paper makes some valid technical contributions related to a machine learning problem of interest to the community, but the clarity and presentation is lacking in several respects. I will try my best to elaborate on the points which are lacking in a constructive but concise fashion below, using some concrete examples from the text.\n\nTaking a macroscopic view of section 3, any reader will notice that sections 3.1 and 3.2 are extremely similar, following a clear template with the only real difference being that the fixed cycle length $m$ in 3.1 is replaced with the stochastic \"regeneration times\" $r\\_{k}$ in 3.2. Quite honestly, this could all be captured in one section, significantly reducing the redundant material, allowing more space for remarks on the technical differences between the two settings (if any). In my opinion, a re-working of this section is critical.\n\nTaking a more microscopic look at the technical material, I find the notation to be extremely bloated with non-essential complexity. Here are a couple obvious examples.\n\n- The superscripts $(\\\\cdot)^{(m)}$ and $(\\\\cdot)^{(r)}$ severely reduce readability and increase cognitive load, yet have no explicit impact on the results presented in the main paper. At the very least, I know that the value of $m$ should impact the tail index, but if this impact is only made precise in the appendix, there is absolutely no need to explicitly tack on $m$ to all quantities of interest. Same goes for $r$ (whatever $r$ means; see another comment later on).\n\n- A huge amount of notational complexity is also due to the random batching mechanism $\\\\Omega\\_{k}$. As far as I can tell, this mechanism is essentially meaningless to the analysis, since constant batch $b$ and just one pass is made using iid data. All the notational messiness related to the $\\\\Omega\\_{k}$ guys is equivalent to saying \"step sizes are $(\\\\eta\\_{1}/b, \\\\eta\\_{2}/b,\\\\ldots)$ for some constant $b > 0$\". The latter is far simpler, leads to more readable notation, and the link to mini-batching can be easily established with a short remark.\n\nIn addition to bloated notation, there is a fair bit of material that is just plain and simply unclear. Here are some examples.\n\n- Thm 1 is riddled with mystery. What is a \"non-arithmetic\" distribution? What is the difference bounded above by $B^{(m)}$? It looks to be a difference between vectors, but the notation $\\\\lvert \\\\cdot \\\\rvert$ is used; what norm is this? What is $\\\\lvert M^{(m)}\\\\rvert$? Determinant? Going beyond these points, is Thm 1 really all that valuable here? I know the authors are trying to constrast the abstract assumptions of Thm 1 with those made in their analysis, but in its present form, I think it does more harm than good.\n\n- There is a bit of a gap in the tail index notions presented in this paper. In section 2 definitions, tail index $\\\\alpha$ for random vectors is defined using a *constant* $c\\_{0}$ free of $u$, but in the main results, the factor depends on $u$ through the mysterious continuous function $e\\_{\\\\alpha}(\\\\cdot)$.\n\n- In lower bounding the tail index (paragraph before Thm 3), is $h^{(m)}(\\cdot)$ monotonic over the positive reals? Or is this why $\\\\widehat{\\\\alpha}^{(m)} \\\\geq 1$ is needed in Thm 3? I think the analysis here could be a lot more transparent. In the present form, readers are left wondering \"what's so special about the threshold 1?\"\n\n- What is $r$? The authors just say the differences $r\\_{k}-r\\_{k-1}$ have the same distribution as $r\\_{1}$ for all $k$; so is $r$ the common distribution of the differences? If so this is a very poor choice of notation. Furthermore, if $r$ is a random variable (unlike constant $m$ earlier), then one naturally thinks results like Thm 5 should be probabilistic, since for example $e\\_{\\\\alpha^{(r)}}(u)$ would be random if $\\\\alpha^{(r)}$ is random. I assume this is not the case, with all randomness due to the step sizes being captured in the event $\\\\{u^{T}x\\_{\\\\infty}^{(r)} > t\\\\}$, and $r$ is just used here symbolically to differentiate between the setting in 3.1, but this is all quite unclear.\n\nI could go on with similar examples, but I'll get on to one last macroscopic point.\n\nThe *title* says \"Cyclic and Randomized Stepsizes Invoke Heavier Tails in SGD\" and any reader will take this to naturally be a \"main finding\" of this paper. Here, one naturally wants to ask \"heavier than what?\". For example, Prop 2 says that cyclic step sizes yield a larger tail index, i.e., *lighter* tails. I assume that in choosing this title, the authors have Prop 1 in mind (by the way, what is $\\\\rho$ with no superscript?). At this point, I found myself running into the question: \"wait, heavier tails are *better*?\" There is a now-massive literature on robust stochastic gradient descent, and it is provable that heavy-tailed gradients (typically leading to heavy-tailed iterates) left as-is can never enjoy the strong guarantees that their sub-Gaussian counterparts can (thus justifying clipping and normalization and momentum and such to control the distribution and obtain nice high-probability convergence guarantees). I think a non-trivial fraction of readers of this journal will hear \"heavy tails\" and assume \"worse generalization performance\". I know generalization is not discussed directly here (for good reason, I think), but there seems to be a subtext that heavier tails are in general better for learning, which I think is bound to lead to confusion.\n\nMinor points:\n\n- p.1: \"instantaneous\" loss, not familiar with this term. Intention is \"per-instance\" sort of notion?\n- p.4: \"This motivates the study of least square problems ... practical insights to deep learning.\" I feel like this is probably overstated. While I haven't read the cited papers, if linear least squares is a running assumption, links to most interesting (non-linear) deep learning models vanish at that point. In my opinion, all talk of deep learning should be relegated to the relevant empirical experiments; this paper deals with linear least squares, generalizing recent results on the limiting iterate distribution tail index from constant step sizes to more general step size strategies, nothing more, nothing less.\n- p.4: loss function notation is $f\\_{i}(x)$ here, doesn't match $f(x,z\\_{i})$ given on p.1.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Put roughly, the focus of this paper is the following question: \"how do properties of stochastic gradient-based learning algorithms impact the distribution of the resulting iterates?\" The context for this question is a rather substantial literature over the past few years which draws connections between better generalization and iterates with \"lighter tails\".\n\nOf the \"properties\" of learning algorithms just mentioned, the particular focus of this paper is on step size strategies, allowed to be stochastic, albeit independent of the data. The main contributions here are theoretical in nature. They consider stochastic gradient descent applied under the quadratic loss, which of course is very convenient for tying together properties of the iterates and gradients. Their main results are essentially composed of two elements: (1) sufficient conditions for the iterates to have a \"nice\" limiting distribution with tails that are easy to pin down (Thms 2 and 5), and (2) quantitive relationships (via tail index) between different step size strategies, dimensionalities, and batch size settings (all the other Props/Thms besides Thm 1). The key characteristic of this paper is that a rather wide family of step-size strategies are captured (constant, cyclic, uniform, Markov, etc.). The data is assumed to be light-tailed in that all moments are finite, and their strongest results assume Gaussian data.\n\nThere are also apparently many additional results in the appendix related to analogous non-asymptotic guarantees, but I have not looked over these, sorry.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the comments above; I think there are some valid results here, but the presentation as-is is in my opinion quite sub-par. At the very least, section three needs some serious re-writing to illustrate only the essential differences between current sections 3.1 and 3.2, while eliminating redundancy and unclear, bloated notation.\n", "broader_impact_concerns": "No additional concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "R2SmqjR39t", "reviewer": "Reviewer_BHTt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The study of using cyclic, random, and even Markovian step sizes and their effect in learning is, as far as I know, novel and interesting. The industrial side has been using different step size designs for a long time. This study could be a good theoretical understanding of why these tricks are useful.\n\n2. The authors have provided a thorough and detailed analysis of the tail-indices. Although I don't have the time to check the proofs, the theoretical results look promising and are supported by the experimental results.\n\n3. The literature review and the introduction is more than complete and interesting.\n\nWeaknesses:\n1. The theoretical study focuses on purely linear regression and not deep learning models.\n\n2. The paper is a little hard to read because of the heavy notation burden.\n\n3. Some of the assumptions seem to be too strong to be true, especially for deep learning models.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the tail effect of using cyclic, random, and constant step-sizes in the learning process of running SGD on the linear regression problem. The authors have shown that using these special (cyclic, random, etc) step-sizes can actually lead to heavier tails in the distribution of SGD iterates, compared with using constant step-sizes, which is related to better generalization performance. Most of the work is theoretical, but the authors also provide experimental evidence to support their claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The current theoretical analysis focuses on purely linear regression, which is not bad, but I still wonder what the true barrier is if we want to migrate the analysis to neural networks. After many years of development in Neural Tangent Kernel theory, I think the analysis of neural networks should be similar to that of linear regression, especially if we add the assumption that the network can be infinitely wide. See, e.g., https://arxiv.org/abs/1909.12292. Could the authors at least provide some insights on what the true barriers are if we try to conduct a similar analysis in deep learning?\n\n2. The whole section 3 is a little hard to read and takes me a lot of time to understand the notations and proofs. It seems to be an unnecessary burden since the theorems and Section 4 convey the most important information. I would really suggest polishing this section to make it easier for the readers.\n\n3. In Section 4, I wonder what the relationship is between the tail-index of cyclic step-sizes and constant step-sizes. It seems that the comparison is missing. Please correct me if I'm wrong.\n\n4. In the experiments, the authors have only chosen linear regression and 3-layer MLP as the baseline model. I would suggest adding one more deep neural network experiments, e.g., ResNet50, Transformers.\n\n5. The captions of all the figures are highly un-informative and I would suggest adding more related info of the figures to these captions. For example, the experiment setting (linear regression or deep learning), parameter settings, what each line represents and so on.", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers' opinion on this paper was split, with a majority voting for accept. 

A main concern of the reviewers was that the setting (linear regression) and some assumptions (Gaussian data) may be too restrictive to draw conclusions for Deep Learning practice from the results of this paper. In the rebuttal phase, the authors added experimental results to shed more light on this gap, and presented slightly generalized theorem statements. Overall, this paper makes some progress in deepening our understanding of (non-constant) Markovian step sizes in SGD and these results may be of interest to the TMLR community.

Minor revision: please upload a CR version without color annotations.
Decision: Accept (poster)