acceptodds
Under review as a conference paper at ICLR 2027

Analysis of the Stability of Preconditioned Stochastic Gradient Descent

Abstract

We study the algorithmic stability of preconditioned gradient descent (PGD) for empirical risk minimization. Although preconditioning affects finite-time stability, existing analyses fail to explain PGD's long-term behavior. We propose a refined stability analysis that separates the effect of preconditioning on transient optimization dynamics from PGD's intrinsic stability, recovering the long-term behavior obscured by standard contraction-based analyses. For deterministic updates, our decomposition establishes non-asymptotic bounds, while showing that long-term stability is independent of the preconditioner. For stochastic updates, we establish an analogous decomposition with an additional term that retains a dependence on the preconditioner. In both cases, each contribution is of order , up to variance terms and transient terms that decay with the number of iterations. Our conclusions hold in two regimes. First, the regularized setting, where individual losses are Lipschitz and the empirical objective is regularized by a sample-independent strongly convex function. Second, projected PGD for constrained problems, showing that projection introduces only additional residual terms. Finally, we use these stability estimates to derive expected generalization bounds and excess-risk guarantees for regularized and constrained empirical risk minimization.

Primary area:
learning theory
Keywords:
Preconditioned Gradient Descent, Algorithmic Stability, Generalization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_GiM8OpenReview ↗
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 ∥Δt∥≤2G/(μn)+DΣρt\|\Delta_t\|\leq 2G/(\mu n)+D_\Sigma\rho^t, 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

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.

The presentation introduces many auxiliary quantities, making the main results difficult to follow.

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.

The necessity of the decompositions and the roles of individual terms in the final bounds need clearer explanation.

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.

The exposition also devotes substantial space to similar algorithmic formulations while providing limited discussion of the results.

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.

A concise notation table would also improve readability.

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 necessity of each additional component is insufficiently explained

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)

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 Ut=bt+c1t+c2t2nρt−1,U_t=b_t+\frac{c_1t+c_2t^2}{n}\rho^{t-1}, where bt=min⁡(2γtGλmax⁡(P)/n, 2G/(μn))b_t = \min\left( 2\gamma t G \lambda_{\max}(P) / n, \ 2G/(\mu n) \right), and c1,c2c_1,c_2 are given in equation (3.4).

An argument using the convergence to the two empirical minimizers and the ERM stability gives Mt=2Gμn+DΣρt.M_t=\frac{2G}{\mu n}+D_\Sigma\rho^t. Since bt≤2G/(μn)b_t\leq 2G/(\mu n), a sufficient condition to ensure Ut<MtU_t<M_t is c1t+c2t2<nDΣρ.c_1t+c_2t^2<nD_\Sigma\rho. This shows the advantage of our bound for small values of tt: the improvement is favored by sufficiently large sample sizes and/or small values of tt.

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 Ct=2Gλmax⁡(P)μPn(1−ρt).C_t = \frac{2G\lambda_{\max}(P)}{\mu_Pn}(1-\rho^t). converges to 2Gμnλmax⁡(P)λmin⁡(P)\frac{2G}{\mu n} \frac{\lambda_{\max}(P)}{\lambda_{\min}(P)}, whereas our bound converges to 2Gμn\frac{2G}{\mu n}. Therefore our bound eventually improves upon this estimate when κ(P)>1\kappa(P)>1.

Therefore the bound obtained from our decomposition is relevant both for small values of tt and for large values of tt. For intermediate tt, 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 nn, 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.
Reviewer_GiM8OpenReview ↗

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 1/n1/n scaling of the transients improves upon the convergence-based estimate, and show eventual improvement over the standard coupling estimate when κ(P)>1\kappa(P)>1. 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.

