Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors study SGD, with and without replacement, and construct counterexamples for which SGD fails to converge despite the objective being otherwise well-behaved (e.g. convex and smooth).
strengths_and_weaknesses: This appears to be a significant work but is inappropriate for the NeurIPS community because it is too theoretical. The dataset Z and the objective function (bottom pg. 5) are simple but it is unclear how this result relates to real-world machine learning problems. This is evidenced by the lack of experiments in the paper.
questions: None
limitations: N/A
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors provide a stochastic convex optimisation framework in which one passe SGD (classically) minimises the population risk at a $O(1 / \sqrt{n})$ rate but however exhibits a $\Omega(1)$ training error and generalisation error.
strengths_and_weaknesses: The paper is well written. Each result is clear, introduced and commented. The analysis is rigorous and non trivial. Overall I have no criticism concerning the technical results, which I believe are original. However the main results in section 3 seem anedoctal in the sense that (1) nobody does one pass SGD (2) the considered setting is very peculiar and clearly not encountered on a daily basis: cherry picked distribution and loss, $d \geq 2^{n \log n}$.  This on its own would not bother me (as mentioned, I find the results original and interesting), however my main concern are the conclusions / interpretations which are drawn from the results.  Overall I find that the introduction is very misleading, here are several claims in it which I believe are misleading / false:

- *"First, it is clear that SGD cannot be framed as any reasonable regularized empirical risk minimization procedure for the simple reason that it does not minimize the empirical risk, **which challenges the implicit regularization viewpoint to the generalization of SGD**"*: the implicit regularization viewpoint is crucial in the interpolation setting (setting which is met in practice). Hence I cannot agree with your statement: it does not challenge the viewpoint as you consider a totally different setting.

- *"Second, any attempt to explain generalization of SGD by uniform convergence over any (possibly data-dependent) hypotheses set cannot hold, simply because the sample average associated with the very same training set SGD was trained on is not necessarily close to its respective expectation"*:  (1) your result holds only for one pass SGD (which nobody does in practice), hence one could expect the classical train / generalisation gap to hold for multiple passes 

- in the abstract: *"Consequently, it turns out that SGD is not algorithmically stable in any sense, and its generalization ability cannot be explained by uniform convergence or any other currently known generalization bound technique for that matter (other than that of its classical analysis)"*: again this only holds for one pass SGD which is never considered in practice. 


Minor comments: 
- in the population risk convergence, it would have been clearer to put the exact convergence bound instead of a big $O( )$ so that it is clear that there is no hidden dependence in the dimension $d$ which would have killed the rate. 
- a conclusion would have been appreciated 
- line 183: $w^*_S = \arg \min _w \hat{F}(w)$: why is the argmin unique ? if not unique which one do you choose ? 
questions: N/A
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper shows, by considering the stochastic convex optimization framework, that there exist problem instances where the SGD solution exhibits both empirical risk and generalization gap of $\Omega(1)$ (in the without replacement case). SGD is therefore not algorithmically stable. This phenomenon does not occur for SGD with replacement.
strengths_and_weaknesses: Strengths:
- the phenomenon reported in the paper is novel, intriguing and potentially impactful in the context of SGD generalization bounds
- analytical evidence is solid
- the multi-epoch regime is addressed

Weaknesses:
- nor discussions nor conclusions are present
questions: - discussions and conclusions are not present

Minors:
- l338: forgo
limitations: Limitations and potential negative societal impact of this work may be discussed more
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the empirical risk and population risk (together with generalization) for different variants of SGD in the context of stochastic convex optimization (they also extend the analysis to other settings, i.e., convex in expectation, strongly convex). Their main contribution is to construct an example that (one-pass) SGD exhibits both empirical risk and generalization gap of $\Omega(1)$. Moreover, they show that this phenomenon does not exist if we use with-replacement SGD. Last, they derive upper and lower bounds for without-replacement SGD in the multi-epoch regime.
strengths_and_weaknesses: **Strengths:**
* This paper studies the behavior of SGD in SCO, providing new intuition of the analysis of test error (population risk). By their construction, even in the convex optimization, there exists an instance that provably minimizes population risk, while the empirical risk is of constant level, resulting in a constant generalization gap. This observation questions the rational optimization-generalization decomposition framework (or ERM framework). The main reason, is that SGD does not minimize the empirical loss, which differs a lot in the smooth setting. In a word, this observation might lead to a new type of analysis of statistical learning, which can have a broad impact on the community.
* The other observations, together with their proof techniques are also interesting. For example, the comparison between with and without replacement might provide some intuition on the advantage of multi-pass SGD in terms of its implicit regularization.
* The paper is well-structured and provides good intuition for the proof technique.
**Weakness:**
* The construction of the failure seems artificial and might not be general enough. They rely on a special structure that (to my best knowledge) no realistic learning problem has a similar structure. It would be great if the author can provide some connection between their constructed example and some realistic examples.
* The analysis relies on the averaged solution instead of the last iteration solution, which prevents the general impact of this work. It would be great if the author can at least comment on or conjecture the result for the last iteration case.
questions: Please see the weaknesses part.
limitations: Please see the weaknesses part.
review_title: null

Meta-review: metareview: This paper analyzes the behavior of SGD for stochastic convex optimization, showing that there exist problem instances where the SGD solution exhibits both significant empirical risk and generalization gap in the without replacement case. The finding is potentially impactful in the context of SGD generalization bounds. The paper is well-structured and provides good intuition for the proof technique. However, I encourage the author(s) to provide a construction of the failure that is more general and less artificial.
confidence: Less certain
Decision: Accept