{"id":"e1ec0236-354d-4090-8483-62f80d39312d","arxiv_id":"2505.08306","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"In non-smooth stochastic convex optimization, a second epoch of SGD with the standard step size can push the population loss up to a constant, and the paper gives matching rates for any step size and step count.","lead":"Multi-pass stochastic gradient descent can memorize the training set so quickly in a basic convex learning model that one extra pass after the optimal first pass already drives out-of-sample error from near-optimal to constant. The paper proves a tight formula for this overfitting and an improved lower bound for why one-pass SGD cannot be explained by generalization gaps.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main multi-pass lower bound depends on an unproved reduction lemma (D.1, from Livni 2024) whose validity for singleton SGD steps and for projected iterates is not established; if it fails, Theorems 3.1–3.2 fall.","rationale":"The paper's main contribution is the tight multi-pass lower bound, and every lower-bound proof routes through the reduction of Lemma D.1/D.2. The rest of the argument (Lemma 5.1's sample-dependent construction, the matching upper bounds via stability, and the one-pass empirical risk bound) is substantially more self-contained, though the one-pass abstract claim is not exactly what Theorem 4.1 proves. The flagged lemma is not a routine citation: it asserts a universal simulation property of convex functions that is especially delicate when S_t are singletons, and the version in the text also ignores projections in the reduced dynamics. Because the authors do not reproduce or specialize the proof, the central claim is conditional. This agrees with the reader's weakest-assumption analysis; I do not see a separate internal inconsistency in Lemma 5.1's arguments that would change the verdict. The appropriate disposition remains conditional acceptance pending independent verification of the reduction, so the reader's CONDITIONAL verdict stands unchanged.","tokens_in":21246,"tokens_out":33399,"duration_ms":342126,"concrete_test":"Independently instantiate Lemma D.1 with the oracle OS from Lemma 5.1, using singleton S_t={z_{i_t}}, T=2n, tau_epoch=n, and suffix-average q; explicitly construct \\bar f and check for two training sets that differ only in the identity of the absent bad vector whether every subgradient oracle for \\bar f yields u_q = w^S_q while keeping all iterates in the unit ball. If no such \\bar f exists, or if the only available construction requires S_t=S (batch GD), the proof of Theorems 3.1–3.2 collapses. A useful sub-check is to trace the block dynamics of Lemma 5.1 for a small example (e.g., m=3 blocks) to confirm the claimed T' formula.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lower bounds (Theorems 3.1 and 3.2) rest on Lemma D.1/Lemma D.2, quoted from a co-author's earlier paper without proof. The lemma promises that any sample-dependent oracle OS can be simulated by a standard first-order oracle for a convex function \\bar f in one extra coordinate, so that any oracle for \\bar f reproduces the same averaged iterate. This is non-trivial when S_t are singletons, as in SGD: a standard oracle sees only the current example and the current point, so the extra coordinate must encode the whole history of the training set; the original Livni reduction was for batch GD where the full sample is visible at every step. The paper does not show the encoding can be done while keeping the trajectory inside the unit ball of Theorem 3.1; Lemma D.2's updates are unprojected, whereas the theorem's SGD projects. Until Lemma D.1 is verified in the |S_t|=1, projected setting, the claimed Omega(eta sqrt T) population-risk lower bound for multi-pass SGD is not established. A secondary gap: the proof of Theorem 3.1 obtains the 1/(eta T) term from Lemma E.1 without spelling out a product/direct-sum construction that yields both terms for one function.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21674,"tokens_out":14978,"duration_ms":153330,"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":[{"comment":"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":"Appendix D, Lemmas D.1 and D.2; proofs of Theorems 3.1 and 3.2"},{"comment":"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":"Section 5, proof of Theorem 3.1"},{"comment":"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.","section":"Section 5, Lemma 5.1, event E and Equation (4)"}],"minor_comments":[{"comment":"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.","section":"Section 5, Lemma 5.1"},{"comment":"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.","section":"Proof of Lemma 5.2"},{"comment":"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.","section":"Theorems 3.3 and 3.4"},{"comment":"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.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The main lower bound rests on Lemma 9 of Livni (2024), whose author is also a co-author of this manuscript, and the lemma is not proved here. Given that the reduction is nontrivial and is adapted to the SGD setting, I would want either a self-contained proof in an appendix or a precise statement with all conditions verified before publication. The dimension issue in combining the two lower-bound terms also needs to be addressed. These are correctness-relevant gaps rather than presentation quibbles, but they are likely fixable, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know: this paper resolves a long-standing open question in SCO. It shows that multi-pass SGD with the canonical step size eta = Theta(1/sqrt(n)) can suffer Omega(1) population excess risk after just one additional pass, and more generally gives a tight Theta(1/(eta T) + eta sqrt(T)) bound for the population loss from the second epoch onward. That is genuinely new, and if correct it closes an obvious gap left by stability analyses, which are vacuous in this regime.\n\nThe paper does several things well. The upper bounds in Theorems 3.3 and 3.4 are short and correct: standard stability plus optimization error yields exactly the claimed rate. The lower-bound construction adapting Livni's sample-dependent oracle to the memory-bounded SGD setting is a real technical contribution, and the dimension improvement for the one-pass lower bound from quadratic to near-linear is another solid step.\n\nThe main soft spot is the dependence on Lemma D.1, quoted from Livni (2024) without proof. This lemma underlies Theorems 3.1 and 3.2. The stress-test raises a specific worry: the original reduction was for batch GD where the full sample is visible at each step, whereas here the oracle must operate on singleton samples, and the reduced function lives in an unprojected space while the algorithm projects onto the unit ball. The paper does not show the reduction carries over to this setting. I can't tell from the text whether this is a genuine gap or a harmless extension, but it is load-bearing, and a referee needs to work through it.\n\nTwo smaller issues. The abstract claims a generalization-gap lower bound for one-pass SGD, but Theorem 4.1 only proves a lower bound on the empirical excess over the empirical minimizer; the gap statement does not follow without additional population-risk information. And the \"sharp separation\" between smooth and non-smooth cases is advertised without any smooth-case theorem in the paper; either cite a proof or soften the claim.\n\nThe proof of Theorem 3.1 also glosses over how the 1/(eta T) and eta sqrt(T) terms are combined into a single function; Lemma E.1 and Lemma 5.1 each deliver one term, and the direct-sum construction is not spelled out. That is likely fixable, but it needs to be explicit.\n\nWho this is for: anyone working on generalization of SGD, algorithmic stability, or lower bounds in convex optimization. The question is important, and the result is sharp enough to deserve serious referee time even if the reduction lemma turns out to need a fix.\n\nMy recommendation: send it out. The upper bounds are solid and the lower bounds are plausible; the review should focus on verifying Lemma D.2 in the singleton, projected setting.","headline":"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.","tokens_in":22058,"tokens_out":3732,"would_cite":true,"duration_ms":37348,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["multi-pass SGD","stochastic convex optimization","population excess risk","overfitting","without-replacement sampling","with-replacement SGD","generalization gap","sample-dependent oracle"],"falsifier":"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.","tokens_in":21002,"feed_emoji":"📉","tokens_out":15592,"duration_ms":146429,"temperature":0.7,"pith_summary":"The paper asks what happens to stochastic gradient descent's out-of-sample performance when the same training set is used for more than one pass. It claims that in the standard non-smooth convex setting, multi-pass SGD can overfit almost immediately: after the first epoch has let the algorithm see (and effectively memorize) the whole sample, later passes can be steered toward a parameter vector that minimizes the training loss but has constant population loss. In particular, with the step size $\\eta=\\Theta(1/\\sqrt{n})$ that is minimax-optimal for a single pass, the excess population risk becomes $\\Omega(1)$ after just two passes, for any permutation schedule and any first-order oracle, in dimension $d=256n$. The paper also proves a matching upper bound of the form $\\Theta(1/(\\eta T)+\\eta\\sqrt{T})$ for the population excess risk over $T=nK$ steps, and shows that with-replacement SGD overfits at the same rate after $O(n\\log n)$ steps. If these bounds are right, the first epoch is qualitatively special: the online-to-batch argument that explains optimal one-pass behavior stops working, and generalization bounds of stability type become the tight description only from the second epoch on.","feed_headline":"After two passes, SGD can hit a constant population loss","feed_subtitle":"The step size that is optimal for one pass becomes actively harmful from the second epoch onward.","key_machinery":"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))$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the reduction from sample-dependent oracles to standard stochastic oracles (Lemma D.1, cited as Lemma 9) and the packing set construction with exponential size in d; the transfer of the lower bounds to ordinary SGD depends on it.","marker":"Livni (2024)"},{"why":"Provides the spurious-empirical-minimizer construction that the g term is based on, showing that ERM can have a low-population-loss 'bad' vector in high dimension.","marker":"Feldman (2016)"},{"why":"Supplies Lemma E.1, the deterministic hard problem giving the 1/(eta T)+eta component of the lower bound, and earlier generalization-gap lower bounds that are improved here.","marker":"Koren et al. (2022)"},{"why":"Gives the uniform-stability bound for non-smooth multi-pass SGD that produces the matching upper bound.","marker":"Bassily et al. (2020)"},{"why":"Establishes the Theta(1/sqrt(n)) minimax rate for stochastic convex optimization and the stochastic-approximation guarantee that makes the second-pass Omega(1) contrast sharp.","marker":"Nemirovski and Yudin (1983)"},{"why":"Provides the packing lemma and high-probability event used in the one-pass and with-replacement constructions, as well as the prior quadratic-dimension lower bound improved to near-linear here.","marker":"Schliserman et al. (2024)"},{"why":"First showed a dimension-dependent overfitting lower bound for gradient-descent-type methods in SCO, the technique that this paper adapts to multi-pass SGD.","marker":"Amir et al. (2021)"}],"fun_headline_variants":["SGD overfits after just two passes","Multi-pass SGD: overfitting in a few epochs","Second pass of SGD destroys its guarantees","Optimal one-pass step size fails on second epoch"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["SGD overfits after just two passes","Multi-pass SGD: overfitting in a few epochs","Second pass of SGD destroys its guarantees","Optimal one-pass step size fails on second epoch"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000155,"raw_usage":{"total_tokens":1299,"prompt_tokens":1114,"completion_tokens":185,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":730,"completion_tokens_details":{"reasoning_tokens":126}},"tokens_in":730,"tokens_out":185,"duration_ms":2362,"temperature":1.0,"reasoning_tokens":126,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:00:48.552838+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"G eneralization of E R M in S tochastic C onvex O ptimization: T he D imension S trikes B ack","cited_arxiv_id":null,"evidence_quote":"Provides the spurious-empirical-minimizer construction that the g term is based on, showing that ERM can have a low-population-loss 'bad' vector in high dimension."},{"cited_title":"B enign U nderfitting of S tochastic G radient D escent","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma E.1, the deterministic hard problem giving the 1/(eta T)+eta component of the lower bound, and earlier generalization-gap lower bounds that are improved here."},{"cited_title":"S tability of S tochastic G radient D escent on N onsmooth C onvex L osses","cited_arxiv_id":null,"evidence_quote":"Gives the uniform-stability bound for non-smooth multi-pass SGD that produces the matching upper bound."}],"review_version":1}