Reviewer_vtsfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the algorithmic stability of preconditioned gradient descent (PGD) and its stochastic counterpart (PSGD). The authors propose a decomposition of the parameter displacement between neighboring datasets into an intrinsic stability term and additional transient or stochastic contributions. Based on this decomposition, they derive finite-time stability bounds for regularized and constrained optimization, covering both deterministic and stochastic updates. The analysis further leads to generalization and excess-risk bounds. Numerical experiments on regularized logistic regression compare the proposed bounds with standard coupling and convergence-based estimates.

Critical strengths
  1. The proposed decomposition provides a useful characterization of finite-time stability, offering a more refined understanding of stability dynamics across different iteration regimes, particularly during the transition from early-stage to asymptotic behavior.
  2. The analysis covers both deterministic and stochastic updates, including projected variants. The treatment of stochastic fluctuations and projection residuals introduces additional technical challenges, and the resulting decomposition offers a structured way to analyze their contributions to stability.
Critical weaknesses

The proposed decomposition offers a refined characterization of finite-time stability and shows a clear empirical advantage for regularized deterministic PGD in Figure 2(a). However, the improvement is more modest for regularized PSGD in Figure 2(b), and the proposed bounds can be more conservative than the existing alternatives in Figure 2(c)–(d). More broadly, the paper does not clearly characterize the conditions under which the decomposition-based bounds are provably tighter than standard coupling or convergence-based approaches. This makes it difficult to assess whether the refined decomposition offers substantial quantitative improvements over existing stability analyses.

Questions for authors
  1. The analysis relies on strong convexity, Lipschitz continuity, smoothness, and Lipschitz-continuous Hessians. Could the authors clarify which assumptions are essential for the main stability conclusions, and whether some of them can be relaxed? A more explicit comparison with prior results under comparable assumptions would help clarify the theoretical contribution.
  2. The analysis assumes a fixed, data-independent preconditioner PP. Could the authors clarify how a suitable PP should be chosen in practice, and to what extent the proposed theoretical bounds can capture the benefits of effective preconditioning?
  3. Figure 2 shows that the decomposition-based bounds become less tight when stochastic gradients and projection are introduced. Are there identifiable conditions under which the Theorems provide tighter bounds than standard coupling or convergence-based approaches?
  4. In Theorem 5.1, Equation (5.5) is described as "generalization bounds", whereas both inequalities bound the expected excess risk, E[R(xt)]−R(xopt)\mathbb{E}[R(x_t)]-R(x_{\mathrm{opt}}). The expected generalization-gap bound, ∣E[R(xt)−FS(xt)]∣≤Gβt|\mathbb{E}[R(x_t)-F_S(x_t)]|\leq G\beta_t, seems to have been established in the appendix. It would be clearer to explicitly state the generalization-gap guarantee if intended.

I would be willing to reconsider my rating if the authors provide convincing responses to the questions above.

4 comments

We thank the reviewer for their careful reading and constructive comments. We are pleased that the reviewer recognizes the usefulness of the finite-time decomposition and the technical challenges introduced by stochasticity and projection.

We have modified the paper to take into account the reviewers' comments, and highlighted all modifications in blue.

Question 1.

Our assumptions serve different purposes:

  • Strong convexity and smoothness ensure uniqueness of the empirical minimizers and contraction of the deterministic updates for sufficiently small step sizes. These properties allow us to control the optimization errors appearing in the transient terms. These are quite classical conditions, see for instance Hardt et al. (2016), or Vary et al. (2026).
  • Bounded gradients control the perturbation caused by replacing one observation. This is a standard assumption in uniform stability analyses, such as Hardt et al. (2016). It allows us to give upper-bounds that hold uniformly in the datasets. Vary et al. (2026) instead considers a bound on the covariance matrix of the stochastic gradients.
  • Hessian Lipschitzness is essential for our refined control of the nonlinear remainder in our finite-time decomposition while preserving its 1/n1/n scaling. This is a classical assumption in works that give refined control on SGD's errors [2,3,4], and is necessary to control the terms that appear in our exact decomposition of the instability. When this assumption does not hold, we establish in Appendix A.3 that ∥ηk∥≤2LDΣρk\|\eta_k\| \leq 2LD_\Sigma\rho^k, which still vanishes asymptotically but does not retain the explicit 1/n1/n factor.

