Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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:

The 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.   

Following 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.

Regarding 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?

I 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. 

Reference:

[1] Zou et. al., Benign overfitting of constant-stepsize sgd for linear regression, arXiv 2021


==================

I have read the authors' responses. Overall this paper is good and I keep my recommendation of acceptance.
limitations_and_societal_impact: There is no potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: # Pros:
+ The paper is written very well! 
+ 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.

# Cons:
- 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.
- 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. 

# Typos:
* l.201. ... is simple. (, -> .)
* l.327. imposes -> impose. need -> needs.

# Overall
I 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.



------

Post-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. 
limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

My 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.
limitations_and_societal_impact: The authors addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.  

The 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).
The 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})$.
The 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)$.
Lastly, 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})$.
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.

Though some of the constructions rely on previous work(Amir et al [2021], Nesterov [2014]), I find the necessary extensions as novel and non-trivial.

One 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.

-----Response-----
The 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.
limitations_and_societal_impact: There are no foreseen societal implications.
review_title: null

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)