- 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 ) and the loss smoothness constant jointly determine the worst-case expected excess risk of projected gradient descent (PGD) on the unit ball. Within the class of convex, 1-Lipschitz, -smooth losses, the authors establish a complete curvature-time risk law (Theorem 2.1): the worst-case risk is , where is an -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 cost in stability analysis to (when ). Consequently, the optimal risk persists until , while constant-order risk appears only at ; 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 -weakly convex loss class, the last iterate and the full parameter average satisfy different sharp risk laws (Theorem 3.1). On a single -dimensional instance, the later-time risks of the three outputs become , , and , 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 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 to . 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 , 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- 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 . 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 ? 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 risk at an earlier time, while the sharp separation into , , and is demonstrated only at the much later time . 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
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, -Lipschitz, -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 .
| Sample size | ||
|---|---|---|
At , risk is approximately , 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 is smaller than the classical bound by factors of –, 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 confidence intervals for the risk estimates. For the time scale of deterioration, Figure 4(b) shows nearly coincident population readout curves against , 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 , 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 .
| Sample size | Last iterate | Uniform checkpoint | Full parameter average |
|---|---|---|---|
At , parameter averaging gives approximately 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 , .
| Treatment | Bound on the higher-order contribution () |
|---|---|
| Drop dissipation and take absolute values | |
| Drop dissipation but preserve signs | |
| Use dissipation and complete squares |
The bound obtained by completing squares is smaller by factors of and 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 , the measured mean squared change in the output is for and for . 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 , increasing from to raises risk from to , 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.
Thank You for Your Feedback (Part 3/3)
Q4: The low-curvature and high-curvature regimes are separated by the threshold . 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 ?
A: Thanks. The threshold 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 requires , while keeping the additional risk below requires in the low-curvature regime. These two time scales coincide precisely when . Consequently, Theorem 2.1 gives the sharp endpoint of the optimal-risk plateau:
When , the optimal risk persists until . When , the optimal-risk plateau ends at . 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 risk at an earlier time, while the sharp separation into , , and is demonstrated only at the much later time . 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 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 :
\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.
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.
In Remark 2.3, we added the following explanation for L=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), while first-order terms contribute O(η/n3/2).” The proof then sums this bound over the updates and applies Eq. (5) to obtain the O(q/n3/2) sample-reuse term.
In Section 3, the proof sketch after Theorem 3.1 now includes: “Let vt denote the mean squared replacement distance at step t. The absorption estimate for the convexified losses gives vt+1≤(1+ηρ)2vt+Cη/n3/2 for the original updates.” The sketch derives both response kernels and explains how the output rules differ. The uniform checkpoint averages vt, whereas the full parameter average has the bound (T−1∑tvt)2 by the L2 triangle inequality. We also explain the additional O(ρ) 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.
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.