Overall, the assumptions we make are standard, and have all been used in prior literature on the topic. Our contribution is a direct finite-time decomposition of the neighboring-trajectory displacement, including nonlinear, stochastic, and projection effects, with uniform control over neighboring datasets.

Question 2 (i).

The analysis assumes a fixed, data-independent preconditioner PP. Could the authors clarify how a suitable PP should be chosen in practice

Our results indeed require PP to be fixed and independent of the training sample, and aim to characterize its impact on stability. Regarding the choice of PP, one could choose data-dependent preconditioning (as suggested in [1, Chapter 5]) or adaptive preconditioners (like in Adam [2] or Shampoo [3]), such as those updated using gradients computed on the training data. The impact on stability of these procedure is very intricate, and is beyond the scope of our analysis. We believe extending our analysis technique to these method is a promising perspective for future work, thank you for the suggestion!

Question 2 (ii).

to what extent the proposed theoretical bounds can capture the benefits of effective preconditioning?*

Thank you for allowing us to clarify this critical point: a preconditioner that improves the conditioning of the preconditioned Hessian can actually improve stability. This can be seen from our novel decomposition of stability, as the preconditioner accelerates the decay of AtΔ⋆A^t\Delta^\star. Hence, this can accelerate the convergence of (i) the intrinsic component Bt=(I−At)Δ⋆\mathcal B_t=(I-A^t)\Delta^\star towards Δ⋆\Delta^\star and (ii) instability terms which decay in ρt\rho^t.

More precisely, this can be seen in our decomposition, which makes this dependence on PP explicit. In particular, the intrinsic sensitivity term is

\qquad A=I-\gamma PH,$$ which depends on the spectrum and eigendirections of $PH$. Specifically, if $P$ compensates for ill-conditioning of $H$, this can be much faster. The same idea applies to other terms in our decomposition, whose decay depends on the eigenvalues of $PH$. We have added this discussion to the revised manuscript. (Continued below)

Question 3 and Weakness.

In general, there is no uniform ordering between the different bounds. However, the regularized deterministic setting provides explicit regimes in which our decomposition improves upon the standard alternatives. Specifically, write the bound from Theorem 3.5 as Ut=bt+c1t+c2t2nρt−1,U_t=b_t+\frac{c_1t+c_2t^2}{n}\rho^{t-1}, where bt≤2Gμnb_t \le \frac{2G}{\mu n}, and c1,c2c_1,c_2 denote the corresponding nonnegative constants given in equation (3.4).

A direct argument using the convergence to the two empirical minimizers gives the upper-bound Mt=2Gμn+DΣρt.M_t=\frac{2G}{\mu n}+D_\Sigma\rho^t. Since bt≤2G/(μn)b_t\leq 2G/(\mu n), a sufficient condition for Ut<MtU_t<M_t is c1t+c2t2<nDΣρ.c_1t+c_2t^2<nD_\Sigma\rho. This identifies a small-tt regime where the transient terms in our decomposition provide a sharper bound. In particular, the improvement is favored by sufficiently large sample sizes and moderate drift constants.

The standard norm-based coupling estimate gives the upper-bound Ct=2Gλmax⁡(P)μPn(1−ρt).C_t = \frac{2G\lambda_{\max}(P)}{\mu_Pn}(1-\rho^t). This bound converges to 2Gμnλmax⁡(P)λmin⁡(P)\frac{2G}{\mu n} \frac{\lambda_{\max}(P)}{\lambda_{\min}(P)}, whereas our bound converges to 2Gμn\frac{2G}{\mu n}. Therefore, when κ(P)>1\kappa(P)>1, our bound eventually improves upon this particular coupling estimate.

