SGD with memory: fundamental properties and stochastic acceleration
Authors: Dmitry Yarotsky
Maksim Velikanov
Venue: ICLR 2025 Poster (2025)
Keywords: Stochastic Gradient Descent
SGD
spectral power laws
acceleration
effective learning rate
quadratic problems
stability
Heavy Ball
momentum
Primary area: optimization

Abstract: An important open problem is the theoretically feasible acceleration of mini-batch SGD-type algorithms on quadratic problems with power-law spectrum. In the non-stochastic setting, the optimal exponent $\xi$ in the loss convergence $L_t\sim C_Lt^{-\xi}$ is double that in plain GD and is achievable using Heavy Ball (HB) with a suitable schedule; this no longer works in the presence of mini-batch noise. We address this challenge by considering first-order methods with an arbitrary fixed number $M$ of auxiliary velocity vectors (*memory-$M$ algorithms*). We first prove an equivalence between two forms of such algorithms and describe them in terms of suitable characteristic polynomials. Then we develop a general expansion of the loss in terms of *signal and noise propagators*. Using it, we show that losses of stationary stable memory-$M$ algorithms always retain the exponent $\xi$ of plain GD, but can have different constants $C_L$ depending on their *effective learning rate* that generalizes that of HB. We prove that in memory-1 algorithms we can make $C_L$ arbitrarily small while maintaining stability. As a consequence, we propose a memory-1 algorithm with a time-dependent schedule that we show heuristically and experimentally to improve the exponent $\xi$ of plain SGD.

Published as a conference paper at ICLR 2025
SGD WITH MEMORY: FUNDAMENTAL PROPERTIES
AND STOCHASTIC ACCELERATION
Dmitry Yarotsky
Maksim Velikanov
Skoltech,
Technology Innovation Institute, CMAP, Ecole Polytechnique ma ksim, vel www.iittiiiiii....
Steklov Mathematical Institute
d. v. b.yyroossy@skkltechh
ABSTRACT
An important open problem is the theoretically feasible acceleration of mini- batch SGD-type algorithms quadratic problems with power-law spectrum. In the non-stochastic setting, the optimal exponent Ç in the loss convergence Lt Cgt= double that in plain GD and achievable using Heavy Ball (HB) with a suitable schedule; this no longer works in the presence of mini-bat batch noise. We address this challenge by considering first-order methods with an arbitrary fixed number M of auxiliary velocity vectors (memory-M algorithms). We first prove an equivalence between two forms of such algorithms and describe them in terms of suitable characteristic polynomials. Then we develop general ex- pansion the loss terms signal and noise propugators. Using it, we show that losses of stationary stable memory-M algorithms always retain the exponent & of plain GD, but can have different constants CL depending on their effective learning rate that generalizes that of HB. We prove that in memory-1 algorithms we can make Cz arbitrarily small while maintaining stability. As a consequence, we propose memory-1 algorithm with time-dependent schedule that show heuristically and experimentally to improve the exponent & of plain SGD.
INTRODUCTION
Optimization is a central component of deep learning, with accelerated training algorithms provid- ing both better final results and reducing the large amounts of compute used to train modern large models. The key aspects of this optimization is huge number of degrees of freedom and the batch- wise learning process. The theoretical understanding of even simple gradient- based algorithms such Stochastic Gradient Descent (SGD) is currently limited, and their acceleration challenging.
Deep neural networks can be approximated with linear models when close to convergence or in wide network regimes (Lee et al.) 2019 Fort al.) 2020). For regression problems with MSE loss, this leads to quadratic optimization problem. The resulting spectral distributions the eigenvalues A of the Hessian and the coefficients eı of the expansion of the optimal solution w. over the Hessian eigenvectors are often well described by power-laws when numerically computed on real-world data (Cui al. (202T): Bahri al.) (202T); (Wei al.] (2022). see more details and related work in Sec. A). With this motivation, we focus on dineen-odinniionall quadratic problems, and especially (but exclusively) those with power-law asymptotic form eigenvalues Å and coefficients og:
A AA (1 + o(1)), --+ 00;
d = (1 + o()), 7
(1)
These power laws can be thought of as stricter versions of the classical capacity and source con- ditions (Caponnetto & De Vito 2007). Convergence rates of different first-order algorithms determined by the eigenvalue and target exponents v, >>
Theoretically more tractable are stationary algorithms, i.e. with deration-independeen parameters. In the non-stochastic setting, both stationary GD and Heavy Ball (HB) exhibit the same loss rate S) (Nemirovskiy & Polyak 1984). In the presence of mini-batch noise, analysis of convergence becomes more challenging, with only the recent works Berthier et al. (2020); Varre et al. (202I) showing that the rate of stationary GD remains (t--)) for sufficiently hard targets with Ç <

---

