acceptodds
Under review as a conference paper at ICLR 2027

How Smoothness Controls Overfitting: Sharp Curvature–Time Laws for Gradient Descent

Abstract

How does the population risk of gradient descent evolve as optimization continues on the same finite training sample? Classical stability bounds can overstate the statistical cost of longer training. We establish sharp curvature–time laws for projected gradient descent on the unit ball with convex, -Lipschitz, -smooth losses for every . At unit smoothness, the worst-case expected excess risk is for sample size and cumulative step size . Although the classical stability certificate is already constant-order at , the worst-case risk remains at the optimal scale and reaches constant order only at . The key is an interaction–dissipation principle that balances higher-order sample interactions against the stabilizing effect of losses unchanged by sample replacement. Beyond convexity, sharp risk laws show that even vanishing negative curvature can separate the last iterate from the full parameter average. On a single weakly nonconvex instance, the last iterate, a uniformly sampled iterate, and the full parameter average all have risk at an earlier horizon, but at a common later horizon their risks are , , and , respectively. Further applications yield sharp guarantees for weakly regularized pairwise learning, randomized coordinate descent, and fixed-source learning.

Primary area:
learning theory
Keywords:
generalization theory, projected gradient descent, algorithmic stability, overfitting, weak convexity, interaction-dissipation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_hGqfOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how training time (measured by cumulative step size q=ηTq=\eta T) and the loss smoothness constant LL jointly determine the worst-case expected excess risk of projected gradient descent (PGD) on the unit ball. Within the class of convex, 1-Lipschitz, LL-smooth losses, the authors establish a complete curvature-time risk law (Theorem 2.1): the worst-case risk is Θ(min⁡{1,q−1+n−1/2+gn,L(q)})\Theta(\min\{1, q^{-1}+n^{-1/2}+g_{n,L}(q)\}), where gn,L(q)g_{n,L}(q) is an LL-dependent sample-reuse growth term. The key technical contribution is the "interaction-dissipation" principle: before taking absolute values, signed sample interactions caused by replacing one observation are paired with dissipation terms arising from shared losses of unchanged samples. This improves the classical q/nq/n cost in stability analysis to q/n3/2q/n^{3/2} (when L=1L=1). Consequently, the optimal n−1/2n^{-1/2} risk persists until q≍nq\asymp n, while constant-order risk appears only at q≍n3/2q\asymp n^{3/2}; the authors also claim to resolve an open problem of Livni (2024) for this loss class.

The paper further studies output separation under weak negative curvature: in the ρ\rho-weakly convex loss class, the last iterate and the full parameter average satisfy different sharp risk laws (Theorem 3.1). On a single O(n)O(n)-dimensional instance, the later-time risks of the three outputs become Θ(1)\Theta(1), Θ((log⁡n)−1)\Theta((\log n)^{-1}), and Θ((log⁡n)−2)\Theta((\log n)^{-2}), respectively (Corollary 3.2). Finally, the authors extend the interaction-dissipation framework to weighted-factor objectives and apply it to pairwise weak regularization (Theorem 4.3), first-projection adaptive risk (Theorem 4.5), and fixed-source learning (Theorem 4.7), claiming strictly sharper guarantees than published stability bounds in key regimes.

Critical strengths

1.Theorem 2.1 provides a complete curvature-time law for the worst-case expected excess risk of PGD under convex, Lipschitz, and smooth losses, with matching upper bounds and explicit lower-bound constructions.

2.Classical stability analysis accumulates worst-case perturbations round by round and takes absolute values, leading to the loose q/nq/n certificate. The authors instead pair higher-order sample interactions with dissipation terms from unchanged losses and perform the crucial cancellation before taking absolute values, reducing the sample-reuse cost from q/nq/n to q/n3/2q/n^{3/2}. This mechanism reveals why risk can remain statistically optimal even after the stability certificate becomes vacuous, and constitutes an important supplement to stability theory.

3.The weak-convexity output separation results (Theorem 3.1, Corollary 3.2) demonstrate the advantage of parameter averaging and uniform checkpoints under long training time and is one of the highlights of the paper.

4.Section 4 demonstrates the advantage of the interaction-dissipation framework in other applications, achieving better upper bounds than previous corresponding bounds.

Critical weaknesses

1.Almost all proof details are relegated to an appendix exceeding 4000 lines. The main text provides almost no operational proof intuition for core theorems such as Theorem 2.1 and Theorem 3.1, and the explanation of interaction-dissipation remains at a very high level. This structure makes it difficult for readers to quickly locate the key location and increases the risk that potential errors are buried. Moreover, as requested, I have read only the main text, which explicitly depends on extensive details in Appendices C, D, E, I, J, K, L, etc. If the authors want the review to be effective, they should at least provide a more complete proof sketch for each main theorem in the main text.

2.The paper repeatedly claims that in key regimes its guarantees are strictly sharper than the published bounds of Lei et al. (2020), Wu et al. (2025), and Nikolakakis et al. (2023), but all comparisons are deferred to Appendix L. In the main text, these are only briefly mentioned in Remarks 4.4, 4.6, and 4.8. As a reviewer, I cannot determine from the main text whether the comparisons are made for exactly the same algorithmic instance, the same parameters, the same output rule, and the same risk quantity (certificate upper bound vs. actual risk). I recommend that the authors include a clear table in the main text listing the objects of comparison, the settings, and the quantitative gaps.