These comparisons show that the refined decomposition can provide quantitative gains both by preserving the sample-size dependence of the transients and by avoiding the preconditioner-dependent factor in the limiting coupling bound.

For PSGD, additional stochastic residuals appear. The bound from Theorem 3.7 can be rewritten more compactly as

= \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 has a better dependence in $n$ than what naive bounds can achieve. Of course, the contribution of this bound depends on the step size, preconditioner, and gradient fluctuations. Smaller step sizes can reduce these contributions, at the cost of slower optimization. A quantitative improvement is present when stochastic fluctuations are sufficiently small, but our theorems do not establish a uniform improvement over the alternative estimates. Projection introduces further residual terms, which may also make the bounds more conservative. When projection is inactive along the relevant trajectories and at the reference points, these residuals vanish and the unprojected analysis applies. This is consistent with Figure 2: the clearest quantitative advantage appears in the regularized deterministic setting, while the stochastic and projected cases can produce more conservative bounds. We have made these comparisons explicit in the revised paper. **Question 4.** We thank the reviewer for pointing out this imprecision. Both inequalities in Equation (5.5) are indeed expected excess-risk bounds, and we have corrected the terminology accordingly in the revised paper. The expected generalization-gap guarantee obtained from algorithmic stability is $$\left| \mathbb E\left[R(x_t)-F_S(x_t)\right] \right| \leq G\beta_t.$$ The excess-risk bounds in Theorem 5.1 then follow by combining this inequality with the corresponding empirical optimization-error estimates. We have explicitly stated the generalization-gap inequality in the main text of the revised paper, and distinguished it from the subsequent excess-risk guarantees. --- We thank the reviewer again for their extremely valuable suggestions, specifically regarding the clarification on the impact of an efficient choice of preconditioner and the identifications of regimes where our results improve over standard coupling arguments. We have extended the discussion on these points based on these suggestions, which we believe greatly improves the clarity and readability of our manuscript. If the reviewer has further suggestions or remaining concerns, we are happy to address them. [1] Nocedal \& Wright (2006), Numerical Optimization, Section 5.3 (Preconditioning) [2] Kingma, Diederik P., and Jimmy Ba. "Adam: A method for stochastic optimization." arXiv preprint arXiv:1412.6980 (2014). [3] Gupta, Vineet, Tomer Koren, and Yoram Singer. "Shampoo: Preconditioned stochastic tensor optimization." ICML, 2018.

I thank the authors for their detailed responses and clarifications. While I appreciate the value of the refined finite-time stability analysis, I am not fully convinced that the demonstrated improvements over existing stability bounds are sufficiently substantial or general. Therefore, I maintain my original rating.

Your original review asked for conditions under which our bounds provably improve upon standard alternatives. Our response provides explicit conditions in the regularized deterministic setting: c1t+c2t2<nDΣρc_1t+c_2t^2<nD_\Sigma\rho is sufficient for improvement over the convergence-based estimate, while κ(P)>1\kappa(P)>1 guarantees eventual improvement over the stated norm-based coupling estimate. These comparisons quantify two benefits: preserving the 1/n1/n scaling of the transient terms and removing the preconditioner-dependent factor from the limiting bound.

We also clarified the scope of these improvements. Stochasticity and active projection introduce additional residuals, so the bounds need not improve uniformly over the alternatives. The revised discussion makes this distinction explicit.

Your follow-up questions whether the improvements are sufficiently substantial or general. Could you specify these concerns, and tell us which additional comparison or result would address it? This would allow us to improve the quality of our manuscript in consequence.

Reviewer_cXYgOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the algorithmic stability of preconditioned gradient descent (PGD) and its stochastic version (PSGD) for empirical risk minimization. The authors use a decomposition that separates the main instability term from the two other sums. For deterministic updates under strong convexity, the authors show a long-run stability of order 1/n and independent of P. For constant-step stochastic updates, a preconditioner-dependent noise term remains and disappears if the step size is sent to zero after the iteration count goes to infinity. The same decomposition covers a regularized unconstrained setting and a projected constrained setting. These stability bounds yield expected generalization and excess-risk guarantees that recover the 1/n rate of the empirical minimizer in the limit.

