Asymptotic theory of SGD with a general learning-rate
Authors: Or Goldreich
Ziyang Wei
Soham Bonnerjee
Jiaqi Li
Wei Biao Wu
Venue: NeurIPS 2025 poster ()
Keywords: Learning Rate Schedules
Convergence Analysis
Stochastic Gradient Descent
Online Learning
Primary area: theory

Abstract: Stochastic gradient descent (SGD) with polynomially decaying step‐sizes has long underpinned theoretical analyses, yielding a broad spectrum of statistically attractive guarantees. Yet in practice, such schedules find rare use due to their prohibitively slow convergence, revealing a persistent gap between theory and empirical performance. In this paper, we introduce a unified framework that quantifies the uncertainty of online SGD under arbitrary learning‐rate choices. In particular, we provide the first comprehensive convergence characterizations for two widely used but theoretically under-examined schemes—cyclical learning rates and linear decay to zero. Our results not only explain the observed behavior of these schedules but also facilitate principled tools for statistical inference and algorithm design. All theoretical findings are corroborated by extensive simulations across diverse settings.

Asymptotic theory of SGD with a general learning-rate
Or Goldreich Department of Statisties University of Chicago Chicago, II. 60637
Ziyang Wei Department of Statistics University of Chicago Chicago, IL 60637 ziyangweuchicago. edu
orgoodrreichhuuciiaggo edu
Soham Bonnerjee
Jiaqi Li Department Statistics University of Chicago Chicago, IL 60637 jqli@uchicago.eem edu
Wei Biao Wu Department of Statistics University of Chicago Chicago, IL 60637 wbwu@chicago.. edu
Department of Statistics
University of Chicago Chicago, IL 60637
scharbbnnnerjjeebuhhaaag...oe edu
Abstract
Stochastic gradient descent (SGD) with polynomially decaying step-sizes has long underpinned theoretical analyses, yielding broad spectrum of statistically attractive guarantees. Yet in practice, such schedules find rare use due to their prohibitively slow convergence, revealing persistent gap between theory and empirical performance. In this paper. we introduce a unified framework that quantifies the uncertainty of online SGD under arbitrary learning-rate choices. particular, we provide the first comprehensive convergence characterizations for two widely used but theoretically under-examined rates and linear decay to zero. Our results not only explain the observed behavior these schedules but also facilitate principled tools for statistical inference and algorithm design. All theoretical findings corroborated by extensive simulations across diverse settings.
cechemes-cyllicc learning
Introduction
Stochastic Gradient Descent (SGD) has gained popularity in modern machine learning since the seminal work of Robbins and Monro [1951]. While its theoretical foundations are well established, the literature has largely focused on two standard step-size choices: constant step-sizes, which provide exponentially fast convergence to biased stationary distribution and allow straightforward tuning, and polynomially decaying step-sizes, typically of the form f) X t which offer statistical guarantees such as consistency and asymptotic normality [Chung, 1954, Sacks, 1958, Fabian, 1968, Ruppert, 1988, Polyak and Juditsky, 1992] and extend to many SGD variants [Poljak, 1964, Gadat and Panloup. 2023, Li et al., 2024b]. However, polynomially decaying schedules converge slowly in practice. while constant step-sizes require careful calibration to avoid divergence [Bengio. 2012]. Hybrid schemes combining these approaches have gained traction in deep learning [He et al., 2016, Smith and Topin, 2019], though learning rates are often chosen empirically or via hyper-pan parameee tuning over standard schedules [Wu et al., 2018]. This practical reliance leaves notable gap in theoretical understanding of general step-size effects on SGD. The critical role of learning rates in stochastic approximation convergence has long been recognized [Spall, 2003, Nemirovski et al., 2008], underscoring the need for unified theoretical framework encompassing a broader range of step-size strategies.
Recent applications have introduced variety of learning rate schedules that, despite their empirical success, lack comprehensive theoretical support. For instance, Smith [] proposes several cyclical
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

learning rate schemes that perform well in practice across standard neural network architectures. Another under-theorized category is that of smite-horizon schedules, where the learning rate depends explicitly the total number of iterations. In high-dimensional linear regression, for example, Agrawalla et al. [2023] recommends a schedule of the form Mttn & logn Among such schedules, the linearly decaying to zero (Linear-D22) learning rate has seen widespread use in training large-scale architectures. Detailed discussion the relevant literature though by no means exhaustive is included in Section 1.3. Despite its prevalence, the non-asymptotic behavior of Linear- D22 and related soiteehorizoon step-size policies remains poorly understood from theoretical standpoint. In this work, we aim to bridge this theoretical gap by (i) developing a unified framework to show the non-asymptotic moment convergence, and (ii explicitly characterizing the non-asymptotic behavior of the wide class of cyclical learning rates as well as Linear DD2Z.
1.1 SGD preliminaries
Before summarizing the main contributions of this article, we briefly introduce the stochastic gradient descent (SGD) problem and establish a consistent notational framework for the analysis. Consider the problem of minimizing function : RRd + R, F E C², given by:
0
arg min F(O),
OER
and the corresponding SGD algorithm:
0. 02 7/ ( -
1o E Bd
(1.1)
where Th are step-sizes at t-th step, and E1, E are i...d samples from some unknown distribution Pe such that Eg-P,,V f0.-11, {t] (F) for all 0 IRd, With this formulation in place, now proceed to outlining the main contributions of this work.
1.2 Main contributions
This article presents unified framework for deriving the non-asymptotic mean-squared error for arbitrary learning rate schedules. Our results not only encompass the known theory for polynomially decaying learning rates as specific case, but also extend the asymptotic analysis other commonly used learning rates that previously lacked theoretical support. Our main contributions are summarized below.
(1) In our Theorem 2.1, we prove general bound on the mean error the SGD iterates, E[J0, - [P] involving the step sizes {n }. In particular, under certain regularity conditions, we prove the following.
Theorem 1.1 (Theorem 2.1, informal). Sa, = Ej=stt Oi for I. 8, then it holds that
E| - 00P) exp(seepsss,,,.1 - 0-p Σ n exp(-c j=1
This result enables straightforward application to a wide range of learning rate schedules n) provided that the second term, Σラ 11 exp(-c,,),m),, can be effectively controlled. For example, such bounds are typically tractable for many "approximately" polynomially decaying learning rates. Moreover, the result explicitly captures the influence of the initial point on the final error of the SGD iterates.
(2) A key aspect of Theorem 2.1 is that the step sizes π are allowed to depend on the total iteration learning rate schedules. Such schedules have rarely
count n, thereby accommodating been studied in the context of mean-squared error. We specifically examine the widely used linearly decaying schedule πソ- = r7(1 1 t/n) representative case. In Theorem 2.2, we leverage Theorem 2.1 to characterize the non con-asymptotic moment convergence of SGD iterates under this step-size rule. Although this schedule is common in practice, Theorem 2.2 provides, the best of our knowledge, its first explicit, rigorous analysis in the online SGD setting. Furthermore, our approach can be readily extended to broad class of finite-horizon schedules.
(3) When the learning rate is constant (7)- = 1)) or cyclical (1) = ')t mod T), Theorem 2. yields only an (1) bound, which offers only limited insight. While it is well established that, in the constant

---

case, the SGD iterates converge to stationary distribution, there is, to the best of our knowledge, no existing asymptotic theory for the cyclical learning rate setting. In Theorem 2.4, we address this gap by presenting novel convergence result for SGD iterates under cyclical learning rate schedules.
Theorem 1.2 (Theorem 2.4, informal), For a cyclical learning rate = (mh....,,7) if not all of the Ti 's are too big, then there exists "cyclostationary" process such that
O, m
n. as
where 25 denotes the convergence distribution.
This result highlights a fundamental behavioral difference between SGD with cyclical learning rates and with constant learning rates. While the latter typically converges to a stationary distribution, resembling the behavior of Markov chain, the former converges to distinct type of -tatstationary distribution exhibiting periodic patterns over time- formally known as cyclostationary distribution. To aid the reader's understanding, we also include brief but formal discussion of cyclostationary processes.
(4) Our theoretical results substantiated by extensive numerical exercises. Section 3.2 focuses on linearly decaying schedules, which empirically demonstrate both fast early convergence and low final error, consistent with Theorem 2.2, and justifying their practical appeal. On the other hand, Section 3.3 examines cosine schedules, where the learning rate follows a smooth periodic pattern; the resulting error exhibits eyclical behavior, particularly in the variance of its estimate, also complimenting Theorem 2.4. Some additional numerical exercises can be found in Appendix C. Specifically, Appendix C.6 collects five different learning schedules, and provides comparative study that highlights both their behavior in the "transient" (i.e. with respect to initialization) phase, as well as their asymptotic behavior.
1.3 Related works
There exists substantial, though primarily empirical, body of literature examining gradient descent and batched SGD in the context of neural networks. For instance, Wu et al. [2019] investigates a vari- ety of step-size schedules, including exponentially decaying and time-inverted schemes. Among the many proposed strategies, our focus is on two broad and widely used classes: cyclical schedules and linearly decaying schedules. Since the introduction of the "triangular" learning rate by Smith [2017], periodic learning rate schemes-and their decaying variants such as cosine annealing-have become influential in training deep architectures like convolutional neural networks (CNNs) [Loshchilov and Hutter, 2017, Smith, 2023, Wang et al., 2023]. The periodic structure of these schedules allows for intermittent large steps (which encourage exploration) followed by smaller steps (which promote convergence), behavior associated with so-called "super-conver conper-convergence" as observed in both empirical and theoretical work Smith and Topin [2019], Oymak [2021].
In parallel, annealing- based strategies have also played a prominent role in optimization [Huang et al., 2017, Li et al., 2019, Nakkiran, 2020], with certain variants sacch as geometrically decaying step-sizes proven to be minimax optimal convex settings [Ge et al., 2019]. Within this context, the linearly decaying zero (Linear-D22) schedule has gained significant traction in applications involving highly non-smooth or complex optimization landscapes, including state-space models [Touvron al., 2023], large language models [Devlin et al., 2019, Liu al., 2019, Bergsma et al., 2025], and vision transformers [Wu et al., 2024]. Notably, several works advocate for a "knee schedule" [Howard and Ruder, 2018, Hoffmann et al., 2022, Iyer al., 2023, Defazio al., 2023, Hägele et al., 2024, Bergsma et al., 2025], which begins with large learning rate (a "warm start") followed by Linear-D2Z phase. Despite their widespread adoption, the asymptotic behavior of both cyclical and Linear DDZ step-size schedules remains theoretically unexplored even in relatively simple convex settings. This lack of theoretical understanding presents significant barrier to rigorous statistical inference and uncertainty quantification, underscoring the need for systematic analysis.
1.4 Notations
In this paper, denote the set f1....,n) n by [n]. The d-dimensional Euclidean space is IR For vector æd, |a| denotes its Euclidean norm. For a random vector X I2 and > 0,
3

---