3.The paper contains no numerical experiments or even simple simulations, only schematic figures (Figures 1 and 2) to present the gaps among upper bounds. While experiments are not mandatory for a theory paper, the paper studies a very intuitive phenomenon—the relationship between training time and generalization risk. Using the paper's own constructive instances or simpler synthetic losses, one could plot empirical curves of risk versus qq, which would directly verify the risk plateau, the critical time, and the output separation, and also give readers more confidence in the theoretical constants and finite-nn behavior. Currently, there are only schematic figures (Figures 1 and 2) with no supporting data, which reduces the accessibility of the results.

Questions for authors

1.The low-curvature and high-curvature regimes are separated by the threshold L∼nL\sim\sqrt{n}. Is this threshold a technical artifact of the proof, or is it forced by the trade-off between optimization error and statistical error? More precisely, why does the phase transition occur at n\sqrt{n}? Clarifying this would help readers understand the role of smoothness in the theory.

2.In Corollary 3.2, all three outputs already achieve the optimal O(n−1/2)O(n^{-1/2}) risk at an earlier time, while the sharp separation into Θ(1)\Theta(1), (log⁡n)−1(\log n)^{-1}, and (log⁡n)−2(\log n)^{-2} is demonstrated only at the much later time q=(n/4)log⁡nq=(n/4)\log n. Is this late separation time an artifact of the weak-curvature construction, or is it an inherent feature of the problem? Could a milder but still visible separation appear much earlier? If so, the results would be easier to connect to practical training-time selection.

5 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/3)

Thank you for your thoughtful feedback and for recognizing the contributions of our curvature-time risk law and interaction-dissipation principle. We have revised the manuscript and highlighted all changes in blue. Our point-by-point responses follow.


Q1: The main text provides almost no operational proof intuition for Theorems 2.1 and 3.1, and the explanation of interaction–dissipation remains at a very high level. Could the authors provide more complete proof sketches in the main text?

A: Thank you for this suggestion. We have revised the manuscript to provide fuller proof sketches for Theorems 2.1 and 3.1 and explain the interaction–dissipation argument more concretely.

ProofLocation in the revised manuscriptWhat we added
Theorem 2.1: upper boundSection 2.2, Remark 2.3The worked example makes the cancellation explicit. The resulting stability estimate is then converted into the risk bound for general LL.
Theorem 2.1: lower boundSection 2.3, Remark 2.6To explain why the bounds are sharp, we relate the constructions' time constraints to the low- and high-curvature risk rates.
Theorem 3.1Section 3, immediately after the theorem(1) The response kernels now follow from explicit update recurrences. (2) The sketch explains all three output rules and their matching lower bounds.

In Remark 2.3, we added the following explanation for L=1L=1: “Smooth convexity gives negative squared-gradient terms from shared losses. We pair these with signed interactions and complete squares. Orthogonality bounds the total higher-order contribution per step by O(η/n2)O(\eta/n^2), while first-order terms contribute O(η/n3/2)O(\eta/n^{3/2}).” The proof then sums this bound over the updates and applies Eq. (5) to obtain the O(q/n3/2)O(q/n^{3/2}) sample-reuse term.

In Section 3, the proof sketch after Theorem 3.1 now includes: “Let vtv_t denote the mean squared replacement distance at step tt. The absorption estimate for the convexified losses gives vt+1≤(1+ηρ)2vt+Cη/n3/2v_{t+1}\le(1+\eta\rho)^2v_t+C\eta/n^{3/2} for the original updates.” The sketch derives both response kernels and explains how the output rules differ. The uniform checkpoint averages vtv_t, whereas the full parameter average has the bound (T−1∑tvt)2(T^{-1}\sum_t\sqrt{v_t})^2 by the L2L^2 triangle inequality. We also explain the additional O(ρ)O(\rho) term from weakly convex optimization and risk conversion. Please see Sections 2.2, 2.3, and 3 of the revised manuscript for the detailed revisions.


Q2: Are the claimed improvements over Lei et al. (2020), Wu et al. (2025), and Nikolakakis et al. (2023) compared under the same algorithmic instance, parameters, output rule, and risk quantity (certificate upper bound vs. actual risk)? Could the authors include a clear comparison table in the main text?

A: Yes. For each prior work, we compare its published bound with our result using exactly the same loss function, data distribution, algorithm, hyperparameters, and output rule. We also ensure that both results concern the same risk quantity, namely expected excess risk. The three comparisons cover different learning settings, as summarized below.