Critical strengths
  1. The paper has a clear structure and is easy to follow.
  2. The paper gives a complete analysis of the stability of preconditioned methods, covering both deterministic and stochastic settings, as well as both generalization and optimization.
Critical weaknesses
  1. This paper claims that the long-term stability is independent of the preconditioner. However, they rely on Hessian Lipschitz and uniformly bounded gradients, which are not required in Vary et al. (2026) or Zeng & Lei (2026). Furthermore, the PP-independent bound is obtained when the stepsize γ→0\gamma\to 0, which removes the constant-step noise rather than controlling stability at a step size that still optimizes. Vary et al. (2026) keep ηt∼1/(t+1)\eta_t\sim 1/(t+1) and are left with (64/r)tr⁡(PΣ)/n(64/r)\operatorname{tr}(P\Sigma)/n, which depends on PP, while Zeng & Lei (2026) obtain stability for ηt≲1/T\eta_t\lesssim 1/\sqrt{T}, and for ηt=1/(λt)\eta_t=1/(\lambda t) under strong convexity, without sending the step size to zero.

  2. This paper may misunderstood the the conclusions in Vary et al. (2026), where they say their (64/r)tr⁡(PΣ)/n(64/r)\operatorname{tr}(P\Sigma)/n term is the statistical term of multipass PSGD with steps ηt∼1/(t+1)\eta_t\sim 1/(t+1), and that this trajectory bound does not describe generalization at convergence, since every PP should reach the same empirical minimizer. To my best knowledge, their PL bound at convergence is 2tr⁡(H−1Σ)/(μn)2\operatorname{tr}(H^{-1}\Sigma)/(\mu n), which does not depend on the preconditioner.

  3. The limiting excess risk 2G2/(μn)2G^2/(\mu n) is the classical guarantee for the empirical minimizer, not a consequence of preconditioning. See Shalev-Shwartz et al. (2010).

Questions for authors
  1. Could the authors discuss whether the long-term stability remain independent of PP without Hessian Lipschitzness and uniformly bounded gradients, and for stochastic updates at a fixed or ηt∼1/t\eta_t\sim 1/t step size that still optimizes, rather than only after γ→0\gamma\to 0?

  2. Could the author give a more detailed comparison with existing analyses such as Vary et al. (2026) and Zeng & Lei (2026)?

  3. Since 2G2/(μn)2G^2/(\mu n) is the classical stability of a Lipschitz strongly convex empirical minimizer (Shalev-Shwartz et al., 2010), what does preconditioning change in the excess risk beyond this guarantee?

4 comments

We thank the reviewer for their careful reading and constructive comments. We appreciate that the reviewer deemed our analysis complete and our manuscript easy to read.

We stress that our main contribution is not a new stability guarantee for empirical minimizers, but a precise decomposition of the finite-time dynamics that separates the true underlying instability of the method (i.e., intrinsic sensitivity) from nonlinear transient effects, stochastic fluctuations, and projection residuals. This provides a more detailed characterization of how preconditioning affects stability throughout optimization, both at initial and late training stages.

We address the reviewer's main concerns below.

Question 1.

Could the authors discuss whether the long-term stability remain independent of PP without Hessian Lipschitzness and uniformly bounded gradients [...]

First, we recall that since both sequences converge to the corresponding empirical minimizers which are independent of PP, bounded gradients or Lipschitz-continuous Hessian assumptions are not necessary for asymptotic preconditioner independence in the deterministic setting.

