Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
Authors: Shira Vansover-Hager
Tomer Koren
Roi Livni
Venue: ICML 2025 spotlightposter (2025)
Keywords: Stochastic convex optimization
SGD
multi-pass SGD
generalization
risk bounds
Primary area: theory->learning_theory
TL;DR: We derive tight population loss bounds for multi-pass SGD in stochastic convex optimization, demonstrating that overfitting can occur rapidly, even after just a few epochs.

Abstract: We study the out-of-sample performance of multi-pass stochastic gradient descent (SGD) in the fundamental stochastic convex optimization (SCO) model. While one-pass SGD is known to achieve an optimal $\Theta(1/\sqrt{n})$ excess population loss given a sample of size $n$, much less is understood about the multi-pass version of the algorithm which is widely used in practice. Somewhat surprisingly, we show that in the general non-smooth case of SCO, just a few epochs of SGD can already hurt its out-of-sample performance significantly and lead to overfitting. In particular, using a step size $\eta = \Theta(1/\sqrt{n})$, which gives the optimal rate after one pass, can lead to population loss as large as $\Omega(1)$ after just one additional pass. More generally, we show that the population loss from the second pass onward is of the order $\Theta(1/(\eta T) + \eta \sqrt{T})$, where $T$ is the total number of steps. These results reveal a certain phase-transition in the out-of-sample behavior of SGD after the first epoch, as well as a sharp separation between the rates of overfitting in the smooth and non-smooth cases of SCO. Additionally, we extend our results to with-replacement SGD, proving that the same asymptotic bounds hold after $O(n \log n)$ steps. Finally, we also prove a lower bound of $\Omega(\eta \sqrt{n})$ on the generalization gap of one-pass SGD in dimension $d = {\widetilde O}(n)$, improving on recent results of Koren et al. (2022) and Schliserman et al. (2024).

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
Shira Vansover-Hager'
Tomer Koren 12 Roi Livni
Abstract
analysis of SGD has traditionally focused on its behavior in the one-pass (single-epoch) setting, partieularly in the context of convex optimization, where it is well understood that SGD achieves an optimal excess population loss of or- der @(1/ when trained on a sample of size n. This rate is known to be minimax optimal under standard assump- tions (Nemirovskił & Yudin, 1983).
We study the out-of-sample performance of multi- pass stochastic gradient descent (SGD) in the fun- damental stochastic convex optimization (SCO) model. While one-pass SGD is known to achieve an optimal @(1 / Vn) excess population loss given sample of size n, much less is understood about the multi-pass pasts version of the algorithm which is widely used in practice. Somewhat surprisingly. we show that in the general non-smooth case of SCO, a few epochs of SGD can already hurt its out-of-sample performance significantly and lead to overfitting. In particular, using a step size n O(1/vn), which gives the optimal rate after one pass, can lead to population loss as large as 211) after just one additional pass. More gener- ally, we show that the population loss from the sec- ond pass onward is of the order O(1 VI)T), where 7' is the total number of steps. These re- sults reveal certain phase-transition in the out- of-sample behavior of SGD after the first epoch. as well as a sharp separation between the rates of overfitting in the smooth and non-smooth cases of SCO. Additionally, we extend our results to with- replacement SGD, proving that the same asymp- totic bounds hold after (n log n) steps. Finally, we also prove a lower bound of ((TVR) on the generalization gap of one-pass SGD in dimension d = (n), improving on recent results of Koren et al. (2022) and Schliserman et al. (2024).
However, in practice, common to run multiple passes over the training data, scheme often referred as multi- pass SGD, where, in each pass, training examples are sam- pled without-replacemmnt, with or without reshuffling be- tween passes. Despite its empirical success, the theoretical implications of performing multiple passes are far less un- derstood, particularly with respect to generalization and our- of-sample performance. The standard intuition, based on empirical observations, suggests that more training should lead to better empirical performance, yet, more steps and passes might eventually lead to overfitting as the model becomes too closely tailored to the training data being pro- cessed repeatedly.
Indeed, a substantial body of work has studied the conver- gence of multi-pass SGD in finite-sum problems (e.g.. Recht & Re, 2012;
Hardt et al., 2016; Nagaraj et al., 2019; Rajput et al., 2020; Safran & Shamir, 2020; 2021; Koren al., 2022; Cha et al., 2023). However, these studies primarily fo- cus on optimization convergence in terms of empirical risk and how is influenced by vithout-replacenet as opposed to with rethhrreplcemmet which is significantly easier to analyze theoretically. Far less attention has been given to convergence in terms of population risk, which quantifies out-of out-of-sample performance and is arguably the true goal in the context of machine learning.
sampling,
1. Introduction
In fact, to the best of our knowledge, the following basic question still remains, rather surprisingly, unanswered:
Stochastic gradient descent (SGD) is one of the most fun- damental algorithms in machine learning and optimization, widely used for training large-scale models. Theoretical
How does the population risk performance of SGD, tuned to attain the minimax optimal rate after a single pass, deteriorate (if at all) after making just a few additional passes?
Blavatnik School of Computer Science, Tel Aviv Univer- sity 'Goole Research ASchool of Electrical and Computer Engineering, Tel Aviv University. Correspondence to: Shira Vansover- <shiravde @ www.maaa.aaa.c.a.ommmmaa tal. Roi Livni 'rlivni@tauce aau.ac.ll.
Tomer Koren <tko-
While there are several existing upper bounds on the pop- ulation risk in the multi-pass scenario (e.g., Hardt et al., 2016; Bassily et al., 2020), none of them give a meaningful, nontrivial answer to this question in the general stochas-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
tie convex setting in which the (nl/vn) minimax rate of Nemirovskit & Yudin (1983) applies.
1.2. Discussion and Open Questions
It is insightful contrast our lower bounds for multi-pass SGD with existing lower bounds for gradient methods in SCO. Most prior work on population risk lower bounds has focused on algorithms that approximately minimize the em- pirical risk, such as full-batch gradient descent (Amir et al., 2021; Schliserman et al., 2024; Livni, 2024). A key observa- tion in these works is that after just a single step of gradient descent, the entire training set has been "touched" and so can be effectively memorized in the optimization iterate. Once this occurs, subsequent gradient steps can be steered toward an overfitting solution with respect to the particular training set at hand. Our results in the present paper reveal a similar memorization effect for multi-pass SGD: after a single full pass, SGD is also capable of effectively memorizing the training set and driving the optimization towards overfitting. However, crucial (and quite remarkable) difference is that this effect cannot be manifested before completing the first pass, as doing so would contradict the classical Nemirovskif & Yudin (1983) stochastic approximation upper bounds.
Our investigation in this work reveals rather surprising answer to this basic question: we show that even in the fundamental, well-studied convex setting, multiple passes of SGD can lead to rapid overfitting and reach a trivially-large population loss after just one additional pass. In particular, using the canonical stepsize of 17- @(1/vn) that leads to the minimax rate after single pass, results in population excess risk as high as 12(1) after merely two passes. More generally, we establish tight population excess risk bounds for multi- pass SGD using any stepsize and number of steps T. Our results cover authout-rellceement single-shuffle and multi-shuffle, multi-pass SGD as well as with-rep SGD, demonstrating similar rapid overfitting in all cases. An illustration of the population risk bounds we obtain across different epochs and stepsizes can be seen in Figure 1.
1.1. Our Contributions
In some more detail, examine the out-of-sample behavior of multi-pass SGD in the fundamental setting of Stochastic Convex Optimization (SCO). In this setting, we operate with a convex and Lipschitz (yet not necessarily smooth) loss function over a bounded convex domain.
Our result regarding the empirical risk of one-pass SGD complement earlier work by Koren et al. (2022); Schlis- erman et al. (2024) and challenges the classic learning paradigm of minimizing empirical risk and generalization gap in relation to SGD. It reveals that the generalization gap is inadequate in explaining the minimax optimal generaliza- tion behavior of one-pass SGD, which constitute one of the fundamental comnrstones of convex optimization. Together with our lower bounds for multi-pass SGD, this result high- lights a sharp phase transition between the first and later epochs: generalization bounds, such as those implied by algorithmic stability (Bousquet & Elisseeff, 2002; Hardt et al., 2016; Bassily et al., 2020), are ineffective during the first pass but become tight after the second pass, whereas the optimal performance in the first pass is only explained by online-to-baad batch (aka stochastic approximation) arguments which collapse immediately after the first pass.
In this setting, we make the following contributions:
We establish a tight bound of (11(TTT) + ITVT) on the population excess risk of multi pass (without replacement)) SGD with stepsize 17 over T steps (see Theorems 3.1 and 3.3 in Section 3). This result applies to both the single-shuffle and multi-shuffth variants, but also more generally to any multi-pass multi-pass scheme that processes exam- ples according to an arbitrary sequence of permutations.
We also prove a similar tight (11/ population excess risk bound for with-replacement SGD, that holds after On log n) steps (see Theorems 3.2 and 3.4).
Finally, we also provide a new (2(1v7) lower bound on the empirical risk (and therefore also the generalization gap) of single-pass SGD. Our result holds in dimension (n) thus improving upon previous results by Koren et al. (2022); Schliserman et al. (2024) that were established in dimension at least quadratic in n.
Open questions. Our findings raise several intriguing open questions for further investigation:
First, our construction leverages techniques for lower bounding the generalization gap in SCO in order to con- trol the population risk of multi-pass SGD. However, in principle, the population risk performance of multi-pass SGD should be unrelated to its generalization gap (c.g.. as in the case of one-pass SGD). In particular, it is an interesting question whether our results could be repro- duced in settings where uniform convergence holds (e.g.. low-norm linear predictors with Lipschitz. loss), and the generalization gap is necessarily small.
We note that all of our lower bound constructions apply in an overparameterized regime, where the dimension scales linearly in the sample size n. Our approach builds on recent techniques developed for analyzing the sample complexity of (approximate) empirical risk minimization in stochastic convex optimization (Feldman, 2016; Amir et al., 2021; Koren et al., 2022; Schliserman et al., 2024; Livni, 2024). In particular, we leverage methods from Livni (2024), who refined these constructions to achieve minimal dimension dependence of (n).
Another interesting problem is to precisely characterize the rate which overfitting develops during the second
2

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
tions. Some works specifically study the differences in optimization convergence rates between with-replacement and without--eplacement sampling (e.g., Recht & Re, 2012; Yun et al., 2021; Lai & Lim, 2020; De Sa, 2020; Safran & Shamir, 2021). Other works examine the population per- formance of multi-pass SGD. For example, Sekhari et al. (2021) focused on establishing upper bounds for a variant of multi-pass SGD that uses validation set, and in a slightly non-standard formulation of SCO that allows for non-convex individual functions. In contrast, our main focus is on lower bounds for standard multi-pass pass SGD in the classical SCO model -Shalev-Shward et al., 2010). Lei et al. (2021) derive upper bounds using decreasing step sizes, without assum- ing Lipschitz continuity but requiring gradient norms to be bounded linearly by function values. In contrast, we estab- lish tight bounds for fixed stepsize SGD under the standard Lipschitz assumption. Other upper bounds on population loss for the closely related with-replacement SGD can be found in Hardt et al. (2016); Lei & Ying (2020).
n= 1 n= 7= 0 n -675 g=0-1
Population
Number of kpochs
Figure 1. An illustration of the minmax rates for the population loss of multi-pass SGD established in Theorems 3.1 and 3.3, through K 5 epochs and for different stepsizes r.
pass. Indeed, our results are only effective starting from the end of the second epoch and onward. As we discussed earlier, generalization bounds remain vacuous at the start of the second pass, and regret analysis fails due its reliance on independent samples at each iteration. Thus, it appears that more refined techniques will be required to analyze SGD dynamics immediately after the first pass.
Lower bounds for SGD. In terms of lower bounds, Zhang et al. (2023) and Nikolakakis al. (2023) analyzed SGD with replacement and multi-pass SGD,, respectively, but both focused specifically on the unconstrained (smooth) case and allowed for unbounded function values, which in general, render the problem unlcarnable, as discussed before. We, on the other hand, focus exclusively on bounded domains and functions values bounded by a constant, where the classical Nemirovskii & Yudin (1983) results apply. More recently, Koren et al. (2022) established lower bounds for the gener- alization gap of me-pass SGD. They demonstrate that even though SGD achieves optimal population loss rates after a single pass, its empirical risk can be as high as Q(7vT) after T steps. Their construction was dimension exponential in the sample size, which was later improved to quadratic by Schliserman et al. (2024). Here, we further improve the dimensionality dependence to linear, which, as argued by Feldman (2016); Livni (2024), is optimal.
Finally, our work focuses on the general SCO setting, which allows for non-smooth convex loss functions. Es- tablishing population risk bound for multi-pass projected SGD in the analogous smooth setting remains an inter- esting open question that is likely to require significantly different techniques than those used in the non-smooth case. We remark that for unconstrained optimization, it is known that variants of smooth GD and SGD can overfit, even in dimension one (Nikolakakis et al., 2023; Zhang et al., 2023). However, these results rely on unbounded losses over unbounded domains, where learnability itself is not guaranteed.' In contrast, our focus is on constrained optimization-a regime where learning is possible yet ERM- -RMM- methods can fail-and the open question per- tains to this case as well.
Stochastic Convex Optimization (SCO). Our work be- longs to the study of sample complexity of learning algo- rithms in the fundamental SCO model. Previous research has shown that in SCO some algorithms overfit when the sample size depends on the dimension (Shalev-Shward, et al., 2010; Feldman, 2016), while others like online-to- batch algorithms achieve dimension independent rates (Ne- mirovskii & Yudin, 1983). This makes SCO a valuable model for testing the generalization and sample complexity of learning algorithms. Amir et al. (2021) were the first to establish dimension dependent lower bound for the sample complexity of gradient descent (GD), they showed a pop- ulation loss lower bound of Q(πv7) after T steps using a step size 17 in a construction with dimension exponential in the sample size n. Later, Schliserman et al. (2024) extended
1.3. Additional Related Work
Convergence bounds for multi-pass SGD. Numerous studies have explored multi-pass SGD from optimiza- tion perspective (e.g., Rajput et al., 2020; Safran & Shamir, 2020; Cha et al., 2023). Notably, focusing on empirical performance in finite-sum problems, Nagaraj et al. (2019) derived upper bounds for smooth functions, and Koren et al. (2022) extended these results to non-smooth func-
Indeed, with an unbounded range of function values, even evaluating the loss of single model, let alone learning, becomes intractable. (E.g., without additional assumptions, standard con- centration bounds scale linearly with the range of the random variables.)
3

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
this result to functions with dimensions proportional to the square of the sample size, and Livni (2024) further reduced it to linear size. This shows that to prevent GD from over- fitting, a sample of size (2d) must be considered. While we build on ideas from these works, our focus is on SGD- rather than GD-which does generalize in its first epoch. Specifically, multi-pass SGD circumvents previous hard- ness constructions during its first pass and begins the second epoch with optimal generalization performance. This behav- ior requires careful adaptation of existing constructions to account for the rapid deterioration of generalization after the first epoch.
and we denote by w e arg win (w( its minimizer.
One-pass Stochastic Gradient Descent (SGD). One- Pass SGD receives training set S = (z)...., Znh, step size > O, a suffix averaging parameter T [n + 1] and a first-order oracle (z(w) E (((,,)) and proceeds as:
Initialize:
Wo 0
For I 1,
Wy+1 lw [wr- [w:-n00, 20 (w;)]
Wn.t 1
Σ
Output:
Wr.
[=n-T+1
Algorithmic stability. Our work is also related the study of stability of learning algorithms as means to es- tablish generalization bounds "Shale-Shwarrde et al., 2010; Bousquet& & Elisseeff, 2002). The crucial advantage of sta- bility in the multi-epoch (without replacement) setting is the fact it does not require individual examples to be sampled ii assumption that only holds during the first pass. Notably, Hardt et al. (2016) show bounds on uniform sta- bility of multi-pass SGD for smooth functions and Bassily et al. (2020) show tight stability bounds for non-smooth functions. Their results demonstrate that in the non-smooth case, an additional ( VT) term must be added, that make such bounds vacuous (at least for the purpose of establishing risk bounds) unless the stepsize is extremely small as func- tion of T. Importantly, these bounds apply uniformly across epochs and do not explain why SGD) generalizes well in its first pass and overfitting starts only from the second pass. This suggests gap between instability and generalization behavior, which calls for a more refined analysis that goes beyond plain stability arguments.
where Nw R - W denotes the projections onto W. Note that we consider general r-suffix averaging as an output.
Multi-pass SGD. In contrast to single-pass SGD, multi- pass SGD does several passes on permutations of the same training set. It receives training set S = (zI.....,Zn]
number of epochs K. step size 1) 0, K permutations {Æ& [n] - [<]], a suffix averaging parameter r e [nK + I] and a first-order oracle (z(w) E 0f(w, z), and proceeds as follows:
Initialize:
W =
For / = 1, nk:
i, [u/n (1 mod n)
We+1 [w [w, n10 (w:)]
T
Output:
WI.r [=T-r+1
WD
where T= = nk is the total number of steps. We note two important special cases: the single-shuffle and multi-shuffle. In the single-shuffle case, π is chosen uniformly at random, and πΙ = T& for all k E [K]; in the multi-shuffle case, the teK are chosen uniformly and independently.
2. Problem Setup
Stochastic Convex Optimization (SCO). We study out- sa-sam performance of multi-pass SGD in the context of the fundamental stochastic convex optimization (SCO) framework. A learning problem in SCO is defined by con- vex and G-Lipschitz loss function f : W x Z - R, where is a sample space endowed with a population distribu- tion Z, and W is a convex, compact domain with diameter bounded by D. A learning algorithm receives training set S = (Zi,..., 3 of n i..dd samples from Z and outputs model w E W, with the goal of minimizing the population loss:
With-replacement SGD. With replacement SGD receives training set S = {z Zn), a number of steps T, step size 17 > 0, suffix averaging parameter T E [n + 1] and a first-order oracle (w(w) E @f(w,,)) z). It then proceeds as follows:
Initialize:
Wo =
For 1, I....T:: i, Unif([n])
Wr+1 = Iw 1 (we)
F(w) = E
" Wn.r Σ
Let w* arg min F(w) denote a minimizer of the ob- jective. The empirical loss on the sample S is given by:
Output:
Wr.
[=n
Note that this is not a multi-pass algorithm per-se, as the stochastic gradients used are independent regardless of the total number of steps T.
(w( = 1 Σ f(w, zi),
4

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
3. Population Risk Bounds
Following Livni (2024), we rely on loss function with the following structure:
We present a lower bound and a matching upper bound for the population loss of multi-pass SGD for K n epochs.
f(w. V) = (ww, V) + ahh(w,,
3.1. Lower Bound for Multi-Pass SGD
where g(w, V) is a variant of Feldman's function (Feldman, 2016) that has the property that it has spurious empirical risk minimizers. Namely, using this function and a specific distribution, we can guarantee the high-probability exis- tence of "bad" vector, which for this bound will have high population loss. The second term, h(w), is used to guide the iterates toward this bad vector, enabling us to achieve the lower bound. The constant a prevents projections from disrupting this process.
We begin with stating the lower bound, which constitutes our main contribution:
Theorem 3.1. For every n 2 24,2 K s T d= 256n, 7, > 0 and r [T+ let W {w RR,d+1 ||w||2 x I then there are a finite sample space Z, distribution Z over Z, 4- 4-Lisschitz convex function f(w, z) in 222+1 such
that for any first order oracle of f(w,z) z) with probability 1 if we run without replacement SGD for T steps with stepsize
o and with any sequence of permutations:
Feldman's 's function and existence of a spurious empirical minimizer. Feldman's function, g, relies on the existence of set U c Rd with |U] 2 2 such that for every u # ve E U, we have
1 = s2 min (TTT+ 7 (1
We note that this result applies to single, multi shuffle and more generally for any sequence of permutations. In partic- ular, for 1 = @(1 that yields minimax optimal result for one-pass, can lead up to ((1) population loss after just one additional pass.
(u, v) c1 < c2 11v11.
We consider the following function:
gi(w, V) = max (cI, V- w).
veV
We provide here proof sketch, the full proof is presented in Section 5.
The existence of such U follows from a standard packing argument. Next, we let Z = P(U). the powerset of U, and treat examples in Z subsets of U. Let Z be distribution over Z such that for V Z every E U in V with probability 6.
Proof sketch. To obtain the lower bound, we rely on the, recently introduced, notion of a sample-dependent oracle introduced by Livni (2024), and the reduction from sample- dependent oracles to the standard setting of stochastic con- vex optimization. Livni (2024) observed that if the gradi- ents of an algorithm such as Gradient Descent (GD) are dependent on the whole sample, then one can utilize that to construct stochastic functions for which Gradient Descent overfits. It also turns out that one can reduce the standard setup of stochastic optimization to this weaker setting of a sample dependent oracle, for GD. These observations al- lowed the construction of distributions that cause GD to overfit at certain regimes.
Notice that if w E V. then (w V) 2 C2. and otherwise, 81 (w, V) = C1- Let = (Vi..... Vn). For this bound we will define bad vector as an ERM with high population loss. Notice that any vector no & U/= V, is an ERM since -
-1-11- - C1 O. If, furher, uo U, then its population loss is given by F(uo) 2 6(c² c1). By setting 8 = 1. we can show then that any such uo is bad ERM. By further setting d = Q(n), we can show that with high probability such a mo E U exists.
SGD, though, differ from GD that observes the whole sam- ple at the first iteration. In particular, it is impossible for the trajectory of SGD to depend on future seen examples. In turn, the reduction becomes more subtle. We note that this is not just an artifact of the proof technique, but is demon- strated by the fact that, indeed, SGD does minimize the population loss at the first epoch, and SGD circumvent the hard construction of Livni (2024). Nevertheless, we build similar approach, and we use weaker sample dependent first order oracle, that cannot depend on the whole sample but may depend on past observations. As it turns out, such an oracle is enough to construct lower bounds, and also allows a reduction for the case of SGD.
Reaching spurious empirical risk minimizer. Feldman's function demonstrated that there exists a "bad vector" in the sense that there are minimizers of the empirical risk that yield large population loss. However, there is no guarantee that if we run SGD on Feldman's function we will reach such a minimzer (in fact, notice that SGD applied on g will remain at zero). Therefore, our strategy is to add a further term h that will cause SGD to converge towards un- For simplicity of the overview we assume here that no E (0, 1)d.
For T = Od),, we use the following function as h:
h1 (w) max (0.-w())): ic[d]
5

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
Assume we ran SGD for n iterations. Notice that 0 e ah (0), therefore, in setup we are allowed to return a O subgradient for iterations. After iterations, we start using h after identifying a specific bad vector No. Here, we exploit the fact that our oracle is sample dependent, and we use h to take one step on each of the positive coordinates of un to reach nju in at most d steps.
probability 1 if we run with-replacement SGD for T steps with stepsize ny
+( - F(w*)) s2 min foVT+ n 1)
Proof sketch. Noticing that the key idea in the construction of Theorem 3.1 is to memorize the entire training set and then step in a "bad direction" uninterrupted, we can also ap- ply the same approach here. In the case of with-replacement sampling, from folklore analysis of the coupon collector's problem we know that with probability 1 we have seen the entire training set after Or logn) steps, and from that point we can proceed similarly.
When T> > d. h won't suffice since after d such steps, we can't further increase the desired loss. To achieve the d term, we use the following function instead:
(w)) = max (0. -w(1), -(w(1) w(i+ 1))}
iE[d]
With the following oracle:
3.3. Matching Upper Bounds
1. If there is an index i such that w(1) = w(i 1) n, then output: ej+1 ei.
Finally, we give matching upper bounds to the two lower bounds presented above. Both bounds are straightforward consequences of standard techniques in convex optimization and algorithmic stability analysis; we only state the bounds here and defer proofs to Appendix
2. If there is no such index and if i is the minimal index such that w(1) = O, output: -ej-
3. If neither of the above conditions holds, output: O.
Theorem 3.3. Let f be a convex, non-smooth, and G- Lipschitz function, and let S be a dataset of n samples. If we run multi-pass pass SGD (either multi-shuffte or single-shuffle) with step size n > 0 ffr K 2 1 epochs, for total of nK steps. Then, for any suffix average iterate = (2(T,, we have the following guarantee:
By applying these gradient steps only for the positive indices of ug. this will allow us to achieve Q(TVT) when T d².
For the case when d < T < d,, we will use h2, but instead of considering one index at a time, we consider blocks of indices of size B 2 1 to achieve the same effect.
E [[F(Wr.)) = (IVT+++++
nT nT
Putting it together. To compute and reach the bad vector we use the oracle's sample dependence and the fact that 00, v) for all V, allowing us to stay at O. During the first epoch, we remain at observe the examples. At the start of the second epoch we have memorized the entire training set S. we compute no & UT_ Vi and take gradient steps to reach it using h.
We will note that while the upper bound holds for the multi- shuffle and single-shuffle cases, our lower bound holds for every set of K permutations. A similar result can be derived for with-replacement SGD:
Theorem 3.4. Let f be a convex, non-smooth, and G- Lipschitz functiinn and let S be dataset of samples. If we run with-replacement SGI) with step size > 0 for K 2 1 epochs, for total of = nK steps. Then, for any suffix average iterate I = Q(T), we have the following guarantee:
Reduction. The construction we described assumes a sample-dependent oracle. The key idea behind the reduction to this case encoding information about past examples into the iterates. This allows the gradient to use knowledge of previous examples by examining only the current iterate and sample.
E - - (000)))000000 O
nT TTT n
3.2. Lower Bound for With-Replaccmment SGD
4. Empirical Risk Bounds
Using the same technique, we also prove a lower bound for with-replacement SGD. The proof is given in Section 5 and here we give short sketch of the proof.
We further prove lower bound of 2( (T) for the empirical risk (equivalently, the generalization gap) of one-pass SGD using a construction in dimension d = (n),, improving on results from Koren et al. (2022); Schliserman et al. (2024).
Theorem 3.2. For every 2 24, < K nn, T= Kn log d = 256n, 77 > 0 and T E [T+ 1], let W = (w E 22d+1 [|w]| N 1} then there are a finite sample space Z, a distri- bution Z over Z, a 4- Lippchhtt convex function fw, 2) in 22d+1 such that for any first order oracle of f(w,2) 2) with
Theorem 4.1. For every n 2 17, = 712n log n, 1) > O,
and T E [n + 1] let W = {w E 2dd-1 : [|w|| s 1) then
there are a datapoint set Z. and a distribution Z over Z,
6

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
4-Lisschitz convex function f(w, 2) in R2d+1 such that for any first order oracle of f(w,2) 2) with probability & ie run one-pass SGD with ll as a learning rate for n steps then:
when S1.0 = 0, S (S1, ................................ (SI......,,)) and O (S 1: w)
0 f (w, The trajectory induced by Os which is initialized at wo 0 is specified by the following equation:
Fw( - Fs(w3) = 22 (min (nvv,
Wx+1 = Wt 15
We will state the following general Lemma for an upper bound of Q(TVV) and later show how it proves Theo- rems 3.1 and 3.2.
The proof is deferred to Appendix C. This result strengthens the previous results that one-pass SGD cannot be fully ex- plained by the classical learning framework of minimizing empirical loss and generalization gap. Specifieally, while SGD ensures low population loss with 17 ((1 it can still cause generalization gap of up to Q11). Moreover, the construction is done in nearly linear dimension (up to a logarithmic factor), which is the lower bound for the di- mension for such results, as uniform convergence must not hold.
Lemma 5.1. For every n, Tepock 2 24, K 2 2, and step size n > O, define T = Tepocti and d = 256n and let W = {w E R ||wll S 13. There exist a finite dataset Z, a distribution Z over Z. a 3-Lipschitz convex function (w. in R24, as well as sample-dependent first-order oracle Os such that for every training set S Z" drawn ii.d and every sequence of samples S (S1,...,Sr) where S, C S. for all 1 E [T], if with probability p it holds that U S; = S, then with probability at least 3p, for every suffix averaging T:
Proof sketch. We use the same kind of construction as we did for the other proofs. Dinstinctively, though, to achieve high empirical risk, "bad vector" is a vector that appears frequently in the training set, but infrequent on the pop- ulation. To guarantee the existence of such a vector we change the distribution Z so that uo E V with probability 5 = 011n²))
F(WT.))- = 2 min n min fn². T3. 11)
mim
This Lemma shows that once an algorithm memorizes the entire training set we can quickly lead it to overfit.
A similar argument (but reversed) as before demonstrates that there has to be a "bad vector" that is frequent at the first //16 16n of the examples, observed by the algorithm, but does not appear at the tail of the training set.
Proof. We will prove here the Lemma for the case K 2 34. For 2 s K s 34 the proof is deferred to Appendix B. First we notice that there exists d s d' < 2d such that d' = 2 for some m N. Our construction will be over Rd which of course implies that such a construction can be done in Rdd using only subspace of dimension d'. From the proof of Lemma 8 in Livni (2024) there exists U {0, 1)d such that:
The appearance at a constant fraction of the training set ensures high empirical risk. On the other hand, absence from the tail allows uninterrupted advancement there in a similar technique as before. Our strategy then is similar to before, to compute the bad vector ug. we also stay at 0, this time for n/ 16 steps. Then if 2//6 V, # 0. we select the minimal vector uo from this set and take gradient steps to reach it using h.
5 _ d' and ||u]]2 = _ d', 16
7
Vu#veU,u.
16
and
O
|U| d d2/258
d/258
> 2d/256 = =
5. Proofs of Theorems 3.1 and 3.2
We will let Z P(U) and define distribution Z over Z such that for random sample V Z, each u E U lies in V with probability $. Let a = min 1 1.. First we will assume T d and we will consider the case where T d at the end. Let B E N be such that:
We first prove the results using weaker notion of a sample- dependent oracle and later relax this dependence. Formally, a cumple-dependers oracle is gradient oracle that, at each step, has access to both the current and all previous samples. We denote it as Os. where S = (S....., Sy) is the ordered sequence of sample sets. At iteration 1, the algorithm re- ceives S, which may be set of samples rather than a single sample. This general setting captures broad class of algo- rithms, including variants of SGD, as well as GD and batch methods. The oracle is defined as:
1/3
T
d' s B
< 2d'
34
One can show that without loss of generality we can assume B is also power of 2, in particular d' is divisible by B for a large enough T. This will imply two useful facts:
Os OS(
1
Σ Oz(S w;),
d'3
T
d
T
T
1
|S, ZES,
<
=
Tepoch
_T
T,
(1)
B
34
B
34
34
17
7

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
since T 2 34 Tepoch and
Lemma 5.2. Os as stated above is a valid sample depen- dent first order oracle of f as defined in Equation (3). Fur- thermore if & holds it will induce trajectory such that never leave the unit ball and no projection takes place.
272d' T S
B3
which we will use later. We consider blocks of indices so we will present the following notation: for two sets of indices J c [d'] denote 1 < J if max(i 1) min(j J} and denote:
We will now assume that & holds. Since |U] 2 2" from Lemma E.2 and from the definition of Tepoch
Pr[E] -r 1=1 S, S] Pr[3uo e U : $ UvEsV]
1 VI 1e7
Σ
1
Σ w(f)
e1
e; and w(1)
2 -PP
VITI iET
Next we will assume that & holds. Then after at most Id'
We will define the functions:
T' Tepoch
Σ E
steps we will have that for
h(w) = max (0.
max (-w(1),
every E 4, (i) = an VB I' 2 T', Wy wr which implies
ld
+ 11-1 11). and for every
1c|d',111
168
1<J (-((()) - -w(())
max
3dt
7d
45nad
Wy 40 WT 40 = VBn
--1
g(w, V)
max Vd veV 2 162 B1.5 W
1=1
16B
Finally our loss function will be:
V Bna
f(w, V) = g(w, V) ah(w).
(3)
v BBj
7d'
Notice that f is convex and 3-Lipschitz. Next we define sample dependent oracle Os. Given w and all examples seen far S (S),.............. S.):
16B
49dl
VBna
2. *(16B)2
1. If 1S11l I Tepoch output 0.
Since 7" S Tepuch
dr B²
s 1 (see Equation (1)), for every
2. Otherwise check in lexicographic order if there exists "o E U such that u0 & (U Uves, V).
suffix averaging T:
there doesn't exist such un or u0 E (U', (argaat Uves, V) output an arbitrary sub- gradient.
WT.r uo 2 WT up N VBna
16
46d
17
2. (16B)2*
Also because we assumed = 272 and with probability at least 2 u0 will appear in a fresh sample:
8¹ (see Equation (2)),
Otherwise will compute the Id' indices of uo that hold un = 1 denote them J = To a set exists since || 7d' and uo {0, 1)dd We 16
/16/16). Such
will divide the indices in J to blocks of size B, for 3d
1
46 Bard
45 45
(WT,+)-F(0)
1,.
2
2. (168)²
2. 2(168)2
ToB
Im = (J(m-1)- B+1 .........Im..... Jm.B..
on
(,5 1.5
4. 162
B
We have three scenarios:
(a) If there is a block I such that w(1)) w > 0 then output: a a(éI,. - e,,)
1
min (in 1}.
4. v2. V272 162
(b) If there is no such block and if I is the minimal block such that w(1)) = output: -0ee,-
This concludes the proof for the case T S d²3 when d' if we take the construction with T = d then after T steps our oracle will keep giving O, hence construction for any T' > T. So for T > d we have with probability 1p:
(c) If both of the conditions stated above do not hold output: O.
can use the above
We will denote the following event:
1
& = { U S, = S and 3uo E U un & U t=1
Tepoch Uvas, V..
F(Wr.)) - -FF() 4v2 V272 162
min(n7V 1}
(4)
1
We will prove Os is a valid oracle in the following lemma whose proof is deferred to Appendix B.I.
min (1/v (256n)3 1).
4v2. V272 162
8

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
Overall in both cases with probability pp:
References
Amir, I., Koren, T., and Livni, R. SGD Generalizes Better than GD (and Regularization Doesn't Help). In Confer- ence on Learning Theory, pp. 63-92. PMLR, 2021.
F(WT,=)- - F(0) 22 I min
We will now show how the lemma gives the desired results.
Bassily, R.,, Feldman, V., Guzmán, C., and Talwar, K. Stabil- ity of Stochastic Gradient Descent on Nonsmooth Convex Losses, Advances in Neural Information Processing Sys- tems, 33:4381 1-391,,,1,,,,, 2020.
Proof of Theorem 3.1. The (r7((r7)) + 1)) term is given in Lemma E.1. For the (1)VT) term we will use Lemma 5.1. Let S [[zi)...... )) be the ordered sequence of sam- ples given to multi-pass SGD during a run of T steps with training set S of nt samples. After the first epoch we are sure to have observed the entire training set, so for Tepoch n and from Lemma 5.1 we get the result using a sample- dependent oracle. We can relax this dependence using the reduction in Lemma D.2 and conclude the proof.
Bousquet, O. and Elisseeff, A. Stability and Generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Cha, J., Lee, J., and Yun, C. Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond. In International Conference on Machine Learning, pp. 3855- 3912. PMLR, 2023.
t
De Sa, C. M. Random Reshuffingg is Not Always Better. Advances in Neural Information Processing Systems, 33: 5957-5967, 2020.
Proof of Theorem 3.2. The (17( + 1)) term is given in Lemma E.1. For the (T) term we will use Lemma 5.1. Let S [...,, (2+ be the ordered sequence of sam- ples given to with-replacement SGD during a run of T steps with training set S with samples. From folklore analysis of the coupon collector's 's problem it is known that with prob- ability& & after at most n log n iterations we have memorized the entire training set, so for Tepoch n log and p 1/2 from Lemma 5.1 we get the result using a sample-dependent or- acle. We can relax this dependence using the reduction in Lemma D.2 and conclude the proof.
Feldman, V. Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back. Advances in Neural Information Processing Systems, 29, 2016.
Hardt, M., Recht, B., and Singer, Y. Train Faster, Generalize Better: Stability of Stochastic Gradient Descent. In Inter- national conference on machine learning, pp. 1234-1234. PMLR, 2016
D
Koren, T., Livni, R., Mansour, Y., and Sherman, U. Benign Underfitting of Stochastic Gradient Descent. Advances in Neural Information Processing Systems, 35:1 9605- 19617, 2022.
Acknowledgments
This project has received funding from the European Re- search Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreements OPTGEN-10107807 and FoG-1011162550
Lai, Z. and Lim, L.-H. Recht-ré noncommutative arithmetic- geometric mean conjecture is false. In International Con- ference on Machine Learning, pp. 5608-5617. PMI.R, 2020.
Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. This work received additional support from the Is- rael Science Foundation (ISF; grants numbers 3174/23 and 2188/20), and a grant from the Tel Aviv University Center for AI and Data Science (TAD) and grant from the Israeli Council of Higher Education.
Lei, Y. and Ying. Y. Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent, In International Conference on Machine Learning, pp. 5809 5819. PMLR, 2020.
Lei, Y., Hu, T., and Tang, K. Generalization Performance of Multi-Past Stochastic Gradient Descent with Convex Loss Functions. Journal of Machine Learning Research, 22(25): 2021.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Livni, R. The Sample Complexity of Gradient Descent in Stochastic Convex Optimization, 2024. URL https: / w/arxiv.ogg/abs////.. 2444bb//1.44.4.141.... 04931.
9

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
Nagaraj. D., Jain, P., and Netrapalli, P. SGD Without Re- placement: Sharper Rates for Ggeneral Smooth Con- vex Functions, In International Conference Machine Learning, Pp. 4703-4711 PMLR, 2019.
Nemirovskit, A. and Yudin, D. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
Nikolakakis, K. E., Karbasi, A., and Kalogerias, D. Select without Fear: Almost All Mini-Batch Schedules Gener- alize Optimally, 2023. URL https: httpt://aaaaee http:://axxvvvoooeeeoo abs/2300 02247.
Rajput, S., Gupta, A., and Papailiopoulos, D. Closing the Convergence Gap of SGD Without Replacement. International Conference on Machine Learning, pp. 7964- 7973. PMLR, 2020.
Recht, B. and Re, C. Beneath the valley of the noncommu- tative arithmetic-geometric mean inequality: conjectures, case-studies. Technical report, Technical report, and con- sequences. Technical report, University of .... 2012.
Safran, I. and Shamir, O. How Good SGD with Ran- dom Shuffling? Abernethy, and Agarwal, S. (eds.), Proceedings of Thirty Third Conference on Learning The- ory, volume 125 of Proceedings of Machine Learning Research, pp. 3250-3284 PMLR, 09-12 Jul 2020.
Safran, I. and Shamir, O. Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems. Advances in Neural Information Processing Systems, 34: 15151-15161, 2021.
Schliserman, M., Sherman, U., and Koren, T. The Dimen- sion Strikes Back with Gradients: Generalization of Gra- dient Methods in Stochastic Convex Optimization, 2024. URL htt.tttss///axii...t./ org/ abs/ 240..22088
Sekhari, A., Sridharan, K., and Kale, S. SGD: The Role of Implicit Regularization, Batch-Size and Multiple-Fpochs. Advances In Neural Information Processing Systems, 34: 27422-27433, 2021.
Shwlev-Shwartz, S., Shamir, O., Srebro, N., and Sridharan, K. Learnability, Stability and Uniform Convergence, The Journal of Machine Learning Research, 11:2635-2670, 2010.
Yun, C., Sra, S., and Jadbabaie, A. Can Single-Shuffle SGD Better Than Reshuffling SGD and GD? arXiv preprint arXiv:2103.0777 070797 2021.
Zhang, P., Teng. J., and Zhang, J. Lower Generalization Bounds for GD and SGD in Smooth Stochastic Con- vex Optimization, 2023. URL htt.t:://///// /ttp://axxxvvo/o///// abs/2303.10755
10

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
A. Proofs of Upper Bounds
To establish the upper bounds, we will use stability arguments, and state the following definition for uniform stability:
Definition A.1. A randomized algorithm A is e-uniformly stable if for all data sets S. E Z" such that S and S differ in at most one example, we have:
sup E (f(A(S)) - f(A(S), sc.
We will denote by Esab the infimum over such We recall the important Lemma stating that uniform stability implies generalization in expectation:
Lemma A.2 (Lemma 7 in Bousquet & Elisseeff (2002)). Let A be algorithm that is uniformly stable, then:
(FAA()))()) Fs(A(S)) s..
In particular using our notation:
[ES [F(A(S)) Fs(A(S)] s Estab-
Our upper bounds will be established using the following standard inequality:
50
[F(W) [[=*]] = [[(F(W)
[s(() - Fs(w5)) +E (Fs(w)) Fs(w*)] + +E [Fs(w*) F(w*)]
[F
Fs(W3)]
Using Lemma A.2 yeilds:
E [[((W) - F(w*)] S Estab E (Fs((w)) Fs(w5))
(5)
We will now continue prove the upper bounds.
Proof of Theorem 3.3. We will prove the theorem for the average of the iterates. The proof for any suffix average r 2(T) can be derived using similar arguments. To bound the stability we will use the following Lemma which was originally given for multi-pass SGD with single-shuffle but can easily be extended the multi shuffle case using similar arguments.
Lemma A.3 (Theorem 3.4 in Bassily al. (2020)). Let f W - R be convex funnciiittt Then the uniform stability of multi-pas SGD with multi- multi-shuffling single-shuffling is bounded as:
Enah $ 2G 4G n
To bound the optimization error will use the following:
Lemma A.4 (Theorem 6 in Koren al., 2022). Let W Z - R be convex and G-Lipschitz, function. And let S= (zi...., mn} be some training set. Consider running K 2 epochs of without replacement SGD over f and S. Then, have the following guarantee for w nk E7+1 Wy.
For the multi-shuffle case:
D² E (w) - Fs(w3)) s 2 vn+
2nnK ?
For the single-shuffee case:
E [s()) Fs(W3) 882nVvk 8G2nk 1D2
2mn + n/2
2

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
So for both cases
D2
G
E [ - Fs(w3)) & 8G²IVVK S
21ynK +
2
Using Equation (5):
F[((W) F(w*)] s Faah +E [Fi(wW) - Fs((3))
s 20 (nNnk + 2nk) + 80² n 80' + 112
2mnK + nG²
D²
10 12G j0²n.
2nKn
So have:
=0 + +n !77
E F(w*) =0
nKn
177
11
this concludes the proof.
Proof of Thheorem 3.4. We will prove the theorem for the average of the iterates. The proof for any suffix average r = -2(7) can be derived using similar arguments. To bound the stability we will use the following Lemma
Lemma A.5 (Theorem 3.3 in Bassily al. (2020)). Let f: W - R be convex f--apscchitzfunntiion Then the uniform stability of SGD with-replacement is bounded as:
Eaaa S 4C + 4G
To bound the optimization error we will use the following classical result from Nemirovskit Yudin (1983)-
Lemma A.6. Assume we run SGD with stepsize 17 on a convex function F' =EzIs' z)1, for some distribution Z. assume further that f' G Lipschitz and [[wo w D. Let w denote the average of the T iterates of the algorithm. Then we have:
D2
Fw) Fww
G2n 2
2nT
Applying Lemma A.6 on the empirical loss = Fs with Z being the uniform distribution over we have:
D² G2n.
E ( Fs(w3)
2nKn 2
Using Equation (5) and putting everything together:
E E(F(W) F(w*)] s Estab + [Ws( Fs((3)]
D
G2 + 4G² (n + nk
2n
D
1
+ 2G 222 (Vvnk+
s
2nK
So we have:
E [[(()-((wt)) =0 0 nKn
+ 1n + + =
+ VVV 1T
(n 1/
this concludes the proof.
12

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
B. Proof of Lemma 5.1
We will prove now the Lemma for S á 34. The proof for the K 2 34 case is given Section From the proof of Lemma 8 in Livni (2024) there exists {0. 13dd such that for every u # v U:
5d
7
(u, v) -
= ||v|
16
16
and,
|0| 2 d/258 2".
We will take the power set of U as the sample space: Z = P(U), identifying samples as subsets of U. Define a distribution
Z over Z such that for a random sample Z, each u E U lies V with probability 1 Let a min
denote
,yv
w (1) = w[1 d) and (22)) = w(dd + 1: 2d]. We will introduce the following notation for a block of indices c [d]:
Σ 1c7
e, and w(I)
w(i).
TE/
For B 3d consider the following functions:
Topach
g(w.V) V)
1
Sa 166VB
nd, w + (2)
7VB 1
5ma 1
(6)
Vd
5 max
{0, w (1) (1) 2
h(w) 7 scld)i/ss
max lcdd/://B
- (1))
(7)
Finally, our loss function will be:
f (w, V) = g(( w, V) ah(ww).
(8)
holds that f is convex and 3-Lipschitz. Next we define a sample dependent oracle Os. Given w, and all the examples seen so St., = (S,....,,,} S,):
1. If S S Tepoch output O.
2. Otherwise we can check if there exists un U such that un (U,Tr Uves, V). We will check this in lexicographic order.
(a) If there doesn't exist such no. or un E (U' +1 Uves, V), output an arbitrary sub-gradient.
(b) Otherwise we compute the following set:
1 - [d] un( = and
w7 (1)
Sna= W
(2)
(i) 0f
T B
if (J > 0 choose min (2,1) indices out of J denote them Z, If |Z,1 |,,11 let O, 0. Otherwise we will let
O, be most B elements of the following set:
4 21 ie [d] and u)( = and (1) (I)
(2) 5na
(1) < 170
w B
VB
Finally, output
2 5 [e(Z)) 20(0.))
We will denote the following event:
& = U Toue S, = S and 3uo E U : & (U Uves, v)}
(9)
We will prove Os a valid oracle and that under the event of & no projections take place in the following Lemma whose proof deferred to the end of the proof.
13

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
Lemma B.1. Os stated above is valid sample dependent first order oracle of f defined in Equation (8). Farthermore will induce trajectory such that if holds then never leave the unit ball and no projections take place.
Since [0] 2" from Lemma E.2 and the definition of Tepoch
Pr[E] Pr[U Tepach S, S] Pr[ Pr U 40 & (V Uves, V Eapach 1=1 S, S
Pr[U, Tepech S = S] 1.-r U ; 40 & UvESV 2 2
Next will assume that & holds. According to Os in every step we change least B indices unless output 0. So after
at most 7" Tepoch + [ steps we will have | = | O meaning that (1) WT + WT TB
(2) Sya i
Mo. Note that: VB
na
d
T" Tepoch +
B
Tepoch
S Tepoch
3
Tepoch
Tepoch
3
Tepoch
Tepoch
S Tepoch
Tepoch 2
3
24
TTeucch
From the way we defined Os for every 1' T': Wy wr. For every i [d] such that uo(i) 1:
T
(1) T.r
+
(2)
Sna BVB
(1) =
1
W + +w, (2) +
Sna-
i
(i)
7.r
T
[=T-T+1
Σ
W
(1)
+ (2) + 5nar
(1)
T 1=1
7
5
T''
(T TT)
TVB
7
1J0
5 3
1
11
VB
2
2
14VB
Which implies:
(1) (2) Wr, WT,
5na
7d
11pa
1nadd
7VB
16
14vB
32VB
From the definition of Z, with probability 1, uo will appear in random sample for every suffix averaging
F(WT,)) F(0) 2
(1))
WT.
(2)
TTr
Sma i 7
40
16 VB
San
Vd
Vl
Swn Vd
32VB
16 2vC
an
32 .B
Overall we have shown that with probability for every suffix averaging T:
on 2-32
d an)
Tepoch
52 min (1,/vT))
F(Wr,))- F(0)
V 2-32
3
since (Tepocth) the proof is complete.
14

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
B.1. Proofs for Auxiliary Lemmas
We will prove here Lemmas 5.2 and B.I that concern gradient oracles that were given in the proof's of Lemma 5.1.
Proof of Lemma B.I. First we note that for every E U
5per
7
5ma 5næd
T 16 d.
1
(10)
7VB
16vB
So 0 0 v) for every V P(U). For that reason we can stay at 0 for long as want. Note that it suffices show that if & holds the oracle is valid since for every other scenario output either 0 or arbitrary subgradient. If & holds we are clearly outputting subgradient of ah(ww) in Item 2b, so it is left to prove that for every V S we have that 0 E (w, v). Indeed.
If for all i e [d]: w (2)
Sna i TVB
(i) -
Sna TVB
then we saw in Equation (10) this holds.
If there exists i [d] such that: [w(") w/
Sqa 7VB
Sye this can happen only after have zeroed all the TVB
entries that no has zeros on. So we are left only with positive coordinates of uo and the proof is completed by noticing that since uo & UvesV, for every v E UveSV:
(1) w + w. (2)
5mp
na
5nard
v
uo
7
VB
16VB
This completes the proof that Os valid.
To see that projections don't 't't take place according to this oracle for every e [7] ga which implies:
and i [2d] have that: wi(
VB
2d
TTeoch
||,]11 S na
V
S na
na 1
B
3
since a min (1, | |
Proof of Lemma 5.2. For the first part of the oracle note that 0 (0, V) particular for Tepoch steps. For the second part of the oracle, if there doesn't 'ttstt exists such uo or uo (U/=rguettH Uves, V) left to show
stay at 0 for as long like, in
we output a valid sub- aab-gradient by definition. Otherwise, we are clearly taking gradient steps for ah(w). that in this case 0 Ög(w,, V). Indeed, this event ensures that up this point the oracle only output 0 or executes Items 2a to 2c, our only nonzero coordinates positive coordinates of uo. Also, for every (Uves, V), we have that # uo v 4o S 5d' which implies:
16
Se"
Se"
I6N
7d
7d
W7
w; (1)1 (v(i) =o(i)
Bmjar
Breer
16B 1)
168
i=1
1=0
5d'
7
5d'
2)
45d
v Bmjar
v VBna
16B
16B
2
16B
(16B)2
This concludes the proof that Os is well defined. To prove we never leave the unit ball if & as depicted in Equation (4) holds, notice that this is exactly the event where we either output 0 or execute one of Items 2a to 2c in the oracle. We will show by induction that for all / [T]:
[I ||w, - -/Os( (Sta, w,, v.) < a² 1).
15

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
For the base case ||woll = 2n Now assume it holds for and will prove for Consider the case where the first type of update is performed with w, (1)) w,(()+1):
|w l|w,
naer + +nae,, 11
(w,())))+( +w)(()))))))((((()))))))))))) na)
Σ s=
(wr (1))
Jdt
( - +21
(w, (w,)
s 2n 1 1/ a² =====1² af
And if the second type of update occurs:
||w llw, + naei,l
(w)(())) + af²
$41
22 17 22 $ 20
Since min (1,
1/v2T this shows that for all r [T]: ||w;|| a 2n (1, (1
2xp s
C. Proof of Theorem 4.1
From the reduction Lemma D.2 it suffices to prove the result for a sample-dependen oracle as defined in Appendix D. This is established in the following Lemma:
Lemma C.1. For every 2 17,4 d 712n logn and 1j > O, there are a finite datapoint set and distribution over 3-Lipschitz convex function (w, in 2d and sample-dependent gradient oracle Os such that with probability if one-pass SGD with 1i as a learning rate for steps then for every suffix averaging E [n 1]:
F F(Wn.)) F(0) = (min {rVVn, 1))-
1 11a va' val
Proof of Lemma C.I. Since d 2 256, from Lemma in Schliserman et al. (2024), there exists c |U| 2 2 2" and for all u e U: (u, r) s This implies that:
such that
9
Vu # v U 1(i E [d] u(f) v(0) N d. 16
(11)
Let Z P(U), and let Z be a distribution over such just for a new sample V Z every a E U will be in with probability 1. 4n2 Let a min(1, ). Let W {x 2d ||x|| < 1). Denote (()) w|1 d], w(2) wld 1 2d).
For subset of indices / c [d] denote the following:
e
1 7
Σ and w(1)
1
Σ w(i)
77
Tel
Tel
We will consider the following function with blocks of indices of size at most 8 log n:
f(w, V) max
9a
2v2 Vn, (wr()) + m21)) .v]
(12)
ver
16
+
max
f0. (1)
(1)}
max 1/8lonn
(2) (D)
/cd:
16

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
It holds that convex and 3-Lipschitz. Now assume have an order over the vectors in U which is lexicographic. Denote by u(r) the r-th vector in such order. We will be interested in the following event:
n # :=1
V, # and min (u(r) ((r) E n El Vi) E O 1-r Vi rE(|o])
(13)
From Lemma E.3, & occurs with probability at least 1.2 From now we will assume & occurs. Let S (V, ........V,,, Vn be some training set. Next we define sample dependent oracle Os. Given and at all past samples S = (V..... V/}:
1. |f 16
output
2. Otherwise check if the exists No /=1 V.. We will check this in lexicographic order over vectors in U, so we will find the minimal such vector.
(a)
In th E V/ = or uo E U r=f 1+1 Vi,, output an arbitrary sub-gradient.
(b) Otherwise compute the following sets:
J = 2i :e [d] and mo(i) > 0 and [w]t] + wx (2)
(1) = 0f
8 = i [d] un(1) < 0 and [w]") (2)2 (1) =0]
We will use (1) to take steps in the negative coordinates of un - J, and w (2) to take steps in the positive coordinates of uo- jf. Choose min(8 log n, |J indices out of J,P denote them P. and min(8 log n. |J out of Jf denote them N,. Output
(e(N.) e(P,))
We will prove this oracle is valid and when & holds not projections take place. Its proof is deferred to Appendix C.I. Lemma C.2. Os stated above is valid sample dependent first order oracle of f defined in Equation (12). Furthermore if holds it will induce a trajectory such that we never leave the unit ball and no projections take place.
Assuming occurs, for T" =[ 8logn
1
we have that
16
Vr 2 T' w
+ +w/
(2)
an
11
a7 /
logn
2v2
So for every suffix averaging T:
T'
Wny + (22)
110 2
1
W
+ w
T
40
11
3n
+2
vn
16
||
2v2
3n
an) an
n 2 16
11
2v2
11
an/n
16
2v2
We now have that with probability 1:
Fs(Wn,z) - (0)
1
n
1an
+
7n
90m
9
-min mmin(1,7vR).
16
16
2v2
16-2
16 2v2
365
365
17

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
C.1. Proofs for Auxiliary Lemmas
Proof of Lemma C.2. For the first part of the oracle note that 0 0f(0, V) we can stay O for as long as we like, in particular for [ steps. For the second part if n /=1 Vi we keep outputting 0 which is allowed as saw before. If DEl V; 0 choose some ио- If uo U i= it: |+1 Vi we output valid sub gradient by definition, if it is not are clearly taking gradient step for ar((w). It is thus left to show that in this case 0) @g(w,, V). Indeed, in this event until this point the gradient only output O or executed Item 2b in the oracle so the nonzero coordinates in w, have the same sign as Also for all v E Vi, we have that * uo which suggests using Equation (11):
W + + (2)) VS
Σ
+ W (w, v(i)
Vd. V8lonn
Σ
uo r(i) S
90m Vn.
16 2V2
(V())=
This concludes the proof that Os is well defined. To see no projections take place if & as depicted in Equation (13) holds, note that this is exactly the event where the oracle either outputs or executes Item 2b in the oracle. In this event:
Vr e [n].i [d] (wl s
an
||w,|12
an\Vd 1 = min m s 2
v8 log
18lg
D. Reduction to Sample-Dependent Oracle
For the reduction we will further formalize the notion of sample-dependent oracle when gradient oracle O2 is data- dependent and at step / it is allowed to depend on the examples seen up to this step. We denote the sample-dependent oracle by Os when (Si...., Sy) and for r E [7]. S, is the set of examples given to the algorithm at step r. For example, for SGD S, {zi, and for Gradient Descent S. Then we denote the following:
Os(S1s-1:S
1 S
Σ 2ES,
Oz(Sir-ii))))
when Oz(S (f
when $1.0 = 0. Sty = (Si...., S,). Finally we denote the trajectory induced by Os which is initialized at wo = 0 and is specified by the following equation:
w r+] = 11
(14)
The following Lemma from Livni (2024) will prove the reduction to the sample dependent oracle case:
Lemma D.1 (Lemma Livni (2024)). Suppose E RR7.1141.a z and Z is finite. And suppose that f(w, z) is a convex, L-Lipschitz. funttioo over w IRd, let n > O, let Os be sample dependent first order oracle, and for every sequence of samples S (S),..... ST) define the sequence {w: ft=l
(wST as in Equation (14).
Then, for every E > there exists an + 1-Lipschitz convex function f((w,x), over Rd+1 (that depends on q, g.f.1 G.f.T.m n,n, Os. E) such that for any oracle fz f(z.-), define un 0 Rd and xo E R and
7
Σ Oz((u,.xi))
(u,,,,) (u,
SS ZES,
then if we define
T w Σ w
q()u, Xg Σ q()xx
Uqq
we have that Ug S for all z:
If((Ug:xg))z) f(w (W5g,2) 21 se
If((0,0), - f(0. 2) Sc
The following Lemma easily follows:
18

---

Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization
Lemma D.2. Suppose Z finite, f(w, 2) convex, L-Lipschitz, function over w Rd, let n O, let Os be sample dependent first order oracle, and for every sequence of samples S -SS....,,yy ST) define the sequence {WT)TH) Equation (14). Suppose also that for some number of steps T and 7 [T 1] we have with probability p:
Itll
in
F F(W F(0)
Where 8 > O. Then there exists an L+ L-ipsshchi convex function f((w.x) x), z) over Rd+1 (that depends on T, f. 17 Os. such that for any oracle foror f(2,-) we define vo E de and
77 [
Σ
Oz(v,).
Vr+1 = Vr
265,
we will have:
l
F(VT,t) 2
Proof. Let E - O, define q e Rd as follows:
T-T+2 TSIST+1 0
(())
otherwise
For this q, let / be the function whose existence follows from Lemma D.I. It is easy to see that w = w.y and Fr = ((g.x Xg).
Then with probability p we have:
F(PT,))- F(ugxxx) F(0)= F(W)) F(O) -2 l C-2. - l
E. Additional Lemmas
Lemma E.1 (Lemmaa 14 in Koren et al. (2022)). For any step-size 11 > 0, T E N and d = [16 there exists a deterministic convex oplimization problem h : W - R where W c Rd+l is of constant diameter such that:
h( w min h(w)= 2 min
+ +7.
weW
8
nT
Lemma E.2. Let U be a subspace such that |U| 2 2". Let Z = P(U) and let Z be a distribution of Z such that for a random sample at least it holds that: U # U
every E U with probability 1. Then for a sample (V..... Vn) Z" with probability
Proof. First it holds that:
Pr|u V =1 - Pr V = 1-2
This implies:
1 2
|0| s (1 (1-2 Pr U U V, = U] MN = (
Lemma E.3 (Lemma 9 in Schliserman et al. (2024)). For d = 712n log and Ua as depicted in Lemma I from Schliserman
et al. (2024), let = P(U) and let a distribution Z over Z be such that for V ~ Z every u E Ua is in V with probability Anz Let (V...... Vn) be a training set drawn i.idd from Z. Denote P, = n--V, V, and = n V, More over if P, # we denote according to some ordering vi of the vectors in U, r, arg min V, P,), and J, Vr, e Ua. denote the following event:
E = (Vr S T, 0 and J, E St).
Then TT Pr[E] J. In particular with probability least ::
P 0 and J[n/16] E S[n/16]-
19


Reviews:
[{"review_id": "aLGyi69z0n", "reviewer": "Reviewer_E6PJ", "summary": "The paper makes three main contributions in Stochastic Convex Optimization with convex and Lipschitz (but not necessarily smooth) loss functions: First, they establish tight bounds on the population excess risk of multi-pass SGD that apply to both single-shuffle and multi-shuffle variants. Second, they prove similar tight bounds for with-replacement SGD that hold after a logarithmic number of steps. Finally, they provide new lower bounds on the empirical risk of single-pass SGD in nearly linear dimension, improving upon previous results that required quadratic dimension.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thorough review and discussion. Following are our responses to your main comments: \n\n> “lacks empirical validation or real-world experiments to demonstrate the practical impact”\n \nOur 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.\n\nWhile 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.\n\n> “Construction-based proofs - relies on specific constructed examples rather than showing results for general cases”\n\nIndeed, 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.\n\n> “Dimensionality assumptions - some results require high-dimensional settings that may not reflect practical scenarios” \n\nThe 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$.)\n\nThe 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$.\n\n>  “Limited practical guidance - doesn't provide clear recommendations for practitioners on how to avoid the identified overfitting issues”\n\nIndeed, 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.\n\nIn 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. \n\n> “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.”\n\nThis 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.\n\nWe will add this discussion in the final version, thank you for this comment!\n\n> “Might want to consider some restructuring, not having a conclusion to tie things together seems a bit odd”\n\nThe 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.\n\n> “Could your analysis extend to other variants of SGD (e.g., with momentum, adaptive methods)?”\n\nThat 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.  \n\n> “What about non-convex settings?”\n\nSince 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).", "claims_and_evidence": "All claims are supported by mathematical proofs:\n\n1. For the multi-pass SGD bounds:\n- They provide a lower bound construction in Section 5 (Theorems 3.1 and 3.2)\n- They prove matching upper bounds in Appendix A (Theorems 3.3 and 3.4)\n- The proofs involve constructing specific loss functions and showing both that these functions are valid (convex, Lipschitz) and that SGD behaves as claimed when applied to them\n\n2. For with-replacement SGD:\n- They use similar techniques but add analysis involving the coupon collector's problem to handle the random sampling\n- The proofs appear in Section 5 and Appendix A\n\n3. For the improved empirical risk bounds:\n- They provide a construction in nearly linear dimension in Section 4 (Theorem 4.1)\n- The proof leverages techniques from previous works, but achieves better dimension dependency\n\nMost proofs are constructive, and seemingly easy to follow given the proof outlines. I did not look into the appendix thoroughly.", "methods_and_evaluation_criteria": "None.", "theoretical_claims": "I did not verify fully the claims made by reviewing the appendix, however because most of the proofs are constructive none seemed incorrect at there face. That said, I am not an expert in this area, and thus some of the bounds discussed or the results derived may not actually make sense.", "experimental_designs_or_analyses": "None.", "relation_to_broader_scientific_literature": "I have a background in convex optimization / online convex optimization and am thus aware of online-to-batch arguments and the like. However, I have not read or interacted with many of the core works that this paper is built off of and thus might not fully appreciate the the impact of this work in the broader scientific literature.", "essential_references_not_discussed": "None that I am aware of, though 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.", "other_strengths_and_weaknesses": "Strengths:\n1. Theoretical rigor - the paper provides complete proofs and careful mathematical constructions for all its claims\n2. Novel insights - reveals a previously unknown phase transition between first and subsequent passes of SGD\n3. Comprehensive analysis - covers multiple variants (with-replacement, single-shuffle, multi-shuffle)\n4. Improves on prior work - achieves better dimension dependency than previous results\n5. Clear practical implications - helps explain why multiple passes might lead to overfitting in the non-smooth setting\n\nWeaknesses: \n1. Theoretical focus - lacks empirical validation or real-world experiments to demonstrate the practical impact\n2. Construction-based proofs - relies on specific constructed examples rather than showing results for general cases\n3. Dimensionality assumptions - some results require high-dimensional settings that may not reflect practical scenarios\n4. Limited practical guidance - doesn't provide clear recommendations for practitioners on how to avoid the identified overfitting issues", "other_comments_or_suggestions": "- There are a couple instances of spelling and grammar issues throughout the paper which can probably addressed by passing tex file through a spell checker.\n- Might want to consider some restructuring, not having a conclusion to tie things together seems a bit odd.\n- Is there any way to provide empirical verification of any of the theoretical claims to illustrate how relevant this is to practical optimization?", "questions_for_authors": "Practical Implications:\n- How do your theoretical results translate to practical guidance for practitioners?\n- Are there specific strategies you'd recommend to mitigate the overfitting in multi-pass SGD?\n- Have you observed the behavior your theory describes empirically in any real-world optimization problems?\n\nExtension Possibilities:\n- Could your analysis extend to other variants of SGD (e.g., with momentum, adaptive methods)?\n- What about non-convex settings?\n- Are there connections to implicit regularization in deep learning?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N9mdtmPv0c", "reviewer": "Reviewer_UpAF", "summary": "This work considers the Stochastic Convex Optimization (SCO) setting and investigates the excess population risk and sample complexity lower bounds for Stochastic Gradient Descent (SGD). While the majority of previous work tackled GD or single-pass SGD, this paper mainly focuses on the multi-pass version of SGD. More specifically, the authors derive excess population risk lower bounds of $\\Omega(\\eta\\sqrt{T} + 1/\\eta T)$ for several versions of multi-pass SGD, both with and without replacement, when the number of passes exceeds a small constant. These lower bounds are tight and match the corresponding upper bounds. Additionally, the authors present a novel empirical risk lower bound of $\\Omega(\\sqrt{\\eta}n)$ for single-pass SGD, further enriching the understanding of SGD's generalization properties.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and discussion. We respond to the main claims below:  \n\n> 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.”\n\nWe 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.\n\n*Regarding Bassily et al:*\n\nAs 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.\n\nWe 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.\n\nOverall 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.\n\n*Regarding Amir et al:*\n\nOne 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.\n\nSome 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. \n\nGiven 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).", "claims_and_evidence": "Not applicable.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "The major theoretical conclusions are reasonable, and the key steps in the proofs appear to be correct.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "This work is entirely theoretical and does not present any negative broader scientific or societal impacts.", "essential_references_not_discussed": "The authors appropriately cite the most relevant prior work and provide a clear and detailed discussion of how their contributions relate to and advance the existing literature.", "other_strengths_and_weaknesses": "**Strengths**\n\nGenerally speaking, the paper is well-written, with a clear exposition that makes it easy to follow. The proof sketch is intuitive and highlights the key ingredients and techniques used in constructing lower bounds. From a contribution perspective, this paper gives a nearly complete picture for the understanding of excess population risk lower bound of multi-pass SGD under the non-smooth SCO setting. These results offer novel insights into the generalization property of multi-pass SGD and the relationship between overfitting, step-size and number of passes.\n\n**Weaknesses**\n\nHowever, the major weakness of this paper lies in its limited novelty. 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]. While the results in this paper are technically new and are different from prior work such as [Amir et al., 2021], which tackles only GD, and [Bassily et al., 2020], which provides only uniform stability lower bounds, the conclusions in this paper are not entirely surprising and unexpected. Given this lack of significant improvement, I tend to reject this work unless the authors could provide more compelling arguments to address these concerns or offer deeper insights into the open questions discussed in the paper.", "other_comments_or_suggestions": "Not applicable.", "questions_for_authors": "No further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LqDzSPpwQY", "reviewer": "Reviewer_M6q6", "summary": "This paper considers multi-pass SGD in the SCO setting. Single pass SGD is known to achieve optimal excess population error, but it was not clear how it performs in terms of population loss after multiple passes. In fact, this paper shows lower bounds indicating that (several versions of) multi-pass can quickly \"overfit\" after even 2 passes over the training data and can have Omega(1) excess population risk when using the single-pass-optimal O(1/sqrt{n}) stepsize.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thorough review and feedback. We respond to main claims below:\n\n> “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”\n\nWe 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.\n\n> “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.”\n\nWe will follow the reviewer’s advice and we will make it easier to follow, by deferring it to the appendix if needed.\n\n> ”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?”\n\nThese 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). \n\n\nAs 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.", "claims_and_evidence": "The claims in the paper are supported by proofs. However, I would not necessarily describe these proofs as \"clear\". This can probably be partially attributed to the fact that the underlying problem and arguments are quite complicated and delicate, but I found it difficult to follow the details of the proofs in the paper. \n\nThe proof sketches give some idea of what is going on, but 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, and so a thorough understanding of this paper appears to depend on the reader already being intimately familiar with Livni 2024 (I am not). Perhaps this is unavoidable, but I think the paper could be improved and made more readable by recapping this paper's Lemma D.1 from Livni 2024 and explaining what is going on there.\n\nIn 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.", "methods_and_evaluation_criteria": "Yes, this is a theory paper and the implicit evaluation metric is, appropriately, the quality of the results of the theorems.", "theoretical_claims": "Even though I would describe myself as an expert on lower bounds for convex optimization, I found it very difficult to follow these proofs, and I am nowhere close to 100% confident that I would have caught an error if there was one. That said, I did read through all of the proofs and did my best to follow them, and I found nothing that looked incorrect. \n\nI will also add that these results hinge crucially on results from Livni 2024, which I was not previously familiar with and which I did not review in detail.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This is a very interesting paper that ties in well to the existing literature. Previously, it was mostly assumed that (1) one-pass SGD is optimal in terms of the excess population risk, (2) \"few\"-pass SGD is probably about the same or maybe even a little better in terms of excess population risk, and (3) that \"many\"-pass SGD might eventually overfit. This paper is a useful and thought provoking corrective to point (2), showing that even 2-3 passes over the training data are enough to overfit, or at least have substantially slower convergence (if the stepsize is chosen optimally, you get T^{-1/4} convergence for multi-pass instead of T^{-1/2} for one-pass).", "essential_references_not_discussed": "Nothing comes to mind.", "other_strengths_and_weaknesses": "See previous comments. Generally, I think the paper is interesting and the prose are well-written and understandable, but I the proofs are quite terse and hard to follow--I think the paper would be greatly improved by making the technical ideas more accessible and readable.", "other_comments_or_suggestions": "pg 5: \"furher\", \"minimzer\"\n\nSection 3: the first sentence says \"for K \\leq n epochs\", but Theorem 3.1 says \"3 \\leq K \\leq n^2\", so there is a discrepancy there.\n\nSection 4: first sentence says \"\\Omega(\\eta \\sqrt{T})\" but Theorem 4.1 says \"\\eta \\sqrt{n}\". This is consistent because it is referring to one pass SGD, but I would suggest using the same letter in both places.", "questions_for_authors": "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, even e.g., \\eta + 10^{-100} N(0,1), because then the argmaxs would be a.s. unique after 2d steps so you could lose control over the iterates. The argument also seems to hinge similarly on initialization at zero (or else argmaxs might always be unique).  Is that correct or am I missing something? Do you see a path towards a similar lower bound for variable stepsizes or e.g. random initialization?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "WtVEfhj1wZ", "reviewer": "Reviewer_4BeX", "summary": "The author(s) analyzed the generalization lower bound of SCO in the multi-pass scenario. The lower bound that SCO with multi-pass can quickly overfit and yield $\\Theta(1)$ population loss.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thorough review and input. Below are our responses to the main comments in your review:\n\n> “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.”\n\nThanks 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.\n\n> ”Merely looking at Theorem 3.1, setting $\\eta = T^{ -3/4 }$ yields population risk converges to 0. Why can't we do this?”\n\nYou 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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The proofs looks reasonable to me. I did not check the proof in detail.", "experimental_designs_or_analyses": "This is a pure theoretical work and there is no numerical experiments.", "relation_to_broader_scientific_literature": "No", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Pros:\n- The writing of the paper is crispy, it is a joy to read the paper;\n- The lower bound of SCO in Theorem 3.1 and 3.2 are new and interesting to me. The analysis is also neat.\n\nCons:\n- 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.", "other_comments_or_suggestions": "right column of line 255, $\\partial h_1(0) 0 $, is this a typo?", "questions_for_authors": "Merely looking at Theorem 3.1, setting $\\eta = T^{ -3/4 }$ yields population risk converges to 0. Why can't we do this?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: This paper derives tight bounds on the population excess risk of multi-pass SGD in the general non-smooth case, both with and without replacement. The results of this work connect well with the existing literature and offer new insights, in particular, that very few passes over the training data are already enough to overfit or at least have substantially slower convergence.

The paper also provides new lower bounds on the empirical risk of single-pass SGD in nearly linear dimension, improving upon previous results that required quadratic dimension.

One reviewer inquired about the technical differences between [Amir et al., 2021] and [Bassily et al., 2020]. The author clarified this in the rebuttal and will incorporate these comments into the final version of the paper.
Decision: Accept (spotlight poster)