Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors of the paper present their work on multipass SGD for least-squares. They show the following contributions:
- The excess risk of SGD is the one of GD plus a positive fluctuation term
- They show data-dependant bound consistent in the $t\to\infty$ regime, where $t$ is the number of iterations
 

strengths_and_weaknesses: ### **Strengths**

- The authors present a clear analysis of the setting they describe: an excess risk upper bound for multipass SGD for Least-squares. As far as I understood, they do so for the *final iterate*, which has been rarely considered. I guess that the authors' could stress on this idea a little bit more as previous analysis do not cover this case. 
- They provide bounds that are consistent in the so-called *benign overfitting regime*


### **Weaknesses**

- The main weakness is that the paper is largely overselling: e.g. the fact that the excess risk of SGD decomposes as GD and a fluctuation error cannot really be considered as a deep contribution even if previous work did not write it explicitly. In the same manner, comparison with existing literature is misleading: what the authors say about the novelty concerning the adaptivity to covariance structure is simply false.
- Indeed, the authors claim that one of the main difference of their bound is that they are data dependant whereas previous work are not. I truly think that there is a confusion with the capacity and source conditions used by the mentioned authors: they correspond exactly to a nice framework showing how adaptive to the data SGD/GD/Ridge is. What is strange is that the authors, to exemplify their bound, take specific polynomial or polynomial + log decrease of eigenvalue of the covariance matrix: that is exactly a *capacity model* of the data.  Going further, it is said that the authors need a Gaussian prior over $w_*$. That condition is indeed not needed in the previous work. Here, the *source condition* could be a deeper look on how $w_*$ has been chosen (think about a *Gaussian process*) and would simply extend the authors' work.
- The data assumptions on $H^{-1/2} x$ is strong (especially the independence of the coordinates). This almost corresponds to a gaussian model of the data. It may be necessary for the benign overfitting phenomenon to be exhibited but as far as the SGD optimisation is concerned, this is a very restrictive assumption compared to previous work.
- Finally, I have to say that I find quite curious that the authors show bounds in the main theorem that necessitate a deep look to be understood (see corollary 4.4 for example). I understand that this appears to be one of the claimed strength of the authors but it is simply misleading for me. 

questions: I have no question regarding the results.
limitations: - Hypothesis on the data to be subgaussian and indepedant.
- Very similar to previous work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work studies the generalization capability of multi-pass SGD for least squares problems under the interpolation regime. Specifically, the excess risk bound using the spectrum of data covariance achieved is provided under the assumptions: Gaussian prior to the true parameter and existence of interpolator. This result demonstrates the advantage of multi-pass SGD over OLS and GD under specific spectrum settings.

strengths_and_weaknesses: **Strengths**

A contribution of this work is that the excess risk bound described with the spectrum of data covariance is derived under the existence of an interpolator for examples, which seems to be new in the context of multi-pass SGD analysis (Pillaud-Vivien et al. [27], Line and Rosasco [21], and Mucke et al. [24]). Indeed, these studies assume specific decay rates of the spectrum and source conditions on the true parameter. 


Although direct comparison with these existing results is difficult in general, the authors show that multi-pass SGD achieves at least the comparable excess risk bound with OLS under a specific spectrum setting (Corollary 4.5) as a sanity check. 


**Weaknesses**

(1) The existence of an interpolator limits the number of examples $n$ to e.g., $n<d$ (where $d$ is dimensionality.) This means we cannot take the limit $n\to \infty$ and cannot show the convergence to zero excess risk. I think this limitation seems unavoidable because the convergence $\hat{w}\to w_*$ (under $n\to\infty$) contradicts the assumptions where $\hat{w}$ has finite norm and $w_*$ follows Gaussian prior. 

(2) On one hand, the assumption of the Gaussian prior is nice because it is a milder assumption compared to the source condition. On the other hand, this hinders characterizing learnable classes of target functions (e.g., Sobolev class et al.). 


**Other comments**

- On line 86-87: ``More recently, ... an exponential rate in the interpolation regime [22,5,33,34]" 
An exponential convergence of SGD under the interpolation regime was also shown in Needell et al. [25].  Note that $\sigma^2=0$ (in Theorem 2.1, [25]) which is attained in the interpolation regime yields an exponential rate.

questions: - On lines 170-173: I am not sure if Young’s inequality (appearing in related works) is a weak point which should be noted. I think it does not slow down the convergence rate. What are the advantages of not using it?

- What happens when taking limit $d\to \infty$ in proportion to $n$ as done in the context of random matrix theory? This question relates to a weakness stated (1) above. I am wondering if zero excess risk is achieved by taking limits of $n, d$, simultaneously.





limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work studies the statistical aspects of empirical risk minimization (ERM) when solving it using SGD. The authors particularly focus on the (un-regularized) least squares objective where the minimum norm solution to the ERM problem can interpolate the empirical data. They show that the excess risk of SGD is exactly that of GD plus a non-negative fluctuation error under the same hyperparameters. This decomposition is used to give problem-dependent risk bounds for SGD and GD. These bounds show that GD achieves lower excess risk than SGD when given the same number of iterations, but SGD has a lower iteration cost so it can still be preferred in terms of computation.
strengths_and_weaknesses: This paper is well organized and highly polished. The claims are mostly sound, although I have only checked the proofs at a high level. I find the risk decomposition result interesting, and that giving problem-dependent risk bound is indeed desired to reflect the inherent difficulty of individual problems. Another strength is that the assumptions made in this paper are more general than existing works analyzing similar problems, although I have one issue regarding the combination of the assumptions together:

Although the authors conjecture that the prior assumption on $w^*$ can potentially be removed, the results still rely on that to be true. However, it is unclear to me why, when a prior is assumed but the updates themselves are solving for an MLE rather than a MAP estimation. That is, if we know that the ground truth comes from Normal distribution with a known covariance that is a multiple of the diagonal, then the most natural thing to do for statistical accuracy is to incorporate that information by imposing a L2 regularization proportional to that multiple. However, if we do that, it'll be uncertain whether the interpolation condition can still easily hold. The minimum norm solution should also have an additional diagonal added to $X^TX$. To me this is a strange setting where a prior is assumed but never used in the algorithm, and I'm not sure how to interpret that, or whether it can be incorporated into the algorithm without contradicting the interpolation assumption. It would be great if the authors could elaborate on the reasoning behind throwing away the prior information, if I understood it correctly.

Lastly, although the authors have fully acknowledged that their results apply only to vanilla SGD in the with replacement setting, and the without replacement setting is set for future work, I still find the "multi-pass SGD" terminology somewhat misleading. In with replacement SGD a single pass does not guarantee a full pass of the training data - that is only guaranteed by some permutation-based SGD. This is not intended to nitpick (and was not a scoring factor in my evaluation) but I would like to encourage the authors to find an alternative expression. 
questions: minor issues:

- "gram" matrix should be spelled as "Gram" matrix
- When comparing with existing results (page 6), it might be helpful to briefly introduce what a *source condition* is, for those who are less familiar with the related work.
limitations: I believe the authors have adequately addressed the limitations, such as lacking results for diminishing step sizes and the multi-pass SGD in the without replacement sampling regime. I agree with the authors on the foreseeable difficulties with these analyses and that they should be considered interesting future directions.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the generalization properties of over-parameterized least squares with SGD. To be specific, the considered SGD works in a setting of multi-pass, one batch, last iterate, constant step-size SGD with replacement. By considering SGD with replacement, the analysis can be simplified due to the unbiased property of stochastic gradients, and accordingly, the iid data sampling strategy still holds under the multi-pass setting.

strengths_and_weaknesses: Pros:

This paper provides a solid analysis of multi-pass SGD of least squares in the interpolation regime. It provides nice results, e.g., 1) under this setting, the excess risk of SGD is always worse than that of GD; 2) the fluctuation error bound as well as the excess risk is based the eigenvalue decay of the data; 3) at the same level of excess risk, SGD requires more iterations but less gradient complexity than GD.

Cons:

I think this work has no significant drawback, but it would better to clarify the theoretical results in several aspects:

1) Line 261: what’s the difference between the expectation over “SGD” and $i_t$? According to the randomness definition of “SGD” in line 155, the randomness only comes from uniformly at random, i.e., “SGD”$=(i_1, i_2, …, i_t, …)$, right? This needs to be clear, especially on $\mathbb{E}_{i_t} {x}_{i_t} {x}_{i_t}^{T}= {\Sigma}$.

2) What’s the benefit of multi-pass version as I don’t find very clear benefit in Corollary 4.5 under a relatively slow eigenvalue decay.


questions: 1) Line 120: The expected covariance matrix H is required to be positive definite and A is full rank?

2) Line 140: Running GD under the interpolation regime converges to the min-norm interpolator. This is a well-known result. However, the convergence of SGD path depends on the choice of the ground truth. It’s unclear to me on the convergence of SGD under the interpolation regime.

3) Line 162: theorem 4.1, I like this theorem as well as (5.3) to show that, the excess risk of SGD is always worse than GD under the same iterations. I’m wondering that, this still holds true for other problem settings? e.g., different loss functions, over-parameterized neural networks. Besides, this result needs to be well discussed when compared to results on implicit bias of SGD.

4) What’s the result under the exponential decay? As the authors mentioned in line 236, SGD with fixed size can only hold for small step-size under the polynomial decay. It seems that Corollary 4.5 allows for large step-size?

5) albeit iid, the data are sampled from the empirical measure instead of the true (but unknown) population distribution \mathcal{D}. Although the empirical measure converges to such true measure a.s. by the strong law of large numbers, it would be better to clarify this as the convergence rate of them needs to be estimated.

6) Line 610: $\Sigma$ is a random matrix, how does the choice of step-size can ensure $I – \eta \Sigma$ is PSD as $\eta$ is in a deterministic upper bound.

Minor issues:

1) some notations are relatively confusing, e.g., $\bf \Theta_1$, $\Theta_1$, and $\Theta$.

2) Line197: Lemma 5.2 requires the assumption $\lambda_1 = \Theta(1)$, please specify it.

3) line 540: $nr$ -> $nr^2$ follows $\chi^2(n)$ distribution. And why $r \geq 1/2$ is satisfied?

Typo:

Line 272: $\hat{\bf w}_t$ is missing in ${\bf \Theta}_1$

Line 675 and line 676 are repeated. 

limitations: yes
review_title: null

Meta-review: metareview: The reviewers have all found that the paper has many interesting ideas and its technical derivations are solid. There have been several questions/concerns which are mostly resolved after the rebuttal. As a result, the reviewers have all unanimously recommended accept.
confidence: Certain
Decision: Accept