Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensions
Authors: Kiwon Lee
Andrew Nicholas Cheng
Elliot Paquette
Courtney Paquette
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stochastic Gradient Descent with Momentum
Random Matrix Theory
High Dimensional Probability

Abstract: We analyze the dynamics of large batch stochastic gradient descent with momentum (SGD+M) on the least squares problem when both the number of samples and dimensions are large. In this setting, we show that the dynamics of SGD+M converge to a deterministic discrete Volterra equation as dimension increases, which we analyze.  We identify a stability measurement, the implicit conditioning ratio (ICR), which regulates the ability of SGD+M to accelerate the algorithm.  When the batch size exceeds this ICR, SGD+M converges linearly at a rate of $\mathcal{O}(1/\sqrt{\kappa})$, matching optimal full-batch momentum (in particular performing as well as a full-batch but with a fraction of the size).  For batch sizes smaller than the ICR, in contrast, SGD+M has rates that scale like a multiple of the single batch SGD rate. We give explicit choices for the learning rate and momentum parameter in terms of the Hessian spectra that achieve this performance.

Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensions
Kiwon Lee
Andrew N. Cheng
Department of Mathematics and Statistics McGill University
Department of Mathematics and Statistics
McGill University
Montreal, QC H3A OB9
Montreal, QC H3A 0B9
kiwon. weweemalllll.....eee.........eee mmwgill.............
andrew. cheng@mail wewmmggmaal.mmmlll....
Courtney Paquette
Elliot Paquette
Department of Mathematics and Statistics
Department of Mathematics and Statistics McGill University
McGill University
Montreal, QC H3A 0B9
Montreal, QC H3A 0B9
courtney paguettebnegiil..cc
elliof pwquette@mcgilllcccommm
Abstract
We analyze the dynamics of large batch stochastic gradient descent with momentum (SGD+M) on the least squares problem when both the number of samples and dimensions are large. In this setting, show that the dynamics of SGD+M converge to deterministic discrete Volterra equation as dimension increases, which analyze. We identify stability measurement, the implicit conditioning ratio (ICR), which regulates the ability of SGD+M to accelerate the algorithm. When the batch size exceeds this ICR, SGD+M converges linearly rate of (k))Vk), matching optimal full-batch momentum (in particular performing as well full-batch but with fraction of the size). For batch sizes smaller than the ICR, in contrast, SGD+M has rates that scale like a multiple of the single batch SGD rate. We give explicit choices for the learning rate and momentum parameter in termss of the Hessian spectra that achieve this performance.
Stochastic learning algorithms the methods of choice for optimization of high-dimensional problems. Often stochastic learning algorithms incorporate momentum into their stochastic gradients improve practical performance. Perhaps the simplest, stochastic gradient descent with momentum (SGD+M) adds a fixed multiple of the backward difference of iterates to its stochastic gradient estimator, Section for details. In the influential work of [33], the authors empirically show augmenting stochastic gradient descent (SGD) with momentum significantly improves training performance of deep neural networks. Despite the wide usage of these stochastic momentum methods in machine learning practice, our understanding of its behaviour is not well-understood.
It has been hypothesized that stochastic- based momentum algorithms improve training because they are employed on a large batch of a data set [15]; thereby emulating the speed-up one sees in full-batch settings. For many learning problems, the "large batch" setting is often paired with high-dimensional problems, meaning there are many samples (and likely also many features to have interesting behavior). While we know of no theoretical work that fully justify these claims for standard SGD+M, there have been some recent progress [6, 7]. For variations of SGD+M and SGD success in proving accelerated rates [3, 13, 18).
with Nesterov momentum [24] there has been One reason has been challenging that the typical approaches for analyzing SGD+M do not distinguish large and small batch sizes. We address this problem in this paper and we introduce
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

