Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the problem of understanding implicit regularization of SGD for the problem of linear regression. The authors compare the excess risk guarantees of SGD solution to the one obtained by solving ridge regression exactly. The main contribution is to identify some conditions on the data distribution and the optimal solution under which: 

- The SGD solution (with log(n) more samples) is at least as good as the one obtained by ridge regression. 
- There exists a problem setting where the excess risk of the ridge regression solution is quadratically worse than the SGD solution. 

The above separation result between SGD and ridge regression is obtained by explicitly computing **instance dependent** upper and lower bounds on their respective excess risk guarantees, and by comparing them under various assumptions on the data distributions. The presented results are shown for the setting when the feature vectors are one-hot or Gaussian. 

main_review: I am a bit unsatisfied with the results and do not support acceptance. My reasons are: 
(1. ) Nature of the results: 
For now, let us restrict to the Gaussian case (Main section of the paper, Section 5). The authors show that there are some conditions (call them A) such that for any learning problem that satisfies A: 
        -SGD is almost as good as Ridge regression. 
        -There exists a problem setting that satisfies A for which ridge regression is quadratically worse than SGD. 

As a result, the authors conclude that SGD has a better implicit regularization than ridge regression. However, this jump is wrong !!! 

The results presented in the paper do not rule out the following: There exists some other conditions B (different from A) on the data distribution such that for any learning problem that satisfies B: 
        -Ridge regression is almost as good as SGD 
        -There exists a problem that satisfies B (but not A) for which SGD is quadratically worse than ridge regression. 

B could be as natural / realistic as A, and the results in Theorem 5.1 shows that this may be possible. Thus, there could be some other conditions where the solutions obtained by ridge regression are better (or as good as) that of SGD. 

In order to claim that SGD is better than ridge regression, one needs to show that (a) SGD works as well as ridge regression whenever ridge regression works, (b) there exists some problem when ridge regression is strictly worse than SGD. 

Note: the experiments shown in Figure 1 in the appendix support the above claim and show that there exist settings where ridge regression requires much less samples than SGD (see the blue line). This shows that the conditions B above may also be easy to characterize. 

(2.)  Step size for SGD: 
The step size required for SGD to match the performance of ridge regression (as in Corollary 5.1 and Theorem 4.1) depends on the data distribution. It is not clear how to estimate it from data. Thus, it is not clear how to run SGD algorithm in practice to match the rates of ridge regression; limiting the scope of this result. 

The choice of step size should not depend on the data distribution. If one has access to the distribution, we can simply run the following trivial algorithm: Given a distribution D, choose the starting point w_0 as the optimal solution for the test loss w.r.t. D. Set the step size to be 0 and run SGD. Here, the final output will be the optimal solution and always better than ridge regression. 

(3.) What about other regularizers? One can have regularizers (potentially data dependent) such that the RERM solution with this regularizer generalizes as well as SGD. I think the classical results which compare SGD solutions with ridge regression solutions are for the worst case distributions only. 

(4.) While the paper is technically rich, many of the instance dependent upper / lower bounds presented in the paper were known in earlier papers (or at least their proof techniques) (e.g. [29], [6]). Thus, the new technical contributions are limited. 

Minor issues / typos: 
       - Line 118 has a typo in H_{k: \infty} in the aligned equation. 
       - Line 209 has a typi in the definition of a. What is N? 
       - The illustrative example from lines 222-228 is circular and uses k(N_{ridge}) in the definition. 

Rest of the paper is well written! 
limitations_and_societal_impact: No
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper compares the excess risk of averaged SGD with that of ridge regression. The comparison is in the setting where the expected noise is zero and also the excess risks of the optimally tuned algorithms are smaller than the optimal population risk. The overall conclusion is that the performance of SGD is close to ridge regression in every problem in the class of interest and can even be better than ridge regression based on the eigenspectrum of the input and the signal-to-noise ratio.
main_review: I'm voting to accept the submission as these results can be a step towards understanding optimization and generalization of overparameterized models with SGD. The reliance of the results on signal-to-noise ratio also matches the previous observation that the behavior of SGD can be vastly different on real data versus random labels [28]. The main weakness is that, although the paper mentions that SGD requires at most logarithmically more samples, the constants in the bound can be huge.

In the instance-wise comparison (Theorem 5.1), the difference between SGD and ridge regression depends on the inverse of the smallest eigenvalue of the input. If the data is not well-conditioned, this factor can easily dominate the bound. The paper then correctly mentions that the constant cannot be removed, but still, with a large multiplicative factor, given the current bound, SGD can vastly underperform ridge regression. Do the authors have any empirical evidence that the smallest eigenvalue is large enough in common datasets?

The paper motivates its results as a study of implicit regularization and generalization of SGD, yet as l215 clarifies, there is an interplay of optimization and generalization at work, and the convergence rate and generalization ability together determine the risk. I suggest that the authors mention the role of convergence rate in the introduction and in other parts of the paper, for example in l256 that describes when SGD "generalizes better" than ridge regression. 

