SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs
Authors: Ayush Sekhari
Karthik Sridharan
Satyen Kale
Venue: NeurIPS 2021 Poster (2021)
Keywords: Theory
Implicit regularization
Stochastic convex optimization
SGD
RERM
Regularized ERM
Multiple-passes
GD

Abstract: Multi-epoch, small-batch, Stochastic Gradient Descent (SGD) has been the method of choice for learning with large over-parameterized models. A popular theory for explaining why SGD works well in practice is that the algorithm has an implicit regularization that biases its output towards a good solution. Perhaps the theoretically most well understood learning setting for SGD is that of Stochastic Convex Optimization (SCO), where it is well known that SGD learns at a rate of $O(1/\sqrt{n})$, where $n$ is the number of samples. In this paper, we consider the problem of SCO and explore the role of implicit regularization, batch size and multiple epochs for SGD. Our main contributions are threefold: 

* We show that for any regularizer, there is an SCO problem for which Regularized Empirical Risk Minimzation fails to learn. This automatically rules out any implicit regularization based explanation for the success of SGD.

* We provide a separation between SGD and learning via Gradient Descent on empirical loss (GD) in terms of sample complexity. We show that there is an SCO problem such that GD with any step size and number of iterations can only learn at a suboptimal rate: at least $\widetilde{\Omega}(1/n^{5/12})$.

*  We present a multi-epoch variant of SGD commonly used in practice. We prove that this algorithm is at least as good as single pass SGD in the worst case. However, for certain SCO problems, taking multiple passes over the dataset can significantly outperform single pass SGD. 

We extend our results to the general learning setting by showing a problem which is learnable for any data distribution, and for this problem, SGD is strictly better than RERM for any regularization function. We conclude by discussing the implications of our results for deep learning, and show a separation between SGD and ERM for two layer diagonal neural networks.

