REVIEW 3 major objections 4 minor 2 cited by
Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization
T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read Multi-pass SGD can reach constant excess population risk after only two passes in non-smooth stochastic convex optimization, even though one pass is optimal.
desk verdict A genuinely new tight characterization of multi-pass SGD overfitting, but the lower bound proof leans on an unverified external reduction (Livni 2024, Lemma D.1) for the singleton, projected setting; referee should check that step carefully. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument works with a 'sample-dependent oracle', a gradient oracle that at step $t$ may condition on all samples seen so far, and then removes that extra power by a reduction to an ordinary first-order oracle on an augmented function. The construction uses a packing-based convex loss $f(w,V)=g(w,V)+\alpha h(w)$: examples $V$ are random subsets of a large set $U\subset\{0,1\}^d$ of almost-orthogonal vectors, and with high probability one vector $u_0\in U$ is absent from the entire training set. The $g$ term makes $u_0$ an empirical-risk minimizer whose population loss is $\Omega(1)$, while the $h$ term supplies subgradients that push the iterate toward $u_0$ once it has spent the first epoch at zero. Because $0\in\partial f(0,V)$ for every example, the sample-dependent oracle can keep the algorithm at the origin during the first pass, effectively memorizing the training set without moving, and then guide it to $u_0$ in the second pass. A cited reduction lemma constructs an augmented function $\bar{f}((w,x),z)$ on one extra coordinate so that any ordinary first-order oracle for $\bar{f}$ is forced to follow essentially the same trajectory, transferring the lower bound to standard SGD. The matching upper bound instead follows from uniform stability: for non-smooth losses stability contributes $O(\eta\sqrt{T})$ and optimization error contributes $O(1/(\eta T))$.
What would settle it
Run the paper's own construction at $n=24$, $d=256n$, drawing $n$ independent subsets $V_i$ of the packing set $U$ with inclusion probability $1/2$. If a vector $u_0\in U$ lies outside $\cup_i V_i$, run without-replacement multi-pass SGD with step size $\eta=1/\sqrt{24}$ for two epochs and measure the suffix-averaged population excess risk; a value of $o(1)$ with probability greater than $1/2$ would contradict Theorem 3.1. Independently, verifying Lemma D.1 by constructing the augmented function and comparing its trajectories for a small instance would settle whether the reduction, and hence the transfer to standard SGD, is sound.
Extended reading notes
Core claim
The central claim is Theorem 3.1: for every $n\ge 24$, $2\le K\le n/2$, $T=nK$, $d=256n$, and any step size $\eta>0$, there exists a 4-Lipschitz convex loss over a bounded domain such that after $T$ steps of without-replacement multi-pass SGD, with any sequence of permutations and any first-order oracle, the excess population risk satisfies $F(\widehat{w}_{T,\tau})-F(w^\star)=\Omega(\min\{\eta\sqrt{T}+1/(\eta T),1\})$ with probability at least $1/2$ over the random training set. Setting $\eta=\Theta(1/\sqrt{n})$ makes this $\Omega(1)$ already at $K=2$ passes. A matching upper bound of the same functional form holds for single-shuffle and multi-shuffle schedules, and the same lower-bound rate holds for with-replacement SGD once it has run for $O(n\log n)$ steps. The paper also proves a separate lower bound of $\Omega(\eta\sqrt{n})$ on the generalization gap of one-pass SGD in near-linear dimension $d=\widetilde{O}(n)$, improving the required dimension from quadratic to near-linear.
Load-bearing premise
The load-bearing premise is that any gradient oracle allowed to use all past examples can be simulated by an ordinary stochastic oracle on a slightly larger loss; this reduction is cited rather than proved here, and if it fails the claimed lower bounds for standard SGD do not follow.
Editorial extensions
If this is right
- With the minimax-optimal step size $\eta=\Theta(1/\sqrt{n})$, the excess population risk of multi-pass SGD becomes $\Omega(1)$ after just two passes, so the first epoch is the only epoch that can achieve the optimal $\Theta(1/\sqrt{n})$ rate.
- The tight rate $\Theta(1/(\eta T)+\eta\sqrt{T})$ holds for every permutation schedule, including single-shuffle and multi-shuffle, so no reshuffling variant avoids the overfitting threshold.
- With-replacement SGD exhibits the same overfitting asymptotics after $O(n\log n)$ steps, meaning the effect is not an artifact of sampling without replacement.
- The first pass is explained by online-to-batch guarantees, while stability-based bounds become the tight description only from the second epoch onward, matching the phase transition.
- The generalization gap of one-pass SGD can be $\Omega(\eta\sqrt{n})$ already in nearly linear dimension $\widetilde{O}(n)$, so minimizing empirical risk and studying the generalization gap cannot explain one-pass SGD's optimal behavior.
Reading between the lines
- Extrapolating from the construction, the same memorize-then-steer mechanism should, if the reduction is sound, transfer to other epoch-based optimizers that see every training point before updating further, such as mini-batched SGD with reshuffling or full-batch gradient descent; the paper proves this only for the SGD variants it studies.
- A direct synthetic check is available at the paper's own parameters: with $n=24$, $d=256n$, subset sampling with inclusion probability $1/2$, and $\eta\approx 1/\sqrt{n}$, the test loss should jump sharply between the end of epoch one and the end of epoch two; observing no jump would point to a flaw in the construction or the reduction.
- Because the dimension in the construction is only a constant multiple of the sample size, the overfitting mechanism may be observable in moderately overparameterized finite-sum problems rather than requiring an exponentially large parameter space; testing smaller random packings would show whether the constant $256$ is an artifact or a genuine threshold.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the population excess risk of multi-pass SGD in non-smooth stochastic convex optimization. Its main results are lower bounds of Ω(min{η√T + 1/(ηT), 1}) on the population loss of without-replacement multi-pass SGD (Theorem 3.1) and of with-replacement SGD after O(n log n) steps (Theorem 3.2), together with matching upper bounds (Theorems 3.3 and 3.4) and an Ω(η√n) lower bound on the empirical risk / generalization gap of one-pass SGD in near-linear dimension (Theorem 4.1). The proofs are built on a sample-dependent oracle construction, a reduction from such oracles to standard stochastic oracles quoted from Livni (2024), and several auxiliary results from Koren et al. (2022) and Schliserman et al. (2024). If the central lower bounds hold, the paper establishes a sharp phase transition between the first and later epochs of SGD and resolves a basic open question about rapid overfitting in multi-pass SGD.
Significance. The claimed results are substantial: they give the first tight population-risk characterization of multi-pass SGD in the classical non-smooth SCO model, and they show that the canonical η = Θ(1/√n) step size can lead to Ω(1) excess population loss after just two passes. The upper and lower bounds match up to constants, and the one-pass empirical-risk lower bound improves the required dimension from quadratic to near-linear, which is optimal up to log factors. The paper is clearly written and the constructions are explicit, with concrete constants. However, the central lower bounds depend on a nontrivial reduction lemma (Lemma D.1, quoted from a co-author's earlier paper) whose applicability to the singleton-step, projected-setting of SGD is not demonstrated, and the proof of Theorem 3.1 does not spell out how the two lower-bound terms are combined within the stated dimension. These issues are load-bearing for the main claim, so the paper is not yet fully established, but the gaps appear fixable within the manuscript's scope.
major comments (3)
- [Appendix D, Lemmas D.1 and D.2; proofs of Theorems 3.1 and 3.2] The reduction from the sample-dependent oracle to a standard stochastic oracle is quoted without proof from Lemma 9 of Livni (2024). This reduction is the step that converts the lower bounds for the oracle-based construction into lower bounds for actual SGD, so it is load-bearing for Theorems 3.1, 3.2, and 4.1. As stated, Lemma D.2 produces an unprojected sequence v_t and guarantees only that the suffix average u_q equals the sample-dependent average w_q; it does not show that the v_t iterates remain inside the unit ball W of Theorem 3.1, nor that the projection step in the SGD protocol leaves the suffix average unchanged. Since Theorem 3.1 is stated for the projected algorithm, this gap must be closed either by proving the reduction in the |S_t| = 1 setting with a projection-preservation argument or by restating the lower bounds for unprojected SGD and then transferring them to the projected setting.
- [Section 5, proof of Theorem 3.1] The proof claims the Ω(1/(ηT) + η√T) lower bound by combining Lemma E.1 (which gives Ω(min{1/(ηT) + η, 1})) with Lemma 5.1 (which gives Ω(min{1, η√min{n³,T}})), but no single function that simultaneously realizes both terms is constructed. Lemma E.1 is a deterministic convex problem in dimension ⌈16η²T²⌉, and a naive direct sum with the sample-dependent construction would exceed the dimension d = 256n stated in Theorem 3.1. The proof needs to spell out a combination (for example, a direct sum with a dimension check in the parameter regime where each term is the larger one, or an argument that the maximum of the two lower bounds suffices) and verify that the dimension bound is respected. As written, the two-term lower bound and the dimension constraint are not jointly established.
- [Section 5, Lemma 5.1, event E and Equation (4)] The proof factors the probability of the event E as Pr[∪_{t=1}^{τepoch} S_t = S] · Pr[∃u0 ∉ ∪_{V∈S} V], which requires the memorization event to be independent of the training set S. This is automatic for the first epoch of without-replacement SGD, where every index is visited and the memorization event is deterministic. For Theorem 3.2, however, the memorization event is that all distinct values of S are seen in the first τepoch = n log n with-replacement draws; this event is correlated with S because training sets with fewer distinct values are more likely to be memorized. The conditional probability that a bad vector u0 exists is therefore not shown to be at least 1/2, and the lower bound for with-replacement SGD does not follow from the present argument. A more careful probabilistic treatment is needed for this case.
minor comments (4)
- [Section 5, Lemma 5.1] The symbol S is used both for the training set and for the ordered sequence (S_1, ..., S_T), which makes statements such as 'if with probability p it holds that ∪_{t=1}^{τepoch} S_t = S' ambiguous. Please use distinct notation for the training set and the sequence of sample sets.
- [Proof of Lemma 5.2] In the induction showing that the trajectory stays in the unit ball, the displayed computation gives ∥w_{t+1}∥² ≤ η²α²(1+t), but the final conclusion is written as ∥w_t∥ ≤ 2η²α²T. The factor-of-two mismatch and the missing square on the norm should be cleaned up so the bound is internally consistent.
- [Theorems 3.3 and 3.4] The proofs are given only for the uniform average of all iterates, while the theorem statements claim the bound for any suffix average τ = Ω(T). The sentence saying that the other suffix averages follow by similar arguments should be expanded, or the statements should be restricted to the case actually proved.
- [Figure 1] The caption and axis labels of Figure 1 appear garbled in the arXiv source (the text contains raw glyph codes such as '/uni00000014'), making the figure unreadable. Please regenerate the figure and caption.
Circularity Check
No result reduces to its inputs by construction; the main new construction (Lemma 5.1) is explicit and self-contained, though the formal bridge from sample-dependent oracles to standard SGD is a load-bearing theorem imported from a co-author's prior paper (Lemma D.1) without proof in this manuscript.
full rationale
The central lower-bound construction is Lemma 5.1, proved in Section 5 and Appendix B: it explicitly defines the sample space, the distribution, the 3-Lipschitz convex loss f(w,V)=g(w,V)+αh(w), and a sample-dependent oracle OS, and it proves both validity and the no-projection property under the relevant event. This construction is not defined in terms of the theorem's conclusion and does not assume the lower bound it derives. The step from this sample-dependent construction to a standard stochastic oracle is carried by Lemma D.2/D.1, quoted as 'Lemma 9 in Livni (2024)' and applied in the proofs of Theorems 3.1, 3.2, and 4.1 ('We can relax this dependence using the reduction in Lemma D.2 and conclude the proof'). This citation is from a co-author and is load-bearing, but it is an external reduction theorem rather than an assumption of the target lower bound; the same-author status is not itself circular. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported to forbid alternatives, and no known result is merely repackaged under new coordinates. A secondary expositional gap is that Theorem 3.1 combines the 1/(eta T) term from Lemma E.1 with the eta sqrt(T) term from Lemma 5.1 without spelling out an explicit direct-sum/product construction yielding both terms for one function; this is again a completeness issue, not circularity. The main risk is the correctness and verification of Lemma D.1 in the singleton-step, projected-iterate setting needed for SGD, which is a proof-gap concern rather than a circularity concern. Accordingly the circularity score is low.
Assumptions & free parameters
free parameters (4)
- alpha (scaling constant) =
min{1, 1/(eta sqrt(2T))} or min{1, 1/(eta sqrt(n))}
- block size B =
about (T/34)^(1/3) in Lemma 5.1; 3d/tau_epoch in Appendix B
- membership probability delta =
1/2 for multi-pass lower bounds; 1/(4n^2) for the one-pass bound
- dimension d =
256n for Theorems 3.1 and 3.2; 712n log n for Theorem 4.1
assumptions (6)
- ad hoc to paper Lemma D.1 (Lemma 9 in Livni 2024): any sample-dependent oracle trajectory can be realized by a standard stochastic oracle on an augmented function with error at most epsilon.
- ad hoc to paper Lemma E.1 (Lemma 14 in Koren et al. 2022): a deterministic convex problem gives excess loss at least (1/8)min{1/(eta T)+eta,1}.
- ad hoc to paper Stability bounds of Bassily et al. (2020), Theorems 3.3 and 3.4, for non-smooth SGD.
- ad hoc to paper Optimization error bound of Koren et al. (2022), Theorem 6, for multi-pass without-replacement SGD.
- ad hoc to paper Lemma E.3 (Lemma 9 in Schliserman et al. 2024): existence of a vector present in the early samples and absent from the tail of the sample.
- standard math Standard packing argument: existence of a set U subset of {0,1}^d with |U| >= 2^(d/256) and pairwise inner products at most 5d/16.
invented entities (1)
-
Sample-dependent first-order oracle with past-only dependence
Cite this review
Pith. "Pith review of Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization." pith.science (2026). https://pith.science/paper/TYQTYRV6
@misc{pith2026250508306,
author = {Pith},
title = {Pith review of: Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/TYQTYRV6}},
note = {Machine review of arXiv:2505.08306}
}
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 = \smash{\widetilde O}(n)$, improving on recent results of Koren et al.(2022) and Schliserman et al.(2024).
Figures
Forward citations
Cited by 2 Pith papers
-
Flat Minima and Generalization: Insights from Stochastic Convex Optimization
In smooth stochastic convex optimization, flat empirical minima can incur constant population risk while sharp minima generalize optimally, and sharpness-aware algorithms can converge to such bad flat minima.
-
The Fourth Quadrant: A Stylized View of Benign Misfitting
In a stylized single-spike linear model, useful span predictors in the window d/gamma^2 << n << d/gamma are forced to overshoot the training labels, so good test error comes together with large training error.
Reference graph
Works this paper leans on
-
[1]
S G D G eneralizes B etter than G D (and R egularization D oesn’t H elp)
Idan Amir, Tomer Koren, and Roi Livni. S G D G eneralizes B etter than G D (and R egularization D oesn’t H elp). In Conference on Learning Theory, pages 63--92. PMLR, 2021
work page 2021
-
[2]
S tability of S tochastic G radient D escent on N onsmooth C onvex L osses
Raef Bassily, Vitaly Feldman, Crist \'o bal Guzm \'a n, and Kunal Talwar. S tability of S tochastic G radient D escent on N onsmooth C onvex L osses. Advances in Neural Information Processing Systems, 33: 0 4381--4391, 2020
work page 2020
-
[3]
S tability and G eneralization
Olivier Bousquet and Andr \'e Elisseeff. S tability and G eneralization. The Journal of Machine Learning Research, 2: 0 499--526, 2002
work page 2002
-
[4]
T ighter L ower B ounds for S huffling S G D : R andom P ermutations and B eyond
Jaeyoung Cha, Jaewook Lee, and Chulhee Yun. T ighter L ower B ounds for S huffling S G D : R andom P ermutations and B eyond. In International Conference on Machine Learning, pages 3855--3912. PMLR, 2023
work page 2023
-
[5]
R andom R eshuffling is N ot A lways B etter
Christopher M De Sa. R andom R eshuffling is N ot A lways B etter. Advances in Neural Information Processing Systems, 33: 0 5957--5967, 2020
work page 2020
-
[6]
G eneralization of E R M in S tochastic C onvex O ptimization: T he D imension S trikes B ack
Vitaly Feldman. G eneralization of E R M in S tochastic C onvex O ptimization: T he D imension S trikes B ack. Advances in Neural Information Processing Systems, 29, 2016
work page 2016
-
[7]
T rain F aster, G eneralize B etter: S tability of S tochastic G radient D escent
Moritz Hardt, Ben Recht, and Yoram Singer. T rain F aster, G eneralize B etter: S tability of S tochastic G radient D escent. In International conference on machine learning, pages 1225--1234. PMLR, 2016
work page 2016
-
[8]
B enign U nderfitting of S tochastic G radient D escent
Tomer Koren, Roi Livni, Yishay Mansour, and Uri Sherman. B enign U nderfitting of S tochastic G radient D escent. Advances in Neural Information Processing Systems, 35: 0 19605--19617, 2022
work page 2022
Show all 24 references
-
[9]
Recht-r \'e noncommutative arithmetic-geometric mean conjecture is false
Zehua Lai and Lek-Heng Lim. Recht-r \'e noncommutative arithmetic-geometric mean conjecture is false. In International Conference on Machine Learning, pages 5608--5617. PMLR, 2020
2020
-
[10]
F ine- G rained A nalysis of S tability and G eneralization for S tochastic G radient D escent
Yunwen Lei and Yiming Ying. F ine- G rained A nalysis of S tability and G eneralization for S tochastic G radient D escent. In International Conference on Machine Learning, pages 5809--5819. PMLR, 2020
2020
-
[11]
G eneralization P erformance of M ulti- P ass S tochastic G radient D escent with C onvex L oss F unctions
Yunwen Lei, Ting Hu, and Ke Tang. G eneralization P erformance of M ulti- P ass S tochastic G radient D escent with C onvex L oss F unctions. Journal of Machine Learning Research, 22 0 (25): 0 1--41, 2021
2021
-
[12]
T he S ample C omplexity of G radient D escent in S tochastic C onvex O ptimization, 2024
Roi Livni. T he S ample C omplexity of G radient D escent in S tochastic C onvex O ptimization, 2024. URL https://arxiv.org/abs/2404.04931
2024 arXiv
-
[13]
S G D W ithout R eplacement: S harper R ates for G general S mooth C onvex F unctions
Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. S G D W ithout R eplacement: S harper R ates for G general S mooth C onvex F unctions. In International Conference on Machine Learning, pages 4703--4711. PMLR, 2019
2019
-
[14]
Nemirovski and D.B
A.S. Nemirovski and D.B. Yudin. P roblem C omplexity and M ethod E fficiency in O ptimization . Wiley, 1983
1983
-
[15]
Nikolakakis, Amin Karbasi, and Dionysis Kalogerias
Konstantinos E. Nikolakakis, Amin Karbasi, and Dionysis Kalogerias. S elect without F ear: A lmost A ll M ini- B atch S chedules G eneralize O ptimally, 2023. URL https://arxiv.org/abs/2305.02247
2023 arXiv
-
[16]
C losing the C onvergence G ap of S G D W ithout R eplacement
Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. C losing the C onvergence G ap of S G D W ithout R eplacement. In International Conference on Machine Learning, pages 7964--7973. PMLR, 2020
2020
-
[17]
Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies
Benjamin Recht and Christopher Re. Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies. Technical report, Technical report, and consequences. Technical report, University of …, 2012
2012
-
[18]
Itay Safran and Ohad Shamir. H ow G ood is S G D with R andom S huffling? In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3250--3284. PMLR, 09--12 Jul 2020
2020
-
[19]
R andom S huffling B eats S G D O nly A fter M any E pochs on I ll- C onditioned P roblems
Itay Safran and Ohad Shamir. R andom S huffling B eats S G D O nly A fter M any E pochs on I ll- C onditioned P roblems. Advances in Neural Information Processing Systems, 34: 0 15151--15161, 2021
2021
-
[20]
T he D imension S trikes B ack with G radients: G eneralization of G radient M ethods in S tochastic C onvex O ptimization, 2024
Matan Schliserman, Uri Sherman, and Tomer Koren. T he D imension S trikes B ack with G radients: G eneralization of G radient M ethods in S tochastic C onvex O ptimization, 2024. URL https://arxiv.org/abs/2401.12058
2024 arXiv
-
[21]
S G D : T he R ole of I mplicit R egularization, B atch- S ize and M ultiple- E pochs
Ayush Sekhari, Karthik Sridharan, and Satyen Kale. S G D : T he R ole of I mplicit R egularization, B atch- S ize and M ultiple- E pochs. Advances In Neural Information Processing Systems, 34: 0 27422--27433, 2021
2021
-
[22]
L earnability, S tability and U niform C onvergence
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. L earnability, S tability and U niform C onvergence. The Journal of Machine Learning Research, 11: 0 2635--2670, 2010
2010
-
[23]
C an S ingle- S huffle SGD B e B etter T han R eshuffling SGD and GD ? arXiv preprint arXiv:2103.07079, 2021
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. C an S ingle- S huffle SGD B e B etter T han R eshuffling SGD and GD ? arXiv preprint arXiv:2103.07079, 2021
2021 arXiv
-
[24]
L ower G eneralization B ounds for G D and S G D in S mooth S tochastic C onvex O ptimization, 2023
Peiyuan Zhang, Jiaye Teng, and Jingzhao Zhang. L ower G eneralization B ounds for G D and S G D in S mooth S tochastic C onvex O ptimization, 2023. URL https://arxiv.org/abs/2303.10758
2023 arXiv
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.