denote | = ? and || - (B(1 We also denote in in-probability convergence,
and stochastic boundedness by op and Op respectively. We write an S bn if an S Cb2 n for some constant C > 0, and = bn if Cibn, I an < C2bn for some constants C12 C2 0. Often we denote On bn by an = O(b.). Additionally, if an/bn O, we write On = o (ba))
2 Non-asymptotic moment convergence of SGD iterates with general step-sizes
This section is devoted establishing the p-th moment convergence of SGD iterates (1.1) for any p 2 2 with a general choice of learning rate. In particular, we allow for finite-horizon schedules; in the notation of Section 1.1, we allow 1)t T),,-- We note that this represents significant improvement the existing body of literature that analyzes the statistical properties of SGD and its variants under different learning rate schedules. Before we discuss our main result, is imperative introduce the crucial technical assumptions behind our result.
2.1 Technical assumptions
We assume the following regularity assumptions. Assumption 2.1. The function F p-strongly convex, i.e. for μ > 0 and for all x, Rd, it holds that
FVF(z) x u|r y/
The strong-convexity assumption 2.1 can further be relaxed into the strong concordance assumption as follows:
Assumption 2.2 (Local strong concordance). There exists p O such that 22F(0") ž s'Is- Moreover, there exists constani C O, and compact set + C Rdd, such that for all 0,, 02 4 holds that
(w)) s C| 0g] p (u), where & : u F (01 + (02 01)) R.
We remark that adoption of Assumption of 2.2 instead of Assumption 2.1 does not significantly alter any of our arguments; see Gu and Chen [2024] for details. For simplicity, we stick with Assumption 2.1.
Assumption 2.3. For the noisy gradients f((,) and some 2 2, there exists constant Lp > 0
such that
( V f(y, 2| < Lfl= vl', for all x, E Rd.
In particular, for some constant Mp 0, it holds that
(0", MP M, < 00.
Assumption 2.3 entails that F is Ly-smooth by Hölder's inequality; in other words, for all x, y Rd. it holds that
FF(z)-FF())) S Lp|x-
Assumptions 2.1 and 2.3 are standard features of statistical analysis of convex stochastic optimization, and have appeared extensively in Ruppert [1 [1988], Polyak and Juditsky [1992], Bottou et al. [2018] 8), Chen et al. [2020], Zhu al. [2023], Wei al. [2023], al. [2024a]. With these standard regularity assumptions, we can introduce our general result.
2.2 A general moment convergence of SGD iterates
In this section, we introduce main contribution umbrella result that furnishes ready-made upper-bound of the SGD iterates (1.1) for any choice of learning rates. In particular, we have the following result.
Theorem 2.1 (LP Convergence). Suppose that Assumptions 2.1 and 2.3 hold for some p 2 2. Let Co 0 be some constant such that for all 1, co < min { 11 2p (6p -5)L3n }. For the
learning rate schedule satisfies
2μ
0< 1)
(2.1)
(6p 5)

---

we have for any 2 1,
10,, - 10, S
5exp exp {
00 Σ Tk 100 2-2 +3p 3(p 1)M3
Σ j=1
15 exp {
- c0
Σ Æ=
mk m.j- (2.2)
Theorem 2.1 is proved in appendix Section A.I. The bound (2.2) highlights the two key terms that the learning rates contribute in the moment bound. In particular, there is an inherent trade-off between the potential choices of step-sizes V that goes into determining the order of the p-th moment. We discuss this property in detail in the subsequent two remarks.
Remark 2.1 (Effect of initialization). Firstly, the exp term in (2.2) highlights that in order to neglect the effect of initialization, one must have Σn_ 7] - oG as n - oo; in other words, the step-sizes cannot be too small. For example, Wu et al. [2019] discusses exponentially decaying step-sizes Th = r². whose performance heavily depends on the initial point even for large n, indicating that the
effect of initialization cannot be ignored in this case.
Remark 2.2 (Effect exploration). The second term Σ}-1 "1 exp { co Exnz+1
J+1 7k encodes the exploration property of the SGD iterates 0g. Intuitively, if 7n - 0 as co, then this second term also o11) Therefore, this term essentially ensures that fy has to be decaying, and not all of them can be too big.
It is instructive examine specific learning rate choices and their implications as reflected by the bound in (2.2). For example, with the commonly used polynomially decaying schedule 1)2 x t-,, the first term behaves like exp(-tt-8) while the second term is on the order of (17.), recovering the classical mean square етrоr (MSE) rate for this setting. In the following section, we apply Theorem 2.1 analyze another important and theoretically less-explored fnite-horizon schedule: the linearly decaying to zero (Linear- D2Z) learning rate.
2.3 Linear decaying step-sizes
As an important application of Theorem 2.1, consider the Linear-D22 learning rate 7 -t/n.. This learning schedule has recently been the forefront of training large architectures, and its optimality properties have been investigated both theoretically [Defazio et al., 2023] and empirically Bergsma al. [2025] in different context. Despite this interest, its non-asymptotic convergence rate remains unknown in the literature. Leveraging the bound in (2.2), we analyze the Lp convergence behavior of SGD under this learning rate schedule.
Theorem 2.2. Recall on from (1.1). Under the conditions of Theorem 2. we have
|| - 11 < 10, - -0110=00 exp( con(n 1) C
Vn'
where is a universal constant independent with n. and Op-
Remark 2.3. Theorem 2.2 offers remarkable insight into the behavior of the linearly decaying learning rate: it effectively combines the advantages of both constant and polynomially decaying step-sizes by being consistent and forgetting the initial condition at an exponential rate. Specifically, for any (0, 1) and all iterations i. < [nc]]. the step size satisfies V/2 2 ry(1 c); that is, the learning rate bchaves like a constant for a substantial portion of the optimization process, providing a "warm start" and ensuring exponential decay relative the initial point. Conversely, when t I - 2-1 for some c > 1/2 and co > O, the step size satisfies 7) = n/or x t-s mimicking a polynomially decaying schedule that yields the MSE of order O(n 112-1/2). Therefore, by leveraging the strengths of both constant and polynomially decaying learning rates, the linearly decaying to zero (Linear- DDZ)) schedule achieves a "best-of-bor wow.oooooo-oooodddo effect. This theoretical insight is empirically validated in Section C.6.
2.4 Asymptotic convergence in distribution of cyclical step-sizes
Note that for constant or cyclical learning rate schemes, Theorem 2.1 can only guarantee an MSE bound order O(1). This naturally motivates a deeper investigation into the convergence properties of these schedules. Specifically, an SGD sequence as defined in (1.1) with constant step size π)
5

---

can be interpreted as an aperiodic Markov chain. Under standard regularity conditions, it is well- known that the iterates 0, converge weakly to stationary distribution. However, as discussed, recent empirical work has highlighted the benefits of periodic or cyclical step-size schedules [Loshchilov and Hutter, 2017, Smith, 2023, Wang et al., 2023], such as 7): = ftt mod T. In this setting, the varying learning rate breaks the asymptotic stationarity of the SGD chain. Nonetheless, the periodic structure of the step-size schedule induces a corresponding periodicity the asymptotic behavior the iterates. Such non-stationary processes, characterized by recurring statistical properties over time, are known as cyclostationary processes, which we briefly introduce below.
Definition 2.3 (Cyclostationary process). stochastic process (Xe)EER is said be cyclosta- tionary with period T > 0 if it holds that for all [T]. and i N. (X,,..,,,,+) { d (X+4,...,,(+44T)] X
Cyclostationary process were introduced as model of communications systems in Bennett [1958] and Franks [1969], later finding wide use in econometrics [Parzen and Pagano, 1979] as well as atmospheric sciences [Bloomfield et al., 1994] the reader is encouraged to look into [Gardner et al., 1994, Napolitano, 2016], and the references therein for an introduction and a comprehensive list of all its applications. In the context of SGD, it is instructive to look at the iterative random function construction the cyclostationary process, as introduced by Bonnerjee et al. [2024]:
X = م6, Fr), F, = (s, S 1), Φt Φe mod for some period T E N.
(2.3)
This representation suggests immediate connection to the SGD iterates 0, in (1.1), which, in the case of cyclical learning schedules, can be represented as
0. = Fs, (1), 0z-1), 1i = 1)t mod for some period T E N, with Fg(n. 0) = - n ()0,E)
(2.4)
Equations (2.3) and (2.4) suggest an immediate connection between the cyclostationary process and SGD with cyclic learning rate, with the choice di l), for [?]. The following result, proved in appendix Section A.2, makes this connection precise by establishing a novel asymptotic convergence result.
Theorem 2.4. Suppose that Assumptions 2.1 and 2.3 hold for some > 2. Let Pp(7)) = (1+7Lp)) -p7Lp- -ppr, 7
R, where μ and Lp are as in Assumptions 2.1 and 2.3 respec- lively. Consider periodic step-size schedule with fixed period T. Then there exist T stationary processes ;I.-.., TT such that for all 1 (MI,...; R² satisfying
Pp(m) ... p. <1,
(2.5)
it holds that
OuT+i S as - oo for all E (T].
(2.6)
Moreover, in further satisfies
T &
min Jp(s) < 1, with J,(s) = EI po(
(2.7)
k=1
where 7, = mod T for > T, then there exists a cyclostationary process n,, such that
A, π as n
oc.
(2.8)
Remark 2.4. Note that (2.5) ensures that Pp (7.-) < 1 where s* = arg min, Tp(s). In contrast to the SGD with constant learning rate, none of the conditions (2.5) and (2.7) presupposes that 77 required to satisfy pp(1)) < 1 for each i E [7]. In particular, at least some of the 7)s 's may be taken to be large, which helps in faster convergence, which is also seen empirically Figure This result underpins the flexibility and the resulting popularity of the periodic step-size schedule over its constant counter-part, guarantceing convergence under very mild conditions (2.5) and (2.7) respectively.
3 Simulation
To validate our theoretical analysis, we conduct an empirical study of SGD with various learning rate schedules. The goal is assess how different step-size strategies affect convergence behavior and

---

