Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

Thank you for reviewing our work and for your support of our work. Please see below our responses to the points you raised.

“the improvement is mainly in the realizable setting with the greedy stepsize. For the general setting, the improvement is somewhat minor, but it's still a strict improvement since the algorithm requires no knowledge of the variance at optimum.”

In the realizable setting, our improvement in fact holds for any stepsize asymptotically larger than $1/\sqrt{T}$ and not only for the greedy stepsize $\eta=1/\beta$. Beyond the realizable setting, our work provides for the first time the (nearly) optimal last-iterate convergence rate of $1/T+\sigma_\star/\sqrt{T}$ in the general convex and smooth case. This rate was previously known only in the special case of ordinary least squares (Varre et al [32]). We view this as a significant result. You are correct to note that none of these results require knowledge of the variance at optimum.

“I wonder if last-iterate convergence guarantees can be potentially obtained for the agnostic setting with the natural $\eta=1/\beta$ choice. If it's not theoretically impossible, what's the main technical difficulty?”

In the agnostic case (which is, to our understanding, the non-realizable case with $\sigma_\star >> 0$), the last-iterate sub-optimality of SGD $\eta=1/\beta$ does not diminish to zero. The best one can hope for is a rate of $O(1/T+\sigma_\star^2)$, and as we discuss in the paper, there is indeed still a gap between our guarantees and the best known lower-bounds in this setting.

From a technical perspective, the main difficulty in improving the bounds is that our current analysis technique is sensitive to multiplicative numerical constants along the analysis, as they carry over to constants in the exponents and therefore translate to polynomial differences in rates. We do not know if a new and innovative new technique is necessary for closing the gap.

Thank you for your thoughtful review—we hope that the below will successfully address all your concerns, in which case we hope you could acknowledge that by updating your score. If any concern still remains however, we will be glad to try and clarify further in the discussion.

“I agree with that deriving convergence results for the last iterate, rather than the averages, of SGD is interesting. Given that the connection between the last iterate and averages has been extensively explored in the literature, the contribution feels somewhat incremental to me.”

We actually believe the fact that a lot of effort has been put into last-iterate analyses over the past decade, while still leaving this fundamental gap open, only emphasizes the significance of our results. In addition, obtaining the new result required new technical innovations, as described in Section 3.1, beyond the techniques already explored in the literature.

“... Theorem 1 suggests that the step-size in case (ii) should outperform the choice in (i). Is this actually observed in practical applications or numerical simulations?”

The gap between cases (i) and (ii) is intriguing. From a theoretical perspective, it remains an open question whether this gap is real, as it is possible that case (i) already achieves the optimal $1/T$ rate. And in practice, even if the gap exists, observing it empirically would be challenging since the number of steps $T$ is usually fixed, making it difficult to distinguish between a $\Theta(1/\beta)$ stepsize and a $\Theta(1/(\beta\log{T}))$ stepsize.

“While the paper focuses on the convex setting---a reasonable starting point for theoretical analysis---this is somewhat limiting given the prevalence and importance of nonconvex optimization in modern machine learning applications.”

The fundamental convex case is the focus of the extensive literature on last-iterate guarantees of SGD, and we have yet to reach a full understanding of convergence and rates even in this case. And indeed, the progress we made in the convex case already required nontrivial technical innovations that will likely be crucial for further advances.

As an aside, it is a folklore fact that meaningful last-iterate guarantees are generally not possible in the non-convex smooth setting, even without noise. (There are simple examples of smooth problems where the norm of the gradient actually increases with time, rather than decreases.)

“As the authors acknowledge, when $\eta=\frac{1}{\beta}$, the convergence rate is $1/\sqrt{T}$ in the interpolating regime, which falls short of the optimal $1/T$ rate achievable with averaged SGD. Moreover, what is the theoretical motivation for considering this particular step-size setting?”

As we explain in the paragraph starting at line 40 and elaborate in Section 5, the choice $\eta=\frac{1}{\beta}$ is crucial in several applications of SGD related to continual learning and the Kaczmarz method, which were actually our main motivation for studying this problem. See Sections 5.2 and 5.3 for more details on these applications.

“Is there any connections between the Zamani and Glineur technique with [1, Theorem 2]?”

Theorem 2 in [1] is based on the Shamir & Zhang analysis technique that, as we discuss in Section 3.1, was used in previous work that was only able to achieve a weaker $1/T^{1/4}$ rate for $\eta=1/\beta$, compared to the $1/\sqrt{T}$ we establish here.

The Zamani and Glineur technique can be seen as an intricate adaptation of Shamir & Zhang, that instead of using the standard SGD potential analysis with relation to previous iterates of the algorithm, it uses such an analysis with respect to certain convex combinations of previous iterates.

“How can the result from Srebro et al. (2010), which uses an approximation error rather than $\sigma_\star$, be refined to obtain the error bound presented in Table 1.”

In Appendix I we provided the refined analysis you seem to allude to, which provides the error bound presented in Table 1. In addition, this analysis applies to a wider range of stepsizes (including $\eta=\frac{1}{\beta}$) compared to the original analysis of Srebro et al. (2010).

Thank you for reviewing our work and providing us with your strong support. It is highly appreciated and encouraging. Please see below our responses to the points you raised.

“Can you explain what exactly is the low-noise regime? The introduction (line 62) says that $\sigma_\star \ll 1$, but the statement of Theorem 2 only requires that $\sigma_\star < \infty$. … Bounded variance (or bounded variance at optimum) is a common assumption in optimization, but is this condition often referred to as low-noise?”

You are correct to note that our results only require an assumption of bounded variance at the optimum, leading to a rate of $\widetilde{O}(1/T + \sigma_\star / \sqrt{T})$ for an optimally tuned stepsize. The term “low-noise” in this context (originally coined by Srebro et al (2010), to our knowledge) refers to cases where $\sigma_\star = o(1)$ (in terms of $T$), in which case a convergence rate strictly better than $1/\sqrt{T}$ rate is possible. Thanks for this comment - we will try to make this terminology clearer in the final version.

“Liu and Zhou [22] have results for both in-expectation and high-probability. Do you think your techniques can be easily extended to allow for high-probability guarantees, assuming say sub-gaussian noise as they do?”

This is a very interesting question we have yet to thoroughly explore. While the results of Liu and Zhou [22] suggest that high-probability last-iterates bounds of this form are achievable, the interplay between the concentration and the weaker noise assumption (bounded variance at the optimum instead of a global variance bound) seems to lead to several technical challenges that we do not yet know how to circumvent.