Prior workSame instance, algorithm, parameters, and outputPublished bound (capped)Our theorem and sharp riskGap
Lei et al. (2020), Thm. 6Pairwise RERM; instance (J.1); AλA_\lambda, λ=c/n\lambda=c/n, fixed c≥8c\geq 8Θ(1)\Theta(1)Thm. 4.3: Θ(n−1/2)\Theta(n^{-1/2})Θ(n1/2)\Theta(n^{1/2})
Wu et al. (2025), Thm. 3Pairwise scalar RCD; instance (H.18); ν=0\nu=0, D=66nD=66n, η=1\eta=1, q=T/D≍n4/3q=T/D\asymp n^{4/3}; last iterateΘ(1)\Theta(1)Thm. 4.5: Θ(n−2/3)\Theta(n^{-2/3})Θ(n2/3)\Theta(n^{2/3})
Nikolakakis et al. (2023), Thms. 10–11Full-batch GD; instance (I.25); fixed Zipf source pj∝j−3/2p_j\propto j^{-3/2}, η=1/2\eta=1/2, q=ηT≍n7/6q=\eta T\asymp n^{7/6}; last iterateΘ(1)\Theta(1)Thm. 4.7: Θ(n−1/2)\Theta(n^{-1/2})Θ(n1/2)\Theta(n^{1/2})

For Lei et al., we convert its generalization bound into an expected excess-risk bound. All comparisons use the original learning algorithms without modification. The reported gaps compare the published upper-bound certificates with our sharp bounds on actual excess risk, not the actual risks of different algorithms. We have added a compact version of this comparison as Table 1 in Section 4.2 (p. 9). Detailed same-instance verification is provided in Sections J.1, J.3, and J.5.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/3)

Q3: The paper contains no numerical experiments, and Figures 1 and 2 are only schematic. Could the authors add finite-sample simulations of excess risk versus training time to illustrate the risk plateau, critical time, and output separation?

A: Thank you for this helpful suggestion. Following your advice, we conducted five numerical experiments within the short rebuttal period and added them to Appendix B (pp. 16–20). They provide numerical support for our main conclusions on risk plateaus and delayed deterioration, output separation, and the role of dissipation in obtaining tighter estimates. We promise to add further experiments in the final version. OpenReview replies do not support figures, so we report key numerical results below and provide the plots in the revised manuscript.

(1) Risk plateau and later deterioration. For convex, 11-Lipschitz, 11-smooth losses, the table reports mean excess risk of the full parameter average over 256 independent training sets per sample size. Values are in units of 10−410^{-4}.

Sample size nnq=nq=nq=4096n3/2q=4096n^{3/2}
2162^{16}4.6964.69610.96910.969
2182^{18}2.3572.3578.6058.605
2202^{20}1.1801.1807.4237.423
2222^{22}0.5910.5916.8316.831

At q=nq=n, risk is approximately 0.12/n0.12/\sqrt n, consistent with the statistical scale in Theorem 2.1, although the classical certificate is already constant-order. The later increase on each fixed instance illustrates the deterioration in Theorem 2.4. Our explicit risk bound at q=nq=n is smaller than the classical bound by factors of 72.372.3–584.3584.3, without fitting constants to the data. Figures 3–5 show the full risk curves, compare the two bounds, and confirm that the plateau and later increase persist across the tested parameter settings. Table B.1 reports 9595\\% confidence intervals for the risk estimates. For the time scale of deterioration, Figure 4(b) shows nearly coincident population readout curves against q/n3/2q/n^{3/2}, and Figure 5(b) reports when the full excess risk crosses fixed thresholds. These plots illustrate the calibrated construction's time scale without independently estimating the critical exponent.

(2) Output separation. Under weak convexity ρ=1/n\rho=1/n, the three outputs of the same PGD runs have the following mean excess risks at the horizon specified in Eq. (B.2). Values are in units of 10−610^{-6}.

Sample size nnLast iterateUniform checkpointFull parameter average
2162^{16}181.925181.92512.79212.7928.0038.003
2182^{18}178.833178.8338.0458.0453.3893.389
2202^{20}177.592177.5926.2416.2411.7381.738
2222^{22}177.051177.0515.4165.4161.0621.062

At n=222n=2^{22}, parameter averaging gives approximately 1/1671/167 of the last-iterate risk. This comparison illustrates the qualitative output separation in Theorem 3.1 and Corollary 3.2. Figure 6 shows the complete trajectories, and Table B.2 provides confidence intervals.

(3) How dissipation tightens the estimate. The following estimates use identical iterates and gradients at n=12n=12, q=64q=64.

TreatmentBound on the higher-order contribution (×10−4\times10^{-4})
Drop dissipation and take absolute values1.0691.069
Drop dissipation but preserve signs0.8020.802
Use dissipation and complete squares0.4050.405

The bound obtained by completing squares is smaller by factors of 2.642.64 and 1.981.98 than the absolute-value and signed baselines, respectively. Figure 7 illustrates the absorption step in Lemma C.1 and Theorem 4.1: the negative dissipation term offsets interactions that would otherwise enlarge the estimate.

(4) Sensitivity to replacing one training example. At q=nq=n, the measured mean squared change in the output is 5.572×10−65.572\times10^{-6} for n=216n=2^{16} and 8.768×10−88.768\times10^{-8} for n=222n=2^{22}. Measurements at all four sample sizes lie below the bound in Eq. (6), consistent with the stability estimate used to control excess risk. Figure 8 in Appendix B.4 presents the complete comparison.

(5) Readout smoothness. At fixed sample size and cumulative step size qq, increasing LL from 11 to 256256 raises risk from 0.0010970.001097 to 0.0139320.013932, while the readout's training gradients remain zero. Figure 9 in Appendix B.5 illustrates how curvature affects population risk within this family, consistent with the smoothness-dependent risk conversion in our analysis.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 3/3)

