Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper investigates the excess risk bounds of constant-stepsize SGD last iterate in the setting of noise-less least squares (i.e., only considering the bias error). The presented bounds could be applied to overparameterized cases, but are also limited to attainable cases. The presented bounds for the last iterate nearly match the established ones for the averaged iterates. 
main_review: # Pros:
+ The presented bounds for the last iterates of SGD are the first results that can be applied in the overparameterized setting.
+ Some of the presented bounds are (nearly) tight and (partly) solve an open question for the rate of SGD last iterate.
+ Lemma 5 is interesting in its own for bounding the SGD (bias) iterates.
+ Overall the paper is organized well, but the writing could be improved here and there.

# Cons:
- The considered least square problems are noiseless, i.e., the variance error bound is not considered. In fact I am thinking that using a large and constant stepsize and without averaging, the variance term cannot be decreased. In this sense the presented results and techniques are somehow less satisfactory.
- The presented bound, e.g., Thm1, requires the true parameter to have a finite $\ell_2$-norm (attainable case), which is limited and could potentially be relaxed to an even more interesting version like $(\theta^*)^\top H \theta^* < \infty$. 
- The writing could be improved in several places. See below.

# Small issues:
* The paper/section/paragraph title capitalization style should be made consistent. 
* l.7. two folds.
* l.25. This sentence is quite confusing. Note that a noisy model could also interpolate. See e.g., [bartlett et al 2020].
* l.37. To be more clear: "... a decreasing sequence in terms of loss"
* l.47. an infinite..
* l.48. This is also confusing, as strongly convex cases are covered by the presented results. Better to write, e.g., "the problem we are considering is not restricted to strongly convex or finite-dim cases".
* l.49. the following two.
* l.55. Everything is known for noisy setting (which covers noiseless setting)? Perhaps you mean the finite-dim setting?
* l.68. This is too confusing... Lots of papers listed in paragraph l.76 explicitly or implicitly discussed how to control SGD last iterate. I agree this paper has some new results for SGD last iterate but the claim here is too exaggerative!
* related works section is quite messy. Perhaps the authors could discuss papers for offline/multi-pass SGD and online/one-pass SGD separately? These two are quite different in terms of generalization bounds. Also, there are big paper overlaps in the three paragraphs & could find better ways to organize.
* l.144. an arbitrarily...
* l.149. Not only in large dim case, but in any case. 
* l.168. a 4th...
* l.173. at least some results in [10] only assume eq (4) instead of something stronger.
* l.203. $C_{ln}$ is not defined. I guess it refers to left hand side of the above inequality?
* l.227. an eigenvalue...
* l.321. remove the empty space before ?

# Overall
Based on my knowledge on papers for SGD last iterate, I think the presented results have their spirits and could be a good reading for controlling SGD last iterate. I would love to see further discussions/results to relax the finite $\ell_2$-norm (of the true parameter) condition, as the $\ell_2$-norm easily blows up in infinite-dim cases. Discussions on how to control the variance error could also be useful. As for the writing, there are plenty places need to revised though. My current evaluation for this paper is neutral and slightly lean to weak acceptance.



[bartlett et al 2020] Bartlett, Peter L., et al. "Benign overfitting in linear regression." Proceedings of the National Academy of Sciences 117.48 (2020): 30063-30070.
limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the least-squares problem in the interpolation regime, solved by the last iterate of the Stochastic Gradient Descent. It characterizes the performance of SGD under 3 sets of assumptions and shows the explicit impact of the conditions on the convergence rate.
main_review: I am not very well familiar with the literature on the infinite-dimensional least-squares problem. My background is mainly in the field of convex optimization, so I will make the comments mainly from this perspective.
Firstly, the assumptions seem strange and hardly interpretable, and I think that the paper can benefit from drawing connections to general convex stochastic optimization. At least it would be helpful for non-experts in this area because, for now, it seems targeted at a very narrow audience.

Could you please tell me what is the purpose of Assumption 2, if the noiseless problem statement includes the existence of $\theta_* \in \mathcal{H}$ such that $\<\theta_*, x> = y$.

How can you use the $H^{-1}$ in Assumption 3 and further, if on page 3 (line 131) it is said that *“$H$ is no longer invertible”*?

