Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization

Thank you for the thorough review and input. Below are our responses to the main comments in your review:

“The theoretical result is some kind of inconsistent with practitioner's observation as multi-pass SGD usually doesn't really hurt the generalization. Better to add a limitation section to address this issue.”

Thanks for this comment. We will add a discussion addressing this limitation. Needless to say, lower bounds depict the worst case and not “typical” cases, which are arguably those encountered in practice. In fact, even in theory, if we add further assumptions such as strong convexity, then multiple passes will no longer hurt performance. We will add this comparison to practical observations, as well as related theoretical setups, in the final version.

”Merely looking at Theorem 3.1, setting $\eta = T^{ -3/4 }$ yields population risk converges to 0. Why can't we do this?”

You are correct: the lower bound is matched by Bassily’s stability upper bound (up to an additive term of $\eta T/n$). So setting $\eta = T^{-3/4}$ will achieve $T^{-1/4} = 1/ ({nK})^{1/4}$ when $n$ is the sample size and $K$ is the number of epochs. Noticeably, in order to achieve the optimal $1/\sqrt{n}$ rate one would need as many as $K = n$ epochs (i.e., $T=n^2$ total number of steps). We will discuss these observations in the final version.

Thank you for the thorough review and feedback. We respond to main claims below:

“a key part of the argument rests on Livni's 2024 connection between 'sample dependent oracles' and a standard SCO oracle. This connection is hardly explained at all”

We thank you for the comment - we will improve this discussion for the final version. Notice that we do discuss it briefly in the main text (see left column line 290) and that we did add a section about the reduction done in Lemma D.1. But, we will add further intuition in the main text to make the result more accessible.

“In the same vein, the proof of Lemma 5.1 is very terse and difficult to follow in full detail. It appears that an effort was made to cram it into the page limit.” I would argue for making it easier to follow, even if it requires punting some/all of it to the appendix.”

We will follow the reviewer’s advice and we will make it easier to follow, by deferring it to the appendix if needed.

”How much of this hinges on using a fixed stepsize? For instance, the h_2 portion of the argument in the Theorem 3.1 sketch seems like it could be complicated even by using variable stepsizes [...] The argument also seems to hinge similarly on initialization at zero [...] Do you see a path towards a similar lower bound for variable stepsizes or e.g. random initialization?”

These are great questions, indeed certain variants of SGD pose a challenge to our proof technique, and it is important to add a discussion to the paper on that. For some variants of SGD such as dynamic learning rate, our technique can be utilized, perhaps with a slight increase in the dimension (when using $h_1$ and not $h_2$, see right column line 251).

As for random initialization - you are correct that our construction relies on deterministic initialization. Showing lower bounds for random initialization is an interesting open problem, and in fact not just in the context of multi-pass SGD but also for full batch GD, for example.

Thank you for the detailed review and discussion. We respond to the main claims below:

It is evident that the excess risk lower bound in Theorem 3.1 and Theorem 3.2 share an identical form with those in [Amir et al., 2021] and [Bassily et al., 2020]. Furthermore, as also acknowledged by the authors, the technique used to construct these lower bounds are direct extension of the technique used in [Amir et al., 2021]. [...] the conclusions in this paper are not entirely surprising and unexpected.”

We see that a more thorough and in-depth comparison of our work to these two references is warranted, and we will make this improvement in the paper. However, the lower bounds in 3.1 and 3.2 do not share an identical form with Amir et al. nor with Bassily et al, and the technique used to construct the lower bounds are not direct extensions of Amir et al.

Regarding Bassily et al:

As you point out, Bassily et al shows a lower bound on stability and not for the generalization gap. One could argue that bad generalization in the face of instability is not surprising. But then at the same time SGD (single pass) counters this statement: it is provably a non-stable algorithm that achieves optimal generalization performance.

We also note that Bassily et al’s lower bound for stability applies to all epochs of SGD, whereas SGD learns at the first epoch and overfits from the second epoch (as we show). It is unclear how one could derive an intuition for such a behavior from the results of Bassily et al.

Overall our proof indeed relies on generating instability (which is a necessary condition for overfitting), but is more involved and incorporates further techniques and constructions such as the usage of Feldman’s function, as well as the notion of sample-dependent oracle which we modify and strengthen to fit our setup.

Regarding Amir et al:

One major challenge we faced, given Amir et al’s work, is that we aimed for constructions in dimension linear in the sample-size. This differs greatly from Amir et al that exhibited an exponential dependence of the dimension on the sample size, and did pose several challenges: for example, we require working with Feldman’s function which is a more subtle construction than previous existing ones in high (exponential) dimension.