Q4: The low-curvature and high-curvature regimes are separated by the threshold L≍nL\asymp\sqrt n. Is this threshold a technical artifact of the proof, or is it forced by the trade-off between optimization error and statistical error? More precisely, why does the phase transition occur at n\sqrt n?

A: Thanks. The threshold L≍nL\asymp\sqrt n is not a proof artifact. Theorem 2.1 establishes matching upper and lower bounds for the complete curvature–time law, confirming that this transition is sharp under the stated dimension conditions.

The transition arises from the trade-off between optimization error and the additional risk from continued training. Achieving the optimal risk n−1/2n^{-1/2} requires q≳nq\gtrsim\sqrt n, while keeping the additional risk Lq/n3/2Lq/n^{3/2} below n−1/2n^{-1/2} requires q≲n/Lq\lesssim n/L in the low-curvature regime. These two time scales coincide precisely when L≍nL\asymp\sqrt n. Consequently, Theorem 2.1 gives the sharp endpoint of the optimal-risk plateau:

qplateau≍max⁡n,n/L.q_{\mathrm{plateau}}\asymp\max\\{\sqrt n,n/L\\}.

When L≪nL\ll\sqrt n, the optimal risk persists until q≍n/Lq\asymp n/L. When L≳nL\gtrsim\sqrt n, the optimal-risk plateau ends at q≍nq\asymp\sqrt n. We have added this explanation to Remark 2.2 in Section 2.2, with the detailed derivation in Section K.2.


Q5: In Corollary 3.2, all three outputs already achieve the optimal O(n−1/2)O(n^{-1/2}) risk at an earlier time, while the sharp separation into Θ(1)\Theta(1), (log⁡n)−1(\log n)^{-1}, and (log⁡n)−2(\log n)^{-2} is demonstrated only at the much later time q=(n/4)log⁡nq=(n/4)\log n. Is this late separation time an artifact of the weak-curvature construction, or is it an inherent feature of the problem? Could a milder but still visible separation appear much earlier?

A: Thank you for this question. The late time q=(n/4)log⁡nq=(n/4)\log n is necessary for constant-order last-iterate risk, but not for output separation itself. Under the weak-curvature setting of Corollary 3.2, Theorem 3.1 gives the following upper bound for every admissible instance when q≥nq\ge\sqrt n:

\lesssim n^{-1/2}e^{2q/n}.$$ Thus, constant-order last-iterate risk requires $q\ge (n/4)\log n-O(n)$ for every admissible instance. This restriction follows from the upper bound for the entire loss class, not from the particular construction. **However, a milder separation can occur much earlier.** By refining the weak-curvature construction in Corollary 3.2, we establish the following result under the same assumptions and output rules. At $q=n\log\log n+O(1)=o(n\log n)$, the three outputs of the same PGD trajectory satisfy: | **Output rule** | **Expected excess risk** | | --- | :---: | | Last iterate $w_T$ | $\Theta\bigl(n^{-1/2}(\log\log n)^2\bigr)$ | | Independent uniform checkpoint $w_J$ | $\Theta\bigl(n^{-1/2}\log\log n\bigr)$ | | Full parameter average $\bar w_T$ | $\Theta(n^{-1/2})$ | At this earlier training time, the full parameter average still achieves the optimal $n^{-1/2}$ risk, while the last iterate and uniform checkpoint already have worse risk rates. This shows that the choice of output affects how long training can continue while maintaining optimal statistical accuracy. We have added this result as Corollary 3.3 in Section 3 and provided its proof and the constant-risk converse in Section G.9.
Reviewer_GXTsOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the worst-case expected population excess risk of projected gradient descent on the unit ball for convex, globally Lipschitz and smooth sample losses. While classical bounds recover the optimal rate by choosing a suitable stopping time, this paper characterizes how risk changes throughout training. At unit smoothness, it shows that the optimal 1n\frac{1}{\sqrt{n}} rate persists from ηT≍n\eta T \asymp \sqrt{n} through ηT≍n\eta T \asymp n.

Critical strengths
  1. . Earlier stability results already assumed smoothness and depended on training time. This paper improves on the classical (q/n) rates .

  2. Matching upper and lower bounds clarify when prolonged training can genuinely worsen population risk. The fixed-instance constructions strengthen the distinction between a worse guarantee and actual deterioration along a trajectory.

Critical weaknesses
  1. In the higher-curvature regime, the matching lower bound requires dimension growing roughly in cubic with the sample size. It remains unclear whether the same risk growth occurs in substantially lower dimensions.

  2. The assumptions are slightly too strict. For example, what about unconstrained GD or SGD?

  3. The improved rate relies on cancellations between sample-dependent terms, but the central quantities and detailed argument are deferred to the appendix. A worked example showing how these cancellations improve the classical bound would make the contribution easier to understand and verify.

Questions for authors
  1. The matching lower bounds require very high dimension in the higher-curvature regime, leaving sharpness in lower dimensions unresolved. Can the authors comment on this ?

  2. The main cancellation argument is difficult to assess from the main text and would benefit from a worked example.

4 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/2)