SGD: The Role of Implicit Regularization, Batch-size and Multiple Epochs
Satyen Kale Google Research, NY satyen@google.com com
Ayush Sekhari Cornell University as3663@corne11.co edu
Karthik Sridharan Cornell University ks9990cornee1. edu
Abstract
Multi-epoch, small-batch, Stochastic Gradient Descent (SGD) has been the method of choice for learning with large over-paramen parammereeeeee models. popular theory for explaining why SGI) works well in practice is that the algorithm has an implicit regularization that biases output towards good solution. Perhaps the theoreti- cally most well understood learning setting for SGD is that of Stochastic Convex Optimization (SCO), where is well known that SGD learns at a rate O(1/ vn), where is the number of samples. In this paper, consider the problem of SCO and explore the role of implicit regularization, batch size and multiple epochs for SGD. Our main contributions are threefold:
1.
We show that for any regularizer, there an SCO problem for which Regular- ized Empirical Risk Minimzation fails to learn. This automatically rules out any implicit regularization based explanation for the success of SGD.
We provide a separation between SGD and learning via Gradient Descent on empirical loss (GD) in terms of sample complexity. We show that there is SCO problem such that GD with any step size and number of iterations can only learn at a suboptimal rate: at least O2(1 (11
3. We present a multi-epoch variant of SGD commonly used in practice. We prove that this algorithm case. However, for certain SCO problems, taking multiple passes over the dataset can significantly outperform single pass SGD.
least as good as single pass SGD the worst
We extend our results to the general learning setting by showing problem which is learnable for any data distribution, and for this problem, SGD is strictly better than RERM for any regularization function. We conclude by discussing the implications our results for deep learning, and show a separation between SGD and ERM for two layer diagonal neural networks.
Introduction
We consider the problem of stochastic optimization of the form:
Minimize F(w)
where the objective F Rd - R is given by F(w) = E Es (w; 2)]. The goal is to perform the minimization based only samples = (21, (.,, drawn i.i.d. from some distribution D. Standard statistical learning problems can be cast as stochastic optimization problems, with F(w)
being the population loss and fww 2) being the instantaneous loss sample for the model
Stochastic Convex Optimization (SCO). Perhaps the most well studied stochastic optimization problem is that of SCO. We define problem to be an instance of a SCO problem if,
Assumption I: Population loss F is convex.
(2)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Notice above that we only require the population loss to be convex and do not impose such a condition on the instantaneous loss functions f.
Algorithms like Stochastic Gradient Descent (SGD), Gradient Descent on training loss (GD), and methods like Regularized Empirical Risk Minimization (RERM) that minimize training loss with additional penalty in the form of regularizer are all popular choices of algorithms used to solve the above problem and have been analyzed theoretically for various settings of Stochastic Optimization problems (convex and non-convex). We discuss below a mix of recent empirical and theoretical insights about SGD algorithms that provide motivation for this work.
SGD and Implicit Regularization. A popular theory for why SGD generalizes so well when used on large wver-parameterized models has been that of implicit regularization. It has been oberved that in large models, often there are multiple global minima for the empirical loss. However not all of these empirical minima have low suboptimality at the population level. SGD when used as the training algorithm often seems to find empirical (near) global minima that also generalize well and have low test loss. Hence while general Empirical Risk Minimization (ERM) algorithm might fail, the implicit bias of SGD) seems to yield a well-generalizing ERM. The idea behind implicit regularization is that the solution of SGD is equivalent to the solution of a Regularized Empirical Risk Minimizer (RERM) for an appropriate implicit regularizer.
The idea of implicit regularization of SGD has been extensively studied in recent years. In Gunasekar et al. [2018a] Zou et al. [2021], the classical setting of linear regression (with square loss) is considered and it was shown that when considering over- wer-parameterized setting, the SGD algorithm is equivalent to fitting with a linear predictor with the smallest euclidean norm. In Soudry et al. [2018], Ji and Telgarsky [2018] linear predictors with logistic loss considered and it noted that SGD for this setting can be seen as having an implicit regularization of le norm. Gunasekar et al. [2018b] considered multi-layer convolutional networks with linear activation considered and showned that SGD for this model can be seen as having an implicit regularization of f2/z. norm (bridge penality for depth L networks) of the Fourier frequencies corresponding to the linear predictor. Gunasekar et al. [2018c] considered matrix factorization and showed that running SGD is equivalent to having a nuclear norm based regularizer. More recent work of Arora et al. [2019], Razin and Cohen [2020] shows that in particular in the deep matrix factorization setting, SGD cannot be seen as having any norm based implicit regularizer but rather a rank based one. However, in all these cases, the behavior of SGD corresponds to regularizers that are independent of the training data (c.g. rank, ln-norm, etc).
One could surmise that grand program for this line of research is that for problems where SGD works well, perhaps there is a corresponding implicit regularization explanation. That is, there exists a regularizer R such that SGD can been seen as performing exact or approximate RERM with respect to this regularizer. In fact, one can ask this question specific to SCO problems. That is, for the problem of SCO, is there an implicit regularizer R such that SGD can be seen as performing approximate RERM? In fact, a more basic question one can ask: is it true that SCO problem is always learnable using some regularized ERM algorithms? We answer both these questions in the negative.
SGD vs GD: Smaller the Batch-size Better the Generalization. It has been observed that in practice, while SGD with small batch size, and performing gradient descent (GD) with empirical loss as the objective function both minimize the training error equally well, the SGD solution generalizes much better than the full gradient descent one [Keskar et al., 2016, Kleinberg et al., 2018]. However, thus far, most existing literature on theorizing why SGD works well for over- para--aarmmtezeed deep learning models also work for gradient descent on training loss [Allen-Zhu and Li, 2019, Allen-Zhu et al., 2018 8a,b, Arora et al., 2018]. In this work, we construct a convex learning problem where single pass SGD provably outperforms GD run on empirical loss, which converges solution that has large excess risk. We thus provide a problem instance where SGD works but GD has strictly inferior sample complexity (with or without early stopping).
Multiple Epochs Help. The final empirical observation we consider is the fact that multiple epochs of SGD tends to further continually decrease not only the training error but also the test error [Zhang et al., 2016, Ma et al., 2018, Bottou and Bousquet, 2011]. In this paper, we construct an SCO instance for which multiple epochs of single sumple SGD, and for the same problem, RERM fails to converge to a good solution, and hence, so does GD when run to convergence.
SGD significuntly oulperforms single pass
2

---

1.1 Our Contributions
We now summarize our main contributions in the paper:
1. SGD and RERM Separation. In Section 3, we demonstrate a SCO problem where a single pass of SGD over data points obtains 1 suboptimality rate. However, for any regularizer Rt regularized ERM does not attain a diminishing suboptimality. We show that this is true even if the regularization parameter is chosen in sample dependent fashion. Our result immediately rules out the explanation that SGD is successful SCO due to some some implicit regularization.
2. SGD and GD Separation. In Section 4, we provide separation between SGD and GD on training loss in terms of sample complexity for SCO. To the best of our knowledge, this is the first! such separation result between SGD and GD in terms of sample complexity. In this work, we show the existence of SCO problems where SGD with n samples achieves a suboptimality of // however, irrespective of what step-size is used and how many iterations we run for, GD cannot obtain a suboptimality better than (/ log". (n)).
3. Single-pass Multi-past pass SGD. In Section 5, we provide an adaptive multi-epoch SGD algorithm that is provably at least as good as single pass SGD algorithm. On the other hand, we also show that this algorithm can far outperform single pass SGD on certain problems where SGD only attains a rate of 1/ /n. Also, on these problems RERM fails to learn, indicating that GD run to convergence fails well.
4. SGD and RERM Separation in the Distribution Free Agnostic PAC Setting. The separation result between SGD and RERM introduced earlier for SCO. However, it turns out that the problem is not agnostically learnable for all distributions but only for distributions that make F convex. In Section 6, provide learning problem that is distribution-fiet learnable, and where SGD provably outperforms any RERM.
5. Beyond Convexity (Deep Learning).
The convergence guarantee for SGD can be easily extended to stochastic optimization settings where the population loss F(w) is linearizable, but may not be convex. We formalize this in Section 7, and show that for two layer diagonal neural networks with ReLU activations, there exists a distribution for which the population loss is linearizable and thus SGD works, but ERM algorithm fails find good solution. This hints at the possibility that the above listed separations between SGD and GD/ / RERM for the SCO setting, also extend to the deep learning setting.
1.2 Preliminaries
standard assumption made by most gradient based algorithms for stochastic optimization problems is the following:
F is L-Lipschitz (w.r.t. E norm)
Assumption II:
Bu* E argmin F(w) s.t. || - -
(3)
supw. ESND [VV z) - vF(w)|2<<>
In the above and throughout this work, the norm denotes the standard Euclidean norm and wy is some initial point known the algorithm. Next, we describe below more formally what the regularized ERM, GD and SGD algorithms are.
(Regularized) Empirical Risk Minimization. Perhaps the simplest algorithm one could consider is the Empirical Risk Minimization (ERM) algorithm where one returns a minimizer of training loss (empirical risk)
- Fs(w) == 12 Σ
fw:; 24))
That is, WERM E argminwew Fs(w). A more common variant of this method is one where we additionally penalize complex models using regularizer function R Rd b R. That is, a Regularized Empirical Risk Minimization (RERM) method consists of returning:
WRERM argmin (s( + R(w).
wEW
Despite the way the result is phrased in Amir et al. [2021], their result does not imply separation between SGD and GD in terms of sample complexity but only number of iterations.
3

---

Gradient Descent (GD) on Training Loss. Gradient descent on training loss is the algorithm that performs the following update on every iteration:
GD
GD - FV
(5)
i+1
where 17 denotes the step size. After rounds, we return the point GCD E W GD
Stochastic Gradient Descent (SGD). Stochastic gradient descent (SGD) has been the method of choice for training large over-vorannn wver-parameterieed deep learning models, and other convex and non-convex learning problems. Single pass SGD algorithm runs for steps and for each step takes a single data point and performs gradient update with respect to that sample. That, is on round E,
SGD f I SGD v/V f fw, SGD, 12)
(6)
Finally, we return ii = - -i= w SGD, Multi-epoch (also known as multi-pass) SGD algorithm simply cycles over the dataset multiple times continuing to perform the same update specified above. It is well know that single pass SGD algorithm enjoys the following convergence guarantee:
Theorem 1 (Nemirovski and Yudin [1983]). On any SCO problem satisfying Assumption I in (2) and Assumption II in (3), running SGD algorithm for n steps with the step size of = 1///n enjoys the guarantee
Es(F( W.
SGD) - inf F(w) S O
woRd
where the constant in the order notation only depends on constants B, L and a in (3) and is independent of the dimension d.
In fact, even weaker assumptions like one-point convexity or star convexity of w.r.t. an optimum on the path of the SGD suffices to obtain the above guarantee. We use this guarantee of SGD) algorithm throughout this work. Up until Section 6 we only consider SCO problems for which SGD automatically works with the above guarantee.
Related Work
On the topic of RERM, implicit regularization and SGD, perhaps the work most relevant this paper is that of Dauber et al. [2020]. Just like this work, they also consider the general setting of stochastic convex optimization (SCO) and show that for this setting, for so-called "admissible" data independent regularizer, SGD can be seen as performing implicit regularized ERM. For the implicit regularization part of work, while in spirit the work aims accomplishing some of the similar goals, their work is in the setting where the instantaneous losses are also convex and Lipschitz. This means that, for their setting, while SGD and regularized ERM may not coincide. regularized ERM is indeed still an optimal algorithm as shown in Shalev-Shward et al. [2009]. In this work we show strict separation between SGD and RERM with an example where SGD works but no RERM can possibly provide a non-trivial learning guarantee. Second, qualitatively, their separation result in Theorems and are somewhat unsatisfactory. This because while they show that for every regularizer there is distribution for which the SGD solution is larger in value than the regularized training loss of the regularized ERM w.r.t. that regularizer, the amount by which it is larger can depend the regularizer and can be vanishingly small. Hence it might very well be that SGD is an approximate RERM. In fact, if one relaxes the requirement of their admissible relaxations then it is possible that their result doesn't hold. For instance, for square norm regularizer, the gap on regularized objective between RERM and SGD is only shown to be as large as the regularization parameter which is typically set to be a diminishing function of n.
On the topic of comparison GD on training loss with single epoch SGD, one can hope for three kinds of separation. First, separation in terms of work (number of gradient computations), second, separation in terms of number of iterations, and finally separation terms of sample complexity. A classic result from Nemirovski and Yudin [1983] tells us that for the SCO setting, the number of gradient computations required for SGD to obtain suboptimality guarantee of is equal to the optimal sample complexity (for s) and hence is optimal (in the worst case). On the other hand, single iteration of GD on training loss requires the same number of gradient computations and hence any more than a constant number of iterations of GD already gives separation between GD and

---

SGD in terms of work. This result has been explored in Shalev-Shwartz et al. [2007] for instance. The separation of GD and SGD in terms of number of iterations has been considered in Amir et al. [2021]. Amir et al. [2021] demonstrate a concrete SCO problem on which GD on the training loss requires at least (2(1/")) sstes to obtain an e-suboptimal solution for the test loss. Whereas, SGD) only requires ( iterations. However, their result does not provide any separation between GID and SGD in terms of sample complexity. Indeed, in their example, using the upper bound for GD using Bassily et al. [2020] one can that if GD is run n samples for T = xea iterations with the appropriate step size, then it does achieve a 1/ Vi suboptimality. In comparison our work provides a much stronger separation between GD and SGD. We show sample complexity separation, meaning that to obtain a specific suboptimality, GD requires more samples than SGD, irrespective of how many iterations we run it for. Our separation result also yields separation in terms of both number of iterations and number of gradient computations.
3 Regularized ERM, Implicit Regularization and SGD
In Shalev-Shwartz al. [2009] (see also Feldman [2016]), SCO problems where not just the population loss F but where also for each E Z, the instantaneous loss (() is convex is considered. In this setting, the authors show that the appropriate & norm square regularized RERM always obtains the optimal rate of 1/ However, for SGD to obtain a 1/ 1/vri guarantee, one only needs convexity at the population level. In this section, based on construction of SCO problems that are convex only at population level and not at the empirical level, we show strict separation between SGD and RERM. Specifically, while SGD is always successful for any SCO problem we consider here, we show that for any regularizer R. there is an instance of an SCO problem for which RERM w.r.t. this regularizer has suboptimality lower bounded by a constant.
In Shalev-Shwartz et al. [2009] (see also Feldman [2016]), SCO problems where not just the population loss F but where also for each- E Z, the instantaneous loss f(;,z) is convex is considered. In this setting, the authors show that the appropriate Ea norm square regularized RERM always obtains the optimal rate of 1/.n. However, for SGD to obtain 1/ //víi guarantee, one only needs convexity at the population level. In this section, based on construction of SCO problems that are convex only at population level and not the empirical level, we show a strict separation between SGD and RERM. Specifically, while SGD is always successful for any SCO problem we consider here, we show that for any regularizer R. there is an instance of an SCO problem for which RERM with respect to this regularizer has suboptimality lower bounded by constant.
Theorem 2. For any regularizer R, there exists an instance of a SCO problem that satisfies both Assumptions I and II given in Equations (2) and (3), which
(WRERW))))]] - inf F(w)= 2 S((),,
wERd
where WRERM is the solution to (4) with respect to the prescribed regularizer.
The regularizer R we consider in the above result is sample independent, that is, it has to be chosen before receiving any samples. In general, if one is allowed an arbitrary sample dependent regularizer, one can encode any learning algorithm as an RERM. This is because, for any algorithm, one can simply contrive the regularizer R have its minimum the output model of the algorithm on the given sample, and a very high penalty on other models. Hence, to have a meaningful comparison between SGD (or for that matter any algorithm) and RERM, one can either consider sample independent regularizers or at the very least, consider only some specific restricted family of sample dependent regularizers. One natural variant of considering mildly sample dependent regularizers is to first, in a sample independent way pick some regularization function R and then allow arbitrary sample dependent regularization parameters that multiply the regularizer R. The following corollary shows that even with such mildly data dependent regularizers, one can still find SCO instances for which the RERM solution has no non-trivial convergence guarantees.
Corollary 1. For any regularizer R. there exists an instance of a SCO problem that satisfies both Assumptions I and H. for which the point WRERM argmin Fs(w)) + XR(w), where X is any arbitrary sample dependent regularization parameter, has the lower bound
Es [F [S[FF(WRen (WRERM)]
- inf F(w) 2 S2(1).
WERd
5

---

The SCO problem in Theorem 2 and Corollary is based on the function f(A) given by: [(a)(w; 2) = yll(w - a) 3 x||,
(A)
where each instance 2 E Z can be written as a triplet z (sr, y, a) and the notation @ denotes Hadamard product (entry wise product) of the two vectors. We set x E [0, y E [+1] and a E (0,ei,...,,ea f-a) where é1 to ed denote the standard basis in d dimensions. We also set d > 2".
In the following, we provide a sketch for why f2-norm square regularization fails and show no regularization parameter works. In the detailed proof provided in the Appendix, we deal with arbitrary regularizers. The basic idea behind the proof is simple. Consider the distribution: and y is set to be +1 with probability 0.6 and -1 with probability 0.4, and set a = e deterministically, In this case, note that the population function is 0.2 Unii 1) || @ (w e1)ll2 which is indeed convex, Lipchitz and sandwiched between 0.1] w e1 and 0.2|| e1 ||. Hence, any sub-optimal solution / must satisfy [ - eill I 10s.
Unif 1))²
Since 2n, with constant probability there is at least one coordinate, say j E [d], such that for any data sample (Iee yr) for 1 E [n], we have xe [ whenever Y/ = +1 and x: [ = 1 whenever 3/- 1. Hence, ERM would simply put large weight on the J coordinate and attain a large negative value for training loss (as an example, = cg has training loss of roughly -0.4). However, for test
loss be small, we need the algorithm to put little weight on coordinate j. Now for any square norm regularizer R(w)= = Al|w| 2 to prevent RERM from making this 3 coordinate large, À has to be at least as large as a constant.
However, already argued that any sub-optimal solution T should be such that | c1 ll S 10s. When A is chosen to be as large as a constant, the regularizer will bias the solution towards 0 and thus the returned solution will never satisfy the inequality || eil || S 10s. This leads to contradiction: To find an e sub-optimal solution, we need a regularization that would avoid picking large value on the spurious coordinate ÿ but on the other hand, any such strong regularization, will not allow RERM to pick a solution that close enough e1. Hence, any such regularized ERM cannot find an E sub-optimal solution. This shows that no regularization parameter works for norm square regularization. the Appendix we expand this idea for arbitrary regularizers R.
The construction we use in this section has dimensionality that is exponential in number of samples n. However similarly modifying the construction in Feldman [2016], using the y +1 variable multiplying the construction there, one can extend this result to a case where dimensionality is ((n). Alternatively, noting that for the maximum deviation from mean over coordinates is of order /log d n, one can use a simple modification of the exact construction here, and instead of getting the strong separation like the one above where RERM does not learn but SGD does, one can instead have d = n2 for p E (0, 1] and obtain a separation where SGD obtains the 1/vni rate but no RERM can beat a rate of order / n/nn
Implicit Regularization. As mentioned earlier, proposed theory for why SGD algorithms are so successful is that they are finding some implicitly regularized empirical risk minimizers, and that this implicit bias helps them learn effectively with low generalization error. However, at least for SCO problems, the above strict separation result tells us that SGD cannot be seen as performing implicitly regularized ERM, neither exactly nor approximately.
4 Gradient Descent (Large-batch) vs SGD (Small-batch)
In the previous section, we provided an instance of a SCO problem on which no regularized ERM works well SGD. When gradient descent algorithm (specified in (5)) is used for training, one would expect that GD, and in general large batch SGD, will also eventually converge to an ERM and so after enough iterations would also fail to find good solution. In this section, we formalize this intuition to provide lower bounds on the performance of GD.
Theorem 3.
There exists an instance of a SCO problem such that for any choice of step size n and number of iterations T, the following lower bound on performance of GD holds:
[s[F [[]F(
inf F(w) 2 5 52/12
wERd

---

Theorem 3 suggests that there is an instance of a SCO problem for which the performance of GD is lower bound by 1/n0-42 On the other hand, SGD with the step size of 1j = 1/n learns at rate of 1 1/n0 for this problem. This suggests that GD (large batch size) is worse learning algorithm than SGD. We defer the proof to Appendix and give brief sketch below.
Our lower bound proof builds on the recent works of Amir et al. [2021], which gives an instance of a SCO problem for which the performance guarantee of GD algorithm is R(TVT + 1///") We provide an instance of SCO problem for which GD has a lower bound of (11 Adding the two instances together gives us an SCO problem for which GD has lower bound of
1
9 T
T/ n
This lower bound is by itself not sufficient. In particular, for 1/n and T = n² the right hand side of (7) evaluates to O(1/Vn), which matches the performance guarantee of SGD for this SCO problem. Hence, this leaves open the possibility that GD may work well SGD. However, note that in order to match the performance guarantee of SGD, GD needs to be run for quadratically more number of steps and with smaller step size. In fact, rate in (7), must set 7) O11/n//3 and T = (n?))
show that in order to attain O(1/vn)
The lower bound Theorem follows by adding to the SCO instance in (7) another objective that rules out small step-sizes. This additional objective is added by increasing the dimensionality of the problem by one and on this extra coordinate adding a stochastic function that convex in expectation. The expected loss this coordinate is a piecewise linear convex function. However, the stochastic component on this coordinate has random kinks at intervals of width 1/n that vanish in expectation, but can make the empirical loss point in the opposite direction with probability 1/2. Since the problem is still an SCO problem, SGD works as earlier. On the other hand, when one considers training loss, there are up to n of these kinks and roughly half of them make the training loss flat. Thus, if GD is used on training loss with step size smaller than 1//s/4 then it is very likely that GD hits at least one such kink and will get stuck there. This function, thus, rules out GD with step size smaller than 1/n2//4 Restricting the step size ((L/n5//)), the lower bound in (7) evaluates to the 22(1 //2///111)) giving us the result of Theorem 3.
Our lower bound in (7) matches the recently shown performance guarantee for GD algorithm by Bassily et al. [2020]; albeit under slightly different assumptions on the loss function f(;:2). Their work assumes that the loss functions f(w; z) is convex in w for every z E Z. On the other hand, we do not require convexity of f but only that F(w) is convex in w (see our Assumptions and II).
5 Single-pass vs Multi-pass SGD
State of the art neural networks are trained by taking multiple passes of SGD over the dataset. However, is not well understood when and why multiple passes help. In this section, we provide theoretical insights into the benefits of taking multiple passes over the dataset. The multi-pass SGD algorithm that we consider is:
1. Split the dataset into two equal sized datasets S1 and S2-
2. Run & passes of SGD algorithm using fixed ordering of the samples in Si where,
The step size for the jth pass is set as 77 = 1/ 1/jnj.
At the end of jth pass, compute w = nj generated so far.
2 Ens/2 wSGD as the average of all the iterates
3. Output the point Mr := argmin wew Fs, (w) where w:= = ( w
The complete pseudocode is given in the Appendix. In the following, we show that the above multi-pass SGD algorithm performs at least as well as taking single pass of SGD.
Proposition The output MP of multippasss6 SSDD algorithm satisfies
Es(F((MP)) ) < [F[ ) + Ō
where SGD denotes the output of running (one pass) SGD algorithm for n/ steps with step size n/2
1/ Vn.
7

---

This suggests that the output point of the above multi- pass SGD algorithm is not too much worse than that of SGD (single pass). For problems in SCO, SGD has a rate of O (1/ (see Theorem 1), and in for these problems, the above bound implies that multi-pass SGD also enjoys the rate of O(1/vn).
5.1 Multiple Passes Can Help!
In certain favorable situations the output of multi-pass SGD can be much better:
Theorem 4. Let k be a positive integer and let R(-) be regularization function. There exists an instance of a SCO problem such that:
(a) For any step size n,, the output of the SGD algorithm has the lower bound
1
Eg(F((u inf F(w)= 2 52
Vi
wERd
Furthermore, running SGD with rj = 1//nn achieves the above 1/ 1/vnn rate.
(b) On the other hand, multi-pass SGD algorithm with le passes has the following guarantee:
Es [s[F( inf F(w)= & ( (
weRd
Vnk
(c) RERM algorithi has the lower bound: Es[F(WRERNI) -inf F(w) 2 Q(1).
We defer the proof details Appendix D and provide the intuition below. Parts (a) and (b) follow easily by taking a standard construction in [Nesterov, 2014, Section 3.2.1J. Here, a convex determin- istic function F over optimization variable is provided such that Assumption II is satisfied with L = O(1), and any gradient based scheme (such as SGD, which is equivalent to GD on FN) has a suboptimality of 12(1/VT) after n iterations (which corresponds to single pass SGD). On the other hand, because FN satisfies Assumption II, k passes of SGD, which correspond to nkk iterations of
GD, will result in suboptimality of O(1/ / nk)) for the given step sizes.
The more challenging part is to prove part (c). It is tempting to simply add the SCO instance from Theorem 2, but that may break the required upper bound of O(1/ (nk/vnk) for multipass SGD. To get around this issue, we construct our SCO instance by making & consist of k components (E1,.... Ex} drawn independently from the distribution considered in Theorem 2. Furthermore, the loss function considered in Theorem 2 also defines the loss corresponding to each & component for an optimization variable that is different from the optimization variable v.
The key idea in the construction is that, while each data sample consists of k independently sampled components, at any time step, SGD gets to see only of these components. Specifically, in the first pass over the dataset, we only observe the &ı component of every sample, and in the second pass only observe the ε component for every sample and for SGD is induced by using an independent control variable u. The optimization objective for u is such that SGD increases u monotonically with every iteration. The value of u controls which of the S, components is observed during that time step. In particular, when we run our multipass SGD algorithm, during the first pass, the value of is such that get second pass, u has become large enough to reveal E,2, and so on for further passes. Thus, in l: passes, multipass SGD gets to see nık "fresh" samples and hence achieves an suboptimality of O(1/v Vnk), as required in part (b). Finally, part (c) follows from the same reasoning as in Theorem 2 since the same SCO instance is used.
for further passes. This behavior
& only. However, on the
6 Distribution Free Learning
In this section, we consider the general learning setting [Vapnik, 2013) and aim for a distribution free learnability result. That is, we would like to provide problem settings where one has suboptimality that diminishes with n for any distribution over the instance space Z. For the SCO setting we considered earlier, the assumptions in (2) and the assumption in (3) that the population loss is convex, imposes restrictions on the distributions allowed to be considered. Specifically, since f((:2) need not be convex for every 2, can easily construct distributions for which the problem is not SCO and in
8

---

fact, may not even be learnable. E.g., consider the distribution that puts all its mass on & for which f( 2) non-convex. In this section we will consider problems that are so called learnable, meaning that there is a learning algorithm with diminishing in suboptimality for any distribution 'D on the instance space 2. Under this setting, we show a separation between SGD and RERM. Specifically, we provide a problem instance that is learnable at a rate of cn (211/n //////// for any distribution over the instance space Z. In particular, we show that the worst case rate of SGD is Cn. for this problem. However, on the subset of distributions for which the problem SCO, SGD as expected obtains a rate of 1/vn. On the other hand, for the same problem we show that RERM while having worst case rate no better than Cn. has a lower bound of ((()) on SCO instances.
Our lower bound in this section is based on the following learning setting: For d > 2", let 2 = {0, 13dd x {0, , 6a) be the instance space, let the instantaneous loss function be given by:
(w 2) 2 (1 a) @ x 2|
On w| - all + max 1, [|]]
BB)
2
where = (z)
a) and Cn == n (1-)) for some 7 > 0.
Additionally, let Pe denote the set of distributions over instances space Z for which F is convex, i.c.
2e = {D F(w)= Eu~D [f(m) (w, 2)] is convex in w).
(8)
Note that under the distributions from Ze, the problem is an instance of an SCO problem. We show a separation between SGD and RERM over the class Ze. In the theorem below claim that the above learning problem is learnable with a worst case rate of order en (by SGD), and whenever 'D E Ze, SGD learns at faster rate of I/v To begin with we first provide the following proposition for the problem described by the function ((B) that shows that no algorithm can have a worst case rate better than Cn for this problem.
Proposition 2. For any algorithm ALG that outputs @LLG there is a distribution D on the instance space, such that for the learning problem specified by function f(m):
Es[F([ALG))] inf F(w) 2 Gp wEW
4
Next, we show that SGD obtains this worst case rate, and a much better rate of 1//nn for any distribution in Ze. However, we also show that for this problem, no RERM can obtain a rate better than e for every distribution in Do. This shows that while SGD and RERM have the same worst case rate, SGD outperforms any RERM whenever the problem turns out to be convex.
Theorem 5. For the learning problem specified by function f(B):
(a) For every regularizer R, there exists a distribution D E De such that,
inf F(w) 2 R(c)))
wER4
(b) For the SGD algorithm have the following upper bounds:
VD E 2o. Es(P(
inf F(w)= S 0 we Rd
VD E 2e, Es (TGGG)
inf F(w) S 0 (cn).
WeRd
As an example, plugging in C, = n implies that when D & 2c, the suboptimality of SGD is bounded by O(1/n1/8), and when D E Zc. the suboptimality of SGD is bounded by O(1/V). However, for any RERM, there exists a distribution D E 2z, on which the RERM has a suboptimality of 1/1/n//A) and the worst case rate of any RERM is also -1/8 This suggests that SGD is superior algorithm to RERM for any regularizer R, even in the distribution free learning setting.
o-Linearizable Functions and Deep Learning
While the classic convergence proof for SGD is shown for SCO setting, a reader familiar with the proof technique will recognize that the same result also holds when we only assume that the population loss F is star-convex or one-point-convex with respect to any optimum w", or in fact even it is star-convex only on the path of SGD. The following definition of Linearizable population loss generalizes star-convexity and con-point-

---

Definition 1 (a-Linearizable), A stochastic optimization problem with population loss F(w) is o-Linearizable if there exists a w² E argmin F(w) such that for every point w E R
F(w) - F(w"(( S a a (F(W),,-W--) w")
For linearizable function, one upper bound the suboptimality any point by a linear function given by Vww)). The convergence guarantee for SGD now follows by bounding the cumulative sum of this linear function using standard arguments, giving us the following performance guarantee.
Theorem 6. On any o-Liinariazeabl stochastic optimization problem satisfying Assumption II in (3), running SGD algorithm for steps with the step size of 1 = =1//n enjoys the guarantee:
Es(F(a,
(GF)) inf F(w)= S O wERd
where the constant in the order notation only depends on constants B, and in (3) and is independent of the dimension d.
The hypothesis that this phenomenon is what makes SGD successful for deep learning has been proposed and explored in various forms [Zhou et al., 2019, Kleinberg et al., 2018]. On the other hand our lower bound results hold even for the simpler SCO setting. Of course, claim such a separation of SGD with respect to GD or RERM in the deep learning setting, one would need to show that our lower bound constructions can be represented as deep neural networks with roughly the same dimensionality as the original problem. In fact, all the functions that we considered so far can be easily expressed by restricted deep neural networks (where some weights are fixed) with square activation functions practical neural networks would look anything like our restricted neural network constructions; it still opens the possibility that the underlying phenomena we exploit to show these separations hold in practical deep learning setting. In the following, we give an example of a simple two layer neural network with ReLU activation function where SGD enjoys rate of 1/ /n, but any ERM algorithm fails to find an Ouu)suubal solution.
show in Appendix F.3. Although, it would be stretch to claim that
Let the input sample (x. y) be such that æ E {0, and E {-1,1}. Given the weights w = (wi, W2), where w1 E Rd and wy E IRd, we define two layer ReLU neural network that on the input outputs
h(w;,) x) ReLU(w,, ReLU((e @ x)).
This is two layer neural network with the input layer having diagonal structure and output layer being fully connected (hence the name diagonal neural network). Suppose the network is trained using the absolute loss, i.e. on data sample (æ, y) and for weights = (w), we use the loss
[w;; =) = ly lww; =)1 by ReLU(w, ReLU(w) + x))]-
Theorem 7 (Two layer diagonal network). For the loss function given in (9) using a two layer diagonal neural network, there exists a distribution over the instance space Z such that:
(a) F(w) is L/2-Linearizable, and thus SGD run with step-size 1/ //V has excess risk O(L
(b) For d 2 2", with probability 0.9, ERM algorithm fails to find an O(1)-suboptimal point.
Remark 1. The result of Theorem 7 can be extended to diagonal two layer neural networks trained with linear loss fww; 2) yh( x)., or with hinge loss f(w; x) max (0. yh(w; 2)).
While the above result shows that for a simple two layer neural network, SGD performs better than ERM, our construction requires the first layer to be diagonal. direction to explore whether a similar phenomena can be demonstrated in more practical network architectures, for eg. fully connected networks, convolutional neural networks (CNN), recurrent neural networks (RNN), etc. It would also be interesting to extend our lower bounds for GD algorithm from Section 4 to these network architectures. The key idea is that SGD only requires certain nice properties (eg, convex. Lincarizable, etc) the population level, which might fail to hold at the empirical level in large dimensional models; hence, batch algorithms like GD and RERM might fail.
an interesting future research
10

---

Acknowledgements
We thank Roi Livni, Robert Kleinberg and Mehryar Mohri for helpful discussions, AS was an intern Google Research, NY when a part of the work was performed. KS acknowledges support from NSF CAREER Award 1750575.
Funding Transparency Statement
Funding in direct support of this work: NSF CAREER Award 1750575.
References
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841. PMLR, 2018a.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M Kakade. Benign overfitting of constant-stepsize sgd for linear regression. arXiv preprint arXiv:2103. 12692, 2021.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint 1:Xiv:/003.07300 2018.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks. arXiv preprint arXiv::806.. 806.00468, 2018b.
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro.
Implicit regularization in matrix factorization. In 2018 Information Theory and Applications Workshop (ITA), pages 1-10. IEEE, 2018c.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Xrxiv preprint arXiv: /905. /365,,, 2019.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. arXiv preprint arXiv:2005.0633 2020.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On aurge-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609, 1et..04669. 2016.
Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? In International Conference Machine Learning, pages
PMLR, 2018.
Zeyuan Allen Zhu and Yuanzhi Li. Can sgd learn recurrent neural networks with provable general- ization? arXiv preprint 190.:1902.01022 2019.
Zeyuan Allen Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv preprint arXiv:1811.04911 2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. the convergence rate training recurrent neural networks. arXiv preprini arXiiv///00 12065, 2018b.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning, pages 244-253, PMLR, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint (rXiv:1611.0333 2016.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern ever-parametrized learning. International Conference on Machine Learning, pages 3325-3334. PMLR, 2018.

---

Léon Bottou and Olivier Bousquet. The tradeoffs of large-scale learning. Optimization for machine learning, page 351, 2011.
Idan Amir, Tomer Koren, and Roi Livni. Sgd generalizes better than gd (and regularization doesn't t help). arXiv preprint arXiv:2 0000000/177 2021.
Arkadi Semenovië Nemirovski and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Assaf Dauber, Meir Feder, Tomer Koren, and Roi Livni. Can implicit bias explain generalization? stochastic convex optimization case study, arXiv preprint arXiv:2003.06152, 2020.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, 2009.
S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: Primal Estimated sub-GrAdient SOlver for SVM. pages 807-814, 2007.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. arXiv preprint arXiv:2006.06914 2020.
Vitaly Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. arXiv preprint arXiv:1608. 1eter16088..4444 04414, 2016.
Yurii Nesterov. Introductory Lectures on Corvex Optimization: A Basic Course. Springer Publishing Company, Incorporated, edition, 2014. ISBN 1461346916.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. Sgd converges to global minimum in deep learning via star-convex path. arXiv preprint arXiv:1901.00451, 2019.
Jifí Matoušek and Jan Vondrák. The probabilistic method. Lecture Notes, Department of Applied Mathematics, Charles University, Prague, 2001.
Dmitriy Panchenko. Some extensions of an inequality of vapnik and chervonenkis. Electronic Communications Probability, 7:55-65, 2002.
12


Reviews:
[{"review_id": "mawzO4dYQNH", "reviewer": "Reviewer_Esyv", "summary": "The paper considers the problem of stochastic convex optimization where the population loss is convex, while the empirical loss is not necessarily convex. Specifically, this work examines SGD,GD and RERM under this setting.  \n\nThe first result demonstrates a separation between SGD and RERM, in contrast to the more common SCO problem. It is well known that SGD ,given $n$ samples, obtains an $O(1/\\sqrt{n})$-optimal solution (in population risk) after one pass over the dataset. They provide a lower bound of $\\Omega(1)$ for RERM w.r.t any sample independent regularizer and any regularization parameter(possibly sample dependent).\nThe second result extends that of Amir et al. [2021] (in the slightly different setting of SCO), and they provide a lower bound in terms of sample complexity for GD of - $\\tilde\\Omega(1/n^{5/12})$.\nThe authors also provide an instance of SCO problem in which $k$-multi-pass SGD achieves a $O(1/\\sqrt{nk})$ excess population risk, while RERM attains a lower bound of $\\Omega(1)$.\nLastly, they provide a separation between RERM and SGD in the distribution free model, where SGD outperforms RERM (for any regularizer) for distributions where the population loss is convex - SGD upper bound of $O(1/\\sqrt{n})$ vs RERM lower bound of $\\Omega(1/n^{1/8})$. And also for distributions where the population loss is $\\text{\\emph{not}}$ convex - SGD upper bound of $O(1/n^{1/8})$ vs RERM lower bound of $\\Omega(1/n^{1/8})$.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written and clearly explains the problem, the lower bounds, and the ideas behind the proofs. This paper affirms that SGD is indeed superior to GD and also surprisingly to RERM for any regularizer, in the specific regime this paper considers. This also substantiates the claim that implicit regularization is not the reason for the generalization properties of SGD.\n\nThough some of the constructions rely on previous work(Amir et al [2021], Nesterov [2014]), I find the necessary extensions as novel and non-trivial.\n\nOne comment I have, in Theorem 7 you claim that $w^\\star$ is in the unit ball. However, based on the construction this seems to be incorrect as for $w\\in\\mathcal{R}^d$ we have $\\min_{w\\in\\mathcal{R}^d}F(w)\\rightarrow -\\infty$. Please address this issue in the rebuttal, as it might have implications on the following Theorem 8, Theorem 9 and ultimately Theorem 3.\n\n-----Response-----\nThe concerns raised over the boundness of $F(w)$ were properly answered. As far as I understand, the point that the global minimizer is in the unit balI was not mentioned in the paper of Amir et al, so I would suggest addressing this point in the proof.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no foreseen societal implications. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "jnprVVXFMor", "reviewer": "Reviewer_7fEN", "summary": "This paper studies the generalization error bound of multi-epoch, small-batch, SGD for learning over-parameterized models. In particular, the authors compare the generalization performance of SGD to GD and regularized empirical risk minimization (RERM). For RERM, the authors show that there is an SCO problem for which RERM will not give vanishing generalization error while SGD enjoys a $O(1/\\sqrt{n})$ rate. For GD, the authors also show that for some SCO problems GD with any step size and number of iteration can only achieve a $\\Omega(1/n^{5/12})$ rate, which is also worse than SGD. Lastly, the authors show that multi-epoch SGD can perform better than single-pass SGD.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Generally speaking, this paper is well written and the comparison to RERM and GD verifies the effectiveness of SGD. Detailed comments are as follows:\n\nThe claim that “this automatically rules out any implicit regularization based explanation for the success of SGD” is a bit overstated because the comparison of generalization error between SGD and RERM in this paper is only performed for a small class of problem instances. It is likely that given more conditions on the problem instance there could be a connection between RERM and SGD. For example, as shown in [1], for the least square problem, SGD (with iterate averaging) has a similar generalization performance compared to ridge regression solution in terms of the generalization error bound.   \n\nFollowing the previous comment, this paper only provides one side comparison between SGD and RERM/GD, i.e., only shows that for one single problem instance RERM/GD performs worse than SGD. Given this, it is also likely that for some problems RERM/GD can perform much better than SGD. A discussion on this opposite side may also need to be included.\n\nRegarding the multi-epoch SGD algorithm, why do you only calculate the average of the first $nj/2$ iterates rather than all of them? Besides, the first $nj/2$ iterates are generated using different learning rates, would it be better to take this into consideration and use a weighted average?\n\nI did not check the proof but I guess Proposition 1 requires that the loss function on $S_2$ can well concentrate around its expectation. But this may require the loss function is subgaussian or upper bounded. However, this paper only assumes that the loss function is Lipschitz rather than bounded. \n\nReference:\n\n[1] Zou et. al., Benign overfitting of constant-stepsize sgd for linear regression, arXiv 2021\n\n\n==================\n\nI have read the authors' responses. Overall this paper is good and I keep my recommendation of acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hrs"}, "extra_text": {}}, {"review_id": "DbaL4mf0WuX", "reviewer": "Reviewer_5qGy", "summary": "This paper considers the sample complexity comparison between one-pass SGD vs. ERM/RERM/GD/multi-pass SGD in the setting of SCO (with Lipschitz, finite $\\ell_2$-norm solution, bounded gradient variance). It shows that, for any problem instances in the considered SCO class, one-pass SGD always achieves good, $1/\\sqrt{n}$ rate; in contrast, ERM, RERM (that is distribution-agnostic but is allowed to tune a multiplicative hyperparameter), GD (with any number of passes) could be arbitrarily bad in the worse-case instance in the considered problem class. Moreover, when used with a hold-out validation set, multi-pass SGD can outperform (at least no worse than) one-pass SGD. In conclusion, the paper reveals an important message, that (one-pass) SGD does have its own implicit bias, but it cannot be explained by a simple explicit regularizer.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Pros:\n+ The paper is written very well! \n+ A systematic (worse-case) sample complexity comparison between one-pass SGD vs. ERM/RERM/GD/multi-pass SGD in the setting of SCO problem class is conducted. The presented results are quite inspiring for understanding the implicit bias of (single-pass) SGD.\n\n# Cons:\n- The considered multi-pass SGD is with a hold-out validation set. However the considered GD does not utilize a similar setup. This is not fair  to the statement for GD. With that being said, I think the authors have done a good job of making things clear & the part of multi-pass SGD is also inspiring in its own.\n- Some dimension factors are hidden in the constants in Assumption II. Since the considered dimension is large, this could limit the applicability of the presented results. \n\n# Typos:\n* l.201. ... is simple. (, -> .)\n* l.327. imposes -> impose. need -> needs.\n\n# Overall\nI had the fortune to be one of the reviewers of (an old version of) this paper in another conference (where we had a very long discussion weighting the spirits and shortcomings). Compared with the old version that I had read (which already shows interesting spirits but has some shortcomings), the current version is way more clear and complete. Almost all the issues that I used to have are resolved in this version. Though there are a few (less-critical) points that can be improved, I am quite happy to score this version an acceptance.\n\n\n\n------\n\nPost-rebutal:  my issues are largely resolved after reading the authors reply. After reading the other reviewers comments, I will maintain my initial score and recommend to accept this paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "8Q8a9134hC", "reviewer": "Reviewer_QRsG", "summary": "The paper discusses the current training approaches of SGD from a theoretical perspective. On the negative side, the paper denies a popular conjecture that SGD has an implicit regularization like regularized ERM. On the positive side, the paper shows that SGD does outperform GD in some SCO problems, and that multiple-pass SGD does help in some SCO problems.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is overall well written and technically comprehensive. The result comparing SGD and RERM somewhat addresses a popular \"misbelief\" that SGD works because of implicit regularization and I think this information is worthy conveying. Similar for other results.\n\nMy major concern about the results is that the constructed SCO problems look so \"manufactural\" that it might not be able to reflect reality. For example, the dimension of the constructed negative example in Theorem 1 is about $\\mathcal{O}(2^n)$. This brings two disadvantages: 1. In practice no dimension is in the scale of $\\mathcal{O}(2^n)$, so the counter-example might not be enough to deny the possibly of SGD having implicit regularization; 2. Due to such a high dimension, the proof is essentially finding a dimension that \"overfits\" the finite data in the ERM setting but fails to fit the ground truth (which can be seen as a population setting). So actually in this case the difference of SGD and RERM is caused by the difference of population risk and ERM, and thus seems not related to SGD itself. Please correct me if I misunderstand something. I understand the theoretical flavor of this paper, but I'm just wondering whether the result can be improved to be more practical.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations and potential negative societal impact of their work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents interesting results refining the relationship between SGD and GD, and also implicit regularization.  The reviewers are all in support, and I request the authors carefully consider the reviewers' suggestions in their revisions.
Decision: Accept (Poster)