However, the Hessian Lipschitzness assumption is essential for our refined control of the nonlinear remainder in our finite-time decomposition while preserving its 1/n1/n scaling. This is a classical assumption in works that give refined control on SGD's errors [2,3,4], and is necessary to control the terms that appear in our exact decomposition of the instability. When this assumption does not hold, we establish in Appendix A.3 that ∥ηk∥≤2LDΣρk\|\eta_k\| \leq 2LD_\Sigma\rho^k, which still vanishes asymptotically but does not retain the explicit 1/n1/n factor.

Regarding the gradients, a uniform bound over all neighboring datasets requires control of the replacement perturbation, which is usually done by using a uniform bound on the gradients in the literature on stability of gradient descent, such as Hardt et al. (2016).

[...] and for stochastic updates at a fixed or ηt∼1/t\eta_t\sim1/t step size that still optimizes, rather than only after γ→0\gamma\to0? \medskip

We agree that taking γ→0\gamma\to0 after t→∞t\to\infty does not establish preconditioner-independent stability at a fixed positive step size. We do not claim otherwise.

The limit γ→0\gamma\to0 is not required for any of our results to hold. Constant step size PSGD is a stochastic algorithm, and thus does not converge to a unique point due to persistent gradient noise. Remarkably, its stationary fluctuations depend on the linearized dynamics of the algorithm, in a similar fashion to classical SGD (see, e.g., [1] for the corresponding Markov-chain analysis of constant-step SGD). Preconditioning affects these dynamics, which affects the limiting noise distribution.

Yet, if the step size is small enough, the noise terms vanish. The limit γ→0\gamma\to0 aims to highlight this phenomenon, not to give a condition for this result to hold. Specifically, our Theorem 3.7 provides a finite-time stability bound at a fixed positive step size, with an intrinsic term that is asymptotically preconditioner-independent, and additional preconditioner-dependent stochastic terms. With γ∝1/T\gamma\propto 1/\sqrt{T}, where TT is the total iteration count, the noise terms also vanish asymptotically, similarly to Vary et al., 2026 and Zeng & Lei 2026.

Thank you for raising the lack of clarity regarding this point in our original discussion, we have included this in the revised manuscript.

(Continued below)

Weakness 2.

This paper may misunderstood the the conclusions in Vary et al. (2026), where they say their (64/r)tr⁡(PΣ)/n(64/r)\operatorname{tr}(P\Sigma)/n term is the statistical term of multipass PSGD [...] To my best knowledge, their PL bound at convergence is 2tr⁡(H−1Σ)/(μn)2\operatorname{tr}(H^{-1}\Sigma)/(\mu n), which does not depend on the preconditioner.

Proposition 10 of Vary et al. in the arXiv version gives a non-asymptotic bound which scales as 1/r1/r, where rr is a constant which depends on the problem's Hessian and the preconditioning matrix. When t→+∞t\to+\infty, the bound still retains this 1/r1/r-dependence.

On the other hand, their Proposition 14 gives a bound which is the sum of an optimization term and the 2tr⁡(H−1Σ)/(μn)2\operatorname{tr}(H^{-1}\Sigma)/(\mu n) term. This bound is obtained by combining a convergence argument and the stability of the limiting points, as can be seen in Equation (31) of their proof.

In our paper, we instead use the decomposition

= (I-A^t)\Delta^\star -\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, \qquad A=I-\gamma PH,$$ which separates the intrinsic sensitivity of the linearized dynamics, the variation of the replacement perturbation, and the nonlinear Hessian drift. This allows for precisely characterizing the intrinsic dynamics of the method, and more specifically the impact of the preconditioning. Unlike Proposition 14 from Vary et al., we do **not** use the stability of the ERM to later deduce upper-bounds, but instead **deduce** this asymptotic stability from the decomposition above. **Question 2.** > *Could the author give a more detailed comparison with existing analyses such as Vary et al. (2026) and Zeng \& Lei (2026)?* \medskip Prior literature makes different claims: - Vary et al. (2026) develop on-average stability bounds for multipass PSGD, focusing on the interaction between preconditioning, curvature, and stochastic noise geometry. They obtain trajectory-dependent excess-risk bounds and separately analyze the behavior of approximate empirical minimizers under a PL condition. Our answer to Weakness 2 gives further details on the difference with our paper. - Zeng and Lei (2026) develop an on-average squared model stability framework for biased stochastic gradient methods. Their results cover horizon-dependent step sizes and decreasing step sizes in strongly convex settings. However, **they do not consider the case of preconditioned gradient descent**. Our contribution is therefore a direct finite-time decomposition of the neighboring trajectories, with quantitative improvements over simpler estimates in identifiable regimes, particularly for regularized deterministic PGD, when using a *constant stepsize*. **Question 3.** > *Since $2G^2/(\mu n)$ is the classical stability of a Lipschitz strongly convex empirical minimizer (Shalev-Shwartz et al., 2010), what does preconditioning change in the excess risk beyond this guarantee?* As correctly pointed by the reviewer, $2G^2/(\mu n)$ is the classical excess-risk guarantee for the solution of strongly convex ERM. Our result studies the stability of PGD's trajectory, and do not rely on this property of the ERM limit. Our claim is that preconditioning affects the trajectory of the optimization, but has no impact on its limit point. This follows from a novel decomposition of the instability, which explicitly clarifies this intrinsic dependence, and recovers the asymptotic stability term $2G^2/(\mu n)$. --- We thank the reviewer again for their valuable suggestions regarding the clarity of our manuscript and the comparison with prior literature, and have implemented all the reviewer's suggestions in the revised manuscript. We hope this clarifies the reviewer's concerns, and remain available for further clarification if needed. [1] A. Dieuleveut, A. Durmus, and F. Bach, "Bridging the gap between constant step size stochastic gradient descent and Markov chains". [2] M. Sheshukova et al., "Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation." International Conference on Learning Representations, 2025. [3] Ilja Kuzborskij, Christoph Lampert, "Data-Dependent Stability of Stochastic Gradient Descent", ICML 2018. [4] Y. Zhang et al., "Stability of SGD: Tightness analysis and improved bounds", UAI 2022.

Thanks for the detailed response, which addresses part of my concern. However, it seems that they still do not establish preconditioner-independent stability under weaker assumptions and ηt≍1/t\eta_t\asymp 1/t, I will therefore keep my score.

Could you specify which assumptions you would like to see weakened? As explained in our response, bounded gradients are standard in uniform stability analyses, while Hessian Lipschitzness is commonly used for refined analyses of SGD, including the works cited in our rebuttal. We also explained its precise role here: preserving the 1/n1/n scaling of the nonlinear transient. Without it, Appendix A.3 still gives a vanishing remainder, but without this explicit scaling. These assumptions therefore serve a specific purpose in obtaining the refined finite-time guarantees.

Regarding the step size, our paper studies constant-step-size PGD and PSGD. Constant step size is standard setting for stability analysis, including in Hardt, Recht and Singer (2016). Theorem 3.7 holds at a fixed positive step size and retains the preconditioner-dependent stochastic terms; taking γ→0\gamma \to 0 is not a condition for this result. Moreover, the horizon-dependent choice for γ\gamma discussed in our response makes both the transient and stochastic terms vanish asymptotically. This recovers the qualitative conclusion of preconditioner-independent limiting stability, similarly to the γt=1/t\gamma_t = 1/t case.

We also clarified that the limiting ERM guarantee is classical, but that our quantitative contribution concerns finite-time behavior: in the regularized deterministic setting, the refined bound preserves the 1/n1/n scaling of the transients, improves upon the convergence-based estimate in an explicit early-iteration regime, and eventually improves upon the standard coupling estimate when κ(P)>1\kappa(P)>1.

In light of these clarifications, what concern remains about our results and their contribution relative to prior work? A more precise indication would help us address the remaining issue directly.


Reference: Hardt, Recht and Singer (2016), “Train faster, generalize better: Stability of stochastic gradient descent,” ICML.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.