Thank you for your thoughtful feedback and for recognizing the value of our sharper risk bounds and matching lower-bound constructions. We appreciate your positive assessment of our contributions. We have revised the manuscript and highlighted all changes in blue. Our point-by-point responses are provided below.


Q1: In the higher-curvature regime, the matching lower bounds require dimension growing roughly cubically with the sample size, leaving sharpness in substantially lower dimensions unresolved. Can the authors comment on this?

A: Thank you for raising this important question. We have strengthened our matching lower bound, reducing the sufficient dimension from O(n3log⁡2n)O(n^3\log^2 n) to O(n2log⁡3n)O(n^2\log^3 n) in the higher-curvature regime, while preserving the sharp curvature–time risk law in Theorem 2.1. The new construction also preserves the matching persistent-overfitting guarantees of Theorem 2.4 for both the last iterate and the full parameter average. This improvement is achieved through a refined multiscale encoding and compression argument. Thus, the same sharp risk growth can occur in substantially lower dimensions, showing that cubic dimension is not necessary. We have incorporated the improved dimension bound into Theorems 2.1 and 2.4 in Sections 2.2–2.3. The new construction and complete proof are provided in Appendix F, with the completion of both results in Section F.8.


Q2: The assumptions are slightly too strict. For example, what about unconstrained GD or SGD?

A: Thank you for this question. Yes, our main theoretical results can be extended to unconstrained GD and SGD under appropriate conditions. For unconstrained GD, our original manuscript already establishes in Lemma J.2 that uniformly bounded initial empirical sublevel sets containing a population minimizer are sufficient to extend our analysis. Under this condition, we recover the same curvature–time excess-risk upper bounds as our main result (Theorem 2.1). We have now made this existing extension explicit in Section 2.2, in the paragraph “Other update rules”.

For SGD, we now further extend our interaction–dissipation framework to single-sample and mini-batch updates. At unit smoothness, the full parameter average satisfies

\lesssim \min\\{1,q^{-1}+n^{-1/2}+qn^{-3/2}+\eta+\eta q/n\\}.$$ Thus, when $\eta\le n^{-1/2}$, we recover the same upper risk rate as our main result (Theorem 2.1). More generally, sufficiently small stochastic steps preserve the full curvature–time upper bound. We also obtain matching worst-case bounds under a stronger small-noise condition (Theorem L.11 in Section L.8). This step-size restriction is substantive, rather than merely technical. We construct a one-dimensional smooth convex example in which SGD with $\eta=1$ has bounded iterates yet incurs $\Omega(1)$ excess risk for the full parameter average at $q=n$. In contrast, full-batch PGD guarantees $O(n^{-1/2})$ excess risk. This demonstrates why an unrestricted extension to SGD is not possible. The upper bounds and their proofs are provided in Sections L.3–L.7, the matching-law transfer in Section L.8, and the counterexample in Section L.9.
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/2)

Q3: The main cancellation argument is difficult to assess from the main text and would benefit from a worked example.

A: Thank you for this helpful suggestion. We have added a worked comparison to Remark 2.3 to clarify where our improvement comes from. Classical stability analysis (e.g., Hardt et al., 2016) bounds each sample-replacement perturbation in the worst case and accumulates these bounds using nonexpansiveness, yielding an O(q/n)O(q/n) sample-reuse term. Our analysis instead uses the negative square terms contributed by the losses shared by the original and replaced runs to absorb the signed sample interactions.

For a two-sample interaction, let xx denote the corresponding parameter component and b1,b2b_1,b_2 the corresponding gradient components. All norms and inner products below are in L2L^2. After suppressing the common factor η/n2\eta/n^2, an upper bound for its contribution to the one-step recursion is H12=−4⟨b1+b2,x⟩−∑i=12∣bi∣2H_{12}=-4\langle b_1+b_2,x\rangle-\sum_{i=1}^2|b_i|^2. Applying the classical separate worst-case estimate amounts to discarding the negative squares. Since ε=∣x∣≤1\varepsilon=|x|\le1 and ∣bi∣≤1|b_i|\le1, we obtain

\le4(|b_1|+|b_2|)\varepsilon \le8\varepsilon.$$ Our analysis instead completes the square: $$\begin{aligned} H_{12} =\sum_{i=1}^2\left(4|x|^2-|b_i+2x|^2\right) =8\varepsilon^2-\sum_{i=1}^2|b_i+2x|^2 \le8\varepsilon^2. \end{aligned}$$ Since $\varepsilon\le1$, this gives a tighter bound. The same cancellation applies to every higher-order interaction component. Each component contributes at most $8\eta|X_A|^2/n^2$, independently of its order. By orthogonality, $\sum_{|A|\ge2}|X_A|^2\le1$. Thus, all higher-order components together contribute at most $8\eta/n^2$. The first-order components contribute at most $4\eta/n^{3/2}$. Including the discretization term, our per-step bound is $O(\eta/n^{3/2}+\eta/n^2)$. Summing over $T=q/\eta$ updates yields an $O(q/n^{3/2})$ sample-reuse term, improving on the classical $O(q/n)$ bound.
Reviewer_GXTsOpenReview ↗

Acknowledgement

Thanks to the authors for their response. I am satisfied with the anwers and recommend acceptance which is reflected by my score.