Some of these challenges have been tackled before in the context of GD (as opposed to multi-pass SGD), and we incorporate some of these ideas. But our results deal with SGD which, unlike GD that was discussed in previous papers [Amir et. al., 2020, Livni, 2024], does generalize in its first epoch. In particular, it provably circumvents previous hardness constructions in its first epoch, and begins its second epoch from an optimal state in terms of generalization performance.

Given this, we actually think it is a surprising result that SGD’s generalization rapidly deteriorates and has the same asymptotic bounds as its stability so quickly after the first pass (but not during the first pass).

Thank you for the thorough review and discussion. Following are our responses to your main comments:

“lacks empirical validation or real-world experiments to demonstrate the practical impact”

Our main contributions are theoretical and, respectfully, we disagree that this is a weakness. Theoretical results, and specifically in Stochastic Convex Optimization, are well within the traditional scope of ICML and have significant impact on the broader study of machine learning.

While theoretical results do not always offer immediate practical guidance, their goal is to improve understanding of SGD and they provide insight into the behavior of generalization in a simple setup (SCO). Such an understanding is a prerequisite for understanding more involved scenarios, such as those encountered in practical settings.

“Construction-based proofs - relies on specific constructed examples rather than showing results for general cases”

Indeed, our main results are lower bounds --- and lower bounds are inherently construction based proofs. While lower bounds are demonstrated via specific constructions, they aid with providing a complete picture of the guarantees for the examined algorithms: whether we can find better algorithms, or that the algorithms we have at hand are already optimal.

“Dimensionality assumptions - some results require high-dimensional settings that may not reflect practical scenarios”

The vast majority of our results hold already in dimension linear in sample size (and this is tight). Notably, the setting where the dimension is at least the sample size is currently the most interesting regime to study, in light of practical findings where overparameterized networks are shown to achieve superior performance. (In fact, in Theorem 4.1 for example, the main novelty is in reducing the dimension from quadratic in the sample size $n$, as in prior work, to linear in $n$.)

The only exception to this is the case of Theorem 3.1 for $K=2$ epochs, which applies only in dimension exponential in $n$. However, for $K>2$ our proof construction is in dimension linear in $n$.

“Limited practical guidance - doesn't provide clear recommendations for practitioners on how to avoid the identified overfitting issues”

Indeed, we do not propose practical methods to avoid overfitting. Rather, we believe our contributions do give guidance to further theoretical studies, by indicating that in the general case (under the standard assumptions) multi-pass SGD quickly overfits, and additional assumptions will be needed in order to justify its empirical success.

In particular, prior work indeed showed that overfitting can be circumvented by either avoiding overtraining (the classical online-to-batch argument) or through stabilizing the algorithm by decreasing the learning rate (c.f. stability arguments of Bassiley et al). This touches on an important aspect of our work, that shows that, in general, these two solutions are indeed exhaustive: overtraining without stability leads to overfitting.

“given the structure of many of the proofs they discuss it seems a bit surprising that discussions surrounding online convex optimization and adversaries were not discussed in more detail.”

This is a very good point. In a way, our work demonstrates that the classic online-to-batch proof technique is a tight approach for establishing generalization of SGD (Theorem 3.1 shows that once the gradients are biased, like in epochs beyond the first, then generalization deteriorates; and Theorem 4.1 shows that stability/uniform convergence cannot be established in general). From a technical perspective however, we indeed do not invoke the online/regret analysis which is an established technique to achieve algorithmic upper bounds.

We will add this discussion in the final version, thank you for this comment!

“Might want to consider some restructuring, not having a conclusion to tie things together seems a bit odd”

The thing we had in mind is to have the discussion section appear at the end of the introduction (Section 1.2), and before the rest of the paper that delves into the technical proofs and formal statements. But, we will reconsider restructuring for the final version.

“Could your analysis extend to other variants of SGD (e.g., with momentum, adaptive methods)?”

That is a very interesting question. Our results using the same techniques can be extended to SGD with varying stepsizes, perhaps with a slight increase in the dimension. As for other variants of SGD, it is currently unclear to us, and indeed an interesting question. We will add a discussion on further pursuing this avenue to the final version.

“What about non-convex settings?”

Since most of the paper discusses lower bounds, the convex case subsumes the non-convex case, as the lower bounds are harder to achieve under the restriction of convexity (that is, any lower bound for the convex setting is also a lower bound for the non-convex setting).