Published as a conference paper at ICLR 2025
Goussian data with (2, v)= =0 (0.5, 3)
MNIST
Jacobi scheduild HB
[SIGD and our aigonthim
Jacobi scheduled HB
ISiGD and our algortthm
10
20
201
helfbrch
SGD:
RI-10
GED: [R]-10
10a
[B)=10
10
AMT: nai-barth
B1-202
ANT hathh
18)-100
AM2: [80m1
20- B1-1020
AM2: (8)=10
20-2
10
Figure 1: Divergence of Jacobi accelerated HB vs. stability of our accelerated memory-1 (AMI) method. For both synthetic Gaussian data (left) and MNIST classification with shallow ReLU net- work (right), Jacobi HB enjoys the accelerated rate L₁ (t(t(()) in full-batch setting, but even- tually diverges in stochastic one. Increasing batch size only delays the loss explosion. In contrast, our AMI algorithm, although having weaker acceleration than full-batch Jacobi HB, is stable for small batch sizes and a long training duration. For Gaussian data with an ideal power-law spectrum, dashed lines show theoretical loss power laws with predicted exponents (t~ for SGD and (-<(1+))) for AM1) and asymptotically match the experimental loss trajectories. Here ã 0 is the schedule exponent of the effective learning rate Oefff, R t used by AMI algorithm. See precise definition of the AMI schedule and parameters in sec. 6 Also, see sec. M for figure details and extra experi- ments.
while slowing down by noise to (t for casier targets with < > 2 - 1. In the rest of the paper, we will refer these two regimes as signal- and noise-dominated, respectively.
With non-stationary algorithms, the rate in non-stochastic setting can be accelerated to O(t 2C) using HB with schedule of learning rate and momentum based on Jacobi polynomials (Brakhage) 1987]. However, in the stochastic mini-batch setting we are not aware of similar acceleration results for general v, in the literature. Moreover, in Fig. [ we show that direct application of HB with Jacobi schedule to noisy problems consistently leads to divergence of the optimization trajectory.
Previous works point to connection between the observed divergence of Jacobi scheduled HB and a weaker (constant-level) acceleration of the stationary algorithms. Under power law spectrum (I) stationary Heavy Ball in both non-stochastic (Velikanov & Yarotsky 2024 and signal-dominated stochastic (Velikanov et al. 2023) settings has the loss asymptotic L ~ Czt-S, While the exponent Ç is fixed, the constant Cr. can vary greatly with learning rate a and momentum parameters of HB as Cr. (S where aeff T-3 is the effective learning rate. On the one hand, non- stochastic setting allows to take 8 + without destroying the stability of the algorithm, making the constant Ct arbitrarily small. In a sense, this mechanism is behind the Jacobi scheduled HB with the accelerated rate O(t-2c) which slowly takes &r + along the optimization trajectory. On the other hand, Velikanov et al.] (2023) shows that maintaining stability under a mini-batch sampling noise requires Oeef be bounded, thus putting lower bound on the loss constant Ct.-
Our contributions. In this work, we overcome the above limitation by developing a general framework to analyze loss trajectories of broad family of first-order methods. Then, we identify a region in the space of update rules that achieves acceleration while being stable. Specifically:
1. Memory-M algorithms. We define a broad family of first-order algorithms that allow to store an arbitrary fixed amount M of auxiliary vectors (i.e. generalized velocities), and use any linear combinations of them in gradient computation and parameter update. First, we connect these memory-M algorithms with other multistep first-order methods. Then, in the mini-batch setting, we provide unified description of their loss trajectories in terms of expansion in various combinations of elementary signal and noise propagators.
2. Combinatorial approach to loss asymptoties. We use the obtained propagator expansion to enrich in several directions the phase diagram of mini-bateh SGD converges rates, for stationary algorithms. First, we show that the same signal-dominated O(t-S) and noise- dominated O(t (2- rates remain valid for any memory-M algorithm. Second, we give simple interpretation of the two phases in terms of propagator expansion: the loss in
2

---

Published as a conference paper at ICLR 2025
the signal- (resp, noise-) dominated phase is asymptotically mostly determined by config- urations including one long signal (resp, noise) propagator. Finally, we generalize effective learning rate aeff from HB to all memory-M algorithms, and show that it largely deter- mines the constant Cz. in the loss asymptotic.
3. Accelerated update rule. We then focus on general memory-1 algorithms. First, we find explicit expressions for loss asymptotic and full stability conditions of general stationary memory-1 algorithms. Then, in this space of stable algorithms, we find a region with arbitrary large effective learning rate Oeff, which translates into arbitrary small constant CL in the loss asymptotic. The update rule in this region can be obtained by adding an extra learning rate to HB. Finally, we design schedule that travels deep within the region in a power-law manner, and demonstrate that it achieves accelerated convergence rates up to Ott 5(2 ((2-))) in the signal- -ignal-dominatd phase.
2 THE SETTING
We consider the regression problem of fitting target function yxx with a linear model f(w, x) = X, w). Inputs x and parameters w are elements of a (infinte-dimensionaa) Hilbert space H. and (.-) denotes the scalar product in H. Inputs x are drawn from distribution p on H. and we measure the loss of the model as L(w) {x (xx w) y(x))² Importantly, we assume that the target function is representable in as yx) = (x, w.), and require only the norm Fx=ply(x)² of the target but not of the optimal parameters w. to be finite. This setting is relevant to kernel methods or overparametrized neural networks, with x being the mapping of original inputs to either kernel feature space gradients of the model, respectively; see Sec. A for more details. This brings to the quadratic objective
1 (Aw, HAw) L(w) 2
H = Xxxp|xx00 xx),
(2)
where H is the model's Hessian and Áw w W..
We will always assume that the Hessian H has discrete spectrum with eigenvalues A Y 0, A + O.
We will also often (but not always) assume that the eigenvalues d and the respective eigenexpansion
coefficients C2 = (ck, w.) of w. obey power laws
[ with some v/ Ç > O. We allow the "infeasible" (w., W.) O0.
case 0 Ç when (w., Hw.) ) < oc but l|w.
For stochastic optimization, we consider the random mini-batch setting. At each iteration t we choose a batch B (x: of B| i.i.d. samples from p. and compute the gradient the respective empirical loss (g() = 2 E (ix,, Aw)) We focus on the evolution of the mean loss L, = [[L(W:)] averaged w.r.t. the choice of all the batches B,...., B, along the optimization trajectory.
3 GRADIENT DESCENT WITH MEMORY
General form of the algorithm. We start with describing our gradient descent with memory in the non-stochastic setting. While later we will specialize to quadratic objectives as in Eq. (2). GD with memory can be defined as the first-order minimization method applicable any loss L:
Wi+1 We - u1+1
Ot by" D.) (VL(W, af uf!)) U.:)) t= 0, 1,2, u,
(3)
Cr
Here, W. is the step-t approximation to an optimal vector w., and u, is an auxiliary vector rep- resenting the "memory" of the optimizer. We assume that these auxiliary vectors have the form (u(1).. ....
( ())T with (mm) H; in other words, u, is size-M column with each compo- nent belonging to the same space H as the vector w.. We will refer to M as the memory size. The parameters oe (learning rates) are scalar, the parameters ar, b C2 M-dimensional column vec- tors, and Dj are M x M scalar matrices. By a. u, we mean Em= a u (m) where a, (m) are the scalar components of the vector a, The algorithm can be viewed sequence of transformations of size-(M + 1) column vectors ( w: n, ) with H-valued components.
Note few important special cases:
3

---

Published as a conference paper at ICLR 2025
1. The basic gradient descent (GD) Wi+1 Wi a4 (we) is the memory-0 case.
2. The Heavy Ball (a.k.a. GD with momentum, Polyak 1964)) can be defined by the two-step recurrence Wi+1 W. at VL(w,) + 3, W. can be cast in the form (3) with
memory M = 1 by introducing the auxiliary vector u,
W
We+1 We =
Bt Br
V VL(())) ur
(4)
Ux+1
Ctt
3. Averaged GD (Polykk & Juditsky 1992) can be defined by We - w.. where Wi+1 Wi az (WW) (I.e., the onginal GD trajectory Wi is subsequently averaged, usually with the purpose of noise suppression). can be cast in the form (3) with memory M = by introducing the auxiliary vector u, W. We
Wo+1 we ( U1+1
(- Oet
VL(W, + -u:)) Up
(5)
Flammarion & Bach (0155) consider wider family of memory-1 algorithms that also includes Nesterov's 's accelerated gradient (Nesterov 1983). Some algorithms in the literature use memory size larger than 1 (Varre & Flammarion 2022).
Iterations (3) thus represent a general framework encompassing various standard algorithms. The first entry in the l.h.s. is written Wi+1 w, because it is natural to have all matrix elements in Eq. (3) shift- invariant while the sequence w. is naturally shift- eeffvarauuaaiann (see (see B.I.
Clearly, there is some redundancy in the definition of the algorithms (3). In particular, any linear transformation uı- = C,u, of the auxiliary vectors with some non-degenerate M x matrices C₁ produces equivalent algorithm, having new parameters a/. by, c, D/. but preserving the trajectory W₁. A large part of our work will be focused on the stationary setting, i.e. when a, a, b, c, D are t- independent. In this setting we will be able to largely remove redundancy by going an equivalent form of the dynamics.
We assume now a quadratic objective L in Eq. HAw and iterations 3 acquire the form
Quadratic losses.
In this case VL(w)
Awr+1 U1+1 >
- [
by D.
- at (1, aT)
Aww 11
(6)
Ct
Here, Awr) is viewed as an element of the tensor product H. @ R M+1 the operator acts in the first factor, and the rank-1 matrix ( (=a ) a. in the second. In particular, Aw, and u, are eigenvectors of H with eigenvalue A, then
Awz+1 u
Aw: u1
Sx. = [6 D.) +
(-at) Ct
(1, a. )
= Sx,
and the new vectors AW1+1 Ue+1 are again eigenvectors of H with eigenvalue X. As result, performing the spectral decomposition of Aw; u, reduces the original dynamics (3) acting in H & [RM+1 to a X-indexed collection of independent dynamies each acting RM+1
Equivalence with multistep recurrences. As noted carlier, Heavy Ball can be alternatively writ- ten either in the single-step matrix form 4 with auxiliary vectors u,, or as the two-step recurrence W W, as VL(w.) + (w, w:-1) not involving auxiliary vectors, but involving two previous vectors w,, w:-1- A natural question is whether a similar equivalence holds for general algorithms 3 It appears that there is no such equivalence for general loss function L. However, is quadratic as in Eq. (2) and, moreover, the parameters a, a, b, c, D are L-independent, we can prove an equivalence of (3) multistep iterations
WI+++ Σ Puu Wt m Σ 4m VL(Wetm), t t= 1,1,...
where ΣM Pm =
1. Such iterations can be viewed as general stationary shift- thift-invariant algorithms linearly depending on O'th and I'st order information from previous M steps.
4

---

Published as a conference paper at ICLR 2025
Theorem B.2). Suppose that the loss is quadratic as in Eq.
1. Given any t-independent parameters a E R. a, b, C. D E RMXM, define constants
(pm) m (9m) m to be the coefficients in the polynomial expansions
M
Pm = x M+1 - (xr 11)
1)del(( -
-D),
(9)
m=0
Σ 2m det (a'c-a a² 100--b4 b² m=0
-- ).
(10)
c
Then Σm Pm 1 and any solution (w: of matrix dynamics
obeys recurrence
2. Conversely, given constants (pm )M m= (qmn )m such that E Pm 1, there exist pa-
rameters IR, a, b, RM, ,D RMX such that any vector sequence Wt generated
by recurrence (8) satisfies the respective l-independent memory-M matrix dynamics (3) with suitable auxiliary vectors u, Moreover, can
0 and b (1......,0)) 0)
Theorem [ along with its proof provide a constructive correspondence between the two forms of
iterations. The fact that we can a 0 when converting recurrence (8) to matrix iterations (3)
(statement 2) shows that for quadratic losses and stationary dynamics the possibility of shifting the
argument VI. with a * does not increase the expressiveness of the algorithm.
The natural non -oa-stationary analog of Theorem 1 fails to hold in general:
Proposition
BB.). There exist non-stationary dynamics
with M that cannot be written
in the form W Pt,1 We+1 Pr.ow + WW(W:+))+W++)). (we), even for quadratic problems.
4 BATCH SGD WITH MEMORY
Evolution of second moments. SGD with memory is defined similarly to GD with memory 3 but with the batch loss LB instead of L.
For quadratic loss functions, we saw the deterministic GD with memory reduced to a simple evolu- tion (6) of the state (Arr)) Such description no longer feasible for SGD, but we can describe deterministically the evolution of the second moments M, of the state u.
(Aw:)
M. = (3} J. v.), C, E[Aw @ Awe,,
J. = E[Aw, & uf
V, = E
& uf
J.
(11)
The moments C, determine the loss J., = TH(H.,)) A direct computation (see sec.
C.
yields
M = (()
bf" +
au Ct
(1, (1,
M.
(0
by"
+
(ai ct
(1,
(12)
Dt
Dj
+ B
Ep
MM,
8
(-oz
c₂),
(13)
ct
where
Ex Cx)x HCH.
(14)
The term in line 12 corresponds to the noiseless dynamics, while the term in line 13 reflects the stochastic noise vanishing the limit of batch size [B] - cc. The map (C) preserves the
positive semi-definiteness of C (see Lemma so the term in line (13) is also positive semi-definite,
and L, is always not less than its counterpart for the deterministic GD with memory.
For general p. the first term in Mn cannot be expressed via H. thus preventing from describing the loss evolution in terms of the spectral information A Ck- Following Velikanov et al. (2023), we overcome this by replacing E, with the Spectrally Expressible (SE) approximation
(C) = Tr[HC] - HHH
(15)
(1),)))) in Lemma with some parameters Tı, 72- We list basic properties of E preserves semi-definiteness of C whenever TI 72-
In particular, 2 (7)))
5

---

Published as a conference paper at ICLR 2025
We can look at this replacement in two ways. First, Velikanov et al. (202)) show that, for certain choices of 71, 72, the equality Σn = SS holds exactly several natural special scenarios (gaus- sian and translation-invariant data) and approximately for a number of real- world problems such as MNIST classification. Second, generalizing earlier ideas of Bordelon & Pehlevan (2021) and "uniform kurtosis" assumptions (Varre & Flammarion, 2022). show that the loss obtained with ((r,.Ta) can serve as an upper or lower bound for the loss obtained with E.p
"SE
Proposition 2 (.2).. Denote by (P) and Li (TTTTa) the losses obtained using the same initial condi- tion Mo 2 0 and either the map Ep or the map 2S
2x(1.12) in iterations (13), respectively. Suppose
(C)) for all C 2 0, then I.() I I, 1.(7.5a) for all t.
that 0 S 2 72. Then, if (C) S SS
Conversely, if (C) 2 (TTT,TT)) (C)
(C) for all C O, then L! 2 L, (T.rt)) for all t.
SE
Loss expansion. The key role in the subsequent analysis is played by an expansion of I in terms of scalar quantities that we call propagators. To simplify the exposition, we assume now and in the next section the stationary setting (see Sec. D for the non-stationary generalization), Consider the
linear operators Ax R (1+ (I M) R M) (1+-M) associated with the eigenvalues À of H:
A,2 = S,Zsk B z()
(16)
The where SΛ are the noiseless eigencomponent evolution matrices defined in Eq. 77) The operators A describe the M matrix iterations (13) in their diagonal eigencomponents w.r.t. H. If the SE parameter = O, then A simply implements the adjoint action of S on matrices, A = Sx @ Sx. but in general A also includes the effect of the HCH term in the SE noise (15).
Enumerate the cigenvalues of H as λR. and let oz = =eex, w.)² 2 be the respective amplitudes of the target w*, We define the signal propagators Ve, Vi by
Ve = Σ (()),, (18)).
Vi' - AEE (
(17)
where (A, B)- Tr(AA') is the standard inner product between matrices. Note that the difference between V22 and Vú is only in taking this inner product either with (6 with (
We also define noise propagators Uz, Uy (with a similar difference between them) by
U. =
(==) (o=K)) ))) U
Σ (2) A (
(-)))
B
R
(18)
Theorem DD. Assuming Wo O, un for any = 0, 1....
L = 2 (V++ (Ve1 + Σ Σ
U4i1 U 1m-1 Im 1m
U/ U/2tts Vi).
(19)
m==10kh S.CCIS....t.. S... <t+
This expansion results from considering all the configurations in which the iterations are divided into those where we apply the operators Ax, and into remaining .,...., I' where we apply the first term 7ı [rCH the SE noise (15). In the former iterations the states evolve independently in the eigenspaces of H. whereas the latter act rank-1 operators aggregating the states across all eigenspaces. Thanks to the rank-1 property, the loss the configuration is factored as the product of scalar signal- and noise propagators that describe the eigenspace evolutions taken over iteration intervals (tg, +++1) and aggregated at their ends. Each product includes one signal propagator asso- ciated with the evolution of the initial residual Awo
w., and some number of noise propagators associated with the evolution of the noise injected at (,,...,4 4m- The propagators U, V end at the loss evaluation time t, while the propagators U', V' end at one of the noise injection times ti,..., tm- Note that if a = 0, then Ug can be identified with U/ and V2 with V/"
5 STABILITY AND CONVERGENCE OF STATIONARY MEMORY-M SGD
Preliminaries. We will now use loss expansion 19 establish various general stability and convergence properties of stationary SGD with memory. It will be convenient to assume henceforth that all the propagators U,, U., Vi, V, are nonnegative. 2 0, 72 < 0, since for I 0 the maps A preserve positive definitefntssness (see Eq. (16).
particular sufficient condition for this is
Proposition 3. T 2 0 and T2 S 0, then all UH, U. Vi V 2 0.

---

Published as a conference paper at ICLR 2025
Immediate divergence. Recall that dim H. = co and the Hessian H has infinitely many eigenvalues. In this case, even single propagators Ug. Vi,V, may diverge. Note that U/ = (a"c a²² > X and VV = -E ArCE. Accordingly, necessary conditions to avoid divergence in one step for generic a, a are Ee X < xo and Σx Ax < oc. These conditions are clearly also sufficient ensure Ur, Ug Vi, Vi oo for all t. Under power law spectral assumptions [T] we
Ur
automatically have Σx A&ch < co, while Ex X < <o is fulfilled whenever v >
Convergence of the propagator expansion. We analyze now loss expansion 19) and relate con- vergence of L to properties of the propagators. Introduce the sum U3= = Et=1 U, and analogously the sums Ug Vg, V/3 of Uy Vi, V, To simplify exposition, we state the next theorem for the case when U, = 0 and V Vi for all I, which holds if a = 0. See Section G for the general version.
Theorem F Let numbers L, be given by expansion 19 with some U. = U 2 0, Vi = V, 2 0.
1. [Convergence] Suppose that Uy < 1. Art - x0, Vf, O(1) (respectively, V₂ = o(1)),
then also L, = (1) (respectively, I, = o(1))
2. [Divergence] Us; > 1 and V, > 0 ffror al least one I, then sup;=1,2,... Ttp = 50.
3. [Signal-dominated regime] Suppose that there exist constants εv, Cv > 0 such that V, = Cvl-Ev (1 + o(1) as L + xc. Suppose also that Us. < 1 and U, ((t- with some &u > max 1). Then
Cv $v (1+)(1))
L. 2(1 2sx
(20)
4. [Noise-dominated regime] Suppose that there exist constants &y > Et > C, 0 such that U2 = Cut Eu (1 o(1) and V, = O(t-5v) 5V) as t + co. Suppose also that Us < 1. Then
V&CC 2s:-
L.
t Eu (1 (1+
(1))
The first two statement characterize convergence in general, while the last two describe the regimes occurring under power-law propagator decay assumptions. Note that in the non-stochastic GD set- ting the noise propagators U, vanish so that L, 2 V141. Then, statements and say that con- vergence of SGD with memory is equivalent to that of the respective non-stochastic GD plus the condition Uy: < 1. In the general case of a o O, when Us: + U'S the condition is U'-- < 1 (Sec. G
p1p have simple meaning (see Fig. 2 right). In the signal-dominated case the leading contribution to Ta in expansion (19) comes from terms having one long signal propagator and several short noise propagators. The factor Cvt-Ev in Eq. (20) comes from the long signal propagator, while the coefficient (1 - Us} is the accumulated contribution of the noise propagator products, summed over all possible partitions. In the noise-dominated case, the leading terms have one long noise propagator contributing the factor Cv in Eq. (2.). The coefficient
Formulas 20
Vi: (1-Us}" is the accumulated effect of remaining short propagators before and after the long noise propagator.
Stability of the maps Ay. Now we start analyzing the particular form (7). 18 of our propagators
U,, Uf, Ve, Vi. Note first that the linear matrix maps A = (Ax) defined in Eq. (6) may not be stable in the sense of having eigenvalues larger than 1 in absolute value. As a result, this would generally lead to an exponential growth of the propagators and hence an eventual divergence of L,.
At A = 0, Ax= acts as the tensor square Sx=0 @ Sx=0, and its eigenvalues are the products 11 where μi, #2 are the eigenvalues of Sx=0- The eigenvalues of Sx_0 are just and the eigenvalues of D. We will assume henceforth that all the eigenvalues of D are strictly less than in absolute value. We will refer to matrices with this property as strictly stable, When D strictly stable, Ax=0 has the simple leading eigenvalue 1 with the eigenvector M, = ( 8). All the other eigenvalues of Ax= are less than in absolute value. This condition generalizes the standard condition [3]]
for the momentum (Tugay& & Tanik 1989 Roy & Shynk 1990).
As increases, A₁ acquires more complicated form, and its eigenvalues continuously deform from the cigenvalues of Ax It is hard to give exact condition of stability for general À and ma but prove the following:
7

---

Published as a conference paper at ICLR 2025
Signal-dominated
Immeddate divergence Ex A/
U U
V
IH
Eventual divergence Σ, Ai < cc, Ee A
t1 txt2
MMIST-MI
Noise dominated L(t) x gl/m1
Noise-dominated
Signal dominated
U t5 1
U'
V U
L(11
2
t3 t1
Figure 2: Left: The phase diagram of stationary SGD with momentum from Velikanov et 2023 Theorems 3 show that it remains valid for general memory size M. Right: Leading terms in the loss expansion (9)). In the signal-dominated phase the leading terms have one long signal propagator V' and many short noise propagators U". In the roise-dominater phase the leading terms have one long noise propagator U", while the other propagators U and the signal propagators V are short.
Theorem
H
Suppose that D is strictly stable. Define effective learning rate Gelt by
Em Im
O'eff aa-
(22)
-M Em= mipm M
Then for sufficiently small X the leading eigenvalue of the linear maps Ax is MAA 1 20 À + 0(2)). If Oeeft > 0, then for sufficiently small >>> O the linear maps A are strictly stable.
The power-law phase diagram. We verify now the hypotheses of Theorem under the power-law spectral assumptions (I].
Theorem ( Keep assumptions of Theorem f And suppose that A사 are strictly stable for all 0 <
& Amax = max Ag. Then, under spectral assumptions ① with v > 2. the values Vi, V2 U, U given by Eqs.
obey, as - OC,
Vi, = (1 (())) 1)(2aent)
(23)
U, -1+ A) 1/v) (28)
(24)
BB
We that the phase diagram for stationary SGD Berthier et al. 2020) remains valid for arbi- trary memory size (see Fig. 2 Moreover, the algorithm parameters affect the leading terms in Vr, V/. U,, U only though the effective learning rate Oetf and the batch size [B]. However, loss asymptotics (20). 21 depend not only on the leading terms in V4, U,, but also on their sums Vs,, Uy: (in general on V Uz. U see Sec. G.. particular, in the -ignal-dominated scenario, if we wish to accelerate convergence of Lt, we need to increase aeff while keeping U/S < 1. In principle, if by taking B large enough. One can ask, however, aut can be indefinitely increased while keeping [B] and preserving the condition U/. < 1. It was shown in Velikanov af. (2023) that this is impossible for SGD with momentum. We will prove, however, that this can be done even with memory M by slightly generalizing the model.
U/ < 00, we can always ensure U/-
DETAILED INVESTIGATION OF MEMORY-1 ALGORITHM
We aim to check whether memory-1 algorithm can achieve accelerated convergence the signal- dominated phase Ç < 2 with suitable choice of its five scalar hyperparameters or, 0t, by, D,- In this section, we will assume that T2 = to ensure factorization A = 5x % Sx, and striet stability of Aş reduces to that of Sx.
Let us start with the stationary case. According to theorems 3 and stable loss trajectories have the loss asymptotic L, ~ C,t with C, xx a Hence, we want to maximize a (a, a, b, c, D) under the stability constraints. The latter consist of the noiseless stability condition [8x] < followed by
8

---

Published as a conference paper at ICLR 2025
the noisy condition U32 1. To proceed, we find it convenient to denote ò D and multi- step recurrence parametrization of Theorem [
with p1 = 2 and qu, Q1 given by (IO). In particular, t Then, characterize the stability with Theorem Stability of all memory-1 algorithms is fully determined by the tripler (....
applying (22) to memory-1 case gives Oeff
1. Given Amax > 0, the matrix D and the maps Sx are strictly stable for all 0 < A Amax if and only if 0 5 < 2. 90 Amax"
6 and 0 < doxeft < 1-26 -290-
2. Assume < 2 and aet > 0. If q1 S -aeft then the eigenvalues of Sx are real for all
X If q -left, then they are either real lie on the circle { E C: |q1 + qo
8 Oreff (Ceff + ) (see Fig.
3. Denote Rx = Ei= (( (2))))) strictly stable Sx and T2 0,
AR( - (0))))) ) so that U/:
71 B
Ex Rx Then for
2A0 + (Ago + 2 5)00
Rx = A(O + Ago 28- X(2go daven))
(25)
Let us discuss implications of the above result. First, taking into account 140 stability condition statement gives the effective learning rate bound (etf < 8-1 Amane Therefore, the only possibility to have Ocft -> oo is to take å - Now consider the noise stability condition UK- < 1. In the limit 5 - 0, (25) can be simplified, leading to three spectral regions separated by
Amax. the last
and x Af 40
dيg and having distinct impact the stability sum Ek= Rx vo
aeet A 8aen /qu, 9
0 ) XPT
R x A 8aeff + dqh
Xp < X < X5
(26)
8 + Ago
x < X < Amax E,
where is a small constant and f x g denotes eg < f < d'g for some c, > 0. In the last equivalence of (26) we assumed 9o > O. which turns out to be necessary for =k=1 Rr < 00. These observations lead to simple criterion of stable acceleration:
Theorem
K
Consider spectrum Au s.I. Σn Au < 00, AE < Amax 1, and assume T2 = O.
1. Suppose we are adjusting the parameters ō, Ceelf qo so that aeft - oo while maintaining the strict stability of Sx as described in Theorem 0 part 1. Then, the necessary and sufficient
conditions for having Σx=1 X2 Rx, =0(1) are
8 0;
40
Ae- 0 ( (12)))
1K:
8. < 90
<>
5ctatt 46
O Docaft
RE 90
2. Conditions from item I can always be satisfied. In the particular case of power law AE
(1 + o(1)) " >> 1, this can be achieved by choosing Oeff = 8 8-h, go = 89 with any 0 S g < 1 and h S hmax (1 (1 g). Moreover, for g 0 and h < hmaxo the noisy stability condition U/S < can be satisfied with any batch size [B] as + O.
This result fully settles initial question of having arbitrarily small constant Ct in the loss asymp- totic, while maintaining stability.
Now, let look closer the parameters of the obtained accelerated algorithm. First, we see from the second item of theorem that, at given 8, the maximal oef = 8-" is reached with h = 1- 1 by choosing g = O, corresponding to 9o const. Although these values are specific to power-law spectrum with exponent v. they suggest that in the space of algorithm parameters (8, aeff, qu) E R const is the most promising for stable acceleration.
the region& 5-1 > Geft > 40
Power-law schedule with accelerated rate. Jacobi scheduled HB uses momentum 1 1- 8, o t- to achieve accelerated rate O(t-2() in the noiseless setting (Brakhage 1987). Heuristically, we can view this statioatin algorithm so as to increase the effective learning rate auff = & + do while maintaining stability. Mim- icking this connection, we take the accelerated stationary algorithm obtained above and construct
sequence of stationary algorithms gradually changing

---

Published as a conference paper at ICLR 2025
Heavy Ball
Generalized memory-
Figure 3: The geometric position and movement of complex eigenvalues of a memory- matrix Sy as increases from to I (see Theorem
6 part 2). Left: Classical Heavy Ball (go = 0, Polyak (194)); Tugay & Tanik (1989) with 5 0.25, Oef 14. The circle of non-real eigenvalues is centered at v1 6. Acceleration (Oetf > 1) requires ō << 1 and hence large circle, r = 1. Right: Our generalized memory-1 algorithm with ó = 0.15, aefl = 4, = 1.3. The
the origin and has radius
accelerated regime of Theorem 7 corresponds small circles close to point 1.
a schedule (ōt, Ctef.tt 9o,c) that also achieves improved convergence rate. We call the result accel- erated memory-1 algorithm (AMI), heuristically derive its convergence rate below, and verify it empirically in figures and 4. We additionally discuss intuition behind AM1 update rule in sec.
We construct AMI using the power-law ansatz (ōe, Celf. 90.e) (t th const). Assuming an approximate momentary stationarity as above and substituting this ansatz in Theorem part 2, we get the stability condition S 8(1 +). (We emphasize, however, that, strictly speaking, Theorem 7 only holds for stationary algorithms.)
Now we examine the loss convergence rate for these stable 5, a. By Theorem 3 the rate of I4 in the signal-dominated phase is the same that of the noiseless loss V.. We assume that this is also true for our non-stationary algorithm, so we only need to estimate V,- sec. [ we replace evolution matrix AA with its maximal eigenvalue [/max in eq. (7). and obtain Vi = O ((t<((1++)) for 3 < Summarizing, we arrive at the following convergence rate of AMI algorithm:
O ((t=(((+))),
0 S -(1 }), 0 << 1.
(27)
The maximal limiting convergence rate O(t <(2-
((t-((2-))) D) obtained by setting 3 1, a-1-1
DISCUSSION
We have developed general framework of SGD algorithms with size-M memory and analyzed their convergence properties. We developed a loss expansion in terms of signal and noise propaga- tors, and generalized the existing SGD phase diagram of power-law regimes arbitrary M. In the signal-dominated regime, we have found the asymptotic loss convergence to depend on the algo- rithm mostly through the batch size and scalar parameter Oetf that call the effective learning rate. We have proved that already within memory-1 algorithms the effective learning rate can be arbitrarily increased while maintaining stability. As a consequence, schedule for memory-1 SGD which is heuristically expected to improve the standard SGD con- vergence L, = O(t up to ((2- This conjecture was confirmed by experiments with MNIST and synthetic problems.
proposed time-dependent
Interestingly, while our framework allows shifts w, + +aau. in the arguments of computed gradients VL, and these shifts are important for Nesterov momentum (Nesterov) 1983) and averaging (Polyak) & Juditsky 1992). we have not found * 0 to be useful in our setting of quadratic problems and mini- batch noise. The special regime of stably increasing Oef that we identified in Theorem requires separation of scales between the three main memory-1 parameters unrelated a, and does not seem to be easily interpretable in terms of averaging or related general ideas.
Our results leave two obvious open problems: rigorously proving the accelerated convergence L2 ((2-((2)))) and further improving convergence by considering larger memory sizes M.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
We thank Ivan Oseledets and the anonymous reviewers for useful discussions and suggestions that helped improve the paper.
BIBLIOGRAPHY
Alexander Atanasov, Blake Bordelon, and Cengiz Pehlevan. Neural networks kernel learners: The silent alignment effect. arXiv preprint arXiv:2111.0003: 2021.
Francis Bach and Eric Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate o(1/n). In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https::/prrcceeenggg.. www.:n/gs...rrriis...oo cc/paper http:/paarrfffees//eeeeeeee files/ pdf.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXiv preprint (rXxv:2102.0600.0 2021.
Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, Shira Kritchman. Frequency bias in neural networks for input of non-uniform density. In International Conference on Machine Learning, pp. 685-694, PMLR, 2020.
Raphaël Berthier, Francis Bach, and Pierre Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. arXiv preprint arXiv:2006.08212,
2020.
Alberto Bietti. Approximation and learning with deep convolutional models: kernel perspective. arXiv preprini arXiv:2102.10332 2021.
Blake Bordelon and Cengiz Pehlevan. Learning curves for sgd on structured features. arXiv preprint 1xXiv:2106.027133 2021.
Helmut Brakhage. On ill ill-posed problems and the method of conjugate gradients. In Inverse and ill-posed Problems, pp. 165-175. Elsevier, 1987.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model align- ment explain generalization in kernel regression and infinitely wide neural networks. Na- ture Communications, 12(1), may 2021. doi: 10. 1011:06441467-0022233333
URL https:
1038 F4142 021 23103-1
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Lénaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32:2937-2947, 2019.
Elizabeth -Woodin, Courtney Paquette, Elliot Paquette, and Inbar Seroussi. Hitting the high- dimensional notes: An ode for sgd learning dynamics on glms and multi-index models, 2023. URL httpss:/aaxxv..ot
2ww./ 08977
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34, 2021.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger conver- gence rates for least-squares regression. Journal of Machine Learning Research, 18(101):1-51, 2017. URL http::tp://t/ imlr. http://wtr.rrrrpppreeeeeee wwtpo/ppppp./ll.....m
335 html
Xialiang Dou and Tengyuan Liang. Training neural networks as learning data-adaptive ker- nels: Provable representation and approximation benefits. Journal of the American Statisti- cal Association, 1166535) apr 2020. doi: 10.108000122444.22220.11111
URL
https://doof ht..ps://601..rr//0...oo0 10000/000..0001100000 122166214555 621459... 2020 1745812

---

Published as a conference paper at ICLR 2025
Nicolas Flammarion and Francis Bach. From averaging to acceleration, there is only a step-size. In Conference on Learning Theory, pp. 658-695. PMLR, 2015.
Nicolas Flammarion and Francis Bach. Stochastic composite least-squares regression with con- vergence rate o(1/n). In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 831-875. PMLR, 07-10 Jul 2017. BtLhhtps:: /
Lammarionn 1 7a.html
Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy. and Surya Ganguli. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 1850-5861, Curran Associates, Inc., neurips ctt.ccc/ccccocooe cc/paper fi files//aper/2020/ Paper. ppof
2020. URL
fi F1le4408775699106644583187776660
Martin Hanke. Accelerated landweber iterations for the solution of ill-posed equations. Numerische mathemarik, 600 60133334,333,, 1991.
Martin Hanke. Asymptotics of orthogonal polynomials and the numerical solution of ill-posed problems. Numerical Algorithmss, 11(1):203-213, 1996.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. arXiv preprint (rXiv:1806.07572 2018.
Dmitry Kopitkov and Vadim Indelman. Neural spectrum alignment: Empirical study. In Interna- fional Conference on Artificial Neural Networks, pp. 168-179. Springer, 2020.
Jachoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent, 2019.
Jachoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. Advances in Neural Information Processing Systems, 11115-1157722 2020.
Kiwon Lee, Andrew Nicholas Cheng, Elliot Paquette, and Courtney Paquette. Trajectory of mini-batch momentum: Batch size saturation and convergence in high dimensions. In Al- ice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neu- ral Information Processing Systems, 2022. URL.ttps:: /opooeeeeeeeeeeeeeeeeeeeeeeeeeee // net/ forumriricooo #opoo2Ghoh6!
Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.02216 2020.
Wesley Maddox, Shuai Tang, Pablo Moreno, Andrew Gordon Wilson, and Andreas Damianou. Fast adaptation with linearized neural networks. In International Conference Artificial Intelligence and Statistics, pp. 2737-2745. PMLR, 2021.
Aaron Meurer, Christopher P. Smith, Mateusz Paprocki, Ondřej Čertík, Sergey B. Kirpichev, Matthew Rocklin, AMiT Kumar, Sergiu Ivanov, Jason K. Moore, Sartaj Singh, Thilina Rath- nayake, Sean Vig, Brian E. Granger, Richard P. Muller, Francesco Bonazzi, Harsh Gupta, Shivam Vats, Fredrik Johansson, Fabian Pedregosa, Matthew J. Curry, Andy R. Terrel, Štěpán Roučka, Ashutosh Saboo, Isuru Fernando, Sumith Kulal, Robert Cimrman, and Anthony Scopatz. Sympy: symbolic computing in python. PeerJ Computer Scientee Science, 3:e 103, January 2017. ISSN 2376-5992. doi: 10.7717/peerj-cs. cs. Uttptttss://oo. 0ttp:/11.777717117 wtt.ii77777ppeeeooo
103
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. In J. Shawe-Taylos R. Zemel, P. Bartlett, Pereira, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems. volume 24. Curran Associates, Inc., 2011. URL htt http:tssss/rccceee.....oo..o....
files/
12

---

Published as a conference paper at ICLR 2025
Arkadi S Nemirovskiy and Boris T Polyak. Iterative methods for solving linear ill-posed problems under precise information. Eng. Cyber. (4):50-56, 1984.
AS Nemirovsky and BT Polyak. Iterative methods of solving linear ill-posed problems with precise information. i, ii". Izvestiya Akad. Nauk. SSSR. Tekhnicheskaya Kibernetika, 2(13-25):3, 1984.
Yurii Evgen' evich Nesterov. method of solving convex programming problem with convergence rate o(k2)). In Doklady Akademii Nauk, volume 269, pp. 543-547. Russian Academy of Sciences, 1983.
Guillermo Ortiz-Jimenez, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. What can lin- earized neural networks actually say about generalization? In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL httpt:t:/// httpppereeieeeeeee//orrrrraaaaae
Asf
Courtney Paquette and Elliot Paquette. Dynamics of stochastic momentum methods on large-scale, quadratic models. Advances in Neural Information Processing Systems, 34:9229-9222 2021.
Courtney Paquette, Kiwon Lee, Fabian Pedregosa, and Elliot Paquette. Sgd in the large: Average- case analysis, asymptotics, and stepsize criticality. arXiv preprint arXiv:2102.043:00 2021.
Courtney Paquette, Elliot Paquette, Ben Adlam, and Jeffrey Pennington. Homogenization of sgd in
high-dimensions: Exact dynamics and generalization properties, 2022. URLpattps://arxi.
org/ abs/ 220.2225.000
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr compu- lutional mathematics and mathematical physics, 4(5):1-17, 1964.
Boris Polyak and Anatoli Juditsky. Acceleration of stochastic approximation by averaging.
SIAM journal on control and optimization, 30(4):838-855, 1992.
B.T. Polyak. Introduction to Optimization. Optimization Software, New York, 1987.
Sumit Roy and John Shynk. Analysis of the momentum Ims algorithm. IEEE transactions on acousties, speech, and signal processing. 38(12):2088-209) 1990.
Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus teacher-student paradigm. Journal of Statistical Mechanics: Theory and Experiment, 2020(12):124011, December 2020. ISSN 1742-5468.
doi: 10. 10.1088/1742-5468
abc6ld. URL http: /x. www.xxx...o..oooo www.dot.....oooooooooooooo 1088 5468 abc6ld
Mehmet Ali Tugay and Yalcin Tanik. Properties of the momentum Ims algorithm. Signal Processing, 17-2):1771177, 1989.
Aditya Varre and Nicolas Flammarion. Accelerated sgd for non-strongly-conve least squares. arXiv preprint arXiv:2203.0174. 2022.
Aditya Varre, Loucas Eillau-Viivees and Nicolas Flammarion. Last iterate convergence of sgd for least-squares in the interpolation regime. arXiv preprint wxXiv2202..03/8. 2021.
Maksim Velikanov and Dmitry Yarotsky. Explicit loss asymptotics in the gradient descent training of neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Maksim Velikanov and Dmitry Yarotsky. Tight convergence rate bounds for optimization under power law spectral conditions. Journal of Machine Learning Research, 25(81):1-78, 2024. 2024.
Maksim Velikanov, Denis Kuznedelev, and Dmitry Yarotsky. A view of mini-batch sgd via gener- ating functions: conditions of convergence, phase transitions, benefit from negative momenta. In The Eleventh International Conference on Learning Representations (ICLR 2023), 2023. URL.
https: http:///peeeevvieeeeeee ew net. wwt.:/eeetrfmet forum? (ttprummmddizzaaae dd bww.aaaaallss... 1
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize, 2022. URL https: / //trxivvvv////////////aa///aaavl org. abs/
2203. 76
13

---

Published as a conference paper at ICLR 2025
Jingfeng Wu, Wenqing Hu, Haoyi Xiong, Jun Huan, Vladimir Braverman, and Zhanxing Zhu. On the noisy gradient descent that generalizes as sgd. In International Conference on Machine Learning, pp. 10367-10376. PMLR, 2020.
Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Last iterate risk bounds of SGD with decaying stepsize for overparameterized linear regression. In Ka- malika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.). Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 24280-24314. PMLR, 17-23 Jul 2022. URL https::/prroceet ngs ml wtw.s v1 62. wu22p html
Greg Yang and Hadi Salman. A fine fine-grained spectral perspective neural networks, 2020.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. arXiv preprint arXiv:1803.00 00195, 2018.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign over- fitting of constant-stepsize sgd for linear regression. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceed- ings of Machine Learning Research, pp. 4633 4635. PMLR, 15-19 Aug 2021. URL https:
/proceedings . mlr.
zoulaa. html
14

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
2
The setting
Gradient descent with memory
Batch SGD with memory
Stability and convergence of stationary memory-M SGD
Detailed investigation of memory-1 algorithm
Discussion
10
8 Bibliography
11
Related work
16
GD with memory
17
B.1 Shift-invariant and equivariant vectors
17
B2 Proof of Theorem
18
B.3 Proof of Proposition
20
SGD with memory
20
Evolution of second moments
20
Speetrally-expressiblee approximation
Proof of Theoremm 2
22
Propagator identities and bounds
24
General non-stationary case
24
E.2
Stationary case
25
Proof of Theorem
27
F1 Part (convergence)
28
F2 Part 2 (divergence)
28
Part (signal-dominated regime)
28
F.4 Part 4 (noise-dominated regime)
30
Generalization of Theorem 3 to V3 #
31
Proof of Theorem 4
33
15

---

Published as a conference paper at ICLR 2025
Proof of Theorem
34
Proof of Theorem 6
35
K Proof of theorem
37
Convergence of non-stationary algorithm with power-law schedule
38
M Experiments
40
M. Gaussian data
41
M.2 MNIST
41
A RELATED WORK
Linearization of neural networks. The relevance of quadratic optimization problems to deep learning is given by various scenarios where neural network function f(w,x) be linearized with respect to parameters w
fün finnw, = f(wo, + (w wo. fwo x)),
(28)
often referred as kernel regime since fun (w, x) can be described in terms of respective neural langent kernel (NTK) K (x, x') = (V ff (wo. x). Vw (Wo, x' x')). One of such scenario is infinite width limit in NTK regime JJcot al. (2018); Lee et al. (2019); Chizat et al. (2019). where lineariza- tion becomes exact. Another scenario, is an approximate linearization of practical neural network at certain stage of its training Fort al. (2020); Maddox al. (202T); Ortiz-Jimenez al, (2021): Lee et al. (2020). We cover this scenario by linearized network features Vw /wW. x) as inputs in
Power laws. Both classical kernels well NTK often display power-law shapes of their spec- tral distributions when applied to real world data. Typical examples include MNIST and CIFAR on either elassical kernels NTK of different architectures such MLP or resnet (Cui et al. 2021
Bahri et al. 2021] Lee et al.
2020 Canatar et al. 2021 Kopitkov & Indelman 2020 Dou & Liang
2020
Atanasov al. 202 I
Bordelon Pchlevan 2021 Basri al.] 2020 Bietti [222] Wei al.,
2022
Atanasov et al. 2021).
Power-law spectrum also appears theoretically in settings involing
highly oscilating Fourier harmonics (Yang Salman 2020 Spigler al., 2020; Basri et al. 2020
Velikanov & Yarotsky 2021). Finally, power-law spectrum is often used as an assumption (Capon-
netto & De Vito 20077) for different optimization and generalization results on kernel methods.
Importantly, the exponent in the power law spectra of real world problems is typically Ç < for example for MNIST different works report ( [0.2, 0.4). This implies that the respective infinite dimensional problem with < will have divergent series of coefficients |/ Σ 2 xo, so we can refer to respective targets as infeasible. Such setting makes vacuous many classical results relying norm ||w.|2 (Wei et al. 2022: Velikanov & Yarotsky 2024). Results in the present paper were developed to include the case
Quadratic optimization under mini-batch noise. The properties of stochastic optimization can greatly vary with the structure of the noise. In particular, a common setting of additive noise (Polyak & JJditsky 1992 Wu et al. 2020) Zhu et al. 2018) differs substantially from multiplicative noise (Moulines & Bach 2011 Bach & Moulines, 2013) considered in the current paper. The mini-bated
setting for pawer-law spectrum and its phase diagram with signal-dominated Ç < 2 - and noise-
dominated Ç 2 regimes was identified in (Berthier al. 2020 Varre al. 2021 the level of rigorous upper bounds, and in (Velikanov et al.] 2023) on the level of loss symptotics under spectrally expressible (SE) approximation. The latter work relies generating function technique and provides the asymptotic form for the partial sums Eisr th, rather than for the losses Lt. In contrast, the combinatorial approach of propagator expansions used in the present work allows to directly obtain the asymptotics of T...
16

---

Published as a conference paper at ICLR 2025
As we mentioned in the main paper, SE approximation, or its 72 version, is often used as an upper bound assumption on the noise covariance (Bordelon & Pehlevan [202] Flammarion &
Bach 2017 Dieuleveut et al., 2017 Zou et al. 2021 Varre & Flammarion 2022; Wu et al., (022))
Another series of work (Paquette & Paquette 2021 | Paquette et al. 2021] Lee et al. 2022
Paquette al. 2022 Collins- Woodfin et al. al.]3222) consider different high- nigh-ddmensional setting where SGI)
converges deterministic dynamics described by convolution Volterra equation. This setting differes from ours in that eigenvalues are described by limiting density, leading to the regime of immediate divergence Σx X oo, which has to be overcome by scaling the learning rate with dimension as d Apart from this difference, algebraic structure of continuous time Volterra equation close to our discrete time propagator expansion [19), and we expect some of our results to be extendable to the aforementioned setting.
Accelerated algorithms. It is a standard textbook material that Heavy Ball accelerates conver- gence of plain non-stochastic gradient descent quadratic problems (Polyak) 1987). In the setting of non-stochastic optimization of non strictly convex quadratic problems with power law spectral data, convergence rates of different GD-related methods were first analized by Nemirovskiy & Polyak (1984); Nemirovsky & Polyak (1984). In particular, they showed that under the source condition corresponding the second equation ①T with some Ç. the loss convergence rate of standard stationary GD was L, = O(t 9 and also gave number of other upper and lower bounds for different algorithms. [Brakhage| (1987) introduced Heavy Ball with time-dependent schedule based on Jacobi polynomials and showed that such schedules provide acceleration of the standard GD rate T,, = O(L-S) to T,₃ (t)-2) for any spectral exponent Ç. This rate is optimal among algorithms with predefined schedule, though, as shown already by Nemirovskiy & Polyak (1884) Conjugate Gradients can provide an even faster convergence L2 O(t-(2+D))) (but in this algo- rithm the update coefficients are not predefined). See Hanke [1991 1996): Velikanov & Yarotsky (024) for several other results concerning acceleration of non-stochastic gradient descent on non- strongly convex quadratic problems under power law spectral assumptions.
A series of works (Flammarion & Bach 2015 Varre & Flammarion, 2022) consider a special sched- ule of memory-1 SGD parameters such that after rescaling the iterates Aw; = fAw, the update rule become stationary. Then, the stability of w, leads O(t convergence of original iterates Aw; as long as |Awoll ||w. 1|2 < co. In particular, for mini-batch SGD under uniform kurtosis assump- tion (i.e. noise is bound by our SE term), Varre & Flammarion (2022) gives an upper bound O d ), where problem dimension d appears from downscaling learning rate as a = O(d to ensure sta- bility. Potentially, the necessity to downscale learning rate of the algorithm of Varre & Flammarion 2022 can be traced to third stability condition of theorem 7 with the set { go < < < ag covering the whole spectrum, thus requiring small learning rate inversely proportional to the size of the set.
B GD WITH MEMORY
B. SHIFT-INVARIANT AND EQUIVARIANT VECTORS
The vectors w, in the evolution 3 are thift-equivariant while are shift- invariant,,, in the follow- ing sense. Given loss function I.()) and an initial approximation Wa, consider their shifts by some vector v IL(()= = L[- T),-v), v), w/ Wo + Then running the algorithm 3 with the same parameters ae, at, b., Cr, D, yields the shifted trajectory w/ = W. + v, as is commonly expected, while pre- serving the auxiliary trajectory ut u, This can be seen
consequence of using the difference W w, in the l.h.s., since w, being chift--quivariant for all is equivalent to W1+1 w, being shift-invarian for all t. Since the gradients V VL(w, + af u.) are also thift-invariant, all the matrix elements appearing in Eq. (4) are shift-invariant, which is consistent with the mentioned in- and equi-variance of the trajectories u, and w..
17

---

Published as a conference paper at ICLR 2025
B.2 PROOF OF THEOREM
Proof. 1. Consider the characteristic polynomial
x(2, A) det(x= 5x) det 10)000))000 + x (-0) (1, (1,a²) (
bTd (
Σ "max""X"" Ab.
(29)
We can express x in terms of a, b, C, D by conjugating Sx with the matrices
U 1 1 U-t -a 1 )
1 a
(30)
namely
X(r, 2) = =dot(x- - U
(31)
2 (0
b" a 1) +X a''c [1.0i)
det
(32)
D
X(a a) -(b" + + a (D- -1)
del
(33)
-ce
I x- D
x-1
x
-(b"
a²
(D-1))) X det
ca'c-a
-(b" + a 1))
det
I x-
c
x - D
(34)
aac-a
a1 D) D) bT)
= (x - 1) det(2 - D) det
(35)
c
x -
This shows, in partieular, that x be written in the form
M
M
x(x, A) = x. M+1
Pmr
4m
(36)
m==
m=U
with coefficients (pm) M M such that Σ Em=0 Pm
1.
On the other hand, by the Cayley-Hamilone theorem, x(S,, A) = 0. In the time-independent scenario X-eigenvectors ( Aw: are evolved by ue
scenara
AWa+m)
/Aw,
ST
(37)
um+
Ut
Recalling the expansion x(x, A) = Em, m mh A of the characteristic polynomial, follows that
Σ
T'mk Sx x²)
Aww
ur
Σ A
A
Aweem
Up+o
=
H
/Awa+m)
Ur+m
(38)
m
m.k
m.k
In particular, taking the top row,
Σ Tim H Aw m,k
=0
(39)
Since this equation is X-independent, it holds not only for eigenvectors AWt+m. but, by linearity, for any vectors A AWz+m connected by the matrix dynamics (3)
Finally, we obtain the desired identity
8 by substituting the expression 36 for X, recalling that
Em Pm = 1, and noting that HAw VL(w):
M Pm Aw
M
0 = AW
Σ ===
Tm HAW
(40)
m==
M
W
Σ
Pm Witm
4m (L(Wr-)).
(41)
m==
m=0
2. The proof will consist of two components:
18

---

Published as a conference paper at ICLR 2025
a) Construct a, b, D ensure that the sequence Wy satisfies the recurrence
satify Eqs. ( By part 1) of the theorem, this will
b) Show that for any sequence We, Wi:..., wM required to initialize recurrence S one can find initial condition wo for the matrix evolution to produce this initial sequence.
For a), we first satisfy Eq.
9 i.c. construct a matrix such that
M+1
M
Pm m
--1
det(2 D)
m==0
pm x
(42)
m==0
where
Pm
Σ
Pk:
m =
M 1. O....,.--
(43)
k=
A M x M matrix D with such de
D) can be given as
PMM-1
1 0
PM
0
1
0
(44)
p/
0
0
1
Pb
0
0
Now to satisfy Eq.
10)
we choose a = 0, = (1,0,..., ......,"" so that this condition becomes
M
-a -b²
Σ
mm m = dot
(45)
I x- D
m=0
C1
C2
-1
0
= det(( - D)+ +
(46)
CM-1
0
0
-1
CM
0
0
M -1
a det(x D) +
Σ
CM-1-m2"
(47)
m==
Observe that there is a unique assignment of and that satisfies this identity: first we assign
a = QM so that Σm= Imx=" + a det(x - D) is a polynomial of degree not greater than M 1, and its coefficients then exactly the components of the vector
Having constructed a, a, b, D, we check now the completeness condition b). Note that since we have set O, the gradients VL(w, a" u.) ((w.,) appearing in Eq. (3) only depend the target sequence w, and not on the auxiliary sequence u, In the first step of matrix iterations we have
Wo = -VV((wo) + b" ug = vi un w
(48)
with some V, that depends only on Wo and not on ug. the second step, using the explicit form of the matrix D,
W2 W1 aVL((1) - bTu,
(49)
= aVV((w)) b Duo) (1)
(50)
= --VL(W))) VL(wo)cr 1 ub + ug
(2)
(51)
=2 + f
(52)
where V2 is a vector depending on wo, wi and the first component u of un, but not on the second component u (2)
By repeating this process, we see that for all m = 1, 2, ....... M we can write
W m m Vma u
(m)
(53)
19

---

Published as a conference paper at ICLR 2025
(1)
(m-1) but not
(mm)
with vector Vm that depends Wo Wm-1 and Ug ..... Up
(m) we can ensure the desired values
This shows that by sequentially adjusting the components un for all the differences Wm Wm-1, m 1,.... M, i.e. can find the initial condition uu producing the desired sequence Wo...., W.M
B.3 PROOF OF PROPOSITION I
Suppose that L is quadratic and consider iterations 7 in the eigenspace representation, starting from some Awo ). Observe that (Aw. ) polynomial in X, with degree at most and the associated leading term resulting from applying the rank-1 A-term in each step:
Awr 41
=
Ore Ct
II
(.00+1 as) (Aw. aA) + auu) + +(
(54)
In particular,
Aw1 X(-o))(Awo + 01 u1) + 0(1)
(55)
Aw2 (22-22) (A) aq + O())
(56)
Suppose now that ai 0 while 02 * and c₁ K 0. Then the leading term in Aw, vanishes and the degree of Awr drops to O, while the degree of Aw2 is exactly 2. Then, it is impossible for generic Á Awo un to represent Aw₂ as
Aw λςı Aw: + Ago + Aw: + Po
(57)
since the r.h.s. is polynomial
of degree at most Representation (57) is equivalent to Po W2 P1 + Po Wo + 91 VL(wi) + qu ((wo)) (p1 Po 1)w.
(58)
We can assume W. = 0, then this has exactly the form as in the statement the proposition.
C SGD WITH MEMORY
C.1 EVOLUTION OF SECOND MOMENTS
In a single step of SGD, the parameters and memory vectors are updated with stochastic batch Hessian H. Bil ΣxTEB, X2 & X; as
/Aw+1 = S; AAw) 11
S,
by D.
H,
-ac
(1, (1,a?))
(59)
U++1
C₁
To lighten notation, we will sometimes drop the tensor product sign between Hessian and the algo- rithm parameter matrix, writing simply as H, -a (L,
To obtain the update of second moments [T), we simply substitute the update of parameters above, and take the expectation with respect to draw of batches B1, B2.... B,
Aw u1+1
Aw
27
M411 = B.B....B.BB.BBB
U1+1
(60)
Aw;
Aw,
T
= EE B, 1.
S
S = Es, [.M.S]
u,
u;
To calculate the last expectation, Then, for any fixed matrix G in H. the expectations involving two batch Hessians are computed as
that samples x; B, drawn i..d. from distribution p.
[&
EB, H. Ep.
X
Gx,)xx &xy
B
JJ=1
[B|]
1
(61)
HGH
E B.
Ex Gx)x
[B
.IGHH +
(G),,
[B.
20

---

Published as a conference paper at ICLR 2025
where the sampling noise variance (G) is defined by eq. (14).
Using the above, we finish the computation second moments update
M4+1 BBg (6
by
H
at
(1, a
M,
(o
by
H,
04
(1,a7)) )
T
Di
Di
Ct
-( -(( by
H
04
(1, a1,a()) M.
(
by"
H
-0t
(1,
(62)
Dz
Ct
D;
2 (C, + 2J + + Va,
at
(-)),
B2
C.2 SPERESALLY-XRRESSSILLLEE APPROXIMATION
EXPRESSIBLE
As usual, for two Hermitian operators A, B we write A 2 B (or A S B) meaning that A - B is positive (negative) semi-definite.
Recall the maps Ep and (2) SE defined in Eqs. (1). 15
(C) Ex (xx Cx)x x
HCH,
(63)
(2) SE
(C) r. Tr|HC -1, HCH.
(64)
In the following lemma we collect a few useful properties of these maps.
Lemma 1. Suppose that H 2 O.
1. For any C 0 we have HCH S Tr(HC)H.
2. For any rank-1 Hermitian H we have HCH Tr(HC)H.
3. If' S Ti 2 72, then (T)) (C) 2 (C)( 28E
for any C 2 0, and, more generally, (m.
USE
(C)
(C) >
(a) for any 2 C²
USE
(2)) (C) 2 0 for any
4. I/ < 0 or > then it is no longer true in general that SS.. C20 O.
5. (7 SE
(C) N
(n. (C) for any C 0 and 2 0.
SE
6. 2 C) 2 for any C 2 0 and, more generally, CP(C) 2 (C') any C2 C².
Proof.
1. We need to show that for any vector u
(u, HCHu) & (r(HC)) Hu).
(65)
By considering u = Han and rescaling v = u/||u]], it is sufficient to show that (v, H CHèv) < (T(HC) for any unit vector v. But this just follows from the posi- tive semi-definiteness of H CH² and the cyclic property of the trace:
(v. C.CH < ( Tr(HC).
(66)
2. Immediate.
3. For C 2 O) we have (C) = - + (T2 HCH 2 0 by
statement 1 and positive semi-definiteness HCH.
Monotonicity follows from the linearity of (2)
SE
4. If Tı < 0, consider H = 1 and rank-1 C. Then Iim (C) 7. (Ir (Tr 1 C2C which is not positive semi-definite unless the space is l-dimensional.
If T2 > Ti consider a rank-1 1 H. By Statement 2, (71.52) negative semi-definite.
(C) = (n T2 HCH, which is
USE
21

---

Published as a conference paper at ICLR 2025
5. Follows from statement 1.
6. It suffices show that for any two vectors n, have (u, (v & v)u) i..
Ex=pl x)² (x, v) E p x) (x, v)l.
(67)
But this is just special case of the Cauchy inequality x & [x= with f(x) =
(u, x) (x, v).
Monotonicity again follows from the linearity of pp-
We can now prove Proposition
(t) and Ep preserve positive Proof of Proposition By statements 3 and of Lemma, both S semi-definiteness and are monotone in the operator sense.
Let us prove that (C) < (1))7))) (C) for all C 2 implies L < L (1ai2t) for all t. It suffices to SE
show that for all 0, we have C. S C₁ where C, and C2 denote the C-components of the matrices M, Mr corresponding to the dynamics with Ep and I(T..T2) respectively. In turn, sufficient show that < M, I M2 for all t. By induction, suppose that M, S M2 holds for some L. Then, in particular,
5 (1, (1, aT)² s (1. M (L.
(68)
Then, using the hypothesis of the proposition and the monotonicity of 2i5 (7)))2))
0 $ E. (1, (1,,,
(69)
<
(z)))))) SE
(1, (1, MI,,,,
(70)
1 - m2)
(L,
(71)
follows that the noise term 13 of the dy-dynamics is positive semi-definite and dominated by the respective term of the Din -dynamics.. The same holds for the signal terms 12 It follows
that 0 < M & M as desired.
The proof of the converse statement is completely analogous.
D PROOF OF THEOREM
We will derive a more general, non-stationary version of loss expansion (19). which will imply the simplified stationary version.
Consider the M matrix iterations
12
13
in which we, as assumed, the SE approximation
(t) instead of Mp: -SE
M
[
b. D.
0tt H
(1, a²))
M M.((]
by
H
act (1, (1.
T
(72)
C2
D.
c
+ B
(2))2)
SE
(1, (1, s
(-ai
-ai
(-as ct),
(73)
SEE
(2)
(C) (C) T. Tr HCH HCH.
(74)
Let us write these iterations in the form
M = F,M, = (A,+
+ P.)M.,
(75)
where Ft, Ar, Pt are linear operators defining this transformation:
22

---

Published as a conference paper at ICLR 2025
1. Fj is the full transformation;
as part of 2. Pt represents the part of Ft associated with the term 71 Tr|HC in SE Eq. 774 the noisy term (73):
3. A, represents the remaining part of Fe, i.e. the noiseless term 72 and the part T2 HCH of the noisy term 73
The matrix M, has a diagonal component Mi.diag w.n.t the operator H (below we refer to such matrices as H H-diagonal): given the eigenbasis C₁ of H, we can represent M, = Σx. (ex @ e,) &
Zr, with some matrices Zr,u.I E (1+ and then Mr.diax = Ee(es @ ex) @ Z.A.K. Whereas the full matrices M, live the space (H @ RR+ the matrices Mi,ding naturally live in the space H & (RR++M822 We will argue now that we need to only keep track of this diagonal component of M, during the iterations.
Observe first that the diagonal part Mr,ding, evolves independently of the off-diagonal part of M.. Indeed, if M, = (ex @ ei) @ Z with some Z E ( then also A,M; = (ex @ er) @ Z' with some and produces an H-diagonal result.
[[(++)x((++M) On the other hand, P.M, depends on M, only through Mr,iag
Note also that the averaged loss L, only depends on the diagonal part of M,:
L Tr[HC,] = 1/ r
(76)
follows that Le is completely determined by the coffisonsttt evolution of the diagonal compo- nents Mr.ii
Since Wn = 0, Un = 0, and accordingly Awo = - w.. we can then take the initial second moment
matrix Mg to only have H-diagonal nontrivial component Co. i.e. M, 0 0), where Co-
diag (ct) ch (ex, w.)². 2 Then,
L Tr [H. = (A (68), FI( Co 9)),
(77)
where x = diag( (At,g((A,)) ......) .) and the inner product is between matrices, (A, B) = Tr(BB)).
We now describe the action of the operators Pt and A, on H-diagonal matrices M. The operator Pt is a rank-1 1 operator that can be written as
Pt = B
2 (To. X (-ar of ) (1)) )..)
(78)
The operator A, is a system of (1 + (M x (1+ M) matrices A,, acting independently in each A-subspace:
A, (AGa), =
x2 -8 ( B
Ta
2())))))) (0)))
(79)
with Sx, defined in Eq.
We obtain the desired loss expansion by substituting F; = Pt + A for each t in Eq. 77 and expand the result over various choices of the iterations .,,..,,4 4m in which we choose the term P while in the other iterations we choose the term A. Since P: is rank-1, the contribution of each configuration is split into a product of scalar propagators:
L. = 1 [V+1
Σ m=1 OOE,CC....... R... <t+1
U2+1 U Unnittmm Umm-iimm- ... Ulann Vi))
(80)
Here the propagators U/,5, U2 Ví,, Vz have the form
U/ = - (2 & (al ((
A (-0- (-aa c.
(81)
- Σ
)1 A Aeti.el - (-aa,))))))) -
(82)
Vi (A (1 ),A1A A1 8))
(83)
Snceila) (1aT)) A (d0)),
(84)
23

---

Published as a conference paper at ICLR 2025
and Ue Vi are obtained from U/,,, V by replacing (1))(1 a? with (b.) in the left arguments of scalar products in these formulas. The propagators U, V are different from U", V' in that the former end at the loss evaluation time t, whereas the latter end at one the noise injection times f ....... bm- Each term in Eq. (80) contains exactly one signal propagator V or V and some number of noise propagators U or U.
In the stationary single time index U/,== = U2 Ut =\t Ut-s, and replace the products A A A
the above formulas simplify given in Eqs. (7
18
As+1 by the power
E PROPAGATOR IDENTITIES AND BOUNDS
In this section we collect auxiliary results that will be used in the proof of Theorem 3
E.1 GENERAL NON-STATIONARY CASE
Recall that in the general non-stationary case the loss expansion is given by Eqs. 80
84
We will derive a convenient representation the vector loss values,
L = (Lo, LI,...);
(85)
in terms of suitable linear operators. First, consider the values
1 1 2 V 2
1,-
Σ
Σ
12 Umm U Ulm--itm-
Up Una Vi:)
(86)
m= Oct S... <tmstt
and the respective vector
L' (1), .T)
(87)
Observe that where
2 / + UL',
(88)
V (V1, V2....) .T
(89)
and U is the infinite matrix
U441,5+1
t> 8,
(U),s
(90)
0,
t t s.
Note now that L' satisfies the equation
L' L U'L'
(91)
where
V (Vi, V/ V2....)? )T,
(92)
(U'):s U Ul+1, t> s,
(93)
t
The representation (86) corresponds to the formal solution of Eq. 91
L'= 1 - U')-''' ! + U'V' V'v +...).
(94)
When viewed in suitable Banach spaces, these operator representations can be conveniently used to derive upper bounds on L. Specifically, let a, be positive sequence and consider the Banach space of sequences with the norm
[|| = sup larfll f= = (f........).
(95)
Then
||u|| sup 1
Σ
U 11+1,411
(96)
0x
||'|| sup Σ
U 1,++1
dt.
(97)
24

---

t == 1.2.... Published as a conference paper at ICLR 2025
Assuming ||'||| <
1, we get
[L|]| -
(98)
2(1 [0]]
and then
|L| || = 1 V + UL < | + |
(99)
For example, choosing 4; = (t + 1)8, = 0, 1..., with a constant exponent & 2 0, we obtain a simple sufficient condition for the bound L, = Ott Proposition 4. Suppose that
VVl C
(100)
[V/ C
1 t= 1,2....
(101)
Cu sup
10,a <0
(102)
1-1
t
C sup
(103)
121
with some constants Cv,Cv', Cu. Cy.. Then
Cr. Ccv + +Cu C
S (r(++1)
(104)
2(1 Cv.)
In particular, by taking 0 we that if sup1z1 Σ 1 and sup121 EE (Ut co.
then uniform boundedness of Vi, V implies uniform boundedness of TT-
E.2 STATIONARY CASE
Recall the stationary version 19 of the loss expansion:
L.
1 2 Vi+1 +
U Uy tm U
Uy - V2).
(105)
VIA OCA1
<1+1
It is will be occasionally convenient to slightly adjust the operator formalism of previous section by considering two-sided sequences. We adjust the definitions (85) and 89) of the vectors L and V by padding them by 0 the left:
(. (..., 0, Lo, L1 LI....),
(106)
V = (..., 0, V1, V.)...)
(107)
Similar convention applies to L', V
We extend the definition (90) of operator U to double-sided sequences, also taking into account that due to the stationarity U is now translation equivariant:
{ Ut-ss
t =W))=
(U),,
(108)
0. 1 15 8
Similar convention applies to U.
We now establish useful general result showing that U, Eu with &o > implies a similar bound for the matrix elements of (1 U)-1 This can be easily done if we assume not just Us; < and U, O(--uu) ) as Theorem 3 but rather U, S Eu with a sufficiently small C":
Lemma 2. Suppose that U. = for I O and 0 < U, < Sv for > 0 with some C' and EU > Then, if C' is sufficiently small, we have (U²), S - for all t > 0. By iterating this bound, we get
< 2 Ev.
t>0 0
((1 (1-
1,
0
(109)
= 0,
<< 0
25

---

Published as a conference paper at ICLR 2025
Proof. We have for t > 0
(U²), Σ U--
(110)
1/2
x 2 Σ (1 UU
(111)
-=1
1/2
S C'
(112)
2224 C²
Σ ru C'c-Su
(113)
The factor 2 C² E'E r Eu Eo can made less than 1/2 by taking C' small enough.
The relation (109) follows by expanding (1 1--) U+UU +... and repeatedly applying E -t-r) Eu I[C"r S (t)
Now we prove a more subtle statement that only uses the weaker assumptions made in Theorem Lemma 3. Suppose that Uz < and U, = ((L for some &> 1. Then ((1 - 5).
Proof. The operator (1 U)-1 is the operator of convolution with the kernel ((1 - -U)- which can be expanded as
((1 (1- = 6, +U)
(114)
where * denotes the convolution of two sequences, i.e.
(A B): = Σ Br, Br, r= 0,0,
(115)
T=0
for any one-sided sequences A, B. Let us split the sequence U, into finite initial segment A and a
remainder B, with small sum:
U A + B,
(116)
A, U,lesto
(117)
B, U, U,1esta
(118)
(119)
where to such that
EB B. <E
(120)
with sufficiently small e be chosen later. We then have
(1- Σ U
(p) 1=0 ==0==
A A B=(n-k)
(121)
where the binomial expansion is legitimate due to the commutativity and associativity of convolu- tion. Consider the convolutional power B", Recall that B, = O(t-E) We can now argue as in Lemma 2 and show by induction that for any 1,2,...
(B ) -6-5
(122)
26

---

Published as a conference paper at ICLR 2025
with 6 that can be made arbitrarily small by making in Eq. 120) small enough. Indeed, for r
)
Σ B,, Br-
(123)
1/2
Σ
( (B((r-1) 1)) B
(B D.Bio
(124)
s=1
8=t/241
Σ (Br(r-1)) 1), C(t/2) + (t/2) Σ B
(125)
((t/2) CG 2 (t/2)=
(126)
( 1- + (e/E1)25)
(127)
cce
(128)
by choosing so that (f/6))-122 + (e/e))2 <1 for r 2 This proves (22
Now let
a Σ A..
(129)
By assumption, a E U2 < 1. Observe that (A*%)); )) 0 for > ktp. It follows that
Aío
(A** * Bo(a-A)), S
(Aak), )s Cep max klo) -
(130)
S a Cet k- k-1 max(1, toko)
(131)
Then from the binomial expansion
121
((1 U)- 1)e <
a Ce
n-1-k Cen-1-k max(1, 1 - klo) - + a² legent)))
(132)
n=1
k=0
(2(b)
8
Σ
(133)
n=t/(2
1/(2tt)
s (t/2)
Σ
a
Ce
a &Cee--1-
k
k
k=
a=t/(250) ) k==
(134)
t/(2to)
D0
= -1
Σ (a+E))*+C +C Σ
(a+
(135)
(2to(2t))+1
(0 ((1))) + (a + e (2(20)+1))
((1/2)
(136)
By choosing e sufficiently small so that a + < we get the desired property ((1 - U)- 5(1-5).
F PROOF OF THEOREM 3
Throughout this section we will use the stationary-case representation of L, from Eq. (9), with the identified U2- = U/, Ve = Vt::
V4+ + L: 2
1
Σ
Ue+1-tm Utm -t-- -em tm -mm-2- .. U U1-- Vo). (137)
m= C...tt.. <t+1
We use the operator formalism and results from Section
27

---

Published as a conference paper at ICLR 2025
F.1 PART 1 (CONVERGENCE)
If Uy < 1, then V - (11 implies L = (1) by the remark after Proposition
To conclude I,, (1) from V/2 o(1) write
L = Σ (1-- 2
(138)
=
Here
2 0 and
Σ ((1 - -)- 1 Us:
< co.
(139)
For any 6 we can choose such that E ((1 UI- ) < c. Then by Eq. 1388
max,=l....F-1 Vi-+1
emax, t emax, Va
L <
(140)
2(1 - Us)
2
2
follows that L1 + 0.
F.2 PART 2 (DIVERGENCE)
Since U,, V 2 O, we can lower bound, for any k 2 0 and s 2 0,
Leta 2 (U*) ) V
(141)
We choose s so that V.+1 > 0. Since Us > 1, we can choose to such that
fo U. 1.
(142)
Consider the respective truncated sequence Aç:
A Un. 5 to
(143)
10, > lo.
follows from Eq. [141 that
Lats 2 (Ath)eVs+7
(144)
Note that (A**),- = 0 for t kto and (Ath)) = (E Ar)* = a.. follows that
kl+s
Σ L a² Vs+1
(145)
Hence
a V = oc.
sup
L 2 sup
(146)
t=0.1...
k20 klg +
F.3 PART 3 ISIGNAL-DOMINATERD REGIME)
The idea of the proof is that in the signal dominated case expect the main contribution L to come from the terms with large time t of the V-factor and small time increments of the other, U-factors. We then define the potential leading term (V)) by first replacing V,, by V441 in Eq. 137
1 (V.0)
Σ
Σ
UT+I-tm Utm-tmm-
tm- U Umm- 1-mm-2 Uto-os Ve41,
(147)
m= Octs, K.. st+1
28

---

Published as a conference paper at ICLR 2025
and then extending summation to negative t:
2
1
Σ
Ut+1-tm Utm -m-i Umm-1 ... Ut2-ts Ve+1
tm-1
(148)
m=0
Co <t+1
Unn Unn Usmi i.. Un| Vet Vet1
(149)
2
m=D 81 =1
V4+1
(150)
2(1 Uz)
Cv
(1+ (1+1) 5v +o1))
(131)
2(1 Un)
Thus, to establish the desired asymptotics, it is sufficient to show that the differences I I (V.0) and I (V,0)
T, are sub-leading compared the leading term I. (V)
The difference (, L1 (V.0) difference T, I (V.0) as
In terms of the operator U we can write the vector representing the
L (V.) ! -11-U))11000
(152)
where (t) if and 1 otherwise, and @ is the pointwise product. Consider the norm 95 defined with
a. "1
t
(153)
t20
with some & > be chosen later. Then if check that ||U|| 1, then ((1 11-11-1100 5t 5) as t + +oc, in particular implying that
11c0)):
0 - L, V., =(((
(154)
as desired. We have
||U||
sup Σ
U c
(155)
0s
Up sup
(156)
at-
000
U+(5+1)5
(157)
000
By assumption, U, = Sv) with some Eu > 1. Then, by the dominated convergence theorem,
lim Ur(++ ΣV
(158)
+50
by the assumption Us < 1. Therefore, by choosing & small enough, we can ensure ||U|| as desired.
The difference I. (V.0) Lt-
We start by writing
L, - L (V.0)
Σ
Σ
U Utm -m- Upg-os (Ve, V4+1)
(159)
m=1 Octis... <tm
or equivalently
L I (V.0)
-V----V-VV 1,20- 120-
(160)
29

---

Published as a conference paper at ICLR 2025
Let hy be any integer sequence such that & oo and Ke o(t). Using V2 Cvt (v (1 o(1)
and Lemma B, we have
2 2
Tu s
Σ (01
D)-')a/Vet1-s Vetll
(161)
ki
Σ
(162)
==1
ki
1
Σ ((1 U)- )o((t
Σ O(s su ( sv-
(163)
s
f/2
= =(1 + Σ
0 56 ())-v) +
Σ
0 5u 500000 - -)-
s=kt
st/2+
(164)
(w) o(t - )
Σ
O(lt s)-
(165)
s=//241
O(1),
εv >1
= (v) + O(t fv)
O(In),
Ev =1
(166)
εv <1
O(1
>>
= olt ov)+ +
0
t3 =v=1
(167)
((((L-E))-(V),
5v < 1
ott ov)
(168)
where we used the assumptions ε Eo and Eu 1.
Having established Eqs. (54), (188), we have completed the proof that
L, = 1
Cv t Ev (1 o(1).
(169)
2(1 Us)
F.4 PART 4 (NOISE- DXOISE-DOMINATED REGIME)
We transform the original loss Lr to an approximation I. through the following three steps:
1. Isolate in Lr long factor U +1-fm of length T(1 - o(1)):
T T.
(U,0)
Σ
Σ
(UT+1-44 tm 11:11-mptte
... Utmn 12 12- t2)
(170)
2
Oct C......Kl Stoy (Ti(T)
m==0 T- T (T) (1s...tmm my <T+1
x Up 11 tmg (Uemg -mm- ... Ul U,2 Vvs
(171)
Σ
(1-1))-) - -U) Vn.
(172)
0C (T) r-R(()<scT41
fu+
where (T) T
25v
so that in particular (T(T) + xo and (T) o(T), due εv > Ev.
2. Replace in L.C
(U,0) the long factor Ulm, 1 11m1 by Ur:
L
(U,1)
1
Σ
(T- - -)- Va. (173)
2
(CT(ST<T((T) T-TIT)<&STH1
30

---

Published as a conference paper at ICLR 2025
3. Finally, extend summation in (U,1) straints on 8:
dropping the upper constraints 41,6 and the lower con-
47 12)
E
--- Vas
(174)
VeUT
(175)
2(1 Un)²
Vr,CU
2(1 Us:) (T 1)+ (1)
(176)
We argue now that each of these approximations introduces an error of order ST
1. IL. + T.(0.01.. Note that the difference L - -I_ (U,0)) consists of the terms where either
11 (T),, there exists k > 1 for which (T) la < (T) Let bound the contribution of such terms.
the first case, contribution is bounded by (((T) (T)) -v) O(T oTT ), since ξv ξt.
In the second case using ((1 - (1- = O and V (t- , the contribution of these terms can be upper bounded by
T- (T))
T/2
Σ
O((T (2) 10 Ev)
Σ
0(1
(177)
4=T1()
(2))
T1-50)
(178)
o(T
(179)
since EU >
2. (T,00 - T. Since 1 = T(1 + o(1)), we have U.- - UT = (7 and
then also || L (U.1) = o(T Eu by the boundedness the summed products of remaining factors.
3. [[U1.] - I. Here one can use similar arguments, taking into account the relation
UT Ee) and the tail bound
Σ ((1 U) (1-- O(T E>
(180)
following from Lemma
This completes the proof of this part of Theorem
G GENERALIZATION OF THEOREM 3 TO V, + V/, U
In this section we drop the assumption V, V/, U, Uf adopted for Theorem 3 Accordingly, V., Us, Lt, Uz. Vy are now distinct from V/ Uk, L/ Uh. V The respective generalized version of Theorem Breads
Theorem 8. Suppose that the numbers Le are given by expansion 19 with some numbers
U., U, V,, Vi 2.0. O.
1. [Convergence] Let U < 1 and Us: < co. ALL + 0c, V. V = 0(1) (respectively, V1, Ví o(1), then also L; O(1) (respectively, - o(1))
2. [Divergence] If U3 > 1, V at least for one and U, > at least for one t, then sup:=12.... T
31

---

Published as a conference paper at ICLR 2025
3. [Signal-dominated regime] Suppose that there exist constants εv: Cy 0 such that V = Cyt ((1) as t + cc. Suppose also that U// < 1 and U2, Uy = O(t Ev) with some Eu max(Ev, 1). Then
+--U)++Ur)Cr (1 2(1 -U-)
L
(181)
4. NNoise-ominated regime] Suppose that there exist constants Ev > Eo > >1,0U > 0 such Eu
that Ut, U = Cut-Eu (1 + o(1)) and Ve, V (t- as t oc. Suppose also that
Us < 1. Then
L (1 (1-U3 U3 + UE) to (1 + o1)).
(182)
2(1 U2)2
Note that the only essential difference in the conclusions of Theorems 3 and 8 is the factor 1 1- U3, + Uy appearing in the leading terms. In the case Uy = U/S this factor evaluates to 1.
We remark also that thcorem 8 assumes in item 3 that the quantities V2 and V/,, though generally different, have the same leading terms Cvt-Ev; in particular, with the same constant Cv rather than two different constants Cy, Cy This assumption is not important and made simply because is fulfilled by the actual Vi, V as analyzed in Theorem 5 The same remark applies U,, U/ in item 4.
Proof of Theorem 1. [Convergence] The ((1) part of the claim follows from the remark after Proposition 4
For the o(1) part, we already know from Theorem 3 that U/ < 1 and Vi = o(1) imply T42 = o(1) Using the relation
1 Vo+1 + Ev.ii..
L, - -
(183)
2
and the conditions Vi = o(1), Us < oc, we then get L = o(1).
2. [Divergence] We already know from Theorem that sup, Li = co.
Since, for any > 0,
L, 2 U.L.,g. and U, > 0 at least for one s, we also have sup, L1 = co.
3. [Signal-dominated regime] We already know by Theorem that
Cv t fv (1 + o(1))
L
(184)
2(1 - U3))
EU mmaxEx(E (0, 1) and observe that 2EU
Let 7-
1-1
L.
1
V4+
Σ U
(185)
2
1-47 Cv v Ev (1+ + Σ
UU.Li Σ Uniol
(186)
2
s=0
amt-17+1
Cr -ir (1+ + (t-7Eu E + 2(1 - 211))))
Ov t-v (1 + o(1))
Ur-
2
1=1
+7
(187)
0(1),
tv >
(cr + CrUss
1 Cv
t -v (1 + o(1) + O(t maxteel
O(nt),
εv = 1
(188)
2
1- Ug
0
)
εv <1 1
1 -1(
2 Cv + CrUr
t. -Ev (1 o(1))
(189)
1- Ug/
as claimed.
32

---

Published as a conference paper at ICLR 2025
4. NNoise-omminttd regime] We know that, by Theorem
ViCC (1+
L 2(1 U2-)
(190)
We have
L V 141 2
1
Un-Lo ==0
Σ ULL + olt fu) ==0
(191)
Arguing as earlier, the leading contribution to the sum Ee=o يا comes from terms with close to or since the terms in the middle are Ott 20)) ). follows that
ViCC t to (o++
Le
Cu
L
(192)
2(1 U
8=0
We can compute
1
V
Σ
144
(1 U'
Σ
(1 U';1
V
(193)
2
2
2(1 U3)
==0
s=0
8=0
Substituting in 192
V/ Cu 2(1 - UU})
VyCU
L
Uz
Su (1+
(194)
2(1 U222
(1-U' U3 + Uz)
&u (1 +o1))
(195)
2(1 - U2)
H PROOF OF THEOREM 4
Recall that if B, AB are linear operators and / has simple eigenvalue μi associated with a one- dimensional eigenprojector P. then for small AB the operator AB has simple eigenvalue μ given by
μo + Tr|PAB] +(IABB1))
(196)
We apply this to B = Ax=0 and AB = A^ - Ax= with Ax given by (6). Observe that the noisy term Eq. (6) is O(2),, so it will only contribute a correction O()²) to μrx On the other hand, the main term in Ay, given by M + SXMST acts tensor square Sx X Sx. Accordingly, the eigenvalue A.A AA can be written as
MA 2 0(2))
(197)
where Σ사 is the leading eigenvalue of the matrix Sx- The leading linear term in zx be found, for example, from the condition
X A) = 0.
(198)
where (x,, A) is the characteristic polynomial of Sx defined in Eq. (2).. Differentiating condition 198) over X, we get
0x dzy Ox
+ 0x 0.
(199)
dx
ax
Using representation (36) x and taking into account that 2 1, this implies
dzy
0xx
0x dx
MM Im
dA
(A = 0)
(1
0)
Dm 0 mpm M
M
Qaff
(200)
33

---

Published as a conference paper at ICLR 2025
where Cefl is given by the second equality in 22
To that it is equivalent to the first equality
Oef = a - b (1 D) c, note from Eq. 35 that
0x(x, A)
x = 1, = 0) - det(1 - D),
(201)
dz
0x(x, X)
(r 1, = 0) det (acc-a
a²
b²
(202)
0x
c
1-D
det (a bT
(203)
1 1-D)
bT
det(1 - D) det
(204)
(1 - (1-D)-14 D)- I
det(1 D)(a (1-D) c).
(205)
We conclude that 2 = 1 Aed + O(13) and hence PA.A = 1 - -2aett X + O(²)), as claimed.
Clef O, then for small X the leading eigenvalue |PA,A and A^ are strictly stable.
I PROOF OF THEOREM 5
Asymptotics of V2, Vy Recall that
V = Σ "
(206)
Recall by Theorem 4 that for sufficiently small x > 0, say for X X. the maps AĄ have simple leading eigenvalue
AA. = 20 À + 0(22).
(207)
Let PA R(M+))(M++) + (x++))(( denote the corresponding one-dimensional spectral projector. Then, by the assumption of striet stability of Ax:
V
Σ
+ O(r"), + 00,
(208)
for some < r < 1. The second term will be asymptotically negligible, so we can focus on the first one.
Next, observe that the projector PA continuously depends on A. At X = 0 the matrix M, = (d0 is
precisely the leading eigenvector of Ax=0, so
(G)) PX(18)) = = A - 0.
(209)
Since for any fixed Ā > O the contribution of the terms with d > N to the expansion (008) is exponentially small, get
V (1 (1+00 o())
Σ k:AuSA
Aec A.
O(r'), co.
(210)
Given power-law spectral assumptions Enstesh 1 Velikanov Yarotsky (001)))
and relation 207 the asymptotic of
A.A. is derived by standard methods (see e.g. Theorem I in Appendix B of
Σ A.A
ARCEU 1-1 =1++0())Q 1)(2aat!)
(211)
We conclude that
= VV.V=(11
+1+ +1)2amnt))
(212)
claimed.
34

---

Published as a conference paper at ICLR 2025
Asymptotics of U,, U. We have
U.=
B Σ P. (-)))))
(213)
We argue as in the previous paragraph, but the difference now is that the matrix ( ) =e) )" is not an eigenvector Ax=o, so we need to find the projection Px=o (-))) be factored as
At = 0, this can
[ = [s
(214)
where Ps. is the spectral projector for the matrix Sx=0 and its eigenvalue 1. The corresponding eigenvector Sx=0 (b), so
Ps. (T)) x())
(215)
with coefficient that can be found, for example, from the relation
Al=o( =² = x(()) + o(1), t - co.
(216)
We have
(1 b" x
1== Dr)
A 12=0
(217)
D
80
1-1 a + b"
I = lim
DDc)
-Ceff.
(218)
10000
==0
It follows that
([[])) az + o(1), A=0
(219)
and hence
= (1+
Oeff
Σ
A + +0r'', t0.
(220)
Applying the power law spectral assumption on A and computing the standard asymptotic, finally get
- - o(1)) (ae# (ucHA))/ / T(2 1/v) 120)
(221)
|B
J PROOF OF THEOREM 6
1. Strict stability of D is equivalent to
0< 2.
(222)
By Theorem A.d 20 O(A), so
9o + 0
Olff
(223)
necessary condition of strict stability of Sx at small X 0. We exclude the case of equality Octf = 0 in this case -q and so (1, = det(1 - Sx) = 0 for all X, i.e. is an eigenvalue of S2 for all X.
Another necessary condition of strict stability is that the product of both eigenvalues of Sx is less than absolute value, i.e. Ipo + >goo < This holds for all < X < iff this holds for and X Amax- The condition for X = 0 is the already established condition < 8 < 2, while the condition for Xmax means -1 < Po + Ago < 1, i.e.
2 -
90
(224)
Amax
Amax
Under condition (224). stability can only fail to hold if S, has real eigenvalues. At the lowest point À of this failure, of the eigenvalues of Sx must be -1. Since x(1,)) -X(go Q)),
35

---

Published as a conference paper at ICLR 2025
cannot be eigenvalue of Sx for À 0 if Offf 0. On the other hand the condition x(-1, A) reads
- 20 + X(q %o O.
(225)
At = the l.h.s. is positive, so S\ does not have the eigenvalue -1 for 0 S À S Amax iff the l.h.s. also positive À = Amax, i.e.
4 28
dd
2qu = qu 41
<
(226)
Amax
Note that adding this inequality to Oeff > 0 gives the right inequality (224). so we can drop the latter.
Summarizing, the full set of necessary and sufficient conditions of strict stability is
8
4- 25
< ò < 2, O'eff > 0, -u
dcaeff <
-240
(227)
Amax
Amax
The characteristic equation det(r S2 is
(x - 1) 1 + 6) X(q10 + qo) = O.
(228)
Suppose that QI -aef. From the condition Oteff S -Oeff < O. It follows that
we have go + 21 < 0. We also have
go
(229)
F1
On the other hand, Q1 S -aeff means @1 S g0 or, equivalently,
40
1
(230)
Q1
Inequalities 229). 230 show that the root de of the linear A-term X(a + go) lies between the
roots 1, 6 of the quadratic term (xr - (> - - 1 + 8). It follows that at all À E R the matrix Sx has two real eigenvalues (possibly coinciding
02 1 - 8).
b) Now suppose that Q1 > Qcef. Suppose first that 4 > 0. Then
> 1,
(231)
01
Le. the root the term A(qi + qo) lies to the right of both roots 1, 1 8. the polynomial x(x, A) has two different real roots sufficiently small À > 0. Then, À is increased, the roots become not real and complex conjugate, and then again become real, at even larger X.
8. Then, since 91 + qu < 0,
To find the geometric position of the roots, note that they satisfy the condition
(x 1)(x - 1+ 5)
E TR.
(232)
21 + qu
This can be written as
QIœ + 40
hJ
E R.
(233)
h
where
h
(go Q (go + 41 δqi) 8. Otttf (Creff + q1)
(234)
and ((2) is the Joukowsky function. Since J (R) R \ (0) U uufe C: |2| 1}, the roots z either are real or belong to the circle 2 + 9n h, as claimed.
If q1 -fef but gn 0, have
40
6,
(235)
i.c. the root of a qo is the left of both roots 1, 1 8. The same pattern above then applies at small À > 0 there are two real eigenvalues, then complex eigenvalues, then again real, and the non-real eigenvalues again lie on the circle lyr + gol = h.
36

---

Published as a conference paper at ICLR 2025
In the special case Q1 = 0 the root are real, and then for all larger À become complex. The circle 1 gol degenerates into the straight line Rx 1 /
20 becomes infinite. For sufficiently small À the eigenvalues ?1
3. We can compute the value Ry using the identity
2C
RA =
(236)
Here, Ax can be viewed as a linear operator on _2x2 or, simpler, on the space of symmetric matrices Raym = RR. The expression (1-A,) -2)) ) can be found by symbolically solving the 3 x
linear system (1 - Ax)Z = (-2) for Z E Ray. We perform this computation in Sympy (Meurer et 2017) and obtain the reported result.
K PROOF OF THEOREM 7
Part 1. Note that the theorem assumption A < 1 implies that for some e >> 0 all the eigenvalues A < 1 -- This means that the algorithm parameters never approach the boundary of striet stability of Sx, given by theorem 4 at Amax = 1. This observation will be useful throughout the proof.
We start with showing the necessity of the first conditions 6 0 and go that are agnostic to spectrum λg- As mentioned in the main text the necessity of 6 + 0 to have Okeff + oo follows directly from strict stability bound Cef 4. Next, we observe that fixed 5, pairs of strictly stable
8
(oeff, qu) are given by qo > 5 and 0 < Oleff < 4-26 2go These inequalities define a right-angle triangle on (Oreff: go) plane with vertices at {($ -0), (0, -),, (0, -)), which can serve as useful geometric picture of relevant (Aell, ςo) values.
8
8
The condition qo > will follow from noisy stability condition Σx Rx = O()) Hence, we bound different terms appearing in Rx, taking into account A I as
2 - 28 < Ago + 2 - 5) < 4 -25,
(237)
c(4 114-201 28)= < 28 X(290 + da 4.
As - 0, all the bounds above can be replaced by some global ō-independent values. Then, we can simplify Rs up multiplicative constant
NØO dokell
Rx
(238)
A(5 Ago)
reproducing the first part of eq. (66 Observe that for 40 S we have + Ago 2 8, and, there- fore, R₂ 2 caui with some O. Then, for the stability sum we would have Σg X Rx. 2
CCkeff Σx Ax + DO, since aeff + co. This settles impossibility of go S for noisy stability.
Now, proceed to the last two stability conditions condition, assuming go > 0. Then, both nominator and denominator in (238) have only positive terms, and we can write them as + Ago x max(ō, Aqu) and Gge + daat
max(Xqń, da.s). The characteristic spectral scales that separate two choices in these maximums are ATT 4. and X sagtt as given in the main text. Note that we asymptotically have X1 < AST since Ceff + oo while go is bounded. This gives the second part of (26
da
Gafft X
0 0< < X
R
X
X
A < X < x
(239)
x À Amax 8
Substituting the above into the stability sum leads to the condition
Σ X Rs. x Oreff
Σ
+
Σ
1
+
Σ
A 0(1)
(240)
Qo
k:
A
S 95
A: 2 Aagm
37

---

Published as a conference paper at ICLR 2025
Here, the third term is always bounded since Σx A and qo is also bounded. The boundness of the first and second term corresponds to the third and forth stability conditions of theorem 7 respectively. From the argumentation presented above, it is clear that those conditions both necessary and sufficient.
Part 2. In fact, we can consider even weaker power-law spectrum assumption A k- while in the theorem statement we opted for spectral condition ① in the sake of main text consistency. Assuming & + O, the sums (240) can be estimated with a standard power-law arguments in 4o
terms of characteristic spectral index kif = ( - defined by AKT
Σ A
AE x
(241)
90
k: Av.
Sagtt of
90
90 O(). Substituting O(1), which equivalent S (1 - (1 - given in the statement of the theorem. As for the case g 2 1, it breaks the previous assumption do + 0. This brings back qo S case, where the first sum in (20 is estimated as ((ae)), leading to the divergence of Σn Rx.- Finally, when < hmax and g > O, we can see that all three sums in (240) converge zero, which translates U/S at any constant batch size [B].
Then, both the third and fourth stability conditions become andi the ansatz Offf 8- and qo 89, we get 8-h-(1-9)
L CONVERGENCE OF NON-STATIONARY ALGORITHM WITH POWER-LAW SCHEDULE
In this section, we derive the convergence rate signal propagator V/2 given by (17 for the power- law ansatz schedule (ōt, Ofeff,t, 40,+) ~ (t to const).
Adiabatic approximation. For non-stationary algorithm, evolution operators A,, essentially depend on t, making the analysis of the respective products Ax, Ax,0 very challenging.
To overcome this, we rely on the fact that the considered schedule parameters are changing very slowly at large t. Specifically, we assume that a significant change of eigenvectors of Ax, also requires a significant relative change of algorithm parameters (e.g. 2 times increase/decrease) To achieve this change
ビ- Cleff.t tx the
time window (t, At) for any power-law relation ft = t=. a large window size At t is required. Let μ1, #2, P3, f4 be the eigenvalues of Ax,, ordered |ur| > | 4al 2 |ual and S = ($1... .5....5 s1) be the matrix of respective eigenvectors. Then, if we manage to pick window size such that At < and | A < |M1 S 1, for any starting vector R2 69 R22 we have
1+Ar-1
II
A (Ax.) dL r= Σ (He)) TT) (HI
(242)
Thus, evolving starting vector with Ax, aligns the result with eigenvector corresponding the slowest eigenvalue f1 of Ax,t- The magnitude the evolution result is given, up to initial projection (s-'r), by the product of slowest eigenvalue P1. Extending this argument to many consecutive time windows (11,4+11) with At, = litj - lj growing with I,, we naturally arrive to the following adiabatic approximation
II A
I PI.
81,1
+
(243)
'our usage of this approximation has many parallels with adiabatic approximation in quantum mechanics wiki/Adiahatic thcorem
38

---

Published as a conference paper at ICLR 2025
We will use this approximation to compute asymptotic of Vt. Applying 243 to single term Vx, in V sum gives
Vr. = (())()) ArAAr-1A A ... (...Ar-)...AA((68)) x P1.PIIT-1... P1.1
(244)
log
Vadi
x exp
Here in the last transition, used that schedule be smoothly interpolated non-integer Then, replacing the sum by the integral can change the result by at most a constant, as soon as 8 < |M1.| for all
Evolution eigenvalues. Before proceeding to the calculation of the signal propagator as VT x Ex &. Vadi let write down the required properties of eigenvalues of AĄ- First, remind that, as in sec. 6 consider 72 0, which leads factorizable evolution operator A₃ = Sx @ Sx with eigenvalues equal to products of eigenvalues of Sx. With a slight abuse of notation, in the rest of the section will denote 14, H2 the eigenvalues of Sx. These eigenvalues
given by zeros of characteristic equation X(x, A) = 0 (see (36)) which in variables (ó, Ceeff go) is written as
x² x (2
A(Sosot + (0)) + - 8 Ago = 0.
(245)
The respective roots are
+ X(ooroft + 90) + VE
11.2 =
E (6 A(daeh + +o)))² 4Xdaeff
(246)
2
Let us denote Xqy2 the solutions of E(A) O, as they separate the spectrum into regions either real and complex eigenvalues M1,2- In the case 5 < ddaf < go they given by Xi iouef and Aς 46aeff These critical spectral scales, although connected, should not be confused with the other scales Ai2 appearing in (26) and separating different regions of the stability sum. In particular, we have Ag x Xσ but Apr AT. suggesting that behaviour of the stability sum changes in the middle of complex region (ATT,
5
v6
In the left real region À < X evolution eigenvalues can be approximated for À << A as RJ 1- Gen À and #2 = 5, while the border (A(T)) p2(AçT) = 1 1 2h2 (see also fig. 3 and theorem
As the schedule parameters (&e, Getf,t, 90.e) changes with time so will the spectral scales X (t) and the evaluation cigenvalues (1,2(A, t) within the respective spectral regions. The specific behavior of this change is central our computation of the signal propagator asymptotic below.
Signal propagator asymptotic. Now, we come back to signal propagator Vi and its adiabatic approximation X.7- Let fix some À < and increase time T. At first, the chosen eigenvalue À will be very small compared to (t). But as the schedule advances, it will enter the complex region at a transition time t. (A): (t. X. By substituting d,, Ceff. from our schedule, we get (A) ~ (4X) क+क This time signalizes the end of the adiabatic approximation applicability period: the latter requires | > [1z] but at = (A) we have /41 = //2 since the roots a quadratic polynomial merge the border between complex and real regions.
(t) At times T < t. (A), we can use ii (A, t) ~ aef (t) and estimate the propagator adiabatic approximation (recall that s4r (Ax) (#I()))) giving extra factor of 2)
exp J. 2 log in (t)
= exp -
2A dt exp
2 T1ta
XT
(247)
Let us look at the convergence reached by the end of adiabatic approximation applicability time to (A) R (4X) सें, Substituting this value into Vidi leads to
(id ss exp - Cvaasi L
2
Cyasi
(248)
1 78
39

---

Published as a conference paper at ICLR 2025
We see that, for 8 < 1, the propagator at t (A) has the form - with some C2 0. Thus, as À -> O, we have exponential convergence of the propagator Vadi (A) e-11A~ - 0. Moreover, after adiabatic approximation applicability time T = (A) the propagator cannot increase back, because we have strictly stable Sx with |41,2| at all times.
If we now combine the contribution to the propagator from all eigenvalues Vi =x oi Ne.T at some large T, can neglect the terms that are exponentially small in 7 (like e- Cg. C4 0) compared to polynomially small terms of the size 7- C5 > 0. The neglected terms include VA,TT for large eigenvalues λς since large eigenvalues converge exponentially fast with T, regardless of whether adiabatic approximation is used. They also include VAL.T for eigenvalues that have already left adiabatic approximation applicability region T t. (At).. For all such terms we can, in fact, formally use the adiabatic expression (247) because it will also be exponentially converged.
Summarizing, in the limit T - oo we can use the expression 247 all T and Ag and correctly capture the leading contributions into Vr. The resulting asymptotic is
A Jrmm QC Qed VA
VT x
Σ Ce Vania 2
(249)
Amar
@ 1 AT di Q
2
T ((++)
1
Here we used continuous approximation for the sum over λ'. according to ① The integral in the second line is computed by reducing it to Gamma function integral with linear change of variables
2 XT
I+a
Finally, let's comment on the allowed values of momentum exponent J. The derivation above re- quires 3 < 1, otherwise, Vadi (A) will not be exponentially converged according to 248 and adia- batic approximation will not correctly capture the leading contributions to Vy. However, the Jacobi schedule, which is provably optimal in the noiseless setting described by Vr, uses = ā = 1. This suggests that the requirement < is reasonable and approaches the optimal scaling of momentum term 5. Yet, we need a method more accurate than adiabatic approximation to treat = case.
M EXPERIMENTS
In all the experiments we consider Memory-1 algorithms with a = 0. There are many equivalent ways to implement a Memory-1 algorithm. In practice, we found it the most convenient to use minimal modification of standard SGD with momentum algorithm (referred as HB in this work) implemented in modern deep learning framework
HB
W = W. + au4
u = =Bu,- (LWw)),
(250)
Memory-1:
W++1 = W. + 024 a1 L(w,,),
This way, can use update step of standard SGD optimizer class with learning rate 02+ and then manually subtract parameter gradients with new learning rate a1
The new learning rates in parametrization 250) are expressed in terms of our main notations as = 1- 8, a1 20 ar = 6(aell a1). Then, the accelerated region 8 > Cell > qo const translates to < 02 < 01 const.
This gives another perspective the accelerated AMI algorithm identified in sec. 6 To achieve acceleration, we still want, as in HB, to make the velocity vector more inertive (i.e. making the ball "heavier"). However, while the optimally accelerated HB adds this velocity with learning rate, we add it with vanishing 02 = O(daat) + 0 learning rate but compensate with an extra "kick" term ([())) with constant Qj O(1) learning rate. Apparently, this combination leads both acceleration and bounded effect of mini- noise.
O(1)
Next, we discuss our two experimental setups
"See, for example. pytorch/SGI
40

---

Published as a conference paper at ICLR 2025
M.1 GAUSSIAN DATA
For Gaussian data experiments, we generate inputs x ~ (O, from Gaussian distribution with diagonal covariance A = diag(A1, A2,... Ams), leading to diagonal Hessian H A. For the optimal parameters, we simply take the vector of target coefficients w. = (c1, (2,, C2,... Car) Then, we set ideal power-laws for A = k= and o k- which satisfy our asymptotic power-law conditions (I) with 5. This way, we create a simple setting where all the loss curves are expected to have a pronounced power-law shape, and we will be able to directly compare experimental convergence exponents with theoretically predicted ones. We set M = 10 to ensure that truncation of the spectrum has negligible finite size effects and the experiments are well described by the asymptotic regime ł, - oc.
For the experiments fig. and fig. we pick spectral exponents < 0.5, v = 3. For the AM1 schedule exponent we use 8 0.95, a 3(1 b), at the edge of allowed AMI exponents values. In both figures [ and we compare empirical loss trajectories with power-law curves (dashed lines) with predicted convergence rate, which show good agreement between each other. In fig. we try more 8, values, and find good agreement of the experimental loss rates with predicted T, = (()-((a+)))
M.2 MNIST
We design the MNIST experiment to be the opposite of the Gaussian data setting to test our re- sults more general scenario beyond quadratic problems with asymptotically power-law spectrum. Specifically, we apply single-hidden layer neural network flattened MNIST images x E 1768;
S(W1, W2, b)
22 ReLU b) E
(251)
Vn
where Wi E R b, E 767 W2 E 1 with model width taken as n = 1000. Then, we consider one hot encoded vectors y ,,, I,..,,,...., 0) E R-O as quadratic loss LB 28 Eh y=1l2 as an empirical loss function to be minimized.
The above setting, although much simpler than modern deep-learning problems, provides ex- ample of non-convex optimization function. In particular, if one linearizes f(W1, W2, b, x) with respect to parameters the current optimization step, the resulting quadratic approximation to the original loss function will evolve during and the respective spectral distributions A C& are expected to deform significantly from the roughly power-law shapes with a 1.33 and Çv e 0.33 reported in Velikanov & Yarotsky (2021) for the limit n + co.
Yet, on f we can still see that both Jacobi-scheduled HB and AMI display qualitatively similar behavior to that of quadratic problems with power-law spectrum, though with slightly different exponents than can be expected from y 1.33, 0.33 estimation. Most importantly, Jacobi- scheduled HB retains its instabiliity in stochastic settings, while AM1 is stable at least for extremely long 10" steps duration of the experiment.
AMI algorithm in fig uses J 1 and in fact, larger than the maximal stable exponent Tmax 5(1 1 0.25 that could be estimated with MNIST eigenvalue exponent // Re 1.33. Yet, we don't 't see any signs of divergence on the whole training duration, but which were observed on Gaussian data experiments in fig. 4 That might suggest that non-quadratic models could exhibit different stability conditions due to some recovery mechanism, with the catapult effect Lewkowyez et al. (2020) being one example of such recovery. We provide MNIST loss trajectories for extra values of Batch size and algorithm parameters in fig.
0.5. This chosen effective learning rate exponent is,
41

---

Published as a conference paper at ICLR 2025
16 20.00.000.00
( 01-10,.0.22
16. 10.22-10.0 00.51
(6. (6.01100.om 4,755
20-(2, 1.50
GD
SGD:
Aul-batch
10
17
81.10.25, 0-25)
00.20.25
(8 (..25-00.25.11
05. 10.20
(0.55 -0.75)
37
144
10
10
187
127
-7
1.4
14-
10
504
16
18
10
18. 0..0m11.0 0.75)
0.-11.1 0,251
alm110
16.
16
16
16
10
30
Figure 4: Comparison of plain GD and AMI grid 7, C. We both algorithms in full-batch setting and mini-batch with |B] = 1. leading to 4 trajectories on each subplot. Also, we choose 0. to avoid any non-asymptotic divergence. For
0.1 for both algorithms, and Oetf, each couple a, we color in green the subplot titles if stability condition and in red otherwise. We observe that all empirically diverged trajectories are predicted correctly by this stability condition, while a single trajectory (5.a) (1.0, 0.75) is expected to diverge but demonstrate only large but bounded noise fluctuations. Finally, along each experimental trajectory, plot exact power-law (dashed) line with rate: tー~ for GD and t (-(+))) for AMI. Again, observe very good agreement between theoretical prediction and empirical rates, validating adiabatic approximation of see. L Moreover, the rate (((1+ remains valid even for the case = not covered by adiabatic approximation.
8(1 !) holds,
42

---

Published as a conference paper at ICLR 2025
Saech des: (8) 10003
Bancs ebe: 101-1200
55
Sehrt dte. -0:-200
Eorch con: 121-10
Barth s0e: B1-1
2
18
Lomn Po Lomvi
18 187
Jackk R1
120 10
Figure 5: Trajectories of plain GD, Jacobi scheduled HB and AMI for different learning rates and batch sizes. For each subplot, learning rate a of and Jacubi-scheduled HB equal to "kick" learning rate 01 of AMI. Also, Jacobi-scheduled HB and AMI have exactly the same values of momentum Bg = 2 on each iteration. We observe that AMI is indeed much more stable than Jacobi-scheduled HB for range of learning rates and batch sizes. Moreover, it is stable for larger values of a than estimated maximal value Omax 2 0.25. Another interesting observation is that the divergent trajectories of Jacobi scheduled HB, unlike for pure quadratic problems, only get stuck around the loss of random prediction instead of diverging to infinity.
43


Reviews:
[{"review_id": "TMIELXwL1u", "reviewer": "Reviewer_kpRS", "summary": "This paper establishes a theoretical framework for the so-called memory-M algorithms - first order algorithms that are augmented with storage for M vectors in the gradient space, and uses a linear combination of them to compute the gradients and modify weight updates. The usefulness of this framework is that it is a natural generalization of Heavy Ball and a number of other first order algorithms. The work provides an equivalence of this formulation with recursive multi-step first-order algorithms. The work also provides a generalized loss decomposition into signal and noise propagations. The paper also provides a detailed description of convergence properties of memory-M (and focusing on memory-1) algorithms - including the main parameters controlling this convergence and an algorithm providing equivalent convergence rates for the SGD case.", "questions": "As mentioned, I wonder if there are any ways of improving the readability of the technical portions with further addition of intuitions and heuristics. This wouldn’t change the technical contributions of the paper but would make the paper more accessible for the readers and thus facilitate the propagation of ideas in it.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Overall, this is a very good paper. I think it is very methodical in its development of the memory-M framework - starting with existing issues of accelerated HB for SGD, moving to the description of the generalized framework for GD and SGD, loss decomposition and improved algorithm and convergence properties. The topic coverage is very comprehensive, covering the expected questions raising with the development of the generalized framework. There are clearly a lot of efforts made towards the balance between rigor and readability - with moving a lot of the technical details into the appendix (e.g. the phrasing of Theorem 2). The contributions are novel to the field of stochastic optimization", "weaknesses": "An expected consequence of the comprehensiveness of the paper is its density - making it relatively hard to read. As mentioned before, there was clearly a lot of effort put towards reorganization and moving details into the appendix - but I wonder if more could be done in that direction. For example, the Loss expansion section with the introduction of propagators seemed too dense - and was lacking intuitions that would facilitate further reading of the paper, since those concepts were heavily relied on for further developments in the paper. Those intuitions were present in the earlier sections and were thus helpful for speeding up understanding of the paper", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XpTcF1q2XW", "reviewer": "Reviewer_1Va8", "summary": "This paper introduces a framework for analyzing iterative optimization methods, referred to as memory-$M$ algorithms, which allow the gradient to be evaluated at shifted points relative to $w_t$ additionally a shift term is added to the gradient when doing the update. The authors explore both stationary (with fixed update parameters) and non-stationary versions of these algorithms. They establish that memory-$M$ algorithms can achieve the optimal convergence rate for data with a power-law spectrum, even under mini-batch noise. Notably, they propose a memory-1 algorithm with a time-dependent power-law schedule, which provides a heuristic pathway to accelerated convergence, supported by empirical results.\n\n\n**Justification for the score**\n\nWhile I think the result is important in establishing convergence results for a large family of methods, I think the presentation of the paper could be significantly improved.", "questions": "1. Could such a framework be extended to non-IID batching, that is, batching with replacement (recent work [1,2])?\n\n2. Could you say anything about the generalization error using [3]?\n\n3. Could we add label noise or regularization?\n\n[1] Lok, Jackie, Rishi Sonthalia, and Elizaveta Rebrova. \"Discrete error dynamics of mini-batch gradient descent for least squares regression.\" arXiv preprint arXiv:2406.03696 (2024).\n\n[2] Beneventano, Pierfrancesco. \"On the trajectories of sgd without replacement.\" arXiv preprint arXiv:2312.16143 (2023).\n\n[3]  Wang, Y., Sonthalia, R. &amp; Hu, W.. (2024). Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization. <i>Proceedings of The 27th International Conference on Artificial Intelligence and Statistics</i>, in <i>Proceedings of Machine Learning Research</i> 238:4483-4491 Available from https://proceedings.mlr.press/v238/wang24l.html.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "The paper's biggest strength is the establishment of strong convergence rates for iterative methods. Mini-batched algorithms are difficult to analyze; hence, establishing the convergence rate for regression in the noiseless regime is interesting. \n\nAdditionally, the method allows for controlling the constant and shows that it can also be arbitrarily improved. \n\nI think both of these are important contributions. \n\nIn addition, the paper introduces a general framework for analyzing such methods. i think this is an important contribution as well.", "weaknesses": "The writing of the paper is a major weakness. It is very dense notationally, not necessarily conceptually. This makes it quite challenging to build intuition as one reads the paper. One possible suggestion is that the paper develops the results initially in the $a = 0$ as the shifts are not needed for the main contributions and then provide extensions, possibly in the appendix. The other is to hide some of the intermediate steps to provide space for more intuition for the different objects. \n\nOne thing that threw me off is using capital letters for the propagators as these are scalars.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kpr7VMcwkF", "reviewer": "Reviewer_LKb1", "summary": "This paper explores how to make stochastic gradient descent (SGD) faster on certain types of optimization problems, specifically those that involve a noisy mini-batch setting. The authors examine how adding \"memory\" (extra helper variables) to SGD can help. They introduce \"memory-$M$\" algorithms, where $M$ is the number of extra velocity vectors added. Through mathematical analysis, they show that these memory-$M$ algorithms can achieve better performance by improving certain constants that affect convergence speed, even though they don’t change the basic rate of convergence.\n\nThe authors also propose a new \"memory-1\" algorithm, which has only one extra velocity vector and uses a special time-based schedule for learning. This algorithm is shown to improve performance both theoretically and in experiments.", "questions": "Can authors convince me that their work fits the spirit of this conference? This question is not obvious to me at this point.....", "limitations": "", "rating": 3, "confidence": 2, "soundness": 1, "presentation": 1, "contribution": 3, "strengths": "The work is a definite interest to read, and the results seem to hold a lot of promise.", "weaknesses": "- Introduction: The reader who is not an expert in this field will find this introduction difficult to understand. I recommend that it be significantly reworked using various welcome tricks, such as tables. In general, the text is difficult to read....\n\n- I don't fully understand about the experimental part. Is it just not there?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r1vb9WvrpD", "reviewer": "Reviewer_eHN7", "summary": "In this work, the authors address the open problem of theoretical feasible acceleration of mini-batch SGD-type algorithms (i.e. in the stochastic setting) on infinite-dimensional quadratic problems, particularly with power-law spectrum. \nThe authors introduce memory-M algorithms with M auxiliary velocity vectors and show the equivalence to the multistep recurrence formulation if the loss $L$ is quadratic and hyperparameters of the algorithm are stationary. \nBy expanding the loss in terms of so-called signal and noise propagators, the authors show that the loss convergence $L_t \\sim C_l t^{-\\xi}$ of stationary stable memory-M algorithms retain the exponent $\\xi$ of plain GD, but can have different constants $C_L$. Finally the authors prove that memory-1 algorithms can make $C_L$ arbitrarily small while maintaining stability. The theoretical results are empirically verified on synthetic Gaussian data and MNIST using a shallow ReLU network.", "questions": "1. I do not fully understand the image on the right of Figure 2. What are $t_1, ..., t_4$ supposed to denote or perhaps more generally what does it mean that a signal/noise propagator is \"long\" or \"short\"?\n2. I have another question regarding the stability of the maps $A_\\lambda$: If I understood it correctly, $\\lambda$ corresponds to the eigenvalues of the matrix $\\mathbf{H}$ (line 201). Thus, it seems to me that we have to assume $\\lambda > 0$ in general. Does Theorem 3 then imply that one can only have strict stability of $A_{\\lambda}$ if $\\lambda_{\\max}$ is sufficiently small? \n3. What are the values of $\\xi_V$ and $\\xi_U$ respectively in Eq. (21) and (22)? \n4. Have the authors also considered non-quadratic settings and how does it perform here?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The authors are able to (heuristically) derive an accelerated and stable rate of convergence in their algorithm AM1 and verify the rate empirically. (However I am not too familiar with the field to judge the novelty of this contribution.) \n- The derivation of the stability of stationary stable memory-M algorithms seems rigorous and it is interesting to see that stationary stable algorithms cannot achieve a faster rate than plain GD even using arbitrary numbers $M$ auxiliary vectors. \n- The analysis of the convergence constant $C_L$ and the possibility of making it arbitrarily small for stationary stable memory-1 algorithms and how it relates to the effective learning rate $\\alpha_{eff}$ was also insightful.", "weaknesses": "- The paper seemed quite convoluted with many different symbols, equations and indices due to its mathematic rigor and it could benefit from restructuring it such that it becomes more accessible. \n- The empirical validation of the results remains quite limited with only experiments on synthetic Gaussian data and MNIST. Particularly, the spectrally expressible approximation holds exactly for gaussian data and approximately for MNIST classification. It would be interesting to see also experiments where this approximation is less exact.\n- It is seems like the optimal rate depends on the right choice of hyperparameters, such as $\\alpha_0$, $q_0$ and $\\delta$. However it is unclear to me how to select or estimate them in practice. This limits its application to real-world problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)