AuthorsOpenReview ↗

Thank You for Your Encouraging Feedback

Thank you for your positive assessment and recommendation for acceptance. We are very pleased that our responses have addressed your concerns. Your thoughtful comments were important in guiding our revisions and improving the manuscript. We are grateful for your careful review and encouragement.

Reviewer_u2FsOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies the population risk of gradient descent on the same finite training sample. The authors extend the bound on the cumulative step size from nn to n3/2n^{3/2}, that still achieves the lower bound on the required algorithm complexity. In the nonconvex setup the authors also provide bounds for last iterate, uniformly sampled iterate and the full parameter average point.

Critical strengths

1)The cumulative step size analysis seems appealing, and may be adopted in other areas.

Critical weaknesses

1)No numerical experiment justifying the assumptions and/or the results were provided.

2)1-Lipschitzness and gradient smoothness (with LL \geq 1) on the Euclidean unit ball are strong assumptions, especially given the convexity.

3)Generalization bounds are usually algorithmic agnostic, but in the manuscript PGD is considered.

4)The paper is challenging to read.

Questions for authors

1)Can the assumptions be relaxed?

2)What changes after adding stochasticity?

3)Can the bound be transferred to any first-order method under given cumulative step size? What is the block?

4 comments
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 1/3)

Thank you for your constructive feedback and for recognizing the value of our cumulative-step analysis. We have revised the manuscript and highlighted all changes in blue. Our point-by-point responses are provided below.


Q1: 1-Lipschitzness and gradient smoothness (with L≥1L\ge1) on the Euclidean unit ball are strong assumptions, especially given convexity. Can the assumptions be relaxed?

A: Yes. We establish new results that relax Lipschitzness. For convexity, Theorem 3.1 in our original manuscript already extends our results to nonconvex losses with bounded negative curvature. However, smoothness cannot be removed while preserving the same risk law.

Lipschitzness. We establish a new extension showing that the complete sharp curvature–time law in Theorem 2.1 remains unchanged when uniform Lipschitzness is replaced by the weaker condition

\sup_{w\in B_d}\|\nabla f(w,Z)\|^2 \right]\le 1.$$ This condition allows unbounded sample gradients. Similar second-moment assumptions have been used in prior work [1, 2]. Importantly, the matching upper and lower bounds remain unchanged for all $L\ge1$. At $L=1$, even $\mathbb{E}\|\nabla f(0,Z)\|^2\le1$ suffices. We have summarized these extensions in Section 2.2 and provided their formal statements and proofs in Section L.1 (Theorem L.1 and Corollary L.2). **Convexity.** More specifically, Theorem 3.1 gives sharp excess-risk laws under $\rho$-weak convexity for the last iterate, a uniformly sampled iterate, and the full parameter average. These laws recover the convex case when $\rho=0$. **Smoothness.** Proposition K.2 shows that nonsmooth convex losses can incur $\Theta(1)$ excess risk at $q\asymp n$ under constrained subgradient flow, whereas the 1-smooth class still has $\Theta(n^{-1/2})$ worst-case risk at the same horizon. The unit radius is only a normalization, and the results extend to Euclidean balls of arbitrary radii by rescaling (Section K.4). --- **Q2: Generalization bounds are usually algorithm-agnostic, but the manuscript considers PGD. Can the bound be transferred to any first-order method with the same cumulative step size? What is the block?** **A:** Thank you for this question. Our analysis builds on algorithmic stability, a well-established framework for algorithm-dependent generalization guarantees (see *Foundations of Machine Learning* [3, Chapter 14] and *Understanding Machine Learning* [4, Chapter 13]). The cumulative step size alone **is insufficient to guarantee comparable excess risk across different first-order methods**, as the counterexample below shows. As a simple counterexample, consider $f(w,z)=-w_1$ on the unit ball in dimension $d=n$, with $\eta=1$ and $T=\lceil\sqrt{n}\rceil$. PGD reaches the optimum in one step, whereas uniform randomized coordinate descent still has expected excess risk $(1-1/n)^T=1-o(1)$. In contrast, Theorem 2.1 guarantees $O(n^{-1/2})$ worst-case excess risk for PGD at the same cumulative step size. The key obstacle is that optimization error and sample-replacement stability depend on the algorithm's update rule, not just its cumulative step size. Our general analysis framework (Eq. (5) and Theorem 4.1) has already been applied to other learning methods, including randomized coordinate descent (Theorem 4.5) and ridge-regularized empirical risk minimization (Theorem 4.3). We have clarified this algorithm dependence in Section 2.2 and provided the counterexample in Section L.10. --- **Q3: What changes after adding stochasticity?** **A:** Thank you for this question. Our original manuscript already considers stochasticity through randomized coordinate descent (Theorem 4.5). We further extend our key interaction–dissipation technique to **SGD**, where randomness comes from sampling training examples rather than coordinates. Under bounded trajectories, we establish a new excess-risk bound for the full parameter average. At unit smoothness, $$\mathbb{E}[F(\bar w_T)-F^\star] \lesssim \min\left\\{ 1,\frac1q+\frac1{\sqrt n} +\frac q{n^{3/2}}+\eta+\frac{\eta q}{n} \right\\}.$$ Thus, with a sufficiently small stepsize ($\eta\le n^{-1/2}$), **we recover the original PGD risk upper bound.** This extension also covers mini-batch SGD for all $L\ge1$, provided the stepsize respects smoothness and the effective per-sample step is sufficiently small. However, some control of the stepsize is necessary. We construct a one-dimensional smooth convex example where SGD with $\eta=1$ incurs $\Omega(1)$ excess risk at $q=n$, even for the full parameter average and with all iterates bounded. In contrast, PGD retains $\Theta(n^{-1/2})$ worst-case risk at the same horizon. This shows that stochasticity can change the actual risk, not merely the analysis. We have summarized these results in Section 2.2, with the upper bounds and proofs in Sections L.3–L.7 and the counterexample in Section L.9 (Proposition L.12).
AuthorsOpenReview ↗