Figure 1: Concentration of SGD+M on a Gaussian random least squares problem such that the ratio d/n is fixed to be 2; 30 runs of SGD+M and the 80th percentile confidence intervals recorded (shaded re- gion) for each n.. The parameters for SGD+M are 0.5, Section 1.1. The random least squares problem becomes non-random in the large limit and all runs of SGD+M converge to deterministic function (t) (red) given by our Volterra equation (I).
109
Volterse. n= 64
Function Values
1
256
1024
10.2
4096
10
A = 0.5, 7 = 0.4,
10
10-5
10
0
20
40
60
80
100
Iterations
stability measurement that exactly captures the transition of SGD+M to an accelerated method. We comment that in the high-dimensional vanishing batch fraction setting (the mini- size is o(n), where n is the number of samples), there is work proving in various simplified settings that SGD+M produces the same iterates as SGD with a larger learning rate, up to a vanishing error [26].
In this paper, we study the dynamics of mini-batch least
SGD+M (with constant learning rate) squares problem when the number of samples n and features d are large (see Section for details). We assume the targets are generated using a linear (gener- ative) model. We are motivated by the setting where the mini-batch size 3 is proportionate to the number
1.00
0.95
0.90
=0.50
0.55
convergence
0.85
0.60
0.80
0.65
0.70
del of samples n and so we define the ratio ( B/n, which we refer to as the batch fraction. We provide a asymptotto comparison for the behavior of the training loss under SGD+M to deterministic func- tion v. whose accuracy improves when the number of samples and features large while the batch frac- tion is strictly positive (see Figure 1). This function d solves a discrete Volterra equation:
0.75
0.75
0.80
0.70
0.95
0.90
0.65
0.95
0.60
(= ICR
0.60
0.65
0.70
0.75
0.80 0.85
0.95 1.00
batch fraction {
Figure 2: Convergence rate as batch size changes on a Gaussian random least squares
problem with ratio r def d varying. Here k = " (+ ++v/)2/(1-// /F)² and = 1/(1 1 -
(t++1) + =((++))=(((+D) F(++1) + (())((I- - k). (1)
k=
When < goes above a specific value (see Proposition 5), the convergence rate freezes at 1/ Otherwise the rate behaves like C/R with constant C = </(1 - () and we get speed up from SGD+M.
The forcing term F(t) and kernel K(t) are explicit functions that depend on the hyperparameters and the full Hessian spectra (see Section 2 and Ap- pendix A). They transparently reveal that the dynam- ics of SGD+M and of SGD are truly non-equivalent in that there is no mapping of the hyperparameters which leads them to have the same training dynamics. We also note that a similar equation appears in the vanishing batch setting [27], although in that setting it is a Volterra integral equation, which can be recovered from (1) by sending < - 0.
An advantage of the exact loss trajectory is that we give a rigorous definition of the large batch and small batch regimes which reflect transition in the convergence behavior of SGD+M. To do this we introduce the condition number K., the average condition number R, and the implicit conditioning ratio (ICR) defined as
def Ejenn of 2
max
def min
2
K
and ICR
def
R VK
Here o3 are the cigenvalues of the Hessian of the least squares problem with o and a the largest and smallest (non-zero) eigenvalues. We refer to the large batch regime where Ç 2 ICR and the small batch regime where Ç < ICR. In the large batch regime (2), SGD+M matches the performance of the heavy-ball algorithm: the convergence is linear with rate given by O(1/ In the small batch regime, the performance matches that of SGD, i.e. the convergence rate is O(C/R). We give matching lower bounds, and we provide momentum and learning rate choices that achieve the claimed performance. In addition we show there is a saturating batch fruction (see Figure 2),
2

---

after which increasing the batch fraction does not improve the rate. It explicitly occurs when Ç ICR. Moreover this saturating batch fraction occurs before full batch, i.c. Ç (= 1.
Related work. Recent works have established convergence guarantees for SGD+M in both strongly convex and non-strongly convex setting [9, 31], including almost sure convergence [10]. In the work of [25], they used stochastic differential equations (SDEs) to obtain convergence of SGD+M. Specializing to the setting of minimizing quadraties, the authors of [19] demonstrated that the iterates of SGD+M converge linearly (but not in 1.2) under an exactness assumption.
Determining batch size has been an important issue in determining the convergence rate of SGD and SGD+M. There are instances where (small batch size) SGD+M does not necessarily achieve better performances than small batch size SGD (see [15, 27, 35)). As for mini-batch SGD without momentum, [20] showed that there is a saturating batch size (roughly R R/K) above which increasing the batch size no longer improves the rate. In [8]. the authors implemented an adaptive (increasing) batch size schedule and they used it to show linear convergence for SGD. For generalization, [32] empirically showed that for SGD and SGD+M, instead of decaying the learning rate, one can increase the batch size during training to obtain similar learning curve.
SGD+M has been proven be useful in practical applications as well, including machine learning. [33] demonstrated that SGD+M shows an empirical advantage in training deep and recurrent neural networks (DNNs and RNNs respectively). Many authors have proposed that learning rate warmup enables us to scale training efficiently to larger batch sizes ([11, 22, 32]).
1 Setting
We consider the least squares problem when the number of samples (n) and features (d) are large:
{ f(x)
Σ (1( def Σ (a - b.) (a,x-b.,)
with b def A +
arg min mERd
(3)
where A Rexd a data matrix whose i-th row is denoted by a, Rd, E Rd is the signal vector, and 17 E R" is a source of noise. The target b = A + comes from a generative model corrupted by noise. We let of 2 ... of 2 be the eigenvalues of the matrix AA" with o and a oiin the largest and smallest (nonzero) eigenvalues.
We apply SGD with momentum (SGD+M) with mini- to the finite sum, quadratic problem (3). Let 2o E IRd be randomly selected following 1.1 and æ; be generated from SGD without momentum, no
i.e. 3 35 - 7 Eien, V (((oo)). SGD+M iterates by selecting uniformly random subset
B& S {1. ... .n3 of cardinality B and makes the update
1k41 Th 7
Σ REBR
f((z)) A(#x xK-1)
(4)
= F3 A PA b) A(# - Ik-1), where
PR
def
Σ c,e
R
with P& random orthogonal projection matrix and e; the i-th standard basis vector. Here is the learning rate parameter, A the momentum parameter, and the function f; is the i-th element of the sum in (3).
When the stochastic gradient in (4) is replaced with the full-gradient V (xx),, the resulting algorithm with learning rate and momentum optimally chosen yields the celebrated algorithm, heavy-ball momentum (a.k.a. Polyak momentum) [29]. The optimal learning rate and momentum parameters are explicitly given by
V Vonax
V min
and
(5)
muxx +
min )2
Viuax
well-known that heavy-ball an optimal algorithm on the least squares problem in that it converges linearly at rate of ((1 (see [28]).
In this paper, we adhere whenever possible to the following notation. We denote vectors lowercase
boldface (a:) and matrices in upper boldface (A). The entries of vector (or matrix) are denoted by
3

---

0.3
Empircal Vattrra X 2.5)
5GD+M1 0.5)
densty
0.2
Function Values
xx
0.1
30
3x
0.0
logfeigenvallues, MNIST
Iterations
Figure 3: SGD+M vs. Theory on even/odd MNIST. MNIST (60, 000 x 28 28 images) [16] is reshaped into single matrix of dimension 60, 000 x 784 (preconditioned to have centered rows of norm-l), representing 60,000 samples of 10 digits. The target satisfies b; 0.5 the 7th sample is an odd digit and b; = -0.5 otherwise. SGD+M was run 10 times with (A = 0.8, and the empirical Volterra was run once with (R = 1000, R = 5300). The 10 to 90 percentile interval is displayed for the loss values of 10 runs of SGD+M. While MNIST data set does not satisfy eigenvalue assumption on the data matrix, the solution to the Volterra equation MNIST data set captures the dynamics SGD+M. See App. D for more details.
0.001, S = 0.5)
subscripts. Unless otherwise specified, the norm || ll2 is taken to be the standard Euclidean norm if it is applied to vector and the operator 2-norm if it is applied to matrix.
1.1 Random least squares problem
To perform our analysis we make the following explicit assumptions on the signal x, the noise r7, and the data matrix A.
Assumption 1.1 (Initialization, signal, and noise). The initial vector ao E Rd is chosen so that 2o - n. is independent of the matrix A. The noise vector E Rh is centered and has ii.d entries, independent of A. The signal and noise are normalized so that
E
DD
and E[ R
Next we state assumptions on the data matrix A as well as its eigenvalue and eigenvector distribution. for all i. We suggest
Each row a; E Rdx is centered and is normalized so that Ella,1| as central example the Gaussian random least squares setup where each entry of A is sampled independently from a standard normal distribution with variance 7.
Assumption 1.2 (Orthogonal invariance). Let A be random x d mutrix. Suppose these random matrices satisfy a left orthogonal invariance condition: Let E Rax= be an orthogonal matrix. Then the matrix A is orthogonally left invariant in the sense that
OA
law A.
This assumption implies that the left singular vectors of are uniformly distributed on the sphere which is the strongest form of eigenvector delocalization; many distributions of random matrices including some sparse ones (such as random regular graph adjacency matrices) are known to have some form of cigenvector delocalization. The classic example of random matrix which has left orthogonal invariance is the sample covariance matrix, Z E, for i..d. Gaussian matrix Z and any covariance matrix Σ. Numerical simulations suggest that (6) can be weakened in that the theory herein be applied to other ensembles without this orthogonal invariance property. See Figure 3.
2 Deterministic Dynamical Equivalent of SGD+M
With these assumptions, we can give an explicit representation of the loss values on a least squares problem at the iterates generated by SGD+M algorithm. We show in this section (see Theorem 1): for any > 0,
sup [f(w)) (b)) + 0 in probability, 05157

---

where solves (1). We begin by discussing the forcing and the noise terms of (t) and their relationship to SGD+M.
Forcing term: problem instance information. The forcing term represents the mean (with respect to expectation over the mini-batches) behavior of SGD+M. In fact, the forcing term the loss I under full-batch gradient descent with momentum A but with learning rate 75. For small learning rate 7, the forcing term F(t) in (1) governs the dynamics of (t)..
Let wi Ax; b and observe that 1/2l|2// 112 is the loss f(z)). One way to get the dynamics of f is by deriving a recurrence for w (for each j E [n]) which we get from the updates of SGD+M. The
recurrence is as followed: define Lz, def (uf, w2-1 w1.) and there exists a matrix M, (see Appendix A.2) so that
R+11= = -M, + (Error).
(7)
The forcing term at iteration / is given by applying a linear recurrence M, operator t -- times on vector containing initialization information at each E [n] and then summed up for the first coordinate. It is clear that the maximum of the eigenvalues of the operator M, is essential to analyze the convergence behavior of Ft)). We denote X1,j A and X i 2, 3, the eigenvalues of M, and note that I max;=2,3 Ar,l (see (39) for an explicit formula of Ax, that depends only on % A, and eigenvalues of AA Let X2 be the eigenvalue of M, with the biggest modulus and let
def max 122,51-
m2max
From this, an equation for the forcing term F()) can be made explicit in terms of Xı,, see Thm. below and Appendix A. We can conclude that F(t) (X2 max))
Kernel term: noise from the algorithm. The convolution term in (1) is due to the inherent stochasticity of SGD+M. More specifically, it is given by
72 - () k=
Hz - k)),)),
where
Q2 = xÇa} + A,
(9)
20
and H2(1) def
-
A+1
144 + - -
Ω3 41
2 2,
The presence of vp (training loss) is due to the fact that the noise generated by the k-th stochastic gradient proportional to vkk) (training loss), and the function Hz fiff-Kt k) represents the progress of the algorithm in sending this extra noise to O. Observe (9) scales quadratically in the learning rate y. Hence for large learning rates, (9) dominates the decay behaviour of tb. Further details discussed in Section 3.1.
We now state the main result:
Theorem 1 (Concentration of SGD+M), Suppose Assumptions 1.1 and 1.2 hold with the learning rate 7 Co
I+ and the batch size satisfies B/n = Ç for some Ç O. Let the constant N. Then
there exists C > O such that for any c > O, there exists D > 0 satisfying
15(x)) +0)) [(0)> -c] <Dn
Pr
sup OSISTHIEN
(10)
for sufficiently large n E N.. The function up is the solution to the Volterra equation
R (t + +
R ht + +1++ +
v((+1) + 1)= -
2C(1 - H)H2(t k)),(),,
x00) = f(xo), (11)
2
2
k=0
forring
noise
where for k = 0, 3, and j E [m]] Kig
def
=
+ A). and
1
2(07)*
--An((o3) A 1 (K2. -)2)')))))
1 _ A)2 -(aa)))
(t)
+ 2
71
22
4A
5