mean squared error, and how these compare with the theoretical predictions in Theorems 2.1, 2.2 and 2.4. For simplicity. all experiments use simple linear regression model with known ground truth and are repeated across multiple Monte Carlo runs to estimate average performance and variability. In particular, Section 3.1 provides the model specifications. Section 3.2, we study the linearly decaying to zero (Linear-DD2Z) schedule 1/- (1 t/n), confirming its performance- early convergence and diminishing final error-as as predicted by Theorem 2.2. Finally, Section 3.3 examines cosine learning rate schedules of the form T)e (70 + cos(It//2) (T'), where we observe periodic error fluctuations that empirically confirm the cyclostationary behavior predicted by Theorem 2.4. Additional empirical studies be found in Appendix C, where also include a particularly illuminating comparative study between the different schedules in Section C.6. All the code files are available in GitHub.
3.1 Model specification
All the experiments are based on the following simple linear regression model:
Vi ( + g(()) x3 Es. 6 ~ ~V 1) Lid., 6* = ( E R
(3.1)
where (i) E I denotes the observed data and l E R is the unknown parameter. The true parameter vector is fixed at 0* = (2, -3) throughout all experiments. For all the subsequent simulation studies, we initialize the SGD chain at (0, T which provides sufficient distance for meaningful comparisons across different learning rate schedules, while not being so far away from the ground truth so that it fails to converge and denies us the full picture. Subsequently, we focus on an empirical evaluation of both the convergence trajectory and the distribution of the final error across different learning rate strategies.
3.2 Linear-D2Z rate
We consider Linear-D22 schedules the form fr = -70(1-t/n). which, despite their widespread use, have received comparatively little theoretical attention. Similar to Section 3.3, we let no e (0.01, 0.05, 0.1), and for each experiment, the mean errors are estimated via Nitee = 500 many independent repetitions. Firstly, to analyze the non-asymptotie MSE of the end-term SGD iterates, 8n we run SGD on the same regression task with {100, 200.... 10*), using 500 independent repetitions for each Figure displays the terminal squared error, which decays polynomially with n, in line with Theorems 2 and 2.2.
The appeal of the Linear-D24 schedule lies in its hybrid structure: as explained in Remark 2.3, early iterations benefit from relatively large step sizes, enabling rapid pessentt-potentalll faster than constant-rate scheme. Later, the schedule tapers off, reducing variance and yielding low final error. We numerically investigate this as follows. For a fixed n 10 Figure 2 shows the first 100 iterations for 1/u E {0.05, 0.1, 0.5). Across all settings, the error drops sharply, even under the high- vagianar TJo 0.5 case, demonstrating the robustness of the approach. Later in training, as shown in Figure 3) the error decay appears nearly linear before plateauing, with the stabilization occurring earlier for larger Y/o.
FijO -af)
7500
Sample
Figure 1: Plot of the terminal MSE estimate averaged over 500 SGD runs for 100 to n 10
7

---

Learnnng Rote
10
12-
12
100
80
8GD Benaks
930 Baraki
830 Benass
Figure Plot of the MSE estimate averaged over 500 SGD runs for n 10 iterations under Linear-D2Z schedule, observing from step to 100.
Learning Rate
000
000
00-
SGD Teralos
SGD heratess
350 Heeates
Figure 3: Plot of the MSE estimate averaged over 500 SGD runs for 10 iterations under Linear-D2Z schedule, observing from step 500 onward.
3.3 Cosine learning rate
As an example of the cyclical learning rate, we employ the widely-used cosine scheduling. Specifi- cally, we employ the schedule:
2n
7: = 170 1 cos
(3.2)
T
where 7oo is the base learning rate and I' denotes the period.
To assess the behavior induced by such schedules, perform online SGD for 104 iterations with "oo E {0.01, 0.05, 0.1} and T T= 3, averaging results over nater = 500 independent trials. Figure presents the resulting mean squared error (MSE) trajectories. Across all settings, the MSE exhibits an exponentially fast decay from the initial points before exhibiting persistent fluctuations about steady-state level. The periodicity, as predicted by Theorem 2.4 is not apparent from this plot. To further probe this structure, we examine the standard deviation of the MSE across runs over the final 100 iterations in Figure 5. Despite autocorrelation between estimates (due small step sizes), periodicity remains visible in the standard deviation curves, Even for no0 = 0.01, where the process converges slowly, the periodicity of order 3 easily discernible the plot. This empirically confirms Theorem 2.4: despite the huge nuto-correlation between successive iterations, with cyclical learning rates SGD iterates 92 do not settle but oscillate periodically, reflecting the learning rate' 's structure. The oscillation's 's amplitude and frequency depend on Tu. with larger values causing stronger fluctuations and faster initial progress. This nuanced behavior highlights balance between exploration and convergence enabled specifically by periodic schedules. For comparison, Figure 6 shows standard deviation curves under constant learning rates, which lack periodicity, confirming that the patterns in Figure arise from the cosine schedule.

---

Leamiig Ratb Schooile
01-11-222200
2 01-0622-421
0.
020
0.15
E(1
0.10
Hulls Mos
0.05
000
0.00
2:3-
1300
1500
800 Herraas
96D Nerasos
S0D Hersans
Figure 4: MSE estimates over 500 SGD runs (10* steps) with cosine learning rates, observing from step 500 onward. Periodic error fluctuations are evident, indicating cyclostationary dynamics.
Leamiing Rate Scheddlee
M
mun
01000-
0.000
01000
Figure 5: Standard deviation of the MSE over the final 100 iterations (across 500 runs) with cosine learning rates. Periodic fluctuation is clearly observed, even at a small 17o-
Leaming Fate (eO)
WM
0.002
00075
5003
0225
2050
2075
10000
2000
0023
2050
2075
10000
2900
3325
2030
2075
10000
Figure 6: Standard deviation of the MSE over the final 100 iterations with constant learning rates. No periodicity is observed.
4 Conclusion
Sharp theoretical MSE bounds offer critical insights into the behavior of SGD for given learning rate schedules, yet most prior work has focused on polynomially decaying step sizes, often sacrificing convergence speed for statistical tractability. To the best of our knowledge, this paper is the first to systematically develop unified framework that provides explicit MSE upper bounds for broad class of learning rates. In particular, we establish novel convergence guarantees for cyclical and linearly decaying to zero (Linear-Due -D2Z) learning rates two popular but previously under- theorized sroiices-sheddee
light on their strong empirical performance. Our results motivate further exploration beyond the convex setting into non-convex and non-smooth landscapes, with emphasis on understanding the statistical behavior of these schedules, including the potential for central limit theorems and refined uncertainty quantification. In this context, this work provides new insights into

---

the practically important yet theoretically underexplored area of learning rate selection, and serves as foundation for bridging practical success and theoretical understanding of SGD across diverse learning schedules regimes.
Acknowledgments and Disclosure of Funding
We sincerely thank the program chair, senior chair, area chair, and the five reviewers for their constructive feedback and involved discussion, which has greatly improved the clarity of our paper. Jiaqi Li's research is partially supported by the NSF (Grant NSF/DMS-2515926), Wei Biao Wu's research is partially supported by the NSF (Grant NSE/DMS-2311249)
References
B. Agrawalla, K. Balasubramanian, and Ghosal. Statistical inference for linear functionals of online sgd in high-dimensional linear regression. arXiv preprint arXiv:2302.097277 2023.
Y. Bengio. Practical recommendations for gradient- training of deep architectures. G. Mon- tavon, G. B. Oir, and K. Müller, editors, Neural Networks: Tricks of the Trade Second Edition, volume 7700 of Lecture Notes in Computer Science, pages 437-478. Springer, 2012. doi: 10.1007/ 978-3-642-35289- 26. URL https: org/ 1 /978 /97077/78-3--11 3-2--------------- -
W. R. Bennett. Statistics of regenerative digital transmission. Bell System Tech. J., 37:1501-1544 1958. ISSN 0005 8580. doi: 10. 10.1002/j.155 1550) .66..001560. URL 1002/j 1001-138-77 7305. 1958. tb01560... x.
S. Bergsma, N. S. Dey, G. Gosal, G. Gray, D. Soboleva, and Hestness. Straight to zero: Why linearly works best for llms. In The Thirteenth International Conference
decaying the learning rate on Learning Reprexentations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. URL https: /ttp::://pppenae hptp///pnnrreeeeeeeeeeeeeeeeeeea net. htt.://rrrum/..chholBBtttt.t
P. Bloomfield, H. I.. Hurd, and R. B. Lund. Periodic correlation in stratospheric ozone data. J. Time Ser. Anal., 15(2):127-150, 1994. ISSN 0144-9982,,4467-9992 doi: 10.11111,,146799992.. 11111111111999999211111 1994 tb00181.x..
tb00181.x. URL htwph:tt////e //t.i//oii///o org/ 10. 1111/jiiiijjja 111.1-1679922
S. Bonnerjee, S. Karmakar, and W. B. Wu. Gaussian approximation for nonstationary time series with optimal rate and explicit construction. Ann. Statist., 52(5):2293-2311 2024. ISSN 0090- 3364,2168-8966 doi: 10.
URL https: //t::://dooi orooooog//.....o 10. 24
L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Rev. (0(2):223-311 2018. ISSN 0036- 1445,1095-7200 doi: 10.1137/16M100017. URL
atttp:///oii org/ 10. 1011/1111111111111
X. Chen, J. D. Lee, stochastic gradient descent. Ann. Statist,, 48( (8(1)::22 48(1):251-273. 2020. ISSN 1990-5364,2168-8998 doi: N0.121411-AAOS180 AOS18801 801. URL
Tong, and Zhang. Statistical inference for model parameters in
1214/121111 AOS1801.
K. L. Chung. On stochastic approximation method. method. Ann. Math. Statistics, 25:463-483, 1954. ISSN 0003-4851. doi: 10. 10.1214/amm/117777/ 1177728716.
URL https:///dii org 1wtp////....//////.. 121.2/21aama.
A. Defazio, A. Cutkosky, H. Mchta, and K. Mishchenko. Optimal linear decay learning rate schedules and further refinements, arXiv preprint arXiv:2310.07831, 2023.
Devlin, M. Chang, K. Lee, and K. Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In J. Burstein, C. Doran, and T. Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume (Long and Short Pupers), pages 4171-4186. A Association for Computational Linguisties, 2019. doi: 10. 18653/V 1/N19- 1423. URL https: / /oi. www.ooorgooiiio
1423.
10

---

V. Fabian. On asymptotic normality in stochastic approximation. Ann. Math. Statist., 39:1327-1332,
1968. ISSN 0003-4851. doi: 10. 1...121//aa //211///m///177/99955555 URL https: //dopp://doi.... org 1214/ aoms/1177698258.
L. Franks. Signal Theory. Information theory series. Prentice-Hall, 1969. ISBN 9780138100773. URL https://books: http://ooooo.ooolle.e..oo
Gadat and F. Panloup. Optimal non-asymptotic analysis of the Ruppert-Polyake averaging stochastic
algorithm. Stochastic Process. Appl. 156:312-348, 2023. ISSN 9104-4149,1879-2000 doi:
htt.1///..pa..202200 1.012. URL https: http:::///ooo..rro..//.. 1016/ www. 2022. 01.012.
W. A. Gardner al. Cyclostationarity in communications and signal processing, volume 1. IEEE press New York, 1994.
R. Ge, S. M. Kakade, R. Kidambi, and P. Netrapalli. The step decay schedule: A near op- timal, geometrically decaying learning rate procedure for least squares. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 14951-14962, 2019. URL https:: http:///poooeeeng..eeeeeee newrips cc/ wttpcc/cpppppa httpppappp////apa/e/ee Abstract. html.
J. Gu and S. X. Chen. Statistical inference for decentralized federated learning. Ann. Statist., 52 (6):2931-2955, 2024. ISSN (090-53642216888666 doi: 10.1214/24-a022452 URL https: //doi.
A. Hägele, E. Bakouch, A. Kosson, L. B. Allal, L. von Werra, and M. Jaggi. Scaling laws and compute-optimal training beyond fixed training durations. In A. Globersons, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. M. Tomezak, and C. Zhang, editors, Ad- vances Neural Information Processing Systems 38: Annual Conference on Neural In- formation Processing Systems 2024, NeurIPS 2024. Vancouver, BC, Canada, December 10 15, 2024, 2024. URL http::/ mips. httpppppe__fffeee httpe//eeeeeeee///2//////// pttpp/ppp////as/////// 8b970e htw.::aeeee..eeaaaaaaa-ee-a-eeee Conference html.
K. He. X. Zhang. S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV. USA, June 27-30, 2016, pages 770-778. IEEE Computer Society, 2016. doi: 1091////.... URL https: /ttps:///oi... http///o..oggr/////// 10. 1109 /CV... 2016.90.
Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, Rutherford, D. de Las Casas, L. A. Hendricks, J. Welbl, A. Clark, T. Hennigan, E. Noland, K. Millican, G. van den Driessche, B. Damoc, A. Guy, Osindero, K. Simonyan, E. Elsen, O. Vinyals, W. Rae, and L. Sifre. An empirical analysis of compute-optimal large language model train- ing. In S. Koyejo, S. Mohamed, A. Agarwal, Belgrave, K. Cho, and Oh, editors, Ad- vances in Neural Information Processing Systems 35: Annual Conference on Neural Infor- mation Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 De- cember 9, 2022, 2022. URL http: http::://ppprrsee cle2faff6f58887 0W2.5588879395111 10055f114eee0443e555 SateneaaeeS-AAAbaaeeee ConstracttConffeeeee
wttpppsscccppppppeeeeeeep files/ ffiles/papeee fateper_filees/ppe//222222 pppppp//022/aaass html.
Howard and S. Ruder. Universal language model fine-tuning for text classification. In I. Gurevych and Y. Miyao, editors, Proceedings of the 56th Annual Meeting of the Association for Computa- tional Linguistics, ACL 2018, Melbourne, Australia, July 15-20, 2018, Volume 1: Long Papers, pages 328-339, Association for Computational Linguistics, 2018. doi: 10.18653/V1/118-1000 URL https: settps:/aacaantholl. /aw.aaaaaaanooooo..oooooo org/P18-11/
G. Huang, Y. Li, Pleiss, 7. Liu, J. F. Hopcroft, and K. Q. Weinberger. Snapshot ensembles: Train get M for free. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https://openreviae wwt.iiiww.eeeeeeeemmm dtttt//oommiiidB//woowoee
N. Iyer, V. Thejas, N. Kwatra, R. Ramjee, and M. Sivathanu. Wide-minima density hypothesis and 2023. URL
the explore-exploit learning rate schedule. J. Mach. Learn. Res., https: /mwrr.///rr/////// org/ wwweerrrggpppppeee atgpapprs/v24/2/ 2ttp://////11///99/9 html.
11

---

J. Li, Z. Lou, S. Richter, and W.-B. Wu, The stochastic gradient descent from nonlinear time series perspective. preprint, 2024a.
Li, T. Xiao, and G. Yang. Revisiting the central limit theorems for the SGD-type methods. Commun. Math. Sci., 1224:44474, 2024b. ISSN 1945-0999.
Y. Li, C. Wei, and T. Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NewrlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 11669 11680, 2019. URL https: https:// p/wp://edoogog.ss..//ooee// .ww.ddinnnn............e.. neurips. Abstractttt..............a html.
cc/paper htt///2099hhhhaa/
Y. Liu, M. Out, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoy- anov. Roberta: robustly optimized bert pretraining approach. arXiv preprint arXiv: 190:. 2019.
1907v 11692,
I. Loshchilov and F. Hutter. SGDR: stochastic gradient descent with warm restarts, In 5th In- ternational Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https:://penreeeee /eett net/ forum?id Sxq89Sxxx
Nakkiran. Learning rate annealing can provably help generalization, even for convex problems. arXiv preprint arXiv:2005.07360, 2020.
A. Napolitano. Cyclostationarity: New trends and applications. Signal Processing, 120:385-408, 2016. ISSN 0165-1684, doi: https://doi.org/// 10. 0iig:///.///gggpo220.....0
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim., 19(4):1574-160, 2008. ISSN 1052 1052-6234,1095-7188 doi: 10.113770707042777 URL https: org/ 1ttp/////001111070000077777
S. Oymak. Provable super-convergence with a large cyclical learning rate. IEEE Signal Process. Lett., 28: 164--1499, 2021. doi: 10.1 N0.100901P.222211100113. URL https://doii org/ 10.1999.... 2021 3101131.
E. Parzen and M. Pagano. An approach to modeling seasonally stationary time series. Jour- nal of Econometrics, 91):137-153, 1979. ISSN 0304-4076. doi: huts:///oi.orr/10..n 0304-4076679990100--3 URL https://: 0304407679901003.
B. Poljak. Some methods of speeding up the convergence of iterative methods. Z. Vyčisl. Mat i Mat. Fiz, 4:791-803, 1964. ISSN 0044-4669,
B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838- 1992.
E. Rio. Moment Inequalities for Sums Dependent Random Variables under Projective Conditions. Journal of Theoretical Probability,
163, Mar. 2009.
H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 2203)4400-407, 1951.
D. Ruppert. Efficient estimations from slowly convergent robbins-monro process. Technical Report, 1988.
Sacks. Asymptotic distribution of stochastic approximation procedures. Ann. Math. Statist., 29: 373-405, 1958. ISSN 0003-4851. doi: 10. 4 URL https://doi. org/10. 1214/aoms/1177766.
L. Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Conference Applications of Computer Vision, WACV 2017, Sunta Rosa, CA, USA, March 24-31, 2017, pages 462-472. IEEE Computer Society, 2017. doi: 10. 1091/AC222000..555 URL https:
//doi. //doi.org/////
org/10..1000 10. 1109 /w////////.//.. 2017.08
12

---

L. N. Smith. General cyclical training of neural networks. Adv. Artif. Intell. Mach. Learn., 3(1): 958-976, 2023, doi: (0.54364/AAIIML.223....1 URL https:///do..rrg/// 54364/aainn 2023. 1157.
L. N. Smith and N. Topin. Super-convergence: Very fast training of neural networks using large learn- ing rates. In Artificial intelligence and machine learning for multi-domain operations applications, volume 11006, pages 369-386. SPIE, 2019.
J. C. Spall. Introduction to stochastic search and optimization. Wiley-Interscient Series in Dis- crete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, 2003. ISBN 0-471-33052-3, doi: 10. 10.00/00477722233.. URL https://doi. http:///d..or///.../// otg/10.10000 0471722138. Estimation, simulation, and control.
H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, al. Llama: Open and efficient foundation language models. arXiv preprint mrXiv:2302.1397/ 2023.
W. Wang, C. M. Lee, J. Liu, T. Çolakoglu, and W. Peng. An empirical study of cyclical learning rate on neural machine translation. Nat. Lang. Eng. 29(2):316-336, 2023. doi: /11///00001//1111499900000000000
10.1017/1135133492200000
URL https://doi
Z. Wei, W. Zhu, and W. B. Wu. Weighted averaged stochastic gradient descent: Asymptotic normality and optimality. arXiv preprint arXiv:2307.06915 2023.
S. Wu, G. Zhang, and X. Liu. SwinSOD: Salient object detection using swin-transformer. Image Vis. Comput., 146(105003):105039,, June 2024.
X. Wu, R. Ward, and Bottou. Wngrad: Learn the learning rate in gradient descent. arXiv preprint DoXiv:8803.0240 2018.
Y. Wu, L. Liu, J. Bae, K. H. Chow, A. Iyengar, C. Pu, W. Wei, L. Yu, and Q Zhang. Demystifying learning rate policies for high accuracy training of deep neural networks. In C. K. Baru, J. Huan, L. Khan, X. Hu, R. Ak, Y. Tian, R. S. Barga, C. Zaniolo, K. Lee, and Y. F. Ye, editors, 2019 IEEE International Conference on Big Data (IEEE BigData), Los Angeles, CA, USA, December 9-12, 2019, pages 1971-1980. IEEE, 2019. doi: 10. TTW.///IIGDAAA449000000.... https://dot /doi: http://doo.ooro////// 1109/BigData470999 2019. 20199000014
URL
W. Zhu, X. Chen, and W. B. Wu. Online covariance matrix estimation in stochastic gradient descent. Amer. Statist. Assoc,, 1185411):333-444, 2023. ISSN 0162- 1537--77777 doi: 10. 1080/ 0 01621459.2021.1993444 URL https: /ttp:///oiiii.. wtt.://////..11//011220222212010 2021 1933498.
13

---

A Postponed Proofs
A.1 Proof of Theorem 2.1
Proof of Theorem 2.1. By recursively applying Lemma B.2, we have
00,, 11 < II (1 0- + 1)M3
Σ
nj
(1
com))
k=
==1
k=j+1
The proof is completed by noting that
II coms) exp k=1
Σ
C0
A.2 Proof of Theorem 2.4
Proof of Theorem 2.4. Suppose (0) = -0 -V0,) encodes the iterative random function governing the SGD trajectory (1.1). Fix i (7). For (2.6), observe that
BxT+: = F
(6in-1)7+44 14) (0 1yT+4, 17.
Xr), where, for X = (x1,...,,r))
we define F (0, 1) == F o... Fx FxToRI (0), with 7/+s
Vits mod T with slight abuse of notation. Applying Theorem of Li of al. [2024a] successively the function compositions of Fx, it holds that
(0, n) - (0', ,T)ll S (pp())...pp(())))
from which, (2.6) follows in light of (2.5) and Theorem 2.2 of Li et al. [2024a]. To ensure (2.8), note that if is cyclostationary process with period I defined on RR then for some stationary process on R Therefore, it is enough to show
iff (X Xr)
(OnT+e (m+11)++) + -
(A.1)
for some stationary process on RdxT and some E (7). Choose & = s" such that
EII (n(+t))
arg min
SE [7 k=1ø=1
Define
Fx) = (Fx,. Fxa. o Fx, Fx (0t), ExT. 0...0 Fx (0t)).
where
θ (01,..., Or) RdXT
Clearly, one derives
T
|(x (
=
Σ
F FX o... Fx,. mors Farm
Fx.. .... Fx..,, (f))
k=1
< 110, 011
ΣI P.
(A.2)
k=1j=1
Writing (1.1) as
(01 Fe fo (10n-1)7++41......
yet another application of Theorem 2.2 Li et al. [2024a] yields (A.1) in light of (A.2) and (2.7).
14

---

A.3 Proof of Corollary 2.2
Proof of Corollary 2.2. When T) = 77(1 t/n). the first term in (2.2) becomes exp( con((n
1) 1-1 For the second term, set m = n j. Then m = 0, 0....... 1, and
= 1l n j- m
Σ
m-1
Σ
(m 1)m
7 (m² - m).
2
2n
k=
k=0
Let Sn Ej= 113 exp
Co Ek=j+1 1k then since m S n.
S, = m=0
Σ
R-1
1
m 2
exp
- cu 2n
(m² - -m) - n² exp(
Cu7l
2
n-1
m²
n²
exp
{ conm²
2n
m==
The sum can further bounded by the integration. Since the function x² expl exppcoopa//11 (00pa///]] /2] is eventually decreasing with I, we have
n-1 m² n2
comm"
O' Vn
- x² ex
cona da ddz=
exp
2n
where C" is universal constant, and the inequality above is obtained by substituting m2 ///... This completes the proof.
B Auxiliary Section
In this section we collect two crucial auxiliary results that contribute towards the proof of Theorem 2.1.
Lemma B.1 (Rio's inequality [Rio, 2009]). Let X Rd and Y IRd be two random vectors such that X|" < and Y < for some p 2. Then we have
|X Y 1 I || (p 1)]
Lemma B.2. Consider the SGD iterates (02 in (1.1). Suppose that Assumptions 2.1 and 2.3 for p 2 Then, for some constant co > such that for all t 1,
---2 2/r - (Gp 5) L2g11 )
CD S min
m7
we have, for all 1. 1 1,
10, 0 S (1 1-ooooo)0100--1 0-11 + +(w - 1) M3.
B.1 Proof of Lemma B.2
Proof of Lemma B.2. Since &., for 2 1, are i.i.d. random samples, follows from the tower rule that
((, (F | 6n-1] = O. Therefore, by applying Rio's inequality in Lemma B.1, for p 2 2, we have
10. 113 < | 0 nn VF(..-)))) + (p 1ym (() -VF(0)-))
I + I2.
We shall bound the two parts 1, and T2 separately. For the first part T, note that FF(0*) = O and by the triangle inequality, we have
T = ||0n1 0* Tn ((nnn)))
= (Bn-1 - 0r, 0n - 8*) 22 (0n-1 - -", VF -
+ (VFV(On (F(0)), VF(O.-1) (PF()-))-VF(())) p/2
VF(OT))
< (0n-1 - - 00 -0") - -2n 0-, 0' -1(00--)-VV(00) V=(OO)
7 VF(On-1) VF(0")
15

---

By applying Assumption 2.1 to the first term and Assumption 2.3 to the second term, we can obtain
I S (1 2/// + 1/2 112)0000011 1
Regarding the second part 12, since VF((0) = 0, we have
[V ( f [
/ - I (n))llp
Hence, by Assumption 2.3, can achieve
[V Em) VF((n-1)113 - 6 1- 1-1 +11 + f Em
Combining results from 1I, and 112, we can obtain
||0, 11, S (1 2//r/1 (6p 5) T2,)) 10 1- 3(p 1) V V E.))
This can directly lead to the desired inequality.
C Additional simulations
In this section, we collect some additional simulation studies, complimenting the numerical exercises of Section 3. particular, in Appendix C.I, we begin with constant learning rates (1): = 7). which serve baseline and exhibit the expected bias-variance tradeoff, with final error scaling linearly in 17. Appendix C.2 turns to polynomially decaying learning rates, 7 = 7ot - and demonstrates how different values of 3 E (1/2, 1) influence the tradeoff' between fast initial descent and long-run variance control, consistent with the structure of Theorem 2.1. Moreover, Appendix C.3 examines alternating schedules that interleave two polynomial decay rates combine constant rate with decaying one, highlighting how the more aggressive schedule tends to dominate long-run behavior. Finally, Appendix C.6 includes detailed comparison study of the different step-sizes considered in this paper, with particular focus into the initial phase, as well as asymptotic behavior upon convergence.
C.1 Constant learning rate
To ground our analysis, we start with the familiar case of constant learning rates long favored for their simplicity, but known to encode fundamental tradeoff. We test three fixed values, 7 = 0.1, 0.05, and 0.01, and track their performance over 10a SGD iterations. The patterns are predictable but instructive: larger step sizes yield faster initial progress, yet settle into higher-variance regimes; smaller ones move more cautiously, but converge closer to optimum with lower final error.
Because the early dynamics often involve rapid error sometiimss several orders of magni- tude-we we focus the MSE plot on later stages: starting from & 100 for r/ = 0.1 and 0.05, and from t = 500 for 17 = 0.01. This lets us zoom in on the asymptotic behavior, where the long-term effects of each learning rate become more clearly visible.
Learing Fale
7-0.5
Pu001
2000
11404
2:334
930 lecates
S30 Itertte
Figure 7: MSE estimates over 500 SGD runs (10 steps) with constant learning rates.
The empirical trajectories in Figure 7 reflect this tradeoff. Larger learning rates lead to faster early reduction in error but exhibit higher variance and stabilize farther from the optimum. contrast, smaller learning rates result in slower progress but achieve significantly lower terminal error.
16

---

To complement this, Figure 8 plots the final mean squared error against a dense grid of fixed learning rates ranging from 17 0.01 to 17 = 0.1. The trend is unmistakable: terminal MSE scales linearly with 7), matching the (()) variance bound predicted by theory. This reinforces the fundamental tension in fixed-rate SGD: speed comes at the cost of noise, and there's no single value of y that avoids the tradeoff entirely.
F(o" -a
0.15
0.10
0.05
0.00
0.025
0.0
0,075
Leamiing rate (t)
Figure 8: Plot of the terminal MSE estimate averaged over 500 SGD runs for 10 steps, for constant values for 1) between 0.01 and 0.1.
C.2 Polynomially decaying learning rate
We now turn to the classical regime of polynomially decaying learning rates. These schedules take the form = not where 'oo > 0 and 3 E (0, 1] controls the rate of decay. The general non-asymptotic error bound given in Theorem 2.1 applies this setting directly, and allows these schedules induce. In particular, when 3 > 2. the sum Er=1 ni converges, ensuring that variance contributions decay to zero; whereas the condition 3 < guarantees Et= Ytt = oo, which is necessary for the bias to vanish. These facts jointly imply that SGD with / E ( 1) is consistent and convergent, with error rates depending sensitively on the balance between the two terms in the bound.
capture the tradeoffs
To explore these effects empirically, simulate SGD with learning rates of the form π) not using two values of 3: 0.505 and 0.75, each tested with base rates ro = 0.1, 0.05, 0.01. Figure shows the mean squared error over time for these settings, averaged over 500 independent runs. The results highlight the central tradeoff: smaller values of B yield faster initial descent but larger long-run fluctuations, while larger 33 dampen early progress but reduce terminal error. This qualitative pattern matches the structure of Theorem 2.1, in which the exponential forgetting term dominates early on, and the variance accumulation term becomes decisive the long run.
Because the early dynamics often involve rapid error ciduuction-smmetines several orders of mag- nitude-wt we focus the MSE plot on later stages: starting from t 1000 for n 0.1,3 0.505, t 4000 for = 0.05, 3 0.505 and = 5000 for 3 = 0.75. This lets us zoom in on the asymptotic behavior, where the long-term effects of each learning rate become more clearly visible.
interesting feature of these experiments is the relative importance of 3 compared to roo While smaller base rates do modestly influence early error and variance, the dominant effect stems from the decay exponent. The case / 0.505, being just above the variance threshold, achieves a strong balance between speed and consistency ceaivveency-coovegiinnn converging faster than 3 = 0.75 while eventually achieving comparably low error. This behavior reflects the non-asymptotic structure predicted by Theorem 2.1, which separates the error into two components: a bias decay term, of the form exp(-c> >i m))), and cumulative variance term, of the form Σソ=1 1) (xp(-<En 7he) For polynomial learning n. and the variance term converges zero if 1 but
rates, the bias term vanishes polynomially only slowly. These dynamics explain the empirical behavior observed: 3 0.505 gives faster early convergence due to slower bias decay, while = 0.75 leads to more effective long-run averaging, with reduced variance. The simulations thus concretely illustrate the tension between forgetting and fluctuation that the theory encodes, and validate the asymptotics of polynomial decay schedules as captured by Theorem 2.
2
17

---

nymo,00,
Eljo" -0.7
0007
0.8
0.0
61f6"
0.24
0.022
0.0
4050
8000
5000
Iterates
SGD Iterates
0.009
-6/
0,002
0,000
0.00
2000
5000
7000
10003
0000
6000
7000
3000
0000
10000
SGD iterates
SGD
iterales
Figure 9: MSE estimates over 500 SGD runs (10* steps) with polynomially decaying learning rates.
C.3
Alternating polynomially decaying learning rate
Building on our observations from the previous experiments, we explore combining the strengths of both polynomially decaying and cyclical approaches. In particular, the cyclical schedules demonstrate superior initial convergence through their ability to take larger steps early in optimization, while polynomial decay provides better asymptotic properties and lower final error. To this end, we tried two forms of dual schedules:
1. Set base rate \/ and alternate between two polynomial decay rates or a polynomial decay rate and a constant rate. Using two values for Vo (0.1, 0.05). a constant rate and two exponents for polynomial decay rates 3 = 0.505, 0.75 gives us six total combinations. In all of these cases, we present the plots for the mixture of a decay schedule and constant rate from 500 and for the mixture of two polynomial decay schedules from 1000, again to observe the general trend rather than the initial decay by several orders of magnitude in short amount of time.
2. Set fixed polynomial decay rate and alternate between two base rates, "large" and "small" one. Plotted from = 2000 for the same consideration as above.
Schedule
0.06
0.00
2.
5200
7500
10020
1000
2000
3G0
3G0 Beralts
Figure 10: Plot of the MSE estimate averaged over 500 SGD runs for 104 steps.
For both To 0.1 and 0.05, if the constant learning rate schedule is one of the two included, process seems to behave in the same way over the long run. However, when we alternate between 3 = 0.505 and / 0.75, we get an outcome more similar to just selecting 3 = 0.505. In all of these cases, the larger learning rate plays the dominant role in determining the convergence rate and terminal eπror of the process.
18

---

Schwidule 30000
5-10000,0755
(-1075.0
0.10
02
0.1
000
0.0
2.3
8GD taratos
8GD Deranes
S0D Harsaes
Figure Plot of the MSE estimate averaged over 500 SGD runs for 10 steps.
Schedule
1, 0.10.1
0.2
0.006
0.0075
0.004
0.0050
0.000
0.0025
0.000
0.0000
6000
SGD iterates
SGD Iterates
Figure 12: Plot of the MSE estimate averaged over 500 SGD runs for 10 steps.
The two plots look almost identical and even have eπror rates that seem to scale sublinearly with njo- Compared with the earlier plots this section and our observations in section 3.3, we have empirical evidence that in polynomial decay and mixed polynomial decay regimes, the choice of the rate of decay 3 far more important than the choice of the base rate 7/o-
C.4 Linear regression with randomly initialized coefficients
In addition to the experiments outlined above, present the results of another simulation, with n = 10a, l" 0) and On initialized randomly. The other settings remain as they were in the paper:
yi = (0)) + ((0) + Ei, e, ~ ((0 0" = (0(0) 00)T E TR?
where (1,, 9:) E RR22 denotes the observed data and 0r E IR2 is the unknown parameter. Results are averaged over 500 SGD runs. We summarize results from iterations 500 5000 within each SGD run in the table below. Mean SE SD in the table is taken over the last 100 iterations.
Table I: Final and Minimum MSE for Cosine Learning Rate Schedules on Simulation Data
Schedule
Final MSE
Min MSE
Final SE SD
Mean SE SD
0.1 - (1 + cos (2 t3)
0.1713
0.1
0.1743
0.2334
0.05 + cos 2m /3))
0.0805
0.0484
0.0777
0.0912
0.01 (1 + cos 2ml /3))
0.0158
0.0101
0.0136
0.0144
19

---

C,5 Testing on MNIST
To demonstrate the validity of our empirical evaluation beyond elementary linear regression cases, conducted additional experiments the MNIST dataset using high-dimensional classification task. Specifically, we trained a multiclass logistic regression model via stochastic gradient descent (SGD) under both the cosine and Linear-D2Z learning rate schedules. The goal of this evaluation to assess whether our theoretical insights carry over to practical settings involving real-world, high-dimensional data. Each MNIST image is flattened into vector E R7744 and paired with a one-hot encoded label y E {0, 1) Given this input-target pair, we minimize the sigmoid loss [a, y: 0), where 0 E IK 784x10 denotes the model parameters. This setup is equivalent to minimizing a sum of binary logistic regression losses across classes in a one-vs-rest fashion. For the cosine schedule 7t- (1 cos(231/3)) we ran SGD for 5000 iterations, anticipating convergence to cyclostationary distribution. The outcome was indeed cyclostationary in nature, similarly to what was observed Figure 4.
For the Linear- -D2 schedule n = no(1 - t//n). we ran SGD in increments of 500 iterations, from 500 to 5000. Performance the classification accuracy (i.e., the proportion of correctly classified digits under arg max, 0 r)). Results presented in the table below.
evaluated in terms of both the average sigmoid loss and
Table 2: Sigmoid loss Estimate for the Linear-D22 schedule on the MNIST dataset
Number of Iterations
MSE
Standard Deviation
500
0,0059
0.0046
1000
0.0042
0.0020
1500
0.0041
0.0015
2000
0.0034
0.0018
2500
0.0034
0.0013
3000
0.0035
0.0012
3500
0.0033
0.0011
4000
0.0032
0.0011
4500
0,0032
0.0012
5000
0.0031
0.0011
C.6 Comparison of different learning rates
In this section, we numerically investigate the comparative performance of the different learning rate schedules analyzed in this paper. Specifically, we plot the estimates of Bi 0,,1%) against n for 10*, and five different learning rate schedules corresponding to Sections 2.3-3.3. along with the additional studies in the appendix C. For careful comparison of both the effect of initialization as well as behavior convergence, we investigate the MSE of 0,, for the initial 100 iterates, in Figure 13, as well as the final 100 iterates, in Figure 14.
Schaok
Grtaite- Au Poyconel
Figure 13: Plot of the evolution of the MSE estimate for the first 100 SGD iterations for five learning rate schedules.
20

---

50
6.00
2010 2010-eent
Figure 14: Plot of the evolution of the MSE estimate for the last 100 SGD iterations for five learning rate schedules.
In the early stages of the process, the models that have non-decaying rate (constant learning rate and cosine schedule), as well as the Linear-D22 model, which as discussed in Sections 2.3-3.3, exhibits superlinear convergence speed away from initialization, while the polynomial decay and mixed polynomial decay model both move more slowly. This is almost reversed the later stages of the process while all five models have converged to small error, Linear-D2Z and the two polynomial decay-based models end up with a far smaller error estimate compared to the constant learning rate and the cosine schedule, which demonstrate consistent bias. This demonstrates well- well-Known theoretical results larger learning rates converge faster but at the cost of larger terminal bias. Linear-D2Z manages reach acceptably small error rather quickly and also enjoys small terminal error due to being defined a way that starts off with large step sizes that then taper off quickly, reinforcing its view "best-of-both-wotte learning schedule.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims of the paper are accurately reflected in both the abstract and introduction. The paper proposes a general framework theoretically derive the MSE of SGD iterates for general class of learning schedules. All claims are theoretically proven and empirically validated throughout the work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: All theoretical assumptions underlying the SGD setting are explicitly stated and discussed in detail in Section 2.1. These sections also elaborate the limitations of the asymptotic analysis, particularly in relation to the two specific learning rate schedules examined in greater depth. These limitations are highlighted through dedicated remarks following the main theorems. Additional commentary open questions and potential extensions provided in the conclusion (Section 4).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
22

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the assumptions can be found in the theorem statements, and discussed in main paper. All the proof' can be found in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The complete model specifications along with parameters, are provided in
Section 3.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
23

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the codes to reproduce the results can be found anonymously github as well in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/ cablic/guiden wttps//oooeeeeeseeoeeeiooa
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/ ccc/pblic//guu http//gwwe///eeeeeeeeeeee/eeeeee /odee////omdbmiii ss aasionPooi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details are provided in Section 3.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Yes, whenever the MSE of the SGD iterates is reported, an estimate of their variability/error-buss is reported in the form of shade.
Guidelines:

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The experiments are lightweight and quickly modern laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that NeurlPS Code of Ethics https: ptttts:///eurigee //nnunnurip... wttpe/pp...ppuppiiipeeeeccccpc.e httpppbicc//hicccuueeeeeiii
didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification: The research follows all ethical guidelines. No human data or ethically sensitive content involved.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
25

---

Since our work is theoretical in nature, we do not anticipate any negative impacts, and as such the paper does not include dedicated speculative discussion of broader societal impacts in separate section.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not release any models or datasets with high risk of misuse. All released components are synthetic and pose no privacy or safety risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All baseline methods are standard, and citations to prior work are provided with proper attribution and licensing notices.
Guidelines:
The answer NA means that the paper does not use existing assets.
26

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cww.coo//oaooooo com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
The paper introduces novel techniques derive MSE of SGD iterates with any step-size choice, which are theoretically validated with extensive proofs. Moreover, char- acterizes the convergence behavior for two widely-used, but theoretically less-und uossuunerstood learning schedules. All the accompanying empirical evidence is documented and released via GitHub repository in anonymized form. Hyperparameters, dependencies, and usage instructions are all included. Guidelines:
Justification:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well as details about compensation (if any)?
Answer: [No]
Justification: The paper does not involve crowdsourcing human subject research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
27

---

Answer:
[No]
Justification:
No human subjects are involved in this research.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [No]
Justification: No large language models (LLMs) were used to produce, analyze, or verify the scientific content of this paper. All methods and results are original and independently verified using rigorous mathematical analysis and custom code.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: /ttp:///eeeu//eeeeeee http://ups.cccooofeeeeeeeeeeeeee cc/Comferences/22255 /LLM) for what should or should not be described.
28


Reviews:
[{"review_id": "UkjYp0NSVG", "reviewer": "Reviewer_WHTk", "summary": "This paper studies how stochastic gradient descent (SGD) behaves when using different kinds of learning rate schedules—especially ones commonly used in practice, like linearly decaying learning rates and cyclical ones. These types of schedules are widely used in training deep learning models but haven’t been fully studied in theory. The authors develop a general framework to analyze these learning rates, providing both theoretical results and experiments. The main contributions include error bounds for general step sizes (Theorem 2.1), analysis of linearly decaying learning rates (Theorem 2.2), and new results about cyclical learning rates (Theorem 2.4), showing that they converge to a repeating (cyclostationary) pattern.", "questions": "Please comment about indicate weaknesses. Does convexity assumptions could be relaxed?", "limitations": "No", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\nThe new theroretical analysis of linear decay to zero SGD.\n\nWeakness\nIn the introduction, the paper does not explain what $\\eta_t$ and $\\eta_{n,t}$ represent, which may confuse readers unfamiliar with the notation. The schedule $\\eta_t = \\eta(1 - t/n)$ is introduced without much context or justification. This type of schedule assumes that the total number of iterations $n$ is known in advance, which is often unrealistic in practice—especially for stochastic algorithms where the convergence time is not fixed and may vary depending on the data or noise. Additionally, the paper does not cite some relevant prior work.\nAssumption 2.3 seems to be more restrictive than usual assumption on boundedness of conditional expectation. In this form this assumption requires that noisy gradient could not depend on past trajectory. \n\nI will reconsider my opinion based on author rebuttal.", "was_revised": true, "final_justification": "Due to the promise to improve a paper I increase my score", "rebuttal": "We sincerely thank the reviewer for their detailed and pertinent comments, along with encouraging words for our theoretical contribution on `Linear-D2Z` schedule. In the following, we address your concerns one by one. We warmly welcome any other additional suggestions to improve this paper, and wholeheartedly appreciate your decision to reconsider the score based on this rebuttal.\n\n## Weaknesses:\n\n- **In the introduction, the paper does not explain what $\\eta_t$ and $\\eta_{n,t}$ represent, which may confuse readers unfamiliar with the notation.**\n\n  *Response.* We appreciate the note on clarity — these both refer to the very same $\\eta_t = \\eta(1 - t/n)$, with or without the additional $n$ in the subscript whenever it may be necessary to specify that this depends on a particular value of $n$. Notes clarifying this have been added to the manuscript.\n\n- **The schedule $\\eta_t = \\eta(1 - t/n)$ is introduced without much context or justification. This type of schedule assumes that the total number of iterations $n$ is known in advance, which is often unrealistic in practice—especially for stochastic algorithms where the convergence time is not fixed and may vary depending on the data or noise. Additionally, the paper does not cite some relevant prior work.**\n\n  *Response.* We thank you for raising this point. As the reviewer *gHWv* also mentioned, the `Linear-D2Z` schedule is widely explored in the literature, in particular in AdamW training (Loshchilov and Hutter, *Decoupled Weight Decay Regularization*, ICLR 2019), as well as in Bregsma et al., *Straight to Zero: Why Linearly Decaying the Learning Rate to Zero Works Best for LLMs*, ICLR 2025, and in Defazio et al., *Optimal Linear Decay Learning Rate Schedules and Further Refinements*, arXiv preprint, 2023, and references therein. The latter has already been cited, and the former has been added to the manuscript for improved clarity.\n\n  Apart from citing these papers and others, we explain the utility of this schedule — one can view its early stages as akin to a fixed learning rate, allowing for fast approach to the solution, and its latter stages decay faster than a polynomial rate, allowing for improved accuracy. Furthermore, 1-batch single epoch SGD is a common approach, and in line with the theoretical work presented in every theoretical step in this paper. Under this framework, the number of steps $n$ is determined by the length of the dataset. One can adapt $n$ if this does not lead to a satisfactory empirical result (i.e., insufficient information on long-term behavior), but this has not been the case here.\n\n- **Assumption 2.3 seems to be more restrictive than the usual assumption on boundedness of conditional expectation. In this form, this assumption requires that noisy gradient could not depend on past trajectory.**\n\n  *Response.* Indeed, by Jensen's inequality, our Assumption 2.3 implies the usual assumption:\n\n  $$\n  |\\nabla F(x) - \\nabla F(y)| \\leq L|x - y|, \\text{ for all } x, y; \\quad \\mathbb{E}[|\\nabla F(\\theta_{t-1}) - \\nabla f(\\theta_{t-1}, \\xi_t)|^2 \\mid \\mathcal{F}_{t-1}] < M_2.\n  $$\n\n  The Lipschitz condition is very classical in the asymptotic analysis of SGD (see Assumption 4.3, Polyak and Juditsky, *Acceleration of Stochastic Approximation by Averaging*, SIAM Optimization, 1992). We note that our proof of Lemma B.2 (the main result behind Theorem 2.1) goes through verbatim with this slightly weaker assumption. Additionally, we point out that our sampling process for $\\xi_t$ is i.i.d., and thus the noisy gradient $\\nabla f(\\theta_{t-1}, \\xi_t)$ depends on the past trajectory only through $\\theta_{t-1}$, similar to a Markov chain. We gladly welcome any further comments from your side if you think further clarifications are required.\n\n## Questions:\n\n**Does convexity assumptions could be relaxed?**\n\n*Response.* We thank the reviewer for raising this pertinent question. If there are only finitely many local minima, our techniques along with a *local strong convexity* assumption can yield the corresponding results conditional on in-probability convergence. See, for example, Zhong et al., *Online Bootstrap Inference with Non-Convex Stochastic Gradient Descent Estimator*, Preprint 2023.\n\nUnfortunately, for non-convex regimes with uncountably many local minima, the error bounds may not be obtained in an $\\mathcal{L}_2$ sense, and it might be more convenient to look at regret bounds or convergence of $\\nabla F(\\theta_t)$. As the reviewer *H11d* points out, PL inequality may be a more appropriate assumption there. For general choices of step sizes, this indeed represents an exciting research direction, and we believe — despite the significant non-triviality — the techniques developed here should be useful there too."}, {"review_id": "4ObKneowAF", "reviewer": "Reviewer_gHWv", "summary": "This paper addresses the gap between the well-established theoretical analyses of stochastic gradient descent (SGD) with polynomially decaying step-sizes and the practical use of alternative learning rate schedules such as cyclical learning rates and linearly decaying to zero (Linear-D2Z), which have been widely adopted in deep learning but lack comprehensive theoretical understanding. The authors develop a unified framework that provides non-asymptotic mean-squared error bounds for SGD iterates under arbitrary learning rate schedules, generalizing classical results and explicitly capturing the influence of initial conditions and step-size sequences. They offer the first rigorous convergence characterization for the popular Linear-D2Z schedule and introduce novel asymptotic theory for cyclical learning rates, showing that SGD with cyclical rates converges to a cyclo-stationary distribution exhibiting periodic behavior, in contrast to the stationary distribution convergence of constant step-size SGD. Numerical experiments validate these theoretical insights, demonstrating fast early convergence and low final error for linearly decaying schedules and cyclical variance patterns for cosine schedules.", "questions": "Please see above.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "I think in general the paper is well written, the motivation is clear and the contribution too. \n\nOne of my main issues with the paper is that I find the title and some parts of the abstract and introduction a bit misleading. I do not want to diminish the contribution of the paper, but they way it is presented, especially in the title for a \"general learning-rate\", the reader might be misled thinking that the proposed framework generalizes all the previous works so far, or is insightful for them. However this is not the case, as for constant learning rate, as the authors point out, later on, their Theorem 2.1 only yields a O(1) bound, which does not seem useful. I do not have an issue with this per se, but with the way the framework is presented and encourage the authors to change this.\n\nThe authors make several assumptions which I do not seem to be too restricting and are standard assumptions in works like this, and they further give comments on these assumptions and relaxations in case where they are possible which I appreciated.\n\nIn Remark 2.4 the authors say that some of the ηi’s maybe taken to be large which helps in faster convergence. This can also be seen empirically in Figure 4. Could the authors be a bit more specific to how they define \"large\" and provide a bit more clarification on this? A histogram for the norms might be interesting. Another thing that I observe in the is: in first example in Figure 4 with 0.1 as the multiplicative constant, the norms of these fluctuations seem to start to be larger and larger as the process progresses. Why did the authors consider 10^4 iterations and not more? For the smaller constant multipliers it seems that the behavior does not change but for the case 0.1 I think it would be useful to further run the simulation. \n\nAlthough the paper is of theoretical nature, it would be beneficial and I would have been keen to give a higher score if the authors have performed more extensive experimental analysis, for example using simple networks as LeNet or AlexNet would suffice on simple datasets like MNIST or CIFAR-10 that do not require intensive computational resources. I think this would make the paper stronger.\n\nAlso, can the authors repeat their experiments with initializations following a zero-centered Gaussian distribution? I think this initialization is, at least from my experience in similar works, a lot more standard. I am not sure why did the authors decide to fix it throughout all experiments and it raised slight confusion, although I believe that the results and findings should not change.", "was_revised": true, "final_justification": "I stand with my initial judgement - after reading other reviews and the additional experiments, I did not find much that changed/improved my initial opinion on the paper. I still lean towards acceptance.", "rebuttal": "We sincerely thank the reviewer for their comprehensive appraisal of our paper, in particularly highlighting our theoretical contribution on `Linear-D2Z`, detailing the first rigorous convergence characterization for that scheme, as well as for cyclical learning rate schedules. We warmly welcome any other additional suggestions that might improve the paper, and wholeheartedly appreciate your willingness to increase the score given more experimental evidence. In particular, we have taken the opportunity of this rebuttal to demonstrate some experimental results on MNIST dataset. However, before discussing that directly, let us address your concerns one by one.\n\n## Weaknesses:\n\n- **One of my main issues with the paper is that I find the title and some parts of the abstract and introduction a bit misleading. I do not want to diminish the contribution of the paper, but the way it is presented, especially in the title for a \"general learning-rate\", the reader might be misled thinking that the proposed framework generalizes all the previous works so far, or is insightful for them. However this is not the case, as for constant learning rate, as the authors point out, later on, their Theorem 2.1 only yields a O(1) bound, which does not seem useful. I do not have an issue with this per se, but with the way the framework is presented and encourage the authors to change this.**\n\n  *Response.* We greatly appreciate your suggestion. In the revision, we will change the title to **\"Asymptotic theory of SGD for a broad class of learning rates\"** to avoid confusion. For the other parts mentioning \"general learning rates\", especially the ones in the abstract and introduction, we will revise the statements accordingly.\n\n- **In Remark 2.4 the authors say that some of the $\\eta_i$’s may be taken to be large which helps in faster convergence. This can also be seen empirically in Figure 4. Could the authors be a bit more specific to how they define \"large\" and provide a bit more clarification on this? A histogram for the norms might be interesting.**\n\n  *Response.* We agree with your concern — \"large\" is relative, and should be calibrated according to the problem at hand. This is best understood as relatively large and relatively small learning rates within the same cyclical schedule. In this paper, we've opted to demonstrate this with an easy to understand example — the cosine learning rate schedule with period 3, resulting in one $\\eta_i$ in each cycle of three being four times as large as the others.\n\n- **Another thing that I observe is: in first example in Figure 4 with 0.1 as the multiplicative constant, the norms of these fluctuations seem to start to be larger and larger as the process progresses. Why did the authors consider $10^4$ iterations and not more? For the smaller constant multipliers it seems that the behavior does not change but for the case 0.1 I think it would be useful to further run the simulation.**\n\n  *Response.* To address your concern, we present the results of another simulation, with $n = 10^5$, $\\theta^* = (0,0)$ and $\\theta_0$ initialized randomly. The other settings remain as they were in the paper:\n\n  $$\n  y_i = \\theta^{(0)} + \\theta^{(1)} x_i + \\varepsilon_i,\\quad \\varepsilon_i \\sim \\mathcal{N}(0,1)\\text{ i.i.d.},\\quad \\theta^* = (\\theta^{(0)}, \\theta^{(1)})^\\top \\in \\mathbb{R}^2\n  $$\n\n  where $(x_i, y_i) \\in \\mathbb{R}^2$ denotes the observed data and $\\theta^* \\in \\mathbb{R}^2$ is the unknown parameter. Results are averaged over 500 SGD runs.\n\n  **Table: Final and Minimum MSE for Cosine Learning Rate Schedules on Simulation Data**\n\n  | Schedule                          | Final MSE | Min MSE | Final SE SD | Mean SE SD (last 100) | Iteration Range |\n  |----------------------------------|-----------|---------|--------------|------------------------|------------------|\n  | 0.1 · (1 + cos(2$\\pi$ t / 3))         | 0.1713    | 0.1103  | 0.1743       | 0.2334                 | 500–5000         |\n  | 0.05 · (1 + cos(2$\\pi$ t / 3))        | 0.0805    | 0.0484  | 0.0777       | 0.0912                 | 500–5000         |\n  | 0.01 · (1 + cos(2$\\pi$ t / 3))        | 0.0158    | 0.0101  | 0.0136       | 0.0144                 | 500–5000         |\n\n- **Although the paper is of theoretical nature, it would be beneficial and I would have been keen to give a higher score if the authors had performed more extensive experimental analysis. For example, using simple networks such as LeNet or AlexNet on simple datasets like MNIST or CIFAR-10 that do not require intensive computational resources. I think this would make the paper stronger.**\n\n  *Response.* To address your concerns regarding the scope of our empirical evaluation, we conducted additional experiments on the MNIST dataset using a high-dimensional classification task. Specifically, we trained a multiclass logistic regression model via stochastic gradient descent (SGD) under both the cosine and `Linear-D2Z` learning rate schedules.\n\n  Each MNIST image is flattened into a vector $x \\in \\mathbb{R}^{784}$ and paired with a one-hot encoded label $y \\in \\{0,1\\}^{10}$. Given this input-target pair, we minimize the sigmoid loss $\\mathcal{L}(x, y; \\theta)$, where $\\theta \\in \\mathbb{R}^{784 \\times 10}$ denotes the model parameters. This setup is equivalent to minimizing a sum of binary logistic regression losses across classes in a one-vs-rest fashion.\n\n  For the cosine schedule $\\eta_t = \\eta_0 (1 + \\cos(2\\pi t / 3))$, we ran SGD for $n = 5000$ iterations, anticipating convergence to a cyclostationary distribution. The outcome was indeed cyclostationary in nature, similarly to what was observed in Figure 4.\n\n  For the `Linear-D2Z` schedule $\\eta_t = \\eta_0 (1 - t/n)$, we ran SGD in increments of 500 iterations, from $n = 500$ to $n = 5000$. Performance was evaluated in terms of both the average sigmoid loss and the classification accuracy (i.e., the proportion of correctly classified digits under $\\arg\\max_j \\theta^\\top x$).\n\n  **Table: Sigmoid Loss Estimate for the `Linear-D2Z` Schedule on the MNIST Dataset**\n\n  | Number of Iterations | MSE    | Standard Deviation |\n  |----------------------|--------|--------------------|\n  | 500                  | 0.0059 | 0.0046             |\n  | 1000                 | 0.0042 | 0.0020             |\n  | 1500                 | 0.0041 | 0.0015             |\n  | 2000                 | 0.0034 | 0.0018             |\n  | 2500                 | 0.0034 | 0.0013             |\n  | 3000                 | 0.0035 | 0.0012             |\n  | 3500                 | 0.0033 | 0.0011             |\n  | 4000                 | 0.0032 | 0.0011             |\n  | 4500                 | 0.0032 | 0.0012             |\n  | 5000                 | 0.0031 | 0.0011             |\n\n- **Also, can the authors repeat their experiments with initializations following a zero-centered Gaussian distribution? I think this initialization is, at least from my experience in similar works, a lot more standard. I am not sure why did the authors decide to fix it throughout all experiments and it raised slight confusion, although I believe that the results and findings should not change.**\n\n  *Response.* See the response to your concern with Figure 4."}, {"review_id": "sg4Fcyemvk", "reviewer": "Reviewer_8TRU", "summary": "This paper analyzes theoretically some learning rates schedules commonly used in practice in ML, the cyclical learning rate and the linear decay to zero learning rate. \nMore precisely, it generalizes previous analyses in terms of mean-squared error to not only tackle polynomially decreasing learning rates, but also more learning rate schedules that previously lacked theoretical support, such as the linearly decaying to zero learning rate (D2Z) and cyclical learning rates.\nAdditionally, the results are verified experimentally.", "questions": "- 1. Could the authors provide maybe more details on how this work, for the convergence rate in the case of the linear schedule, compares with the work of Defazio, and whether there is any fundamental difficulty to obtain their result compared to the one in Defazio ? (even if, I agree, this work is general as it uses $\\ell_p$ norms for the moments, and also, the result for linear decaying learning rate is just one result amongst many results proven in the paper so that does not put in question the rest of the paper). Especially when p=2: the result of Defazio is a convergence result in objective function, but wouldn’t one be able to obtain a result in terms of $\\ell_2$ distance to optimality directly from the objective function bound, by using Assumption 2.1 at the optimum ?\n- 2. Why using the p-norm in Theorem 2.1 (instead of simply the $\\ell_2$ norm) ? I may have missed the motivations behind it but if it is not present in the paper I guess the authors could elaborate on why it is important to prove a result in p-norm.", "limitations": "no specific limitation", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n-  1. I think this paper makes good contributions to the literature of SGD by focusing on learning rate schedules that are recent and more used in practice.\n- 2. The analysis for the linear decaying learning rate looks interesting, as it it expressed in a general $\\ell_p$ norm form which looks novel compared to state of the art results for this setting such as Defazio et. al. (2023)\n- 3. Perhaps more importantly the analysis for cyclical schedules looks interesting and novel since for its proof it uses tools from non-linear time series theory (from Li et. al. 2024), which is not very standard in convergence proofs in optimization (which are usually rather based on judicious refactoring of norm inequalities and using the assumptions ((local) strong convexity, etc) of the problem). The way that the results of Li et. al. are used seem novel up to my knowledge (I checked the paper from Li et. al. and did not see any proof for a cyclic schedule there).\n- 4. Finally, the experiments show well the validity of the results in practice, in particular, they are able to showcase the periodicity in the standard deviations, when using a cyclic schedule.\n\n# Weaknesses\n\n- 1. I think it would be good for that paper to compare in slightly more details to the result from Defazio et. al. (2023), in particular, in 2.3, what do the authors mean by “its non-asymptotic convergence rate\nremains unknown” ? From my understanding, the work from Defazio is non-asymptotic already ? (as it gives a bound for a given iteration number ?)\n- 2. Further on this point, it seems to me at first sight that the proof in the case of linear decay, in terms of the p-norm, is somehow a standard modification of a usual proof of convergence in such setting, but using generalizations of $\\ell_2$ inequalities to p-norms, but I may be wrong. If so, maybe the authors could describe in more details the fundamental difference with other usual proofs, except the use of the p-norm. (I guess in any case it can always be a mildly interesting feature to show such proof in the p-norm).\n\n- 3. **Minor typo:** in 3.2, the reference for the Figure 1 is missing (it is written Figure ??)", "was_revised": true, "final_justification": "As mentioned in the review and updated response, I am recommending accepting this paper as I think it provides interesting insights especially in the case of cyclical schedules. But my confidence score is low so I don't have a strong opinion regarding the final decision.", "rebuttal": "We sincerely thank the reviewer for their expansive and orderly comments, along with acknowledgment for our theoretical contribution on `Linear-D2Z` schedule, as well as our novel use of tools from non-linear time series theory for cyclical learning schedules. In the following, we address your concerns one by one. We warmly welcome any other additional suggestions that you might have. In the event you do not have any other concerns, we humbly request you to consider increasing your score.\n\n## Weaknesses:\n\n- **I think it would be good for that paper to compare in slightly more details to the result from Defazio et. al. (2023), in particular, in 2.3, what do the authors mean by “its non-asymptotic convergence rate remains unknown”? From my understanding, the work from Defazio is non-asymptotic already? (as it gives a bound for a given iteration number?)**\n\n*Response.* Thank you very much for your comment. We strongly agree that the work from Defazio is already non-asymptotic. However, we would like to clarify that in Defazio et al. (2023), the non-asymptotic rates have been provided for the error of loss functions, see for example the convergence of $\\mathbb{E}[f(x_T) - f_{\\star}]$ in their Theorem 1. Differently, the primary focus of our paper is to directly provide non-asymptotic convergence for the estimates $\\theta_n$ (denoted by $x_T$ in Defazio et al. (2023)), i.e., the moment convergence of $\\\\|\\theta_n - \\theta^{\\star}\\\\|_p$  for some  $p \\ge 2$. In general, the convergence rate of loss functions cannot imply the one of the estimates. While we do agree with your Question 1 that under our strong convexity assumption such result with $p = 2$ can be obtained, this leaves $p > 2$ still unexplored. We have revised this statement to make it more specific about the non-asymptotic rate for $\\\\|\\theta_n - \\theta^{\\star}\\\\|_p$ with $p > 2$ to avoid confusion.\n\n- **Further on this point, it seems to me at first sight that the proof in the case of linear decay, in terms of the p-norm, is somehow a standard modification of a usual proof of convergence in such setting, but using generalizations of $\\ell_2$ inequalities to p-norms, but I may be wrong. If so, maybe the authors could describe in more details the fundamental difference with other usual proofs, except the use of the p-norm. (I guess in any case it can always be a mildly interesting feature to show such proof in the $p$-norm).**\n\n  *Response.* We greatly appreciate your feedback. Indeed, the key of our proof for Theorem 2.2, the moment convergence of linear-decaying SGD, is not significantly different from the standard proofs but uses generalizations of the $\\ell^2$-inequalities to $p$-norms. However, we would like to clarify that the main goal of our work is to provide asymptotic theory for a broad class of learning rates, and we choose to include the linear decay one due to its popularity in learning schedules, as introduced by Defazio et al. (2023). We would say the most challenging proofs are those for cyclical step sizes, where one needs to introduce new tools to study the stationarity of the sequence. According to your suggestion, we have expanded upon this discussion and added a remark in our revision.\n\n- **Minor typo: in 3.2, the reference for the Figure 1 is missing (it is written Figure ??).**\n\n  *Response.* Thank you for bringing our attention to this. The broken link in question is indeed for Figure 1, and has been fixed in the manuscript.\n\n## Questions:\n\n- **Could the authors provide maybe more details on how this work, for the convergence rate in the case of the linear schedule, compares with the work of Defazio, and whether there is any fundamental difficulty to obtain their result compared to the one in Defazio? Especially when $p = 2$: the result of Defazio is a convergence result in objective function, but wouldn’t one be able to obtain a result in terms of $\\ell_2$ distance to optimality directly from the objective function bound, by using Assumption 2.1 at the optimum?**\n\n  *Response.* As we mention in our rebuttal to your **Weakness** 1, we do agree that when $p = 2$, the strong convexity assumption together with the non-asymptotic rate of loss-functions can indicate the rate of $\\\\|\\theta_n - \\theta^*\\\\|_p$. However, we would like to emphasize that it is still important to derive $\\ell^p$-type results given the high demand in real applications (please see our reply to your next question for examples) and the necessity of higher-moment convergence for other types of results such as almost sure convergence and convergence in distribution. Our $\\ell^p$-moment convergence can serve as a useful tool for these potential future studies.\n\n- **Why using the $p$-norm in Theorem 2.1 (instead of simply the $\\ell_2$ norm)? I may have missed the motivations behind it but if it is not present in the paper I guess the authors could elaborate on why it is important to prove a result in $p$-norm.**\n\n  *Response.* Thanks so much again for the great question. The $\\ell^2$ convergence does not capture higher-order moments, leaving the behavior of SGD in $\\ell^p$ norms unexplored. Higher-order moments, such as $\\ell^p$ convergence for $p > 2$, are particularly important in applications where large deviations or outliers must be penalized more heavily. For instance:\n\n  - In financial risk management, $\\ell^p$ norms are used to emphasize extreme losses in portfolio optimization and risk assessment (Rockafellar and Uryasev, 2000; Palczewski, 2018).\n  - In environmental sciences, $\\ell^p$ norms are valuable in modeling extreme events such as floods or pollution spikes, where average performance is less relevant (Katz, 2002; Kratz, 2019).\n  - In reinforcement learning, particularly in high-risk decision-making scenarios, penalizing large errors using $\\ell^p$ norms ensures that models learn to avoid catastrophic mistakes more effectively (Moody and Saffell, 2001; Tamar et al., 2015).\n\n  Moreover, if one aims to derive other types of non-asymptotic convergence rates such as the Berry–Esseen bound in Gaussian approximation, then higher-order moments would be required. We will add this discussion to our revision for clearer motivation."}, {"review_id": "eT8pgdYnJX", "reviewer": "Reviewer_H11d", "summary": "The authors propose a unified finite-sample analysis of vanilla SGD under arbitrary learning-rate schedules. 1) General moment bound (Thm 2.1). For any sequence $\\{\\eta_t\\}$, even when $\\eta_t$ depends on the optimisation horizon $n$, they bound the $p$-th moment error by an explicit two-term expression that separates the effect of the initialisation from a weighted sum of squared step-sizes. 2) Specialising Thm 2.1 yields what appears to be the first non-asymptotic MSE guarantee for the popular “linear-D2Z” policy $\\eta_t=\\eta(1-t/n)$ . 3) The authors prove convergence in distribution of the iterates to a cyclostationary process when $\\eta_t$ is $T$-periodic, filling a gap in existing theory . 4) Simulations on a handful of convex models illustrate the contrasting transient and terminal errors of five schedules (constant, cosine, linear-D2Z, polynomial, mixed-polynomial).", "questions": "1) In the first line of Assumption 2.2, an identity matrix in the right-hand side of inequality is missing. Why is this assumption called local strong convexity? What is the point of this assumption brought in the main body when it's not used?\n2) What is $|\\cdot|_{p}$ in Equation (2.2)? Where is it defined?\n3) Typo in line 200, \"Section 2.3\".\n4) Please provide a citation for line 207.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. Treating horizon-dependent and cyclical rates within the same inequality is elegant and may simplify future analyses.\n2. The general bound recovers known optimal rates for polynomially decaying steps and constant steps (up to logarithmic factors).\n3. Providing the first rigorous account of linear-decay and cyclical learning rates bridges a real gap between theory and what deep-learning practitioners actually use.\n5. Despite heavy notation, the paper is well structured (Section 1 to  2 to 3) and key ideas are summarised before each proof .\n\nWeaknesses: \n1) In my view, it's good to bring the technical novelty in the proofs to the audience's attention.\n2) The global strong convexity rules out the non-convex settings (deep nets, GANs) where exotic schedules are most used. So it could be nice to have these results under milder assumptions like PL inequality.", "was_revised": true, "final_justification": "The author’s reply fully resolves my concerns; I’m keeping my current rating.", "rebuttal": "We sincerely thank the reviewer for their thoughtful theoretically-oriented comments, highlighting our contributions on $p$th moment error bounds, our non-asymptotic MSE guarantee for the `Linear-D2Z` schedule, convergence to a cyclostationary process when the learning rate is periodic, and our comparison of multiple convex models pertaining to the theory discussed here. In the following, we address your concerns one by one. We warmly welcome any other additional suggestions that you might have. If our responses are satisfactory, we would greatly appreciate if you can consider a higher score.\n\n## Weaknesses:\n\n- **In my view, it's good to bring the technical novelty in the proofs to the audience's attention.**\n\n  *Response.* Even though most of our proofs are generalizations of standard arguments, the ones for the cyclical step sizes required us to introduce novel tools to study the cyclo-stationarity of the sequence. To address this comment, we have added remarks to informally introduce the main ingredients of the proofs whenever appropriate.\n\n- **The global strong convexity rules out the non-convex settings (deep nets, GANs) where exotic schedules are most used. So it could be nice to have these results under milder assumptions like PL inequality.**\n\n  *Response.* We thank the reviewer for raising this pertinent question. Indeed, global strong convexity rules out the non-convex settings, but we argue that most of our proofs can be modified to also hold under the *local strong convexity* assumption when the number of local minima is finite; also see Zhong et al., *Online Bootstrap Inference with Non-Convex Stochastic Gradient Descent Estimator*, Preprint 2023. Unfortunately, for non-convex regimes with uncountably many local minima, the error bounds may not be obtained in an $\\mathcal{L}_2$ sense, and it might be more convenient to look at regret bounds or convergence of $\\nabla F(\\theta_t)$.\n\n  Regarding the PL inequality, it is indeed a milder assumption, but its structure inherently prevents inference of the quantity $\\\\|\\theta_n - \\theta^\\star\\\\|$; instead, PL inequality is more suited for bounding $|F(\\theta_n) - F(\\theta^\\star)|$, which is not the focus of this paper. However, we agree that corresponding results may be obtained under PL inequality using not too dissimilar techniques, and we again thank the reviewer for pointing to this interesting research direction.\n\n## Questions:\n\n- **In the first line of Assumption 2.2, an identity matrix in the right-hand side of inequality is missing. Why is this assumption called local strong convexity? What is the point of this assumption brought in the main body when it's not used?**\n\n  *Response.* This is a typo on our part; it should be \"local strong concordance\", and we are sorry for the confusion caused. Many examples, such as logistic regression, do not satisfy strong convexity but satisfy the local strong concordance property. The reason we mentioned this assumption was to highlight that our proofs also go through almost verbatim under this condition. We elaborate on this below.\n\n  A recurring theme of our proofs is to show that:\n\n  $$\n  |\\theta - \\theta^\\star - \\eta \\nabla F(\\theta)|^2 \\leq (1 - \\eta c)|\\theta - \\theta^\\star|^2 \\quad \\text{for some } c > 0, \\theta \\in \\mathbb{R}^d.\n  $$\n\n  ### Proof via strong convexity\n\n  $$\n  |\\theta - \\theta^\\star - \\eta \\nabla F(\\theta)|^2 = |\\theta|^2 - 2 \\eta (\\theta - \\theta^\\star)^\\top \\nabla F(\\theta) + \\eta^2 |\\nabla F(\\theta)|^2 \\leq (1 - 2\\eta \\mu + \\eta^2 L^2) |\\theta - \\theta^\\star|^2\n  $$\n\n  so the inequality follows for small enough $\\eta$. Since we use decaying step size $\\eta_t \\propto t^{-\\beta}$, it holds that $1 - 2\\eta_t \\mu + \\eta_t^2 L^2 \\leq 1 - \\eta_t c$ for some $c > 0$ and large enough $t$.\n\n  ### Proof via local strong concordance\n\n  Define $\\phi(u) = F(\\theta^\\star + u(\\theta - \\theta^\\star))$ for $u \\in [0, 1]$. Assume $|\\theta-\\theta^\\star|\\leq R$. Then:\n\n  $$\n  \\phi''(0) \\geq \\mu^\\star |\\theta - \\theta^\\star|^2, \\quad \\phi''(u) \\geq \\phi''(0) \\exp(-C|\\theta - \\theta^\\star|u)\n  $$\n\n  and:\n\n  $$\n  (\\theta - \\theta^\\star)^\\top \\nabla F(\\theta) = \\phi'(1) - \\phi'(0) \\geq \\mu^\\star |\\theta - \\theta^\\star|^2 \\cdot \\frac{1 - \\exp(-C|\\theta - \\theta^\\star|)}{C|\\theta - \\theta^\\star|} \\geq \\mu^\\star C \\exp(-R) |\\theta - \\theta^\\star|^2\n  $$\n\n  which plugs into the earlier inequality to yield the desired bound. This explanation has also been added to the manuscript.\n\n- **What is $\\\\|\\cdot\\\\|_p$ in Equation (2.2)? Where is it defined?**\n\n  *Response.* Assuming that you meant $\\\\|\\cdot\\\\|_p$, we define it as $\\\\|X\\\\|_p = \\left(\\mathbb{E}[|X|^p]\\right)^{1/p}$. This definition has now been added to the manuscript. We also clarify that $|\\cdot|_p$ in your question refers to the vector $\\ell_p$-norm, which is now also included in the text.\n\n- **Typo in line 200, \"Section 2.3\".**\n\n  *Response.* Thank you for pointing this out. This should have been \"Section C.4\", and has been corrected.\n\n- **Please provide a citation for line 207.**\n\n  *Response.* On line 207, we refer back to citations already introduced in lines 103–104: Loschilov and Hutter (*SGDR: Stochastic Gradient Descent with Warm Restarts*, ICLR 2017), Smith (*General Cyclical Training of Neural Networks*, 2023), and Wang et al. (*An Empirical Study of Cyclical Learning Rate on Neural Machine Translation*, 2023). We’ve added these citations to the relevant sentence for clarity."}, {"review_id": "TWU6zmgQVp", "reviewer": "Reviewer_RA5h", "summary": "This paper studied the convergence analysis of SGD with general learning rate that is more aligned with practice. They introduce a unified framework that quantifies the uncertainty of online SGD under arbitrary learning-rate choices. Specifically, they explored cyclical learning rates and linear decaying learning rate. Experiments validate the theoretical findings.", "questions": "1. Reference error: Line 271 ?? \n2. See weakness.", "limitations": "See weakness.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: 1) the problem they studied is important to analyze the theoretical performance of practical working step sizes. 2) the analyzing tools are innovative. The theoretical finding is novel and inspiring. \n\nWeaknesses: (1) For the cosine learning rate, which is widely used in practice, only experimental results are provided, with no accompanying theoretical guarantees. \n\n(2) Theorems include too many assumptions, and their roles—as well as the classes of problems that satisfy them—are not clearly explained. For example, how can condition (2.7) be satisfied in practice? \n\n(3) The experimental evaluation is limited. Although the authors validate various theoretical results through experiments, all experiments are conducted on linear regression problems. No large-scale experiments are included to demonstrate the scalability of the theoretical conclusions to more complex models.\n\n(4) It would be helpful to include a direct comparison of convergence rates with those from existing literature to highlight the effectiveness and novelty of the new proof technique.", "was_revised": true, "final_justification": "The author's response solves all of my concerns so that I will keep my score.", "rebuttal": "We sincerely thank the reviewer for highlighting our practice-oriented analysis, our unified framework for quantifying uncertainty under arbitrary learning rate choices and our focus on cyclical and linearly decaying rates. We also appreciate the recognition of our innovative tools for analysis and the novel theoretical findings. In the following, we address your concerns one by one. We warmly welcome any other additional suggestions that you might have. If our responses seem adequate, we humbly ask you to consider an increase in your score.\n\n## Weaknesses:\n\n- **For the cosine learning rate, which is widely used in practice, only experimental results are provided, with no accompanying theoretical guarantees.**\n\n  *Response.* We respectfully point out that the cosine learning rate schedule is a special case of the periodic learning rate schedule, discussed in Theorem 2.4.\n\n- **Theorems include too many assumptions, and their roles—as well as the classes of problems that satisfy them—are not clearly explained. For example, how can condition (2.7) be satisfied in practice?**\n\n  *Response.* We acknowledge the reviewer’s point that our assumptions, including Condition (2.7), could benefit from clearer contextualization and justification regarding practical applicability. In particular, (2.7) is a rather technical condition, and formal verification of such conditions requires knowledge of problem-specific parameters $p$ and $\\mu$, which are often unknown. A detailed theoretical analysis might involve characterizing cyclical edge of stability, which promises to be an interesting research direction. In practice, however, as long as at least some of the $\\eta_i$ are small, we expect this condition to hold—this is also evidenced by our numerical experiments. We have added this comment in a remark accompanying Theorem 2.4.\n\n  Similarly, equation (2.1) can be interpreted as requiring that step sizes are not too large. The rest of the technical assumptions, such as Assumptions 2.1 and 2.3, are standard in the literature (see, e.g., Polyak and Juditsky, *Acceleration of Stochastic Approximation by Averaging*, SIAM Optimization, 1992), and therefore we do not dwell on them in detail.\n\n- **The experimental evaluation is limited. All experiments are conducted on linear regression problems. No large-scale experiments are included.**\n\n  *Response.* To address this, we present results from a simulation using $n = 10^5$ and randomly initialized $\\theta_0$:\n\n  $$\n  y_i = \\theta^{(0)} + \\theta^{(1)} x_i + \\varepsilon_i,\\quad \\varepsilon_i \\sim \\mathcal{N}(0,1),\\quad \\theta^* = (\\theta^{(0)}, \\theta^{(1)})^\\top \\in \\mathbb{R}^2\n  $$\n\n  where $(x_i, y_i) \\in \\mathbb{R}^2$ is the observed data. Results are averaged over 500 SGD runs.\n\n  **Table: Final and Minimum MSE for Cosine Learning Rate Schedules**\n\n  | Schedule                         | Final MSE | Min MSE | Final SE SD | Mean SE SD (last 100) | Iteration Range |\n  |----------------------------------|-----------|---------|--------------|------------------------|------------------|\n  | 0.1 · (1 + cos(2$\\pi$t / 3))         | 0.1713    | 0.1103  | 0.1743       | 0.2334                 | 500–5000         |\n  | 0.05 · (1 + cos(2$\\pi$t / 3))        | 0.0805    | 0.0484  | 0.0777       | 0.0912                 | 500–5000         |\n  | 0.01 · (1 + cos(2$\\pi$t / 3))        | 0.0158    | 0.0101  | 0.0136       | 0.0144                 | 500–5000         |\n\n  We also conducted new experiments on MNIST. We trained a multiclass logistic regression model via SGD using both cosine and `Linear-D2Z` learning rate schedules. Images were flattened to $x \\in \\mathbb{R}^{784}$ with one-hot label $y \\in \\{0,1\\}^{10}$, minimizing sigmoid loss $\\mathcal{L}(x, y; \\theta)$ with $\\theta \\in \\mathbb{R}^{784 \\times 10}$.\n\n  **Table: Sigmoid Loss Estimate for the `Linear-D2Z` Schedule on MNIST**\n\n  | Number of Iterations | MSE    | Standard Deviation |\n  |----------------------|--------|---------------------|\n  | 500                  | 0.0059 | 0.0046              |\n  | 1000                 | 0.0042 | 0.0020              |\n  | 1500                 | 0.0041 | 0.0015              |\n  | 2000                 | 0.0034 | 0.0018              |\n  | 2500                 | 0.0034 | 0.0013              |\n  | 3000                 | 0.0035 | 0.0012              |\n  | 3500                 | 0.0033 | 0.0011              |\n  | 4000                 | 0.0032 | 0.0011              |\n  | 4500                 | 0.0032 | 0.0012              |\n  | 5000                 | 0.0031 | 0.0011              |\n\n- **It would be helpful to include a direct comparison of convergence rates with those from existing literature.**\n\n  *Response.* We highlight that our work is among the first to derive convergence rates for linear-decaying and cyclical learning rates. For $p=2$, Theorem 2.2 aligns with Defazio et al. (2023), Corollary 2. Our rate of $1/\\sqrt{n}$ matches theirs under strong convexity. In contrast to constant learning rates (which retain fixed bias) or polynomial decay (with slower $\\exp(-cn^{1-\\beta})$ convergence), linear decay achieves $\\exp(-cn)$ forgetting. This showcases the novelty and strength of our results.\n\n## Questions:\n\n- **Reference error: Line 271 ??**\n\n  *Response.* Thank you for pointing this out. The broken reference was for Figure 1 and has been corrected."}]

Author rebuttal:

Meta-review: This paper analyses the convergence of SGD with some learning rate schedules commonly used in practice such as linear decay to zero and cyclical schedules. The aim was to fill a gap between these widely learning rate schedules and existing theory, which focuses mostly on polynomially decaying or constant step sizes. The main contributions include general non-asymptotic convergence bounds applicable to a wide range of schedules, explicit rates for linear decay, and the first rigorous results on the limiting distribution under cyclical learning rates using ideas from nonlinear time series analysis. Reviewers agreed the theory is correct and original, and that the results are well-motivated and may have substantial impact.

The main limitation is that the experiments could be more extensive. While some technical assumptions (e.g., strong convexity, etc.) limit direct applicability to deep models, the authors provided an extension of their result under weaker assumptions, and promised further improvement and clarification to the presentation. It is critical that the authors incorporate all promised changes into the camera-ready version.
Decision: Accept (poster)