The paper is clearly written, and the “related work” section seems complete. Though, excessive details ultimately make it harder to get the broad picture, distinguish the paper's contributions, and compare it to the previous results (especially in terms of technical novelty).

To be honest, I do not quite get the point of considering the infinite-dimensional case, and the motivation presented by the authors does not seem convincing to me. That is why it is hard to see if the results are valuable for the machine learning community.

From the practical viewpoint, the paper seems quite irrelevant, as I can not see any helpful insights for practitioners. The synthetic experiments are very basic, although this is clearly not the main focus of the work.
limitations_and_societal_impact: Not applicable due to theoretical character of the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of minimizing a non-strongly convex Least-Squares using stochastic gradient descent (SGD). The authors show that when the interpolation assumption holds, then under mild assumptions, the last iterate of SGD converge to the optimal solution with rate $\mathcal{O}(\frac{\log(T)}{T})$. And under stronger assumptions, the convergence rate can be improved to $\mathcal{O}(\frac{1}{T})$. 
main_review: I found the manuscript to be clearly written and technically sound.  However, there are still a few points need further clarification:
1. One important setting in this paper is that the covariance operator $H = \mathbb{E}[X \times X]$ is not positive definite, namely the least square is not strongly convex. However, in Assumption 1, it assumes that $H \succeq \frac{\mathbb{E}[\|X\|^2 XX^T]}{R}$. Does it mean that the covariance operator is actually positive definite? Same question for Assumption 3. 
2. In the discussion after Assumption 4, you have the condition $\lambda_{\min} > 0$. I think this is also equivalent to assuming the problem is strongly convex.

Based on the discussion above, I think although there is some novelty in the problem setting and the corresponding theoretical result. The contribution may not be enough provided there are already some result about the convergence of last iterate from the SGD on strongly convex functions. 

limitations_and_societal_impact: There is no negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper explores the last iterate convergence of SGD on the least squares problem in the interpolation regime (noiseless setting). The authors work in an abstract Hilbert space and thus consider (1) the non-strongly convex setting and (2) the streaming or online setting. There are three contributions of the paper:

(1). The final iterate of constant step-size SGD achieves a convergence rate of $O(ln(T)/T)$ under the assumption that the data matrix $X$ has (in expectation) bounded fourth moments. 

(2). Under more assumption about the behavior of the eigenvalues of the covariance matrix of the data, that is $\lambda_i \le O(1/i \log(i))$, the authors can improve the last iterate convergence rate to $O(1/T)$. This matches the rate for the averaged iterates of SGD.

(3). Under stronger assumptions of the eigenvalues of the covariance matrix at the optimum (source) and capacity condition, one can get an even faster rate of convergence. 
main_review: The paper is well written and the details of the exact assumptions are clearly stated and there are enough details to follow the main ideas of the results. Although I did not check the proofs in detail, I am confident that they are correct. One concern about this paper is that it is fully devoted to trying to remove a log factor, which I understand is of interest theoretically, but of practical interest one may not even see. It is not entirely clear that one could even remove the log factor in the general setting. Can one show in simulated data that the $1/T$ is achieved?

I would also suggest that the authors elucidate on the $\alpha$ and $\beta$. While I understand that these assumptions have been used in previous works, it is not clear what are "natural choices" for these parameters. For instance in the case of $X$ having i.i.d. Gaussian entries of mean $0,1$ and $\theta^*$ pure noise, I believe one could compute the values of $\alpha$ and $\beta$. Could the authors comment on this? 

There is also some recent work on last iterate convergence in the multi-pass setting (see Paquette, et al. "SGD in the Large") and could the authors comment on comparisons with this work (to match the streaming setting $r = \infty$)?




limitations_and_societal_impact: The limitations of the results are clearly stated. This result only applies to the least-squares problem and in the streaming setting. The results are purely theoretically.
review_title: null

Meta-review: This paper proves the risk bound of the last iterate for constant step size SGD in the interpolation regime. The main concern from the reviewers is that the linear regression model is assumed to be noiseless, which makes the results less interesting. After the author response and reviewer discussion, the paper gathers enough support from the reviewers. Thus, I recommend acceptance. 
Decision: Accept (Poster)