---

For more detailed description ho, h1 Hg well as the proof of Theorem 1 and Corollary 1, see Appendix A. The expression of y highlights how the algorithm, learning rate, batch size, momentum, and noise levels interact with each other to produce different dynamics. Note that the learning rate assumption will be necessary for the solution to the Volterra equation to be convergent, see Proposition 2. When A - O, obtain the Volterra equation for SGD with mini-batching.
Corollary (Concentration of SGD, no momentum). Under the same setting as Theorem and when A = 0. the function values f(x:) converge to (t()) as in (10) where now the limit to is a solution to the Volterra equation
R (t 1) +
R ho + 1)+ Σ -211 5)h2(t k))(()).
cb 1)
(12)
2
2
k=0
where for k = 1,1
(t) 1
2k (1 -{07)21
jj
n j=1
Remark, Note that Ht) reduces to h2(t) in A = 0) case. Also when the limit Ç - O and when we e 2- This coincides with the result from [27, Theorem 1]. Indeed, this shows not only how our dynamics of SGD+M includes the no momentum case (i.e. SGD), but also how the dynamics of SGD+M differ from SGD.
scale time by t/C. we have that (1 11-2(07) )(-))))
3 Convolution Volterra analysis
In this section, outline how utilize the Volterra equation (11) produce complexity analysis of SGD+M. For additional details and proofs in this section, see Appendix C.
We begin by establishing sufficient conditions for the convergence of the solution to the Volterra equation (11). Our Volterra equation can be seen as the renewal equation ([4)). Let us translate (11) into the form of the renewal equation as follows:
(1 +1) +())))((())( (I)),
(13)
where (ʃ * (1) = Ex f(t k)g(k). Let the kernel norm be ||| E K(t). By [4. Proposition 7.4], we see that ||||| < necessary for our solution to the Volterra equation to convergent. Indeed,
have the following result.
Proposition 1. If the norm ||||| 1. the algorithm is convergent in that
(00) lim (1) (max(11 - d 2.03)
R
(14)
[
Note that the noise factor R and the matrix dimension ratio d/n appear in the limit. Proposition formulates the limit behaviour of the objective function in both the over-determined and the under- determined case of least squares. When under-determined, the ratio d/n 2 1 and the limiting (o())) is O; otherwise the limit loss value is strictly positive. The result (14) only makes sense when the noise term K satisfies ||||| < 1; the next proposition illustrates the conditions on the learning rate and the trace of the eigenvalues of AA" such that the kernel norm is less than 1.
Proposition 2 (Convergence threshold). Under the learning rate condition 7
I+A and trace
condition I-A
(1-()2 1 tr(AAT) < 1, the kernel norm ||]|| < 1, i.e., Eee K(t)<<)
The learning rate condition quantifies an upper bound of good learning rates by the largest eigenvalue of the covariance matrix 2² o batch size S. and the momentum parameter A. The trace condition illustrates a constraint on the growth of _ Moreover, for full batch gradient descent model (S = 1), the trace condition can be dropped and we get the classical learning rate condition for gradient descent.

---

1.0
batch fraction. (= 0.85
batch fraction, (= 0.85
batch fraction. (= 0.85
0.6
0.9
0.6
0.9
0.6
0.9
convergence rale
leamiin rate.
1/Martussian
0.0
0.4
0.7
0.2
0.2
0.2
0.6
Polyak parameters Average-care optimal
8.0
0.2
0.4
0.6
0.8
0.00
0.2
0.4
0.5
0.8
8.0
0.2
0.4
0.6
0.8
momeniuum, A
fraction. C-
fraction, C-
batch fraction, (-
0.95
1.2
0.98
0.8
convergence rate
0
1.0
-.6
2.0
0
0.6
0.8
0.94
learning
0.80
0.92
0.4
1.0
0.4
0.70
0.2
0.75
0.5
0.88
0.0
0.4 0.6
0.00
0.4
0.6
8800
0.2
0.4
momentum,
Figure 4: Different convergence rate regions: problem constrained regime versus algorithmi- cally constrained regime for Gaussian random least squares problem with (n 2000 x d 1000). Plots are functions of momentum (z-axis) and learning rate (y-axis). Analytic expression for X2, (see (8), (39)) convergence rate of forcing term Ft)) given in (top row, column 1) represents the problem constrained region. (top row, column 2) plots 1/MMathusian exponent) ((15), for details see Appendix D); black region is where the Malthusian exponent E does not exist. This represents the algorithmically constrained region. Finally, (top row, column 3 and bottom row) plots convergence rate of SGD+M max (x2xmxxmmxx = =_ }, (see (16)), for various batch fractions. When the Malthusian exponent does not exist (black), m takes over the convergence rate of SGD+M; otherwise the noise in the algorithm (i.e. Malthusian exponent dominates. Optimal parameters that maximize 22maa denoted by Polyak parameters (orange circle, (17)) and the optimal parameters for SGD+M (orange dot); below red line the problem constrained region; otherwise the algorithmic constrained region. When batch fractions < = 0.85 and < = 0.7 (top row and bottom row, column 1) (i.e., large batch), the SGD+M convergence rate is the deterministic momentum rate 1/ VK. As the batch fraction decreases (C 0.25). the convergence rate becomes that of SGD and the optimal parameters of SGD+M and Polyak parameters are quite far from each other. The Malthusian exponent (algorithmically constrained region) starts to control the SGD+M rate as batch fraction -> 0.
3.1
The Malthusian exponent and complexity
The rate of convergence of &a is essentially the worse of two terms - the forcing term F(t) and discrete time convolution Eizo (t))K((t k) which depends the kernel K. Intuitively, the forcing term captures the behavior the expected value of SGD+M and the discrete time convolution captures the slowdown in training due to noise created by the algorithm. Note that F(t) is always a lower bound for (t), but it can be that (t) is exponentially (in t) larger than F(t) owing to the convolution term. This occurs when something called the Malthusian exponent, denoted E, of the convolution Volterra equation exists. The Malthusian exponent 3 is given as the unique solution to
20
22 - +) E'H2(t) 1,
the solution exists.
(15)
The Malthusian exponent enters into the complexity analysis the following way: Theorem (Asymptotic rates). The inverse of the Malthusian exponent always satisfies E-1 A2. for finite n. Moreover, for some C > 0, the convergence rate for SGD+M is
(t) - (00) < C "mxx (2. E 1 and lim (v(() ((x))) max X2,max E-1). (16) 10000
Thus to understand the rates of convergence, it is necessary to understand the Malthusian exponent as a function of and A.
7

---

3.2 Two regimes for the Malthusian exponent
On the one hand, the Malthusian exponent E comes from the stochasticity of the algorithm itself. On the other hand, X2 max (2; Ç) is determined completely by the problem instance information - the eigenspectrum of AA" (Note we want to emphasize the dependence of X mam on learning rate, momentum, and batch fraction.) Let o and o denote the maximum and minimum nonzero eigenvalues of AA", respectively. For a fixed batch size, the optimal parameters (x),Ax) of X2,max
2
(Vonax
Vo min
and A
(17)
Volax max + VVomin In the full batch setting, i.e. Ç = 1, these optimal parameters "/a and 4, for A2,max are exactly the Polyak momentum parameters (5). Moreover, in this setting, there is stochasticity the Malthusian exponent disappears and the convergence rate (16) is X2 max. We observe from (17) that for all fixed batch sizes, the optimal momentum parameter, A,, is independent of batch size. The only dependence on batch size appears in the learning rate. At first it appears that for small batch fractions, one can take large learning rates, but in that case, the inverse of the Malthusian exponent E dominates the convergence rate of SGD+M (16) and you cannot take y and A to be as in (17) (See Figure 4).
Pmax + V O
We will define two subsets of parameter space, the problem constrained regime and the algorithmically constrained regime (or stochastically constrained regime). The problem constrained regime for some tolerance > 0
problem constrained regime
del' ((7.4) A) 1 v3
X s)}.
(18)
The remainder we call the algorithmically constrained regime. To explain the tolerance: for finite n, it transpires that we always have E-1 X2,,max but it could be vanishingly close A2, as function of n. Hence we introduce the tolerance to give the correct qualitative behavior in finite n.
Proposition 3. If the learning rate r S min(
1+A Ç0 man Co
(1-V3)"), with the trace condition
80-O7 1 trAA A) < 1, then (r, A) is in the problem constrained regime with 1/2.
Therefore by (16), we have that
4A2,max
(1) (10) S (1+ Xg
for some D) > 0;
(19)
we note that the expression in the parenthesis is 3 (1_xx,maxx)
xz,max) + +0((1
x2 A2,
In the problem constrained regime, worthwhile to note that the overall convergence rate is the same as full batch momentum with adjusted learning rate, i.e., the batch size does not play important role as long as we are the problem constrained regime:
Proposition 4 (Concentration of SGD + M, full batch). Suppose Ç = 1 and Assumptions 1.1 and 1.2 hold with the learning rate y < 1+ we let ax! denote the iterates of full hall-batch gradient descent with momentum (GD+M), then
max
R Pr + 0, where Upar( + 1) 1)= R h1 (1 Mlo 1). (20)
R
( (()aa()) OS1ST
sup
12-000
The functions hi and he are defined in Theorem with = In particular, let "Ifut denote the learning rate for full batch GD+M, and 7,5 S < with corresponding v in Theorem 1. Then when "full = 76 is satisfied, vé and uyya share the same convergence rate in the problem constrained regime.
for the learning rate and batch fraction in S
4 Performance of SGD+M: implicit conditioning ratio (ICR)
Recall from (2) the definition of condition number, average condition number, and the implicit conditioning ratio
def Σ jEini of
22 Fmax def
ICR def
and
(21)
σ min
Vi
min

---

Figure 5: For each value of the batch fraction, G we run SGD+M for 50 iterations on (normal- ized) MNIST data set using a random features set- up with Gaussian weight matrix W E RT84xd (see App. D for details) and targets odd/even. We record the function value of the last iterate. The momentum and learning rate parameters are set be near- -ear-optimal (22). Gray dot is the computed ICR value. At the predicted Ç ICR (gray dot), there is change in the behavior of the last iter- ate. For Ç S ICR, the value of the last iterate monotonically decreases until it hits the ICR. For < ICR, we see no improvement in the value the last iterate. This agrees with the theory that the convergence rate does not change.
MNIS,, random features d=1000
last iterate function value
MARA M Aom
d-3500
de6000
x 103
C ICR
3x
2 x 10
0.00
0.05
0.10
0.15
0.20
0.25 0.30
zela,
Moreover recall that we refer to the large batch regime where { 2 ICR and the small batch regime where C < ICR.
We begin by giving a rate guarantee that holds in the problem constrained regime, for specific choice of y and A.
Proposition 5 (Good momentum parameters), Suppose the learning rate and momentum satisfy
7 (1 -1-v 2 and A max
2k
where C def 5/(8(1 ())- (22)
Somin
3/2
Then X2maax
A and for some
C >> O, the convergence rate for SGD+M is
{
24
(1) - ((x) S C A A C maxx
(23)
V2k
with the learning rate y as in (22), we have that A2.max A. By minimizing the A (i.e., by finding the fastest convergence rate), we get the formula for the momentum parameter in (22).
Remark 1.
We note that for all satisfying O-VAY < (+VA)
Co
25
The exact tradeoff in convergence rates (23) occurs when
V2 ICR
or Ç
(24)
22
1+ & ICR
As S S 1, this condition is only nontrivial when ICR < 1, in which case - 8 ICR, up to vanishing errors. This is illustrated the MNIST data set in Figure 5.
/2
Large batch 2 ICR). In this regime SGD+M's performance matches the performance of the heavy-ball algorithm with the Polyak momentum parameters (up to absolute constants). More specifically with the choices of y and in Proposition 5, the linear rate of convergence of SGD+M for an absolute e. Note that Ç does not appear in the rate, and in particular there is no gain convergence rate by increasing the batch fraction.
is 1 Vk
Small batch (C S ICR). In the small batch regime, the value of C is relatively small and the first term is dominant in (23), and so the linear rate of convergence SGD+M is & for some absolute constant > 0. In this regime, there is a benefit in increasing the batch fraction, and the rate increases linearly with the fraction. We note that on expanding the choice of constants in small Ç the choices made in Proposition 5 are
C and 7
SR
256 min
This rate can also be achieved by taking = 0, i.e. mini-batch SGD with no momentum. Moreover, it is not possible to beat this by using momentum; we show the following lower bound:

---

Proposition 6. ffC min 2. ICR] then there is an absolute constant C' > 0 so that for convergent
(y, () (those satisfying Proposition 2), v //2,max
This is lower bound the rate of convergence by Theorem 2.
parallel argument of Proposition holds for SGD without momentum.
Proposition 7 (Good learning rate for SGD without momentum). Suppose the learning rate Y
satisfies
7 max
(25)
Co max 8(1-5) A)
Then m2, = (1-1(0 min)) )2 for some C' >> 0, the convergence rate for SGD without momentum is
{ 1
C
v0() (00) S C X2 maxx = C max
(26)
K
where C def c/(8(1-1))
For details on the proof of Proposition 7, see Appendix C. The exact tradeoff in convergence rates occurs when
8 ICR
def
8(1 ()- I)(ATA)) Ç 1 + 8 ICR
where
ICR
(27)
K
As Ç S 1, this condition is only nontrivial when ICR < 1, in which case Ç 8 x ICR, up to vanishing enrors. When we are in the large batch setting (Ç 2 ICR), the linear rate of convergence of SGD is <f for some absolute constant 0.
On the other hand. when in the small batch regime, i.e., < S ICR, the convergence rate is fixed by 1-1. Note that does not appear in the convergence rate, so there is no loss in convergencee rate by decreasing the batch fraction.
As a result, SGD converges more slowly the large batch setting than in the small batch setting (see [14]).
5 Conclusion and future work
We have shown that the SGD+M method on a least squares problem demonstrates deterministic behavior in the large n and limit. We described the dynamics of this algorithm through a dis- crete Volterra equation and for a fixed batch fraction. Moreover we characterized a dichotomy of convergence regimes depending on the learning rate and momentum parameters. Furthermore, we proved that SGD+M shows distinguishable improvement over SGD in the large batch regime and we provided parameters which achieve acceleration. Our theory is also supported by numerical experiments on the isotropic features model and MNIST data set (see Appendix D for details).
While our analysis focuses SGD+M algorithm applied the least squares problems with orthogo- nal invariant data matrix, Figure 3 suggests that the Volterra prediction might hold in even greater generality. Removing these conditions, leave future work. Another direction of future work consists in finding the deterministic dynamics for generalization errors.
Acknowledgments and Disclosure of Funding
C. Paquette's research was supported by CIFAR AI Chair, MILA, a Discovery Grant from the Natural Science and Engineering Council (NSERC), and the FRQNT New University Researcher's 's Start-up Program. Research by Paquette was supported by a Discovery Grant from the Natural Science and Engineering Council (NSERC), Additional revenues related to this work: C. Paquette has part-time employment Google Research, Brain Team, Montreal, QC.
10

---

References
[1] R. Adamczak. A note on the Hanson- Wright inequality for random vectors with dependencies. Electronic Communications in Probability, 20(none):1 13, 2015.
[2] B. Adlam and J. Pennington. The Neural Tangent Kernel in High Dimensions: Triple De- scent and Multi-Scale Theory of Generalization. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 74-84, PMLR, 13-18 Jul 2020.
[3] Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research,
2017.
[4] S. Asmussen. Applied probability and queues. volume 51 of Applications of Mathematics (New York). Springer- Verlag, New York, second edition, 2003. Stochastic Modelling and Applied Probability.
[5] R. Bardenet and Odalric-Ambrym M. Concentration inequalities for sampling without replace- ment. Bernoulli, 21(3):1361 1385, 2015.
[6] R. Bollapragada, T. Chen, and R. Ward. On the fast convergence of minibatch heavy ball momentum. arXiv preprint arXiv:2206.0755 075553, 2022.
[7] B. Can and M. Gurbuzbalaban. Entropic Risk-Averse Generalized Momentum Methods. arXiv preprint arXiv:2204.1122 2022.
[8] S. De, A. Yadav, D. Jacobs, and T. Goldstein. Big Batch SGI): tive Batch Sizes. In Proceedings of the 20th International Conference on Artificial Intelligence and Statisties (AISTATS), 2017.
Automated Inference using Adap-
[9] N. Flammarion and F. Bach. From Averaging to Acceleration, There Only a Step-size. In Proceedings of The 28th Conference Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 658-695. PMLR, 2015.
[10] S. Gadat, Panloup, and S. Saadane. Stochastic heavy ball. Electronic Journal of Statistics, 12(1):461 529, 2018.
[11] Goyal, Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, Kyrola, A. Tulloch, Y. Jia, and K. He. Accurate, Large Minibatch SGD: Training ImageNet in Hour. arXiv preprint MiXiv11706002611 2017.
[12] T. Hastie, A. Montanari, S. Rosset, and R.J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08555 2019.
[13] P. Jain, S. Kakade, R. Kidambi, P. Netrapalli, and Sidford. Accelerating Stochastic Gradient Descent for Least Squares Regression. In Proceedings of the 31st Conference On Learning Theory (COLT), volume 75 of Proceedings of Machine Learning Research, pages 545-604 PMLR, 2018
[14] P. Jain, S. Kakade, R. Kidambi, P. Netrapalli, and A. Sidford. Parallelizing Stochastic Gradient Descent for Least Squares Regression: bati-nat Averaging, and Model Misspecification. Journal of Machine Learning Research (JMLR), 18(223):1-42 2018.
[15] R. Kidambi, P. Netrapalli, P. Jain, and S. Kakade. On the Insufficiency of Existing Momentum Schemes for Stochastic Optimization. In International Conference on Learning Representations (ICLR), pages 1-9, 2018.
[16] Y. LeCun, C. Cortes, and C. Burges. "MNIST" handwritten digit database, 2010.
[17] Z. Liao and R. Couillet. The Dynamics of Learning: A Random Matrix Approach. Proceedings of the 35th International Conference Machine Learning (ICML), 2018.
[18] C. Liu and M. Belkin. Accelerating SGD with momentum for over-parameterizee learning. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.

---

[19] N. Loizou and P. Richtarik. Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods. Comput Optim Appl. 77:653-710, 2020.
[20] S. Ma, R. Bassily, and M. Belkin. The power of interpolation: Understanding the effective- ness of SGD in modern over peea-arrmetrized learning. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 3224-334. PMLR, 2018.
[21] V. Marchenko and L.. Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the USSR-Shornik, 1967.
[22] S. McCandlish, J. Kaplan, D. Amodei, and OpenAl Dota Team. An Empirical Model of Large-Batch Training, 2018.
[23] S. Mei and A. Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv: 05355, 2019.
[24] Y. Nesterov. Introductory lectures on convex optimization. Springer, 2004.
[25] A. Orvieto, J. Kohler, and A. Lucchi. The Role of Memory in Stochastic Optimization. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 356-366, 2020.
[26] C. Paquette and E. Paquette. Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models. In Advances in Neural Information Processing Systems (NeurIPS), vol- ume 34, 2021.
[27] C. Paquette, K. Lee, F. Pedregosa, and E. Paquette. SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality. In Proceedings of Thirty Fourth Conference on Learning Theory (COLT), volume 134 of Proceedings of Machine Learning Research, pages 3548-3626, 2021.
[28] F. Pedregosa. A hitchhiker's guide to momentum, 2021. URL http://fa. http://ffabaaappp/////// wet net/blog/ 2021/hitchhiker/.
[29] B.T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 04, 1964.
[30] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NeurIPS), pages 1177-1184, 2008.
[31] O. Sebbouh, R. Gower, and A. Defazio. Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball. In Proceedings of Thirty Fourth Conference Learning Theory (COLT), volume 134 of Proceedings of Machine Learning Research, pages 3935-3971, 2021.
[32] S.L. Smith, P.-J. Kindermans, C. Ying, and Q V. Le. Don't Decay the Learning Rate, Increase the Batch Size. In International Conference on Learning Representations (ICLR), 2018.
[33] I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and momentum in deep learning. In Proceedings of the 30th International Conference on Machine Learning (ICML), volume 28, pages 1139- 1147, 2013.
[34] R. Vershynin. High--Diensiinnl Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi: 000001/9711102231111
[35] G. Zhang, L. Li, Z. Nado, J. Martens, S. Sachdeva, G. Dahl, C. Shallue, and R. Grosse. Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes] We clearly state in our abstract all the results that we show and we make sure there are corresponding proofs all the theorems in the main text. The abstract indicates explicitly that we are working the high-dimensional least- squares problem.
(b) Did you describe the limitations of your work? [Yes] We make clear that the results only apply to the least squares problem in Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We address the potential negative societal impacts in the appendix. We do not anticipate any ethical or societal issues. The results presented in this paper concern the analysis of existing methods.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] The work presented is purely theoretical and contains an analysis of an existing algorithm.
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions are clearly stated in Section and they are included in the statements of all the theorems. We make sure to inform the reader that the results only hold for the least squares problem and a left orthogonal invariance condition on the data matrix.
(b) Did you include complete proofs of all theoretical results? [Yes] Every statement in the main text has corresponding proof in the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as URL)? [Yes] The hyper- parameters for every experiment are clearly stated in Appendix D. In this section, we describe how we generated each of our figures.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] In Appendix D, we give deseription of how to generate all the figures. We are also providing our simulation code.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We indicate in the caption the figures how many runs we did and if there
any averaging, see e.g., Figure 1.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] All simulations were done on a standard laptop using Colab. No GPUs, internal clusters, cloud providers were used.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets... (a) If your work uses existing assets, did you cite the creators? [Yes]] We cited all the relevant related work. We only used one data set, MNIST [16), which is open source.
We cited the creator of MNIST in the figures.
(b) Did you mention the license of the assets? [Yes] The only data set used is open source.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We included the code to generate all the figures in the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A] The data set (MNIST [16]) is open source.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] The data set (MNIST [16]) used does not contain any personally identifiable information or offensive content. This data set is standard data set used benchmarking.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if ap- plicable? [N/A] The work is purely theoretical and does not require any crowdsoureing or human subjects.
13

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] The work is purely theoretical and does not require any crowdsoureing or human subjects.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] The work is purely theoretical and does not require any crowdsourcing or human subjects.
14