Minor comments:

The Gaussian assumption and Assumption 5.1 are made for simplicity yet it is not clear to me how relaxing these assumptions would change the results and if extra factors would be introduced.

What is lambda in Theorem 5.1. Does the result hold for any lambda?
limitations_and_societal_impact: Limitations are addressed. Societal Impact is not applicable.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Prior work showed that SGD has implicit regularization. This paper comperes the generalization performance of the implicit regularization (namely SGD without regularization) versus $ \ell_2 $ regularization (i.e. ridge regression), which is a popular explicit regularization technique. The generalization performance is measured in excess risk. Using bounds on the excess risk, the authors show that SGD without regularization generalize at least as ridge regression, if not better.
main_review: The article is well written and well organized.
Here are my comments:

1.	The comparison made in the paper between single pass SGD and ridge regression is not impartial. Specifically, single pass SGD sees each sample only once and does not minimize the empirical risk. In contrast, for ridge regression, the authors considered the unique minimizer of the regularized risk. This equivalent to multi pass SGD with explicit regularization. In other words, for unregularized objective they use single pass SGD, and for regularized objective they use multi pass SGD. Why?
2.	The implicit regularization of multi pass SGD for overparametrized linear regression is well understood. In this case, the obtained solution minimizes the Euclidean distance from initialization (this also cited by the authors). Considering my first remark, I think that the article could have been more convincing if they show advantages of implicit regularization over explicit in the simple (and well understood) case of multi pass SGD.
3.	It is quite popular in statistical learning to use bounds that hold for some absolute coefficient. However, I am not sure to what extent these bounds meaningful.

I note that due to time limitations, I have not checked the proofs.

limitations_and_societal_impact: See above
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper shows that for a class of least-squares problems, unregularized SGD generalizes no worse than ridge estimate given additional logarithmically more samples. On the other hand, for certain data sets, ridge estimate (positive regularization) may require quadratically more samples than SGD to achieve the same generalization performance. 
main_review: Overall it is an interesting paper. The main contribution is to show the advantage of unregularized SGD. On the other hand, I have some concerns about how important the contribution is and whether the comparisons are fair.
1) While the logarithm factor does not sound large, it often changes the problem from an over-parameterized regime to an under-parameterized regime.  For example in corollary 1, while the ridge problem is over-parameterized with d=O(n), the SGD problem is very under-parameterized with $d/n\rightarrow 0$. It feels a bit weird to compare two methods within two different regimes. 
2) The error bounds are compared with the constant factor being omitted. So I would not claim SGD outperforms ridge based on Theorem 5.2 or Theorem 5.3 because the constant factor could be less than 1 until I read the proof. I think the authors should make it more clear why the risk of ridge estimate is worse than SGD. In addition, the term $||w^*||_H$ with subscript $k:\infty$ seem to be missed in both risk calculation in the proof of Theorem 5.2. If this term is constant (which is very likely), then this term is the dominant term of the risk.
3) Overall, it seems like comparing ridge with SGD is to compare risk at $d/n\rightarrow \gamma$ at different $\gamma$. I am not entirely convinced that SGD generalizes no worse or better than ridge is because of SGD. The results are just giving another example that we need to tune the ratio $d/n$. Specifically, Theorem 5.1 looks like comparing risk with $\gamma=0$ with $\gamma>1$, and we know given the constant signal-to-noise ratio, the two risks are comparable within a constant factor.  For Theorem 5.2 and 5.3, we know when the sample covariance matrix is very spiky, the best risk is achieved at $\gamma=0$. Adding more samples can make $d/n\rightarrow 0$, or I would suggest doing a PCR and achieve $d/n\rightarrow 0$ by decreasing d.
4) The problem is specific to linear regression which limits the contribution. Further, as shown in [26], in some cases, the optimal ridge parameter is negative. To make the results more convincing, the authors should explore this direction as well.

Overall, I have concerns about the contribution of the paper.
  
limitations_and_societal_impact: It is a theoretical paper. I think the main limitation is that for some regression problems, the sample size is limited. It is easier to select the number of features and the authors have not covered this part.
review_title: null

Meta-review: The paper considers the problem of understanding if SGD can be seen as a solution to implicit regularized empirical risk minimizer for the problem of  linear regression. The authors compare the excess risk guarantees of SGD solution to the one obtained by solving ridge regression exactly. The authors show that SGD solution is always almost as good as the one obtained by ridge regression. But on the other hand, there exists a problem setting where the excess risk of the ridge regression is substantially worse than the SGD solution. This shows that SGD cannot be seen as implicitly regularized ridge regression.

This paper generated a large number of discussions between the reviewers and also between reviewers and authors. While for some points there isnt total agreements, given the reviews and the discussion, it seems clear to me that the paper should be accepted first because despite some of the mentioned possible shortcomings the paper still is interesting and second, the subtler discussion points are exactly why we need to accept the paper so these issues are more widely discussed.
Decision: Accept (Poster)