Thank You for Your Feedback (Part 2/3)

Q4: No numerical experiment justifying the assumptions and/or the results were provided.


A: Thank you for this helpful suggestion. Following your advice, we conducted five numerical experiments within the short rebuttal period and added them to Appendix B (pp. 16–20). They provide numerical support for our main conclusions on risk plateaus and delayed deterioration, output separation, and the role of dissipation in obtaining tighter estimates. We promise to add further experiments in the final version. OpenReview replies do not support figures, so we report key numerical results below and provide the plots in the revised manuscript.

(1) Risk plateau and later deterioration. For convex, 11-Lipschitz, 11-smooth losses, the table reports mean excess risk of the full parameter average over 256 independent training sets per sample size. Values are in units of 10−410^{-4}.

Sample size nnq=nq=nq=4096n3/2q=4096n^{3/2}
2162^{16}4.69610.969
2182^{18}2.3578.605
2202^{20}1.1807.423
2222^{22}0.5916.831

At q=nq=n, risk is approximately 0.12/n0.12/\sqrt{n}, consistent with the statistical scale in Theorem 2.1, although the classical certificate is already constant-order. The later increase on each fixed instance illustrates the deterioration in Theorem 2.4. Our explicit risk bound at q=nq=n is smaller than the classical bound by factors of 72.3–584.3, without fitting constants to the data. Figures 3–5 show the full risk curves, compare the two bounds, and confirm that the plateau and later increase persist across the tested parameter settings. Table B.1 reports 9595\\% confidence intervals for the risk estimates.

(2) Output separation. Under weak convexity ρ=1/n\rho=1/n, the three outputs of the same PGD runs have the following mean excess risks at the horizon specified in Eq. (B.2). Values are in units of 10−610^{-6}.

Sample size nnLast iterateUniform checkpointFull parameter average
2162^{16}181.92512.7928.003
2182^{18}178.8338.0453.389
2202^{20}177.5926.2411.738
2222^{22}177.0515.4161.062

At n=222n=2^{22}, parameter averaging gives approximately 1/167 of the last-iterate risk. This comparison illustrates the qualitative output separation in Theorem 3.1 and Corollary 3.2. Figure 6 shows the complete trajectories, and Table B.2 provides confidence intervals.

(3) How dissipation tightens the estimate. The following estimates use identical iterates and gradients at n=12n=12, q=64q=64.

TreatmentBound on the higher-order contribution (×10−4\times10^{-4})
Drop dissipation and take absolute values1.069
Drop dissipation but preserve signs0.802
Use dissipation and complete squares0.405

The bound obtained by completing squares is smaller by factors of 2.64 and 1.98 than the absolute-value and signed baselines, respectively. Figure 7 illustrates the absorption step in Lemma C.1 and Theorem 4.1: the negative dissipation term offsets interactions that would otherwise enlarge the estimate.

(4) Sensitivity to replacing one training example. At q=nq=n, the measured mean squared change in the output is 5.572×10−65.572\times10^{-6} for n=216n=2^{16} and 8.768×10−88.768\times10^{-8} for n=222n=2^{22}. Measurements at all four sample sizes lie below the bound in Eq. (6), consistent with the stability estimate used to control excess risk. Figure 8 in Appendix B.4 presents the complete comparison.

(5) Readout smoothness. At fixed sample size and cumulative step size qq, increasing LL from 11 to 256256 raises risk from 0.0010970.001097 to 0.0139320.013932, while the readout's training gradients remain zero. Figure 9 in Appendix B.5 illustrates how curvature affects population risk within this family, consistent with the smoothness-dependent risk conversion in our analysis.

AuthorsOpenReview ↗

Thank You for Your Feedback (Part 3/3)

Q5: The paper is challenging to read.


A: Thank you for this feedback. Following your suggestions, we have substantially revised the manuscript to make the main results and proof ideas easier to follow. The main changes are summarized below.

AspectWhat we revisedWhere to find it
Proof intuitionWe expanded the proof sketches for the two main theorems and added a worked example showing how cancellation tightens the bound.Sections 2.2–2.3 and 3, especially Remarks 2.3 and 2.6 (pp. 4–6).
Interpretation of the resultsThe discussion now explains the risk plateau, later deterioration, and why the curvature transition occurs at L≍nL\asymp\sqrt n.Section 2.2, Remark 2.2 (p. 3).
Comparison with prior workTable 1 presents the published bounds alongside our sharp risks for the same learners and budgets.Section 4.2, Table 1 (p. 9).
Numerical illustrationsFive numerical experiments illustrate risk evolution, output separation, and the role of dissipation.Appendix B (pp. 16–20).
Appendix organizationRedundant appendix material has been removed. A compact proof roadmap and a one-page notation reference help readers locate the arguments.The appendix roadmap (p. 14), Appendix A (p. 15), and the streamlined proof appendices.

Please see the corresponding locations in the revised manuscript. New and revised text is marked in blue to make these changes easy to locate.

References

[1] Tianyi Lin, Zeyu Zheng, and Michael I. Jordan. Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization. NeurIPS, 2022.

[2] Guy Kornowski and Ohad Shamir. An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization. JMLR, 25(122):1–14, 2024.

[3] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2018.

[4] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.

AuthorsOpenReview ↗

Thank You for Your Time and Consideration

Thank you very much for your time and consideration. Your feedback is extremely valuable to us and has been instrumental in helping us improve the quality of our paper. As the discussion period is drawing to a close, we would be sincerely grateful if you could let us know whether our responses have adequately addressed your concerns, or whether there are any points that would benefit from further clarification. We fully understand that you may have a busy schedule, and we would greatly appreciate any further thoughts or suggestions you might be willing to share. Thank you again for your patience and generous consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Contributions and Review Discussion

Dear Area Chair,

Thank you for overseeing the review of our submission. We summarize the outcome of the discussion below. Reviewers hGqf, GXTs, and u2Fs gave ratings of 3, 3, and 2, with confidence scores of 2, 2, and 1, respectively. Both hGqf and GXTs expressed support for acceptance. Reviewer u2Fs’s remaining concern was whether the 1-Lipschitz assumption could be relaxed to allow an arbitrary Lipschitz constant. We established this extension in our follow-up response and believe it fully addresses the concern.


Our Core Contributions

We establish a sharp curvature–time law for projected gradient descent in Theorem 2.1. Our matching upper and lower bounds determine how the worst-case expected excess population risk depends on smoothness and training time. This result resolves the open question posed by Livni (2024) on the sample complexity of smooth gradient descent when classical stability bounds can no longer certify generalization.

For unit smoothness and q≍nq\asymp n, classical stability gives only a constant-order bound (Hardt et al., 2016), while we prove that the worst-case risk remains statistically optimal at Θ(n−1/2)\Theta(n^{-1/2}). Our matching upper and lower bounds show that constant-order overfitting begins at q≍n3/2q\asymp n^{3/2}. This is a factor of n\sqrt n later than the horizon at which the classical bound becomes constant. This improvement comes from our key technical innovation, an interaction–dissipation principle that balances higher-order sample interactions against the stabilizing effect of losses unchanged by sample replacement. Reviewer hGqf described this principle as “an important supplement to stability theory.” Reviewer GXTs also recognized the improvement over the classical q/nq/n rate and highlighted our fixed-instance construction, which shows that continued training can cause population risk to deteriorate on a single problem.

Reviewer hGqf also highlighted the sharper guarantees this principle yields in other learning problems. Each comparison in Table 1 of the revised manuscript uses the same instance, algorithm, parameters, and output rule.

Prior workSame instance, algorithm, parameters, and outputPublished bound (capped)Our sharp riskGap
Lei et al. (2020), Thm. 6Pairwise regularized ERM on instance (J.1), with output AλA_\lambda and λ=c/n\lambda=c/n for fixed c≥8c\ge8Θ(1)\Theta(1)Θ(n−1/2)\Theta(n^{-1/2})Θ(n1/2)\Theta(n^{1/2})
Wu et al. (2025), Thm. 3Pairwise scalar randomized coordinate descent on instance (H.18), last iterate. ν=0\nu=0, D=66nD=66n, η=1\eta=1, and q=T/D≍n4/3q=T/D\asymp n^{4/3}Θ(1)\Theta(1)Θ(n−2/3)\Theta(n^{-2/3})Θ(n2/3)\Theta(n^{2/3})
Nikolakakis et al. (2023), Thms. 10–11Full-batch GD on instance (I.25), last iterate. Fixed Zipf source pj∝j−3/2p_j\propto j^{-3/2}, η=1/2\eta=1/2, and q=ηT≍n7/6q=\eta T\asymp n^{7/6}Θ(1)\Theta(1)Θ(n−1/2)\Theta(n^{-1/2})Θ(n1/2)\Theta(n^{1/2})

Reviewer u2Fs’s question about the Lipschitz assumption

Reviewer u2Fs’s remaining concern was whether our results extend from 1-Lipschitz losses to losses with an arbitrary Lipschitz constant. We normalized the Lipschitz constant to 1 in the original manuscript to make the effects of smoothness and training time easier to see. In our follow-up response to u2Fs, we gave matching upper and lower bounds on the worst-case expected excess population risk for any combination of positive values for the Lipschitz constant, the smoothness constant, and the ball radius. Setting the Lipschitz constant and ball radius to 1 recovers the full result of Theorem 2.1 in the original manuscript. We also proved matching bounds under the weaker assumption that the maximum gradient norm over the ball has a finite second moment. We believe these results fully address Reviewer u2Fs’s concern.

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.