- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies the algorithmic stability of preconditioned gradient descent, including deterministic, stochastic, and projected variants. It decomposes the displacement between neighboring-data trajectories into limiting sensitivity, transient drift, and stochastic fluctuations. The resulting stability estimates are used to derive generalization and excess-risk bounds under regularized and constrained settings.
Critical strengths
The paper addresses how preconditioning affects finite-time and limiting stability. It considers both deterministic and stochastic updates, includes projected methods, and connects the stability analysis to generalization and excess risk.
Critical weaknesses
The presentation introduces many auxiliary quantities, making the main results difficult to follow. The necessity of the decompositions and the roles of individual terms in the final bounds need clearer explanation. The exposition also devotes substantial space to similar algorithmic formulations while providing limited discussion of the results.
Questions for authors
1.Section 2 introduces many auxiliary quantities before their roles become clear. Readers must repeatedly refer back to these definitions to understand subsequent propositions and theorems. Additional quantities with similar names are introduced later, further increasing the cognitive burden. The authors should reconsider which variables are essential, introduce intermediate quantities closer to where they are used, and consolidate repeated definitions. A concise notation table would also improve readability.
2.After expanding the notation, the decompositions in Propositions 3.4 and 3.6 lead to fairly complicated stability bounds in Theorems 3.5 and 3.7. Although separating transient effects from limiting sensitivity is relevant to the paper’s motivation, the necessity of each additional component is insufficiently explained. What does each component reveal that a simpler coupling or convergence-based argument cannot capture? The brief discussions following the results do not adequately explain which terms dominate at different training stages or how they depend on the sample size, step size, and preconditioner. The authors should provide a clearer comparison with simpler bounds and explain the benefit obtained from the added complexity.
3.The exposition devotes substantial space to closely related algorithmic formulations while giving comparatively limited attention to interpreting the main results. In particular, PGD and PSGD share the same preconditioned update structure and primarily differ in whether the gradient is evaluated using the full dataset or a randomly sampled observation. Their presentation could therefore be consolidated. The assumptions would also benefit from clearer organization: A3.2 and A4.1 have overlapping regularity requirements, although they apply to different domains and place strong convexity on different components. These shared requirements and substantive differences should be stated explicitly. The space saved could support a more thorough discussion of the propositions and theorems.
4.The benefit of the refined analysis needs clearer justification. A direct comparison with the empirical minimizers already gives , recovering preconditioner-independent limiting stability. Please identify the regimes in which the proposed bounds substantially improve upon this baseline and explain the role of the additional Hessian-Lipschitz assumption.
4 comments
Questions 2 and 4
The authors should provide a clearer comparison with simpler bounds and explain the benefit obtained from the added complexity.
Write the bound from Theorem 3.5 as where , and are given in equation (3.4).
An argument using the convergence to the two empirical minimizers and the ERM stability gives Since , a sufficient condition to ensure is This shows the advantage of our bound for small values of : the improvement is favored by sufficiently large sample sizes and/or small values of .
In the current revised manuscript, we have kept the original statement of our results. Yet, if the reviewer thinks that this compact version of the bound is more understandable, then we will be happy to incorporate it into the revised version of the paper.
Similarly, the standard norm-based coupling estimate converges to , whereas our bound converges to . Therefore our bound eventually improves upon this estimate when .
Therefore the bound obtained from our decomposition is relevant both for small values of and for large values of . For intermediate , there is no general comparison between our bound and the two basic ones: the quality of each one depends on the step size, the value of , the amount of noise, etc.
For PSGD, additional stochastic terms appear. The bound from Theorem 3.7 reads
= \frac{2G}{\mu n} +\frac{1}{\sqrt n}\mathcal{O}(t\rho^{t-1}) +\sqrt{\frac{\gamma}{n}} \left[ c_3 +c_4\left( \frac{c_5}{\sqrt n} +\sqrt\gamma \right) \right]\sqrt{1-\rho^{2t}}.$$ This bound is valid for initial steps and once again has a better dependence in $n$ than what naive bounds can achieve. The strongest quantitative improvements are established in the regularized deterministic setting. Stochasticity and active projection introduce additional residuals that can make the decomposition-based estimates more conservative, as also illustrated in Figure 2. > *explain the role of the additional Hessian-Lipschitz assumption* The Hessian Lipschitzness assumption is essential for our refined control of the nonlinear remainder in our finite-time decomposition while preserving its $1/n$ scaling. This assumption is quite classical in works that give refined control on SGD's errors [1,2,3]. Without this assumption, we establish in Appendix A.3 that $\|\eta_k\| \leq 2LD_\Sigma\rho^k$, which still vanishes asymptotically but does not retain the explicit $1/n$ factor. **Question 3.** We agree that the deterministic and stochastic algorithms share the same underlying preconditioned update structure. We have revised the paper to only present the stochastic algorithms, while deferring the deterministic algorithms to the appendix. Regarding the assumptions, the main distinction is where strong convexity is imposed. In the regularized setting, it is provided by a common data-independent regularizer, while bounded gradients are assumed for the individual data losses. In the constrained setting, the corresponding regularity and convexity conditions are imposed on the losses over the feasible set $K$. We have added a remark in the revised paper to make these differences explicit. If the reviewer has any suggestion as to how we could make this clearer, we will be happy to incorporate them in the paper. --- We thank the reviewer for the constructive feedback on the presentation that will greatly help us improve the manuscript. We incorporated the suggestions in the revised manuscripts. If the reviewer has additional suggestions to further improve the paper, we will be happy to add them. --- [1] M. Sheshukova et al., "Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation." International Conference on Learning Representations, 2025. [2] Ilja Kuzborskij, Christoph Lampert, "Data-Dependent Stability of Stochastic Gradient Descent", ICML 2018. [3] Y. Zhang et al., "Stability of SGD: Tightness analysis and improved bounds", UAI 2022.Post-Rebuttal Assessment
Thanks for the authors' detailed response. It addresses part of my concern. After reading other reviewers' comments, I still think that the discussion of the propositions and theorems is not sufficient. I will hold my score.
We revised the presentation following your comments: auxiliary quantities are introduced closer to their use, a notation table has been added, repeated algorithm descriptions have been reduced, and the differences between the regularized and constrained assumptions are now explicit.
Our response also explains the role of each component of the decomposition and gives quantitative comparisons with simpler bounds. In particular, we identify a regime where preserving the scaling of the transients improves upon the convergence-based estimate, and show eventual improvement over the standard coupling estimate when . These comparisons directly address the question of what the additional complexity provides.
Could you identify which proposition or theorem still needs further explanation, and what specific result or comparison you would need to consider your concern addressed? If the issue is the interpretation of a particular term or its role during training, can you indicate which one? You also refer to the other reviews without more precision: specifying more precisely which concerns you share with other reviewers would allow us to improve the quality of our manuscript by addressing these in priority.
We thank the reviewer for their careful reading and constructive suggestions. We agree that the presentation can be simplified, notably regarding the interpretation of the decomposition we propose: we have extended this discussion in the revised manuscript, and thank the reviewer of their valuable feedback.
We address the questions below.
Weakness and Question 1.
We agree that this paper introduces many variables, and that the presentation could therefore be improved. We have addressed this issue in the revised paper, by introducing the new variables when they are first used instead of all at once at the beginning.
We have also addressed this issue in the revised paper, by adding explanations of the different terms: we describe these clarifications in the response to Question 2.
We have removed some of the algorithmic formulations in the revised papers, stating which are the differences between the variants of the algorithm. We have also added additional explanations and comments throughout the paper.
We have added a table with the main notations in the appendix to improve readability, and to facilitate the understanding of the notations.
Question 2.
The main purpose of the decomposition is to distinguish the different mechanisms generating the displacement between neighboring trajectories, rather than only bounding its magnitude.
For example, in the regularized deterministic setting, Proposition 3.4 gives the exact identity
-\frac{\gamma}{n}\sum_{k<t}A^{t-1-k}P(\delta_k-\delta^\star) -\gamma\sum_{k<t}A^{t-1-k}P\eta_k.$$ Each component has a distinct interpretation: - **Intrinsic sensitivity.** The first term, $B_t=(I-A^t)\Delta^\star$ describes the response to the replacement perturbation through the linearized dynamics. It starts at zero and converges to the actual displacement between the empirical minimizers. Its evolution depends explicitly on $P$ through $A=I-\gamma PH$, while its limiting value $\Delta^\star$ is independent of $P$. - **Replacement drift.** The second term accounts for the difference between the replacement-gradient perturbation along the trajectories and its value at the empirical minimizers. It quantifies an effect that disappears as the trajectories approach their respective minimizers. - **Hessian drift.** The third term measures the deviation of the nonlinear gradient dynamics from the linearization around the empirical minimizers. Hessian Lipschitzness allows us to control this term while preserving its $1/n$ dependence. The decomposition therefore provides information about different stages of training. (Continued below)