Reviews:
[{"review_id": "P9plx6Juyd", "reviewer": "Reviewer_hZQR", "summary": "This paper studies large batch stochastic gradient descent with momentum, where the setting is specialized to the least square problem with large sample size and dimension. It is shown that the dynamics of SGD with momentum will converge to deterministic dynamics described by the discrete Volterra equation, as the sample size increases. Based on this, a quantity called implicit conditioning ratio is identified to characterize when SGD with momentum can achieve acceleration. This further yields suitable choices for the learning rate and momentum parameter.", "questions": "Some comments and questions are as follows:\n\n1. The paper title suggests that the dimension $d$ is high, but this is not clear from the results. For example, in Theorem 1, is it true that the result holds for a fixed $d$ as $n$ goes to infinity? This also concerns the paragraph from line 220 to 225. When $d$ is fixed, it is an over-determined linear regression for large $n$. The same problem exists in the statement of Proposition 4. If $d$ is fixed and $n$ is large, then basically each SGD step corresponds to an over-determined linear regression?  I'd like the authors to clarify the relationship between $n$ and $d$.\n\n2. In Theorem 1, it is said that Eq.(12) holds for sufficiently large $n$. What is the threshold for being 'sufficiently large'? Also, the definition/properties of the function $H$ in Eq.(13) should be specified in the theorem statement, otherwise it is not clear what is its dependence on the problem parameters.\n\n3. What is $\\mathcal{K}$ in Eq.(15) when translating Eq.(13) into the form of Eq.(15)?\n\n4. Theorem 1 characterizes the closeness between the SGD+M iterates and the discrete Volterra equation iterates, but only for finite $T$ and the error does not decrease with $T$. This suggests that there is a gap between the convergence of SGD+M and that of $\\psi$. Thus it is misleading to make claim about the convergence of SGD+M based on the convergence of $\\psi$, as in Theorem 2. I'd like the authors to discuss how to resolve this gap, otherwise the claims about the convergence of SGD+M is problematic. ", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is clearly written and easy to follow. The problem setting and assumptions are clarified, and the discussion on the results yields interesting observations about the behavior of SGD with momentum. However, there is still a gap between the actual convergence of SGD with momentum and the presented equivalence between SGD with momentum and the discrete Volterra equation, which makes some claims a bit misleading. See details below.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "I7AxjeXhHjz", "reviewer": "Reviewer_qtmY", "summary": "In this paper, the authors analyzed the dynamics of stochastic gradient descent with momentum based on the linear regression (least-squares) problems. They used the deterministic discrete Volterra equation to approximate the dynamics of stochastic gradient descent with momentum. They provided proof of convergence of the iterates of stochastic gradient descent with momentum to the discrete Volterra equation in Theorem 1. They proposed the Implicit conditioning ratio (ICR) and claimed that there are two regimes. For large batch sizes, the SGD+M performance matches the performance of the heavy-ball algorithm with Polyak momentum parameters, while there is no gain in convergence rate by increasing the batch fraction. For small batch sizes, there is still a benefit in increasing the batch fraction.", "questions": "1) In Assumption 1.1, there is an assumption about the initialization x_0, which is not normal for the problems. It is hard to check this assumption since the signal \\tilde{x} is not known in practice.\n2) In the experiment part, Figures 4 and 6 are based on Gaussian random least squares problems. They are based on calculating the analytic expression for convergence rate. Is it possible to plot the figure based on an empirical experiment?\n3) In section 4, the authors mentioned the two batch size regimes. Providing experiments comparing these two regimes will be great to validate this claim.\n4) Figure 4 and 6 are based on least-squares problems, are there similar figures for MNIST experiments?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The paper has solid mathematical proof and contributions.\n2) The figures in the paper are well-presented.\n3) The idea of the paper has been written in a clear and reader-friendly way.\n\nWeaknesses:\n1) The organization of the paper is not reader-friendly. The figures of experiments are located in different places on paper and the setting of the experiments is in the supplementary documents. It's quite hard to follow when reading the paper.\n2) There are several functions in the paper, such as h_1, h_0, H_2, which are defined in the supplementary documents. But in the main text, the authors use the conclusion from the function that F(t)-\\bigO(\\lambda _{2,max}^t). This may confuse readers.\n3) Since there are several constants in the paper, it may be better to have a table for the definition of constants.\n4) There is not enough related work discussed in the related work section.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FoEeqR18HW", "reviewer": "Reviewer_n1XZ", "summary": "The author analyzes the dynamics of large batch stochastic gradient descent with momentum and shows that the dynamics of SGD+M converge to a deterministic discrete Volterra equation as dimension increases. The author also identifies a stability measurement, the implicit conditioning ratio (ICR), for the stability of SGD+M and gives explicit choices for the learning rate and momentum parameter.", "questions": "1. When do we say the number of samples (n) is large? n = 1000?\n2. Why does the author add $P_k$ in Eq. (4)? \n3. Since the author uses the function $\\psi$ to approximate the training loss trajectory, how do you select the factors, $R$ and $\\tilde{R}$ such that $\\psi$ can approximate the training loss trajectory accurately?\n\nTypos\n\nLine 86 used a -> used\n\nLine 91 do -> does\n\nLine 191 discussed -> are discussed\n\nLine 211 a produce?\n\nLine 303 benefit -> a benefit\n\nLine 306 achieved -> be achieved\n\netc.\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The author provides a non-asymptotic comparison for the behavior of the training loss under SGD+M to a deterministic function $\\psi$.\n2. The exact loss trajectory gives a rigorous definition of the large batch and small batch regimes.\n3. The author introduces a stability measurement that exactly captures the transition of SGD+M to an accelerated method.\n4. The author finds that the dynamics of SGD+M and of SGD are truly non-equivalent.\n\nWeaknesses\n1. When the number of samples (n) is small, the function $\\psi$ cannot accurately approximate the training loss.\n2. Factors $R$ and $\\tilde{R}$, should be predefined.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CTYXlMwAKtx", "reviewer": "Reviewer_ARN4", "summary": "Analysis and characterization of two regimes for SGD on quadratic problems. Large batch setting where accelerated rates occur and small batch setting where non-accelerated rates occur.", "questions": "It's confusing to use \\kappa as a constant and capital kappa for kernel, the symbols are almost the same, perhaps change the notation for the kernel to just K? a lot of papers use that.\n\nThe beginning of section two doesn't make much sense without reading the appendix, it leaves too much out.\n\nAre the eigenvalues of H $\\sigma$ or $\\sigma^{2}$? Using $\\sigma^{2}$ is a little odd.", "limitations": "A theory paper is always limited by its assumptions. The assumptions are very very strong here, almost the strongest possible given the setting. However, the results are correspondingly concrete and specific, so strong assumptions are ok.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I generally like the approach this paper takes and the theoretical outcomes. The separation of the convergence rates into two regimes makes a lot of sense and matches my personal intuition about the behavior occurring in practice. Although momentum helps stochastic optimization in many practical settings, in my experience it doesn't appear to provide \"acceleration\", but rather robustness and generalization advantages, and I think the behavior in practice is very much what the theory in this paper describes in the small batch setting. I don't know of any papers using large-batch training where acceleration-like improvements are observed when using momentum, I wonder if the authors are aware of any?\nI'm not familiar with discrete Volterra equations, as I expect would be the case for most readers. I'm still able to largely follow the arguments presented. The results are surprisingly precise regarding the $\\zeta$ and its relation to the spectrum. Some further plots showing the behavior in and around the cross-over region would be nice.\n\nThe use of text-wrapped figures here doesn't make sense to me, given that in both cases two figures are stacked, they could easily be instead stacked side-by-side and floated at the top of the pages without losing any space, I would suggest the authors do that for the camera ready. It's more readable.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept