Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions
Authors: Courtney Paquette
Elliot Paquette
Ben Adlam
Jeffrey Pennington
Venue: NeurIPS 2022 Accept (2022)
Keywords: High dimensional
least squares
SGD
implicit regularization
exact dynamics
SDE

Abstract: Stochastic gradient descent (SGD) is a pillar of modern machine learning, serving as the go-to optimization algorithm for a diverse array of problems. While the empirical success of SGD is often attributed to its computational efficiency and favorable generalization behavior, neither effect is well understood and disentangling them remains an open problem. Even in the simple setting of convex quadratic problems, worst-case analyses give an asymptotic convergence rate for SGD that is no better than full-batch gradient descent (GD), and the purported implicit regularization effects of SGD lack a precise explanation. In this work, we study the dynamics of multi-pass SGD on high-dimensional convex quadratics and establish an asymptotic equivalence to a stochastic differential equation, which we call homogenized stochastic gradient descent (HSGD), whose solutions we characterize explicitly in terms of a Volterra integral equation. These results yield precise formulas for the learning and risk trajectories, which reveal a mechanism of implicit conditioning that explains the efficiency of SGD relative to GD. We also prove that the noise from SGD negatively impacts generalization performance, ruling out the possibility of any type of implicit regularization in this context. Finally, we show how to adapt the HSGD formalism to include streaming SGD, which allows us to produce an exact prediction for the excess risk of multi-pass SGD relative to that of streaming SGD (bootstrap risk).

Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions
Courtney Paquette
Elliot Paquette
Google Research, Brain and McGill University courtney paquette@mogill.
McGill University
elliot. www.ootppppuuuttttoolllle.
Ben Adlam Google Research, Brain
Jeffrey Pennington Google Research, Brain
Abstract
Stochastic gradient descent (SGD) is a pillar of modern machine learning, serv- ing the go-to optimization algorithm for diverse array of problems. While the empirical success of SGD is often attributed to its computational efficiency and favorable generalization behavior, neither effect well understood and dis- entangling them remains an open problem. Even in the simple setting of convex quadratic problems, worst-case analyses give an asymptotic convergence rate for SGD that is no better than full-batch gradient descent (GD), and the purported implicit regularization effects of SGD lack a precise explanation. In this work, we study the dynamics of multi-pass SGD high-dimensional convex quadraties and establish an asymptotic equivalence to stochastic differential equation, which we call homogenized stochastic gradient descent (HSGD), whose solutions we characterize explicitly terms of a Volterra integral equation. These results yield precise formulas for the learning and risk trajectories, which reveal mechanism implicit conditioning that explains the efficiency of SGD relative to GD. We also prove that the noise from SGD negatively impacts generalization performance, this context.
ruling out the possibility of any type of implicit regularization Finally, show how to adapt the HSGD formalism include streaming SGD, which allows us to produce an exact prediction for the excess risk of multi-pass SGD relative to that of streaming SGD (bootstrap risk).
Introduction
Stochastic gradient descent (SGD) is the algorithm of choice for optimization in modern machine learning and has been hailed as a major reason for deep learning's success [11, 21]. Explanations for the effectiveness of SGD typically refer its computational efficiency and its favorable generalization properties, but theoretical understanding these purported benefits is far from complete.
The efficiency of SGD has been the subject of extensive research, dating back to the original work of Robbins and Monro [68] and extending to modern large-scale machine learning applications (see e.g. [10, 12]). However, despite its widespread adoption and algorithmic simplicity, surprisingly little is known about how SGD performs in the types of high- nigh-dimensional optimization problems that occur practice. Part of the challenge in deriving robust high-level conclusions about the efficiency depend precisely which quantities are measured and
of SGD is simply that those conclusions what assumptions are leveraged. For example, in the extreme setting where the samples are one-hot vectors, running SGD on quadratic function is actually identical to running full-bater gradient descent; as such, any statements about the two algorithms' relative efficiency must be data-dependent.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Furthermore, the majority of prior analyses focus on the streaming or single-pan pagsse-pssssacoeo setting, where each sample is seen single time. While this setting is appropriate when the number of samples is much larger than the dimensionality d, it does not adequately describe the practically-relevant overparameratized or high-dimensional settings where d 2 n.
Moreover, the practical success of SGD has been so remarkable in recent years that a growing body of literature has suggested that its benefit generalization extends beyond what any improved efficiency might reasonably afford [76, 31, 14, 72, 74]. Some of the myriad explanations for SGD's 's favorable generalization properties include the local geometry of minimizers [32, 26, 82, 24], connections to approximate Bayesian inference [49], and the regularization properties of noise [75], among many others. While some of the these perspectives are intuitive and compelling, they are often difficult to rigorously establish from either an empirical or theoretical perspective. Empirically, simulations large scale command significant computational resources, and can challenging to push to sufficiently late times or sufficiently large batches to establish the appropriate baselines [72, 75]. Theoretically, the strongest existing results are again the single-pass setting, for which a number of works have established excess risk bounds for quadratic problems [6. 18, 20, 81]. Much less is known in the multi-pass setting, though stability results were established by [25], and some recent works have begun examining generalization [39].
In this work, we study the dynamics of multi-pass SGD on high-dimensiones convex quadratic functions and derive exact asymptotic predictions for the learning and risk trajectories. Our analysis establishes an asymptotic equivalence stochastic differential equation, which we call homogenized stochastic gradient descent (HSGD), whose solutions we characterize explicitly in terms of a Volterra integral equation. These results allow to define a precise data-dependent implicit-conditionnng ratio (ICR) that determines whether SGD is more efficient than its full-batch cousins. The ICR favors SGD for many practical datasets, providing some explanation for the observed superior efficiency of SGD; interestingly, we also highlight settings for which SGD is less efficient than full-batch momentum gradient descent, underscoring the data-dependence of the conclusions. Moreover, our results also show that SGD does not improve generalization performance, whether measured in-distribution or disiistriuttion, and therefore that SGD does not offer any form of implicit regularization in this setting. We emphasize that results do not rule out possible benefits for non-convex problems, but they do provide some of the first explicit negative results in the convex quadratic case.
1.1 Contributions
Our primary contributions are to:
1. Establish the equivalence of quadratic statistics computed on the iterates of SGD and on particular stochastic Langevin diffusion process called homogonized SGD (Theorem I);
2. Exactly characterize the asymptotic training and risk trajectories as the solutions of deterministic Volterra integral equation (Theorem 2);
3. Prove that the noise from SGD negatively impacts generalization performance, both in- and out-of-distribution (Section 3)1), but explain why the impact often minimal in practice; ratio that describes when and by how much SGD
4. Introduce the implicit-conditionin accelerates convergence relative to the best full- ball-batch methods (Section 3.2);
5. Analyze the limit of streaming SGD to show its inability to capture many salient features of the dynamics of multi-pass SGD (Appendix C).
2 Preliminaries and background
Problem setting.
We consider high-dimensional (e-regularized least squares problems defined by,
min fxx)
def 1 2
Ax
-b12 + 2
|
Σ (a.x b.)²
n
- +
5 |
(1)
(m))
where 5 2 0 is the ridge-regularization parameter. We denote the ridgeless empirical risk as
((x)
del
Ax b blg.
2

---

On the problem (1), the steps taken by gradient decent (GD) can be written recursively as
m- gd g- 1++1
Ft The V f( (
m-gd
gd 2
Yi. A" (aAAArr) th gd b) Th dze m-gd
(Au
+A(a)) migd m-
(3)
where A 0 is the momentum parameter, 7h is the learning rate schedule, and ao E Rd is initial vector assumed to be independent of all other randomness and having norm at most 1. When A is large, computing these updates can be expensive, so an unbiased estimator for the true gradient is often used, where a subset of the data points are selected uniformly at random. We focus on the setting with batch size equal one and without momentum, which we refer to as stochastic gradient descent (SGD), and for which the iterates can be written recursively as
agu 2 F xx
V Si, (2x; = ad The A Alei,
Ci2 e (Ax; b)
7h sgd
(4)
where the is (ni(( (n]) iid. While it would also be possible to consider mini-batch SGD, previous work has shown that batch sizes that are vanishingly small as a fraction of the number of samples are equivalent to the single-batch analysis, after appropriately adjusting the time by a factor of the batch size [60, Theorem 1]; similarly, we do not consider -ige-iimeniional SGD with momentum as it degenerates to SGD [58]. See also [30].
Diffusion approximations and homogenized SGD. A common paradigm for understanding SGD is through stochastic Langevin diffusions (SLD), i.e. solutions of equations of the form
dx, (V)(((x, dt + v E, dB.),
(5)
where y is the step size of SGD, f is the loss function, B, is a d-dimensional standard Brownian motion, and the matrix 0 3 E, E Rdxd models the noise covariance. In many analyses, no concrete connection between SGD and SL.D is developed, and the diffusion is merely used to build intuition. A common example is the isotropic case (E, xx L2), for which the fokker-Plance equation implies that the dynamics are reversible with respect a density proportional to e C()()) with C2, > 0 some constant. Consequently, the process can escape local minima, exhibiting a trade-off between the entropy and depth of minima and thereby highlighting possible mechanism of implicit regularization. In the general anisotropic case, describing the stationary distribution is more difficult; nonetheless, the local geometry near minima of f can be analyzed, see [14, 35].
While this type of implicit entropic regularization might ultimately underlie the generalization benefits of SGD for nonconvex problems, currently we lack precise connection between a concrete SLD and a practical nonconvex learning problem. As such, the implicit regularization effects of SGD on nonconvex losses remains largely unsolved problem.
For convex quadratics, however, the implications of Eq. (5) are quite clear: there is no notion of implicit regularization as the noise in SLD negatively impacts generalization performance. Note that because the noise is mean zero, any SLD is centered around gradient flow (GF) X which solves
dxc
leading to the following conclusion for generalization (see also [88]):
Lemma 1. Suppose the objective function f(x) = 1 Al b1l2 + 01|==12). Suppose (X, itt [0, oo)) is SLD (i.e. X, solves (5)) with || EE olop almost surely bounded by some C << co. Suppose the population risk R: Rdd + IR a convex function and denote x.
def lime- Xy, then
F(R(X.))
R(X
for all t. 2 and hence,
lim inf E(R(X,)) Z 1-+00
R(x.))
pop. risk of SLD
pop, rick gradiem flo
limiting pop. risk of SLD
Vimiting pop. risk gradient flow
If in addition R strictly convex, and E; + Exc with Eg > 0, then the inequality strict.
Proof. The mean E E[x,), by the linearity of the gradient V f. is GF. Under the conditions given, the law of X, converges Gaussian variable centered at æ,, Hence by Fatou's lemma and Jensen's inequality, the inequality follows.
We emphasize that this conclusion applies even under general distribution shifts, so long as the risk remains a convex function. Still, the utility of Lemma I may not be immediately clear, it pertains
3

---

to SLD and we have not yet established any concrete connection between SLD and the process of interest, SGD. Nor is evident what form such connection should take- the agreement between SGD and an SLDD cannot occur at the level of individual states since the randomness from each process not assumed to be coupled. Instead, the most we can hope for is that statisties of the processes agree. Specifically, we might hope that matching the noise structure of SGD with a careful choice of SLD will cause relevant statistics, like the population risk, to be equal.
It turns out that such a choice of SLD exists for convex quadratic problems in high dimensions, and is given by homogenized SGD (HSGD), introduced simultaneously in [52. 58]. Both the empirical and population risks (L, R resp.) of HSGD agree with the same of SGD in the high-dimensional limit (see Thm. 1). Mathematically. HSGD is the strong solution of the stochastic differential equation:
dx, def = (()) dt +tt ((X dB,, for quadratic L, (7)
where again B, is d-dimensional standard Brownian motion, 7() is the learning rate schedule, and the initial condition is Xn = zn- Roughly, HSGD is a diffusion approximation to SGD that gains explanatory power when the dimensionality is large. In particular, it does not require the step size to be small, in contrast to the usual paradigm of SLD approximations. Note that as with other universality results, the details of the noise distribution are not relevant and only the second-order correlations contribute, which are carefully matched by HSGD to SGD.
The precise sense of the comparison requires to evaluate low-dimensional statistics of the high- dimensional dynamics; diw-ddmensioonl" must be effective, in that the univariate statistics of the SGD iterates concentrate around the same statistic evaluated HSGD. For understanding generalization or implicit regularization properties, a important statistic is the population risk, R.
Assumptions. For all parts of our analysis to hold, the pair (A, b) of the data matrix A E Raxxd and target vector b E RR must satisfy some quasi-random assumptions a set of deterministic conditions on the pair (A, b) that are satisfied with high probability by natural classes of random matrix-vector pairs (see Appendix B for specifics). We use the convention that the target and initialization vectors are bounded independent of n, ||b1|2 < C' and | S C, respectively.
We illustrate some examples below that we have shown to satisfy the quasi-random assumptions.
Gaussian linear regression. Here the rows of A are iid and drawn from a Gaussian with norm-bounded covariance Σ and the target b is drawn from generative model, b = Aæ + for some unknown signal Rd and independent noise v) E IR".
Subgaussian linear designs. In the example above, be of the form 1//2 for æ vector of iid centered subgaussian random variables [88, 30]. Gaussian random features with a linear ground truth [51, 3, 66, 4). Suppose A is given by a (X W) for an iid standard Gaussian weight matrix W and Gaussian data matrix X. Suitable assumptions on the activation function a and the covariance of X added.
relax the Gaussian assumption to
Assumption 1. The population risk R Rd - R is quadratic, that is, it is a degree-2 polynomial or, equivalently, can be represented by
1 R(x:)) = x. Tx: + u x +
2
for some d X d symmetric matrix T. vector E Rd, and scalar R. We further assume that || op < C. [[VR(0)] < C. and IR(0)) C.
A natural population risk is given by R(x)= E
((a x b)a] where (a. b) ~ D. This distribution D may or may not be the same as the distribution that generated the data [A b) used in training.
As we work in the high-dimensional limit, we suppose that 7/k (k/n)) for a smooth, bounded
function 7(-) such that (t) + E 00) and a sup:20 (t) < co.
def
3 Main results
Our main results are analyzable (non-asymptotic) expressions for the empirical risk L and the population risk R of SGD at any time i for the high-dimensional least squares problem (1). To begin, we first establish the following equivalence between SGD and HGSD.

---

Empirical risk
Population risk
SGD n 4,000
10
Volterra 4,000
CIFAR- 5m. Random Features
SGD 6,000
Volterra, 6,000
10-1
SGD 10,000
SGD 20,000
Volterra,
SGD 40,000
10-2
10--
Streamnnn SGD
Streaming Volterra
CIFAR.Sm,
10
10
10'
10
10
10
10a
10a
10r
10*
10
iterations
iterations
Figure 1: Single runs of SGD HSGD (Volterra) in streaming on standarized CIFAR-5M [54] with car/plane class vector (1, 000, 000 samples); standarized ReLu (74) random features model (see Appendix B. was applied with increasing number of samples and fixed d 6000. The predicted behavior from HSGD (denoted by Volterra) matches the performance of single runs of SGD for finite n and streaming (n xc). Shaded region (right) is the moving average of a single run of SGD. Empirical risk (left) increases monotonically with to its limit while population risk generally decreases with n. Streaming corrssoonds to n oo (see Appendix C). For consistency across sample sizes, time is measured in iterations. Additional details in App G.
Theorem (Equivalence of SGD) and HSGD). Suppose the pair (A,b) RRxd RR satisfy the quasi-randon assumptions with de S ni S d for some e E (0, 1}. Let the iterates æz = x be generated from multi-pass SGD Eq. (4) and X2 be the solution of Eq. (7). Then for any deterministic T 0 and any D 0, there is C > O such that
(( R((
(((x:))
d=e/2 CCd..
Pr
sup LoSEST
(((x.)
The rigorous proof is given in [61]. For the rest of this paper, will homogenized SGD to analyze the behavior of multi-pass SGD. See also Appendix where we heuristically extend this to the case of streaming SGD.
While the comparison of SGD to HSGD requires relatively strong assumptions on A and b, the analysis of HSGD can be performed under weaker assumptions (no quasirandomness assumptions are needed). It suffices to suppose the problem is high dimensional the following sense:
Assumption 2. The empirical risk & satisfies V n and 0 N V 3 nd- for some > 0.
This corresponds to the normalization where V AT A and each row of A is length 1 and hence V
5

---

Under Assumptions 1 and 2, the dynamics of the empirical and population risk under HSGD concentrate around deterministic dynamical system driven by Volterra integral equation:
Volterra Dynamics, Multi-pass. The following deterministic dynamical system is the high-dimensional limit for (Xx) and R(x),, respectively
V. ((((()) I. K(t, V ds Q R(())))))))))))) + L/ s(t,,; RRR ds
(Empirical risk)
(8)
(Population risk)
(9)
where the integrated learning rate I and kernel K, for any d x d matrix P, respectively are r(t)= f( 7(5) ds, K(L,;; = P 2(v2 (L) I())))) (10)
Theorem 2 (Concentration of HSGD around Volterra dynamics), Under Assumptions I and 2, for any T and for any D there exists sufficiently large >> O such that for all d
Pr
sup
(((x))
Q2
1/
d d/2 1/2
s CCDD
LOseST
where ee and Q4 solve (8) and (9).
We give a formal proof of the concentration result in Appendix D.I in Theorem 11.
3.1 No implicit regularization from SGD
From (9), for convex R we observe immediately that the population risk Q4 is only larger than the population risk of GF. Morcover, we have explicit formula for the excess risk due to SGD noise,
2r - (x ((0)
def [[x(t, V²R) x V. ds.
limiting
excess
Note that the population risk SGD tracks that of GF. If GF overfits, SGD overfits as well; there is statistical regularization due the noise of SGD applied empirical risk minimization (ERM).
We can further analyze the long-time behavior of SGD with exact limiting values for this excess risk. Theorem 3 (Time infinity risk values). (1) + as t -> oo but T(t) - Do (i.e. the usual Robbins-Mon Monro setting), then the excess population risk of SGD over GF tends to 0. If on the other hand (t) + E E (0, 2 tr Aº A } then with 2o given by the limiting empirical risk.
A)²
V
L (x0g(
(1
7
(22))²
+ SI })
2n
P
the excess risk due SGD converges
74
V2 (2²)) V2L + 8la
Ωr (0-R(xX)))
tr
2n
There are few conclusions draw directly from this. In the interpolation regime, that is where V = 0. there is no excess risk due to SGD and there is no need to send to O. Moreover, if the empirical risk oo is small, the excess risk due to SGD is proportional frequently orders of magnitude smaller than other potential sources of error. Furthermore, the excess risk is affected by how similar the population and empirical risks are, in the large directions. Ridge regularization can substantially reduce excess risk due to SGD in cases where population risk has many small eigenvalues. In summary, either by sending 7 - O, working in the interpolation regime, or otherwise regime V is small, the excess risk incurred by rumning SGD is minimal.
> oo. and hence it is

---

10
Figure 2: ICR function of largest and smallest eigenvalues A with trace nor- malized be 1; blue (smaller, SGD fa- vored) and red (larger, full batched MGD favored). Points indicate ICR for image datasets (MNIST, CIFAR-10, CIFAR-5m) well their images under ReLu ran- dom feature maps of various dimensions (lines). Gaussian random features (n 2000,
10c
10*
maximum eigenvalue
10*
C.EAR caoplare
10a
104
CEAR-10
d 315
10a
10a
QFAR-10
FFRR-1
d 316
10-1 5
10?
GFAR-5m 5m complane
tall
usdank:
226
205 100
10a
10-2
Gaussian-RF
10
10-5
100, various d) and Gaussian data (n 2000, various d) shows ICR for over- and under-paramest parameterized mod- els. Natural datasets tend favor SGD.
MNIST-RF
103,000
5
10
1
10
-10
10-7
10-5
10-2
10
10
105
minimum eigenvalue
3.2 Implicit conditioning of SGD
In contrast, the algorithmic advantages of SGD are substantial. To simplify the discussion, we consider only the case constant learning rate y. this case, the kernel in (8) and (9) simplifies to a convolution kernel, which has much simpler theory. To characterize the rates, we define Amin the smallest non-zero cigenvalue of V2c. Then for generie initial conditions, (in particular almost surely if Xo is nonzero isotropic), GF has the following convergence rate
1/1
7(mii (V22)+6), if 0, 2V
lim 2-000
-
((Xce)
otherwise.
Here we use the notation that Amin HH) and Amax (H) are the smallest and largest eigenvalues the matrix H. The rate of convergence of U to L can be no faster than the underlying GF, given by the rate above. On the other hand, for larger the Volterra term in (8) can frustrate the convergence. The Malthusian exponent of the convolution Volterra equation is given by
X, = inf x: 1x:1=//e e" K(I: K(LV di 22/ f ( vr(((2 exp((2x(())) 27( + ol)))) de )
(11)
As V is finite dimensional, we have that X, 2>y(miin (V2L) 8), owing to the divergence of the integral as approaches this value from below. Note that in principal the Malthusian exponent can be negative, in which case SGD is divergent. The Malthusian exponent gives the effective rate of convergence of constant learning rate SGD. Define
def (min( ((((Amim((())))) + (,) (A,(7)
i > O, if 8 = 0.
(12)
Theorem 4 (SGD convergence rates, average-case), Then the rates of convergence of both the empirical and population risk are controlled by this parameter
lim M V 2x) = =e -E(m) = lim -0 (Lo) 2/1 t-000
t-000
Furthermore, when y = nuu AT A)) we have the rate guarantee E(7) Amin (V2 4)+8
2
The major difference between SGD and full batch methods such momentum gradient descent (MGD; see Appendix F.2 for definitions) is that they have different sensitivities to the Hessian spectrum of the empirical risk L(x)) Al b12 Define the condition numbers
del Amax (V2C)
and def 1 tt((²() Amin (V26) +
Amin (V26) +
The first of these is the classical condition number of the ridge problem, while the second averaged condition number that regulates the behavior of SGD in the high-dimensional limit. MGD has been long established to have rate of convergence, with proper tuning, controlled by the square root of the condition number [65], which is known to be optimal amongst first order algorithms.
7

---

10.
10
Uaanng
10"
10
opecns (R--3877
10
42-3
16
10-4
450
190
KChw1.24
IC1-2.42
Figure 3: ICR effect full batch MGD versus SGD in synthetic least-squares setting. We consider minimizing, for an n x d matrix A (with n = 2400, = 3600) min 1 Ax bll² where A is Gaussian matrix, with correlated rows and b is given by A, +-7 for ground truth, which is isotropic normal of expected norm-square 1, and ny is isotropic normal of expected norm-square 0.02.
2
Theorem 5 (Convergence rates for MGD). For isotropic random initialization Do or noisy b, > 0, and strictly convex population risk R
(A( [(xx))
1/1
a.S.
VK
and (R(= R(xx))
1/K a.s.
VK
VK+1
k-1000
V +1
See Appendix F.2 for elaboration.
In light of Theorems and 5, we can define the implicit-conditioninn ratio
def
ICR
R log
V K
which measures the efficiency of SGD over MGD in that SGD with constant learning rate n/ tr (r(V2L) trains an ICR-multiple of the number of epochs that MGD requires (lower is better for SGD).
Problems favor SGD when there are large outlier eigenvalues, common feature of Hessian spectra the same order the unnormalized trace, individual SGD iterates are as effective as full-batch gradient. In contrast, when the Hessian spectrum is tightly packed, which is less common in practice but occur after some preprocessing techniques or e.g. for uncorrelated Gaussian samples, then MGD is favored. See Fig. 2.
in practice [69, 70. 1]. Indeed, if the largest eigenvalues
3.3 Numerical results on ICR
In Fig. 3, we illustrate how ICR affects the relative performance of full batch MGD versus single batch SGD a synthetic least squares setting where we have tight control over the all the particulars of the problem and in a neural network setting. We control the ICR by controlling the covariance singular value spectrum of the rows of A, which we take as Pareto distributed with exponent s for varying 2. This choice allows to affecct the ICR of the problem without changing the minimum curvature of the Hessian. The results, comparing SGD, MGD, and GD, are given Figure 3.
We note few key qualitative observations. First, even in MGD favored configurations, SGD will outperform MGD on short time scales. When optimizing the hyperparameters in MGD for long- time performance, minimal curvature (which in this case is just the minimal eigenvalue of AA") plays a major role in the choices; being tuned for long-time performance, MGD typically performs suboptimally at initialization. In contrast, the learning rate in SGD only depends on average curvature, and so it generally performs better initialization on problems with a larger interval of Hessian spectra.

---

202
(MCD) (SGD)
10:2-
10-2
307
101
triiing krzs
20
Uaasing
10
8
10
10-3
(MGB)
IC1 (5C22)
10
30
30
opocrs, lavores)
epochs. (avored)
Figure 4: ICR and full-batch MGD versus SGD with fully connected 2-layer neural network with activation function f((z) 1 car/plane. Momentum byper-parameters were tuned empirically to give best performance. We note that the loss curve of MGD also displays the characteristic cycloidal oscillations of tuned momentum on inhomogeneous problems. Left: 3 = 0.01. ICR varies over the course of training but stays above favoring momentum as illustrated in the figure. Right: = 10. ICR varies slightly but always stays below 1 throughout the training and SGD is favored over full-batch momentum.
V er((3zz) on 500-sample subset of CIFAR-10 with targets
Second, we note that the problem setup was chosen to hold the minimum curvature roughly constant while varying s. When tends to 2 from above, the largest eigenvalues of AA" grows with feature dimension d, but the average and minimum eigenvalue stays bounded with feature dimension. Hence we can send the ICR to 0 by choosing by sending s + oc, we send the covariance matrix to the identity, which tends to be momentum favored.
above 2 and increasing d (or n)). On the other hand,
In Fig. 4, we run SGD on a fully- fully-connected 2-layer neural network on a subset of CIFAR-10 in order to examine the dynamics of the ICR for a non-trivial problem and to see how our insights might play out in practice. Owing to the non-convexity of this problem, we define the ICR in terms of the Gauss-Newton approximation to the Hessian, or equivalently in terms of the Neural Tangent Kernel [29]. By changing the activation function the network, we can vary the initial ICR from an SGD-favored to nomentum-favoree value. While the ICR does change over the course of training, we find that, at least in this setting, the initial ICR can nevertheless predict the relative performance of SGD versus MGD. Indeed, for activation functions for which the ICR remains above 1.0. the training remains MGD-favored over sufficiently long times, and we observe that MGD with optimal parameters does converge faster than SGD. In contrast, when the ICR remains below 1.0, find that SGD outperforms MGD.
4 Conclusion.
Using a specific type SLD (called HSGD) that matches the second-order correlations in the noise of SGD, we demonstrated that their empirical and population risks match in the high-dimensional limit. Moreover, the risks of HSGD behavior deterministically, as described by a Volterra equation. With this connection, we investigated the benefits of SGD on a convex objective. While there is no statistical benefit to generalization from the noise of SGD, in overparameterized, interpolating settings little is lost compared to GD. Moreover, when computational restrictions are imposed, SGD can be radically faster than GD because of its dependence on a different condition number of the Hessian. We characterized this speed up using the ICR, which when calculated for datasets common in deep learning clearly favors SGD. This should highlight the difficulty in studying implicit regularization for SGD empirically: any experiment necessarily has finite computational budget and may find
'The relevance of > 2 is that the Pareto has moments up to and including the second moment. For values less than 2, the covariance spectra is sufficiently heavy that the maximum eigenvalue of AA" dominates the trace. In that regime, the problem becomes effectively sparse, with intrinsic dimension depending only and it should expected that GD/SGD are approximately equivalent outperform MGD. FFurthermoee, the average curvature' speedup of SGD on short time scales becomes muted, owing all curvatures being the same.

---

lower population risks with SGD simply via its improved conditioning. Finally, we demonstrated limitations in using streaming SGD alone as tool for studying generalization.
As future work, major outstanding problem (both theoretically and empirically) is extending the analysis above non-quadratic losses, both train and test, and especially other high-dimensional problems not in the kernel regime. Finally, data augmentation can naturally be considered by randomly augmenting each sample from Dn in Eq. (30).
Acknowledgments and Disclosure of Funding
C. Paquette's 's research was supported by CIFAR AI Chair, MILA, Discovery Grant from the Natural Science and Engincering Council (NSERC), and the FRONT New University Researcher's Start-up Program. Research by E. Paquette was supported by a Discovery Grant from the Natural Science and Engincering Council (NSERC). Additional revenues related to this work: C. Paquette has part-time employment at Google Research, Brain Team, Montreal, QC
10

---

References
[1] A. Abdel-Gawad and S. Ratner. Adaptive optimization of hyperparameters in L2-regularised logistic regression. Technical report, 2007.
[2] B. Adlam and J. Pennington. The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization, In Proceedings of the 37th International Conference on Machine Learning (ICML., volume 119, pages 74 84, 13-18 Jul 2020.
[3] B. Adlam and Pennington. Understanding Double Descent Requires A Fine-Graines Bias- Variance Decomposition. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 11022-11032, 2020.
[4] B. Adlam. J.A. Levinson, and J. Pennington. A Random Matrix Perspective on Mixtures of Nonlinearities in High Dimensions. In International Conference on Artificial Intelligncce and Statistics, pages 3434-3457. PMLR, 2022.
[5] S. Asmussen. Applied probability and queues, volume 51 of Applications of Mathematics (New York). Springer-Verte New York, second edition, 2003. Stochastic Modelling and Applied Probability.
[6] Bach and E. Moulines. Non-strongly-comwel smooth stochastic approximation with con- vergence rate O (1/n). Advances in neural information processing systems (NeurIPS), 26, 2013.
[7] D. Barrett and B. Dherin. Implicit Gradient Regularization. In International Conference on Learning Representations, 2021. URL httpps://openreviee..et www.:eeee/oommmmddemneemse
[8] P.L. Bartlett, P.M. Long, G. Lugosi, and A. Tsigler. Benign overfitting linear regression. Proc. Natl. Acad. Sci. USA, 117(45):30063-300070, 2020. doi: 10. 10.1073/pnas:19973783
[9] B. Bordelon and C. Pehlevan. Learning Curves for SGD on Structured Features. In International Conference on Learning Representations (ICLR), 2022.
[10] L. Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010, pages 177-186. Springer, 2010.
[11] L. Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pages 421-436. Springer, 2012.
[12] L. Bottou and O. Bousquet. The tradeoffss of large scale learning. Advances in Neural Informa- tion Processing Systems (NeurIPS), 20, 2007.
[13] J.-P. Bouchaud and A. Georges. Anomalous diffusion in disordered media: statistical mecha- nisms, models and physical applications. Physics reports, 195(4-5):127-29) 1990.
[14] Chaudhari and S. Soatto. Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks. In International Conference on Learning Representations (ICLR), pages 1-20, 2018
[15] X. Cheng, N. Chatterji, Y. Abbasi-Yadkori, P. Bartlett, and M. Jordan. Sharp convergence rates for Langevin dynamics in the nonconvex setting. arXiv preprint arXiv:1805.0 01688, 2018.
[16] A. Defossez. and F. Bach. Averaged Mean-S-rrssSssss Variane Trade-off' and Optimal Sampling Distributions. In Proceedings of the Eighteenth International Conference Artificial Intelligence and Statistics (AISTATS), volume 38, pages 205-213, 2015.
[17] M. Derezinski, F. T. Liang, and M. W. Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 5152-5164, 2020.
[18] A. Dieuleveut, N. Flammarion, and F. Bach. Harder, better, faster, stronger convergence rates for least-squares regression. The Journal of Machine Learning Research, 18(1):3520-3570 2017.
11

---

[19] M. Engeli, Th. Ginsburg. H. Rutishauser, and E. Stiefel. Refined iterative methods for compu- tation of the solution and the eigenvalues of self-adjoint boundary value problems, Mitt. Inst. Angew. Math. Zürich, 8: 3,107, 1959.
[20] R. Ge. S.M. Kakade, R. Kidambi, and P. Netrapalli. The step decay schedule: A near opti- mal, geometrically decaying learning rate procedure for least squares. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
[21] Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT Press, 2016. http:
/ //www. www.deepplearningboo. org.
[22] G. Gripenberg. On the resolvents of nonconvolution Volterra kernels. Funkcial. Ekvac., 23(1): 83-95, 1980.
[23] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro. Characterizing Implicit Bias in Terms of Optimization Geometry. Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
[24] M. Gurbuzhalaban, U. Simsekli, and L.. Zhu. The Heavy-Tail Phenomenon in SGD. In International Conference on Learning Representations (ICL.), 2020.
[25] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of the 33rd International Conference Machine Learning (ICML), volume 48, pages 1225- 1234, 2016.
[26] S. Hochreiter and J. Schmidhuber, Flat minima. Neural computation, 9(1):1-42, 1997.
[27] E. Hoffer, I. Hubara, and D. Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. Advances in Neural Information Processing Systems (NeurIPS), 30, 2017.
[28] W. Hu, Li, Li, and J. Liu. On the diffusion approximation of nonconvex stochastic gradient descent. arXiv preprint arXiv:/70S.. 075607762, 2017.
L.
[29] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems (NeurIPS), 2018
[30] Jain, S. Kakade, R. Kidambi, P. Netrapalli, and A. Sidford. Accelerating Stochastic Gradient Descent for Least Squares Regression. In Proceedings of the 31st Conference On Learning Theory (COLT), volume 75, pages 545-604, 2018.
[31] S. Jastrzebski, Z. Kenton, D. Arpit, N. Ballas, A. Fischer, Y. Bengio, and A. Storkey. Three factors influencing minima in sgd. arXiv preprint arXiv:1711.04623 2017.
[32] N. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. Tang. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima. arXiv preprint arXiv: 1009,0600000000 04836, 2016.
[33] D. Kobak, J. Lomond, and B. Sanchez. The Optimal Ridge Penalty for Real-world High- dimensional Data Can Be Zero Negative due to the Implicit Ridge Regularization. Journal of Machine Learning Research, 21(169):1-16 2020.
[34] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, U. of Toronto, 2009.
[35] D. Kunin, J. Bagastuy-Brent L. Gillespie, E. Margalit, H. Tanaka, S. Ganguli, and D. Yamins. Rethinking the limiting dynamics of SGD: modified loss, phase space oscillations, and anoma- lous diffusion. arXiv preprint arXiv:2107.09133 2021.
[36] H. Kushner and G.G. Yin. Stochastic approximation and recursive algorithmss and applications, volume 35. Springer Science & Business Media, 2003.
[37] Y. LeCun, C. Cortes, and C. Burges. "mnist" handwritten digit database, 2010. URL. http: / //yann. leccun com/ homm/xxdbmnnise
12

---

[38] J. Lee, Y. Bahri, R. Novak, S. Schoenholz, J. Pennington, and J. Sohl-Dickstein. Deep Neural Networks as Gaussian Processes. In International Conference on Learning Representations (ICLRR) 2018.
[39] Y. Lei, T. Hu, and K. Tang. Generalization Performance of Multi-pass Stochastic Gradient Descent with Convex Loss Functions. J. Mach. Learn. Res., 22:25-1,202
[40] A. Lewkowyez, Y. Bahri, E. Dyer, J. Sohl-Dickstein, and G. Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.02218 2020.
[41] C. Li, H. Farkhoor, R. Liu, and J. Yosinski. Measuring the intrinsic dimension of objective landscapes. arXiv preprint
2018.
[42] Q. Li, C. Tai, and W. E. Stochastic Modified Equations and Adaptive Stochastic Gradient Algorithms. In Proceedings of the 34th International Conference on Machine Learning (ICLR), volume 70, pages 2101-2110, 2017.
[43] Q. Li, C. Tai, and W. Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundations. Journal of Machine Learning Research, 20(40):1-4) 2019.
[44] Z. Liao, R. Couillet, and M. Mahoney. A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, Precise Phase Transition, and the Corresponding Double Descent. arXiv preprint mrXiv:2006.05013, 2020.
[45] J. Lin and L. Rosasco. Optimal Rates for Multi-pass Stochastic Gradient Methods. Journal of Machine Learning Research, 18(97):1-47 2017.
[46] L. Ljung. Analysis of recursive stochastic algorithms. IEEE Trans. Automatic Control, AC-22 (4):551-575, 1977.
[47] L. Ljung, G. Pflug, and H. Walk. Stochastic approximation and optimization of random systems, volume 17 of DMV Seminar. Birkhäuser Verlag, Basel, 1992. doi: 10.10077977-330444--6666
[48] S. Mandt, M. Hoffman, and D. Blei. A variational analysis of stochastic gradient algorithms. In International conference on machine learning (ICML), 2016.
[49] S. Mandt, M.D. Hoffman, and D. Blei. Stochastic Gradient Descent as Approximate Bayesian Inference. Journal of Machine Learning Research, 18(134):1-35, 2017.
[50] V.A. Marčenko and L.A. Pastur. Distribution eigenvalues for some sets random matrices. Mathematics of the USSR-Sbornik, 1967.
[51] S. Mei and A. Montanari. The generalization error of random features regression: precise asymptotics and the double descent curve. Comm. Pure Appl. Math., 75(4):667-766, 2022.
[52] Mori, L. Ziyin, K. Liu, and M. Ueda. Logarithmic landscape and power-law escape rate of sgd. arXiv preprint 2.Xiv:2/05.09555 2021.
[53] E. Moulines and F. Bach. Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 24, 2011.
[54] Nakkiran, B. Neyshabur, and H. Sedghi. The Deep Bootstrap Framework: Good Online Learn- are Good Offline Generalizers. In International Conference Learning Representations (ICLR), 2021.
[55] R.M. Neal. Priors for Infinite Networks, pages 29-53. Springer New York, New York, doi: 10.10077978-114611-07755 2. URL https://doi.co http://o...og//1...0....../
NY, 1996. 978 001-466155----00
[56] D. Needell, Srebro, and R. Ward. Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Math. Program., 155(1-2, Ser. A):549-573, 2016.
13

---

[57] B. Neyshabur, R/ Tomioka, and N. Srebro. In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning, arXiv preprint arXiv:1412.6614, 2014.
[58] 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.
[59] 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, pages
2021.
[60] C. Paquette, B. van Merriënboer, and F. Pedregosa. Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis. Foundations of Computational Mathematics, 2022. URL attpss://oii. org/ 1007
[61] E. Paquette, C. Paquette, B. Adlam, and J. Pennington. Homogenization of SGD in high- dimensions: exact dynamics and generalization properties. arXiv preprint arXiv:2205.07063 2022.
[62] Pedregosa. Hitchhiker's Guide to Momentum, 2021. URL http://ttpa....../ bianp net/ blog/2021
[63] S. Pesme, L. Pillaud-Vivisn and N. Flammarion. Implicit bias of sgd for diagonal linear networks: a provable benefit of stochasticity. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
[64] L. Pillaud-Vivien, A. Rudi, and Bach. Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
[65] B.T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 04, 1964.
[66] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NeurIPS), pages 1177-1184, 2008.
[67] S. Resnick. Adventures in stochastic processes. Birkhäuser Boston, Inc., Boston, MA, 1992.
[68] H. Robbins and S. Monro. A Stochastic Approximation Method. Ann. Math. Statist., 1951.
[69] L. Sagun, L. Bottou, and Y. LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint 1611v:161.007770 2016.
[70] L. Sagun, U. Evei, V. Guney, Y. Dauphin, and L. Bottou. Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint arXiv: 04454, 2017.
[71] S. Shalev-Shwartz and T. Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. Math. Program., 155(1-2, Ser. A):105-14: 145, 2016. doi: 10.10077/10107.-04--83--0
[72] C.J. Shallue, J. Lee, J. Antognini, J. Sohl-Dickstein, R. Frostig, and G.E. Dahl. Measuring the Effects of Data Parallelism on Neural Network Training. Journal of Machine Learning Research, 20: 10:1-49,44 2019.
[73] V. Shankar, A. Fang, W. Guo, S. Fridovich-Keil, J. Kelley, L. Schmidt, and B. Recht. Neural Kernels Without Tangents. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119, pages
2020.
[74] S. Smith and Q. Le. bayesian perspective on generalization and stochastic gradient descent. In International Conference on Learning Representations (ICLR), pages 1-13, 2018.
[75] S. Smith, E. Elsen, and S. De. On the Generalization Benefit of Noise in Stochastic Gradient Descent. In Proceedings of the 37th International Conference on Machine Learning (ICML., volume 119, pages 9058-9067 2020.
14

---

[76] S.L. Smith, B. Dherin, D. Barrett, and S. De. On the origin of implicit regularization in stochastic gradient descent. In International Conference on Learning Representations (ICLR), pages 1-14, 2021.
[77] N. Tripuraneni, B. Adlam, and J. Pennington. Covariate Shift in High-Dimensional Random Feature Regression. arXiv preprint 4rXiv:2111.08234, 2021.
[78] A. Tsigler and P. L. Bartlett. Benign overfitting in ridge regression. arXiv preprint 142866 2020.
[79] A. Vardhan Varre, I.. Hillaud-iivien and N. Flammarion. Last iterate convergence of SGD for Least-Squares in the Interpolation regime. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 21581-21591, 2021.
[80] S. Wojtowytsch. Stochastic gradient descent with noise of machine learning type. Part II: Continuous time analysis. arXiv preprint arXiv:2/06.022:
2021.
[81] J. Wu, D. Zou, V. Braverman, Q. Gu, and S. Kakade. Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression. arXiv preprint 10.0022 2021.
[82] L. Wu, C. Ma, and W. E. How SGD Selects the Global Minima in Over- Over-parameterizer Learning: Dynamical Stability Perspective. In Advances in Neural Information Processing Systems (NeurlPS), volume 31, 2018.
[83] S. Yaida. Pluctuation-dissppatiii relations for stochastic gradient descent. In International Conference on Learning Representations(/CLRR) 2019.
[84] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021. doi: 10.1 10.1145/3446776.
[85] Z. Zhu, J. Wu, B. Yu, L. Wu, and J. Ma. The anisotropic noise in stochastic gradient de- scent: Its behavior of escaping from sharp minima and regularization effects. arXiv preprint arXiv:1803.000 0..000, 2018.
[86] L. Ziyin, K. Liu, T. Mori, and M. Ueda. Strength of Minibatch Noise in SGD. In International Conference on Learning Representations (ICLR), 2022.
[87] D. Zou, J. Wu, V. Braverman, Q. Gu, D.P. Foster, and S. Kakade. Regularization from SGD in Least Squares Problems (NeurIPS). In Advances in Neural Information Processing Systems, volume 34, pages 5456-5468, 2021.
The Benefits of Implicit
[88] D. Zou, J. WU, V. Braverman, Q. Gu, and S. M. Kakade. Risk Bounds of Multi-Pass SGD for Least Squares the Interpolation Regime. arXiv preprint 2rX052200.003/59 2022.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We make sure to clearly state our assumptions particular that the results only hold for the e² regularized least squares problem.
(b) Did you describe the limitations of your work? [Yes] We ensure the reader is aware that many of our results follow from another paper. We also make clear which results are proven and which results speculative, but have numerical support.
(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.
15

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The full set of assumptions on the data matrix A, signal B3, initialization æo, and target vector b are listed in the theorems statements with complete description in Appendix B. Moreover state our setting, namely that we are working on the ee regularized least squares problem, clearly in the introduction of the main paper.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs of theoreti- cal results are presented and, if not, referenced to where the proof can be found. We also clearly state conjectures which we believe should be true (see e.g., streaming SGD in Appendix C).
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] We provide code in our supplemental material and describe our experimental simulations in detail in Appendix G. We state all parameters in the captions of the figures.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All parameter choices are clearly stated under each figure and in Appendix G. For example, we give the exact dimensions of the matrices used as well as the learning rates on SGD.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Variance across the runs of SGD were reported.
(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] We indicated the type of resources in Appendix G. All our experiments were done using Colabs and only required single standard GPU.
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 use three data sets to verify our claims. All three data sets (MNIST [37], CIFAR-10 [34], and CIFAR-5m are open source and available in TensorFlow. We cited the creators in the main text.
(b) Did you mention the license of the assets? [Yes] All three data sets used are open source and available on TensorFlow.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We include the code used our simulations as part of the supplemental material. obtained from people whose data you 're
(d) Did you discuss whether and how consent using/curating? [N/A] The data sets are open source.
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A] The data sets used do not contain any personally identifiable information or offensive content. The data sets are standard data sets used in benchmarking.
5. If you used crowdsourcing or 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 crowdsourcing or human subjects.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] The work is purely theoretical and does require any crowdsourcing or human subjects.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A] The work is purely theoretical and does not require any crowdsourcing or human subjects.
16


Reviews:
[{"review_id": "zzUb5uZUKMf", "reviewer": "Reviewer_xitN", "summary": "This work proposes HSGD as a continuous approximation to SGD (multi pass version). It first shows an approximation theorem that justifies the closeness between the continuous HSGD and the discrete SGD. Then by studying HSGD it characterizes the limiting training and population risks through Volterra dynamics. Based on the theorems, the paper concludes that (1) multi-pass SGD does not have implicit bias over GD, at least in the setting of least square, (2) SGD has an effect of implicitly conditioning, that accelerates the convergence. ", "questions": "Please see above.", "limitations": "Please see above. It seems most of the theorems are from existing works. Thus this particular work presents little delta to me. Another thing bothers me is that, the authors did not try to explicitly discuss this issue in their main text. ", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n+ The implicit conditioning could be an interesting perspective to understand the effectiveness of SGD.\n\n# Weakness\n- I find the statement of related literature could be improved. \n\n- please correct the bib formate of reference [36]\n\n- Line 49, could have mentioned [55]. In particular, [55] showed a similar result that multi-pass SGD generalizes worse than GD in the linear regression setting. The authors should mention this when stating their contribution and in Sec 3.1\n\n- Thm 1 and Thm2 seem to from [39]. The authors should explicitly mention [39] after their Thms 1 and 2. Moreover, could you please explain the delta of thms 1 & 2 compared to that in [39]? \n\n- Thms 4 and 5 are from [36, 37, 38] (as explicitly mentioned in line 901 in Appendix). In this sense, the authors should explicitly clarify this issue in their main text. The current writing has caused a huge misunderstanding about its true contribution when I first go through the paper. \n\n- Line 90. Could you explain why SGD with momentum degenerates to SGD?\n\n- Lemma 1. What is $\\gamma$ here? Note that a somewhat related lemma has been shown in [55].\n\n- Line 119-124. I am actually confused, because it has been long known that a continuous SME approximates SGD, see [L 2017] and [H 2017]. \n\n- Line 148. I believe [21] is a wrong citation here. Could you point out where in [21] iid sub gaussian is assumed? \n\n- Line 158. The notation is a bit confusing, is $\\gamma$ still referring to the stepsize?\n\n- Thm 1 is hard for me to interpret. First of all, how do you compare this result to the SME approximation proved by [L 2017] and [H 2017]? \nSecondly, Could you provide some examplar regime where the approximation error is small? It seems for the error to be small one needs $d$ to be large, but on the other hand that implies $n$ needs to be large. How is the error affected by stepsize?\n\n- Thm 2 is also hard for me to interpret. \n\n\n\n\n\n\n\n\n\n\n\n\n\n[L 2017] Li Q, Tai C, Weinan E. Stochastic modified equations and adaptive stochastic gradient algorithms. InInternational Conference on Machine Learning 2017 Jul 17 (pp. 2101-2110). PMLR.\n\n[H 2017] Hu W, Li CJ, Li L, Liu JG. On the diffusion approximation of nonconvex stochastic gradient descent. arXiv preprint arXiv:1705.07562. 2017 May 22.", "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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "jnzDMhrNDdj", "reviewer": "Reviewer_wJVQ", "summary": "The authors of the paper present the following contributions:\n- They show that, in the high dimensional limit, multipass SGD behaves, in terms of empirical and population loss, as a SDE with a particular noise covariance\n- They further show that, in the high dimensional limit, this SDE converges to a deterministic Volterra Dynamics\n- They analyse this dynamics to compare to the one of the gradient flow showing that noise negatively impact the population loss but can accelerate convergence.\n", "questions": "I have one question for the SDE limit of the model: could the authors explain why the quadratic case is special to derive the SDE limit ? How could it be extended to a general convex loss ? or even to a non-convex setup ?\n\n", "limitations": "As I already discussed the limitations in the previous boxes, I'll put the conclusion of my review here. I truly think this is a nice paper, with solid result and an interesting high-dimensional limit dynamics.  I now put a weak accept, but will be happy to raise my score if the authors temper a bit the overselling part, correct the minor flaws and the referencing.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### **Strengths**\n\n- First I have to say that the paper is well written, pleasant to follow and well illustrated by the experiments.\n- Second and more importantly, I really like the results concerning the high dimensional set-up: comparing the losses dynamics to the one of an explicit SDE that can be studied is a good idea. And even I had no time to check the proof, the result seems sound. Then, concentration to Lotka-Volterra dynamics is also a nice development of the analysis!\n\n\n### **Weaknesses**\n\n- Perhaps the first weakness is the limitation of the result: the authors are very precise in the specific setting of linear regression, provide some good material to analyse it, but it is hard to conclude anything deep from their analysis.\n- I know this is a large tendency in the ML community, but I think that overselling the results is counter productive when writing a paper. A good example is the title of the paper where the fact that the focus is on Least-squares should be written. Also, trying to systematically conclude that SGD is \"better\" or that this can explain the amazing performance of SGD in practice is a bit overselling. The results of the authors being already strong, there is no need to oversell the paper like this. \n- In the same direction, I find the introduction confusing and the references to the literature incomplete. I think that the authors should be more specific and really focus on the least squares literature, and not try to refer to the deep learning one (or maybe just at the end to motivate further investigations). In terms of literature, lign 50, the multipass is not properly covered and [1,2] among others are worth mentioning. \n- The paragraph on **Diffusion approximations and homogenized SGD** should be rewritten. A lot of work has been done to model SGD as a diffusion. [3] properly explains how to model SGD with a SDE, [4] analyses it respecting the geometry of the noise and the sentence *we lack a precise connection between a concrete SLD and a practical nonconvex learning problem* is simply wrong as [5] studied exactly a SDE model in a non-convex setting. Finally, to be consistent with the rest of the paper, it would be great that $\\gamma$ appears in the noise term of equation (5). Note also that in the isotropic case, if $\\Sigma$ is proportional to the identity, the invariant measure is not proportional to $e^{-f}$ but to $e^{- C_{\\gamma} f}$, with $C_{\\gamma}>0$ some constant.\n\n\n[1] Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods. Journal of Machine Learning Research, 18(97):1–47, 2017\n\n[2] Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Advances in Neural Information Processing Systems, pages 8125–8135, 2018.\n\n[3] Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations. Journal of Machine Learning Research, 20(40):1–47, 2019.\n \n[4] Stephan Wojtowytsch. Stochastic gradient descent with noise of machine learning type. Part II: Continuous time analysis, *Preprint*, 2021.\n\n[5] Scott Pesme, Loucas Pillaud-Vivien, and Nicolas Flammarion. Implicit bias of sgd for diagonal linear networks: a provable benefit of stochasticity. Advances in Neural Information Processing Systems, 34, 2021.\n\n\n### **Minor Flaws**\n- [36] is an empty reference\n- lign 92: miss a $dt$ in equation (5) for the drift\n- lign 166: explain with you take $tn$ as the time for SGD\n- lign 250: parenthesis problems", "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": "UEkYuZs1qfg", "reviewer": "Reviewer_Nf1A", "summary": "This paper uses SDE (so-called HSGD) to study the optimization property of both streaming and multi-pass SGD over the quadratic functions. First, they show that the risk of SGD is no better than GD, showing that there is no implicit regularization in this setting. Next, they show the connection between SGD and HSGD, enabling them to use HSGD to study the properties of SGD. Their main contribution is to show that SGD enjoys a different condition number that sometimes leads to a better convergence rate over GD. Moreover, they also study the streaming SGD using the same framework and relate them to compare the generalization.", "questions": "Please see the weakness.", "limitations": "Please see the weakness.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n* The most interesting result is to show that SGD has a different condition number for **convex quadratic functions**. In particular, SGD outperforms GD if the spectrum of the Hessian has some outliers, which is usual in realistic applications, see Figure 2.\n* The Volterra Dynamic, though not first proposed by this paper, its analysis might be of independent interest to study the behavior of SGD.\n\n### Weaknesses\n* In Figure 2, they run random feature models for realistic applications, i.e., CIFAR-10, CIFAR-5m, showing that in these cases the Hessian is ill-conditioned, supporting their main arguments that SGD outperforms GD on these realistic applications. However, note that the random feature model is a convex optimization problem, which differs a lot from realistic neural networks. Hence, small ICR on the random feature model cannot be used to show that SGD outperforms GD on realistic optimization problems **directly**. Next, the author should provide the \"real\" convergence comparison between SGD and GD even for the random feature models to support their main observation. ICR is just an indicator for the comparison between SGD and GD. There might be an approximation error due to the usage of HSGD and also the dimension, iteration time is finite. Hence, without this simulation, I am not convinced that SGD does outperform GD in terms of convergence speed.\n\n* The argument that there is no implicit regularization might be trivial. For convex optimization, **any** algorithms, if convergent, then they should converge to the same function value (for strongly convex cases, they converge exactly to the same point). To my best knowledge, all the previous papers studying the implicit regularization focus on nonconvex optimization.\n\n* The introduction of Volterra Dynamics is limited, which is very unfriendly to those unfamiliar with it. It would be good if additional background information can be provided.\n* Missing title in the reference [36].", "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": "Qz48jbosjRh", "reviewer": "Reviewer_XeAd", "summary": "This paper studies the generalization ability of the multi-pass SGD on high-dimensional convex quadratics by relating it to a stochastic differential equation called homogenized stochastic gradient descent (HSGD). The authors show that using the HSGD, a precise risk trajectory of SGD can be established, which reveals the conditions on the data distribution that SGD is more efficient than GD. The authors further extend the analysis to streaming SGD and show its inability to capture certain salient features compared to multi-pass SGD.\n\n", "questions": "Please refer to the weakness section.", "limitations": "Please refer to the weakness section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the strengths of this paper include\n\n(1) establishing an approximation result between SGD and HSGD.\n(2) showing that SGD negatively impacts generalization performance.\n(3) showing how SGD accelerates convergence.\n(4) showing the inability of streaming SGD.\n\nWeaknesses are as follows:\n(1) Although the authors provide a precise characterization of the generalization error of SGD, the formula of the $Psi_t$ and $\\Omega_t$ are still difficult to follow. There lacks a good interpretation of the developed results, especially in the non-asymptotic setting that $t$ is not approaching infinity. Note that for many high-dimensional linear regression problems, GD/SGD with early stopping can give good generalizable solutions while the overfitting will occur if $t\\rightarrow \\infty$.\n\n(2) Additionally, in some cases the condition number $\\kappa$ could be extremely large (when the matrix $T$ or $A$ has a fast decaying eigenspectrum). Then the convergence rate to $\\Psi_\\infty$ and $\\Omega_\\infty$ may not be that interesting as they will be super slow and people tend to early stop the optimization algorithm. \n\n(3) In section 3.2, a detailed explanation about why SGD is more efficient than GD is missing. It seems that the authors only claim that SGD with a constant learning rate can match the convergence of GD, but how this lead to the argument that SGD is more efficient is missing. The authors may need to provide a rigorous comparison between the efficiency of SGD and GD/M-GD.\n\n(4) Lemma 1 is not new in the literature (at least in the case of $\\delta=0$). The following work (see their Theorem 1) has shown that for any feasible learning rate, the excess risk of multi-pass SGD must be greater than or equal to GD,  then taking the limit $learning rate \\rightarrow 0$ can imply the results of Lemma for the case of $\\delta=0$ The authors may need to comment this in the surrounding text.\n\nD. Zou, J. Wu, V. Braverman, Q. Gu, and S. M. Kakade. Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime. arXiv preprint arXiv:2203.03159, 2022.\n\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": {}}]

Author rebuttal:

Decision: Accept