acceptodds
Under review as a conference paper at ICLR 2027

Adapt or Forget: Provable Tradeoffs Between Adam and SGD in Nonstationary Optimization

Abstract

We provide a theoretical analysis of Adam under non-stationary stochastic objectives, separating two regimes: Euclidean tracking under adaptive strong monotonicity of the Adam-preconditioned mean-gradient operator, and high-probability projected stationarity guarantees under general -smooth objectives. In the tracking regime, we derive finite-time expected and high-probability bounds that decompose sharply into four components: initialization, objective drift, a first-moment tracking error governed by , and a preconditioner perturbation governed by . We characterize the burn-in time required for the transient terms to decay to the asymptotic tracking bound under constant and step-decay schedules. We also prove a high-probability bound on the average projected stationarity gap for Adam under distribution shift. Across both analyses, our bounds reveal a noise–drift tradeoff: in noise-dominated regimes, first-moment averaging and adaptive preconditioning can yield favorable upper guarantees, whereas in drift-dominated regimes, stale first-moment information and preconditioner perturbations can enlarge Adam's tracking guarantee, potentially allowing vanilla SGD to attain a smaller tracking error. Our explicit -dependent bounds identify mechanisms through which adaptive step-sizing can help or hurt under nonstationarity and provide theoretical explanations consistent with Adam's empirical instability and stabilization under distribution shift.

Primary area:
optimization
Keywords:
Adam, stochastic gradient descent, adaptive optimization, nonstationary stochastic optimization, tracking error

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_LcAbOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies Adam for stochastic optimization under nonstationary objectives. The authors derive finite-time tracking guarantees under an adaptive strong-monotonicity condition on the predictably preconditioned mean-gradient operator. The resulting bounds separate initialization, objective drift, first-moment tracking error, and second-moment preconditioner perturbation, making the dependence on beta1, beta2, and epsilon explicit. The paper also derives high-probability projected-stationarity guarantees without the adaptive strong-monotonicity assumption.

Critical strengths

Separating first-moment tracking error from second-moment perturbation makes it possible to see distinct roles for beta1, beta2, and epsilon in Adam.

The experiments across several convex and nonconvex problems seem to support the tradeoff predicted by the main theoretical results.

Critical weaknesses

The first-moment memory penalty appears loose as a characterization of nonstationarity. The bias term is controlled using the domain diameter and beta1 rather than directly through objective or minimizer drift.

Questions for authors

The assumptions between the Adam-versus-SGD are not under a common set of assumptions. Can this be achieved to make the separation formal?

Can the first-moment bias term be refined so that it depends explicitly on temporal variation?

4 comments
AuthorsOpenReview ↗

Response to Reviewer LcAb

Dear reviewer, thank you for your helpful feedback. We are glad that you found the problem our paper addresses and our theoretical analysis to be informative and that it provided you a “substantially deeper understanding” of adaptive preconditioning in nonstationary optimization settings. We also thank you for your comments and suggestions, and would like to respond to the points you raised below.

W1/Q2. We thank the reviewer for pointing this out. We agree that indeed this first term β12L2R2/(μ2ϵ2)\beta_{1}^2L^2R^2/(\mu^2 \epsilon^2) is indeed loose even when β1\beta_{1} is sufficiently large. We can indeed sharpen this so it explicitly depends on temporal variation. We have provided a proof sketch under our response to Reviewer N1Ez W1/Q1. We will include this sharpened result in our revised manuscript.

Q1. Although the assumptions for Adam and SGD appear different at first, the tracking guarantees can be established over a common function class. In particular, for twice-differentiable objectives, adaptive strong monotonicity implies strong convexity on the tracking region Θ\Theta. Consequently, the Adam and SGD tracking guarantees can be compared to each other under Assumption 3.1, although their strong convexity constants may differ.

The motivation for adaptive strong monotonicity is that Adam requires contraction of the predictably preconditioned mean-gradient operator, whereas SGD only requires contraction of the mean-gradient operator. Ordinary strong convexity alone does not necessarily imply adaptive strong monotonicity, as demonstrated in Example C.5. Moreover, this framework accommodates objectives that are globally nonconvex but strongly convex on the restricted tracking region Θ\Theta, allowing us to draw parallels with the SGD and SGDM results of [1]. We will make this more explicit in the revised manuscript.

Finally, to facilitate comparisons beyond Euclidean tracking, we additionally provide a projected-stationarity guarantee for SGD under general LL-smooth objectives (see our response to Reviewer fain W1). We also provide an explicit moving quadratic example in which one can establish a performance ordering for Adam and SGD in the respective high-drift/low-noise and low-drift/high-noise settings (see our response to Reviewer N1Ez W3/Q4). We hope this helps clarify the comparison and problem setting.

[1] Sahu, S., Hogan, C. J., & Wells, M. T. (2026). On the provable suboptimality of momentum SGD in nonstationary stochastic optimization. Proceedings of the 43rd International Conference on Machine Learning (ICML).

We hope our response helps clarify the significance of our contribution, and we would be very happy to discuss further. Thank you again for your time and consideration!

Dear reviewer, we sincerely appreciate your constructive feedback and thoughtful suggestions, which have helped us further clarify our theoretical assumptions and strengthen the comparison between Adam and SGD in nonstationary optimization settings.

As the author discussion period is coming to an end, we would be very grateful if you could take a look at our previous rebuttal and let us know whether it has addressed your concerns. In particular, we have:

  • Sharpened the first-moment bias bound to explicitly depend on temporal gradient variation, addressing concerns about the looseness of the original bound.
  • Clarified that the Adam and SGD tracking guarantees can be compared under a common function class, while explaining the role and necessity of adaptive strong monotonicity.
  • Provided an additional projected-stationarity guarantee for SGD and explicit moving-quadratic examples demonstrating the noise–drift tradeoff between Adam and SGD.

If any questions or concerns remain, we would be more than happy to discuss them further before the end of the discussion period. Thank you again for your time and consideration!

I thank the authors for their responses. I believe the paper is solid and will maintain my score.

Thank you for maintaining your positive assessment of our work and for your continued support!

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

This paper studies Adam under nonstationary stochastic objectives, focusing on two criteria: Euclidean tracking error and projected stationarity. By comparing theoretical guarantees for Adam and SGD, the authors highlight an interesting tradeoff between adapting to objective drift and reducing gradient noise. Overall, I find the problem and results interesting, although the presentation could be made more reader-friendly.

Critical strengths

The paper studies an interesting problem. By comparing theoretical guarantees for Adam and SGD, the authors shed light on the tradeoff between adapting to objective drift and reducing gradient noise. Most of the assumptions are standard, and the adaptive strong monotonicity condition is further motivated in the appendix. The experiments are also interesting and broadly consistent with the theoretical insights.

Critical weaknesses

My main concern with the presentation is that the paper asks too much of the reader. Although the theoretical results are interesting, the accumulation of definitions, assumptions, and lengthy theorem statements obscures the central message. The distinction between Euclidean tracking and projected stationarity is especially important, yet the reader has to work to understand how their assumptions and guarantees differ.

I recommend adding a compact table that compares the settings studied in the paper, the applicable assumptions, the Adam and SGD guarantees, and the relevant prior work. The authors could also shorten the theorem statements in the main text and follow each one with a plain-language explanation of its main implication. These changes would make the noise–drift tradeoff much easier to follow without sacrificing technical rigor.

Questions for authors

Assumption 2.3 imposes a uniform conditional sub-Gaussian bound on the gradient noise along the iterates. Remark 2.1 mentions possible alternatives, including sub-exponential noise and bounded higher-order moments. Could the authors clarify whether the main Adam/SGD comparison extends under these weaker conditions? In particular, which conclusions would remain unchanged, and how would the probability bounds or rates be affected?

6 comments
AuthorsOpenReview ↗

Response To Reviewer fain (Part 1/3)

Dear reviewer, thank you for your helpful feedback. We are glad that you found the problem our paper addresses and our theoretical results “interesting” and that it provided you a “substantially deeper understanding” of adaptive preconditioning in nonstationary optimization settings. We also thank you for your comments and suggestions, and would like to respond to the points you raised below.

W1 (Presentation and clarity of theoretical results). We thank the reviewer for this helpful suggestion. To address this, we will add the following compact comparison table to the main text.

Table: Comparison of theoretical settings, assumptions, guarantees, and relevant prior work.

SettingMain assumptionsAdam guaranteeSGD guaranteeRelevant prior work
Euclidean trackingLL-smoothness, sub-Gaussian noise; adaptive strong monotonicity (Adam), strong convexity (SGD).High-probability and expected tracking bounds separating drift, β1\beta_1 memory, and β2\beta_2 perturbation; burn-in guarantees (Thms. 3.1, 3.3).High-probability tracking bound separating initialization, drift, and stochastic noise (Thm. 3.2).[1, 2]
Projected stationarityLL-smoothness, lower-bounded objectives, sub-Gaussian noise; no strong monotonicity.High-probability and expected average metric-projected stationarity bounds involving objective variation and moment-dependent errors (Thm. 4.1).Projected-stationarity guarantee under nonstationarity (new Thm. 4.2; see rebuttal).[3, 4, 5]

Additionally, since we are making a direct comparison between SGD and Adam in the nonconvex setting as well, we will provide an additional result in the main body of the revised manuscript so one can easily compare the stationary guarantees. We write the result below and provide a brief proof sketch:

Result: Under the same assumptions as Theorem 4.1, the iterates generated by the projected SGD update satisfy, with probability at least 1−δ1-\delta,

\begin{align} \frac{1}{T} \sum_{t=0}^{T-1} \lVert \mathcal{G}_{\alpha, t}(\boldsymbol{\theta}_{t}) \rVert_{\widetilde{\boldsymbol{P}}_{t+1}^{-1}}^{2} \lesssim \frac{G_{1}(\boldsymbol{\theta}_{0}) - G^{\star} + \mathfrak{D}_{T}}{\alpha T} + \sigma^{2}d + \frac{\sigma^2 \log (1/\delta)}{T} \end{align}

To prove this result, we note from the proof of Lemma E.2 that it suffices to bound ∑t=0T−1∥ξt+1∥22\sum_{t=0}^{T-1} \lVert \boldsymbol{\xi}_{t+1}\rVert_{2}^2 as there is no first and second moments nor any martingale difference terms with respect to the coordinate-wise squared gradients. The first term appears from the proof of Lemma E.2. Before we prove the result, we remark that we assume subgaussianity in the form ∥ξt+1∥Ψ2∣Ft≤σ\lVert \boldsymbol{\xi}_{t+1}\rVert_{\Psi_{2} \mid \mathcal{F}_{t}} \leq \sigma. Define Ut:={u∈Sd−1:u is Ft-measurable}\mathcal{U}_t:=\lbrace u\in \mathbb{S}^{d-1}:u\text{ is }\mathcal{F}_t\text{-measurable}\rbrace. This is equivalent to the following:

\begin{align} \sup_{\boldsymbol{u} \in \mathbb{S}^{d-1} \cap \ \mathcal{U}_t} \mathbb{E} \left[ \exp\left( \frac{\left\lvert \boldsymbol{u}^{\top} \boldsymbol{\xi}_{t+1} \right\rvert^{2}}{\sigma^2} \right) \mid \mathcal{F}_{t} \right] \leq 2 \quad \mathrm{a.s.} \end{align}

We will make use of this in our proof. We will prove the following result. For all δ∈(0,1)\delta \in (0, 1), the following holds:

\begin{align} \mathbb{P}\left( \forall T \geq 1: \frac{1}{T} \sum_{t=0}^{T-1} \lVert \boldsymbol{\xi}_{t+1}\rVert_{2}^2 \lesssim \sigma^2d + \frac{\sigma^2 \log (1/\delta)}{T} \right) \geq 1-\delta. \end{align}

Proof: Let N⊂Sd−1\mathcal{N} \subset \mathbb{S}^{d-1} be a 1/21/2-net of the Sd−1\mathbb{S}^{d-1}. Then by definition for all v∈Sd−1\boldsymbol{v} \in \mathbb{S}^{d-1}, there exists u∈N\boldsymbol{u} \in \mathcal{N} such that ∥u−v∥2≤1/2\lVert \boldsymbol{u} - \boldsymbol{v} \rVert_{2} \leq 1/2. Standard volumetric arguments imply ∣N∣≤5d\left| \mathcal{N} \right| \leq 5^{d}. Fix x∈Rd\boldsymbol{x} \in \mathbb{R}^{d} and let v=x/∥x∥2\boldsymbol{v} = \boldsymbol{x} / \lVert \boldsymbol{x} \rVert_{2}. One can choose u∈N\boldsymbol{u} \in \mathcal{N} such that ∥u−v∥2≤1/2\lVert \boldsymbol{u} - \boldsymbol{v} \rVert_{2} \leq 1/2. Since u,v\boldsymbol{u}, \boldsymbol{v} are unit vectors, one finds the following:

\begin{align} \boldsymbol{u}^{\top} \boldsymbol{v} = 1 - \frac{1}{2} \lVert \boldsymbol{u} - \boldsymbol{v} \rVert_{2}^2 \geq \frac{7}{8}. \end{align}

This immediately implies that 7∥x∥2/8≤∣u⊤x∣7 \lVert \boldsymbol{x} \rVert_{2} / 8 \leq \left\lvert \boldsymbol{u}^{\top}\boldsymbol{x} \right\rvert. Since this holds for any u∈N\boldsymbol{u} \in \mathcal{N}, we find 49∥x∥22/64≤max⁡u∈N∣u⊤x∣249 \lVert \boldsymbol{x} \rVert_{2}^{2} / 64 \leq \max_{\boldsymbol{u} \in \mathcal{N}} \left\lvert \boldsymbol{u}^{\top}\boldsymbol{x} \right\rvert^2.

AuthorsOpenReview ↗

Response To Reviewer fain (Part 2/3)

W1 (cont). This can now be used as follows:

\begin{align} \exp \left( \frac{49 \lVert \boldsymbol{\xi}_{t+1} \rVert_{2}^{2}}{64 \sigma^2} \right) \leq \exp \left( \max_{\boldsymbol{u} \in \mathcal{N}} \frac{\left\lvert \boldsymbol{u}^{\top}\boldsymbol{\xi}_{t+1} \right\rvert^2}{\sigma^2} \right) = \max_{\boldsymbol{u} \in \mathcal{N}} \exp \left( \frac{\left\lvert \boldsymbol{u}^{\top}\boldsymbol{\xi}_{t+1} \right\rvert^2}{\sigma^2} \right) &\leq \sum_{\boldsymbol{u} \in \mathcal{N}} \exp \left( \frac{\left\lvert \boldsymbol{u}^{\top}\boldsymbol{\xi}_{t+1} \right\rvert^2}{\sigma^2} \right). \end{align}

Taking conditional expectations, we find that

\begin{align} \mathbb{E} \left[ \exp \left( \frac{49 \lVert \boldsymbol{\xi}_{t+1} \rVert_{2}^{2}}{64 \sigma^2} \right) \mid \mathcal{F}_{t} \right] \leq \sum_{\boldsymbol{u} \in \mathcal{N}} \mathbb{E} \left[ \exp \left( \frac{\left\lvert \boldsymbol{u}^{\top}\boldsymbol{\xi}_{t+1} \right\rvert^2}{\sigma^2} \right) \mid \mathcal{F}_{t} \right] \leq 2 \left| \mathcal{N} \right| \leq 2 \cdot 5^{d}. \end{align}

where the first inequality follows from our subgaussianity assumption. If we let c=dlog⁡5+log⁡2c = d\log5 + \log2 and λ=49/(64σ2)\lambda = 49 / (64\sigma^2), then we have shown that E[eλ∥ξt+1∥22∣Ft]≤ec\mathbb{E}[ e^{\lambda \lVert \boldsymbol{\xi}_{t+1} \rVert_{2}^{2}} \mid \mathcal{F}_{t} ] \leq e^{c}.

Define MT=exp⁡(λ∑t=0T−1∥ξt+1∥22−cT)M_{T} = \exp \left( \lambda \sum_{t=0}^{T-1} \lVert \boldsymbol{\xi}_{t+1} \rVert_{2}^{2} - cT \right) where M0=1M_{0} = 1. One can show that this is indeed a supermartingale i.e. E[MT+1∣FT]≤MT\mathbb{E}[M_{T+1} \mid \mathcal{F}_{T}] \leq M_{T}. This allows us to apply a stronger version of Markov’s inequality known as Ville’s inequality to obtain the following result:

\begin{align} \mathbb{P}\left( \exists T \geq 1: \lambda \sum_{t=0}^{T-1} \lVert \boldsymbol{\xi}_{t+1} \rVert_{2}^{2} - cT \geq \log(1/\delta) \right) \leq \delta. \end{align}

Substituting the values of λ\lambda and cc while ignoring constants yields the claim.

Additionally, we will revise the theorem statements in the main text to be shorter and subsequently provide plain-language explanations of implications of the results. We hope including this additional result along with the table allows readers to more easily understand our theoretical contributions and the differences in the assumptions and guarantees.

[1] Sahu, S., Hogan, C. J., & Wells, M. T. (2026). On the provable suboptimality of momentum SGD in nonstationary stochastic optimization. Proceedings of the 43rd International Conference on Machine Learning (ICML).

[2] Cutler, J., Drusvyatskiy, D., & Harchaoui, Z. (2021). Stochastic optimization under time drift: Iterate averaging, step-decay schedules, and high probability guarantees. Advances in Neural Information Processing Systems (NeurIPS).

[3] Reddi, S. J., Kale, S., & Kumar, S. (2018). On the convergence of Adam and beyond. Proceedings of the 6th International Conference on Learning Representations (ICLR).

[4] Défossez, A., Bottou, L., Bach, F., & Usunier, N. (2022). A simple convergence proof of Adam and Adagrad. Transactions on Machine Learning Research (TMLR).

[5] Li, H., Rakhlin, A., & Jadbabaie, A. (2023). Convergence of Adam under relaxed assumptions. Advances in Neural Information Processing Systems (NeurIPS)

AuthorsOpenReview ↗

Response To Reviewer fain (Part 3/3)

Q1. We thank the reviewer for this question. The main Adam–SGD comparison can be extended to weaker tail assumptions, although the stochastic error terms and high-probability rates would change. The underlying tracking recursions, decomposition into drift and moment-dependent errors, and qualitative noise–drift tradeoff should remain applicable.

Below we provide a table illustrating how the high probability rates change under various different noise assumptions. We have also included the rate we derived in our response to W1. Many of these rates follow from standard martingale maximal and LqL^{q} inequalities along with dyadic peeling arguments. We have illustrated these for SGD as is simplest to do, and these arguments and rates can be further used with Adam with a little more technical work.

Each bound BT(δ)B_{T}(\delta) below satisfies $ \mathbb{P}\left( \forall T\ge 1: \frac{1}{T}\sum_{t=0}^{T-1}\lVert \boldsymbol{\xi}_{t+1}\rVert_{2}^2 \lesssim B_{T}(\delta) \right)\ge 1-\delta. $

AssumptionCondition (a.s. for every t)Bound BT(δ)B_{T}(\delta)
Conditional sub-Gaussian (Ψ2\Psi_{2})sup⁡u∈UtE[exp⁡(∣u⊤ξt+1∣2σ2)|Ft]≤2\displaystyle\sup_{\boldsymbol{u}\in\mathcal{U}_{t}}\mathbb{E}\left[\exp\left(\frac{\lvert \boldsymbol{u}^\top\boldsymbol{\xi}_{t+1}\rvert^2}{\sigma^2}\right)\middle\vert\mathcal{F}_{t}\right]\le 2σ2(d+log⁡(1/δ)T)\displaystyle\sigma^2\left(d+\frac{\log(1/\delta)}{T}\right)
Conditional sub-exponential (Ψ1\Psi_{1})sup⁡u∈UtE[exp⁡(∣u⊤ξt+1∣σ)|Ft]≤2\displaystyle\sup_{\boldsymbol{u}\in\mathcal{U}_{t}}\mathbb{E}\left[\exp\left(\frac{\lvert \boldsymbol{u}^\top\boldsymbol{\xi}_{t+1}\rvert}{\sigma}\right)\middle\vert\mathcal{F}_{t}\right]\le 2σ2d[1+(log⁡(e/δ)+log⁡(1+log⁡T))5/2T]\displaystyle \sigma^2d\left[1+\frac{\left(\log(e/\delta)+\log(1+\log T)\right)^{5/2}}{\sqrt{T}}\right]
Conditional finite p-th moment (p>2p>2)sup⁡u∈UtE[∣u⊤ξt+1∣p|Ft]≤σp\displaystyle\sup_{\boldsymbol{u}\in\mathcal{U}_{t}}\mathbb{E}\left[\lvert \boldsymbol{u}^\top\boldsymbol{\xi}_{t+1}\rvert^p\middle\vert\mathcal{F}_{t}\right]\le\sigma^pσ2d[1+(1+log⁡T)4/pδ2/pTmin⁡{1/2,1−2/p}]\displaystyle \sigma^2d\left[1+\frac{(1+\log T)^{4/p}}{\delta^{2/p}T^{\min\lbrace 1/2,1-2/p\rbrace}}\right]
Bounded conditional varianceE[ξt+1ξt+1⊤|Ft]⪯σ2Id\displaystyle\mathbb{E}\left[\boldsymbol{\xi}_{t+1}\boldsymbol{\xi}_{t+1}^\top\middle\vert\mathcal{F}_{t}\right]\preceq\sigma^2\boldsymbol{I}_{d}σ2dδ(1+log⁡T)2\displaystyle\frac{\sigma^2d}{\delta}(1+\log T)^2

We adopt the conditional sub-Gaussian assumption for consistency with the stochastic tracking literature and to present the clearest high-probability guarantees. We will clarify these extensions and their limitations in Remark 2.1.

We will incorporate all rebuttals into our manuscript to improve its quality. We hope our response helps clarify the significance of our contribution, and we would be very happy to discuss further. Thank you again for your time and consideration!

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

The paper studies Adam under time-varying stochastic objectives. It distinguishes two settings: tracking a moving minimizer under adaptive strong monotonicity, and controlling a projected stationarity residual in a predictable preconditioner metric without that condition. The analysis decomposes the update into a predictable mean-gradient step, a first-moment tracking error, and a random-preconditioner perturbation. It provides expectation and high-probability bounds, followed by burn-in guarantees for constant learning rates and step-decay schedules with Adam-state restarts. Experiments compare Adam and SGD on six synthetic online problems and investigate sensitivity to β1,β2,ϵ\beta_1, \beta_2, \epsilon.

Critical strengths

S1. Important and well-motivated research question. Understanding how Adam’s first- and second-moment memory interact with distribution shift is relevant to nonstationary optimization. The paper identifies a concrete tension between noise suppression and responsiveness to changing objectives.

S2. Careful treatment of the random preconditioner’s dependence on the current sample. The analysis explicitly recognizes that P_(t+1) is not measurable with respect to the previous history. Introducing a predictable proxy while retaining a separate perturbation term is a useful way to organize the tracking argument. See pp. 20–23.

S3. Appropriate distinction between tracking and stationarity. The paper does not directly promise tracking of a global minimizer for arbitrary nonconvex objectives. Instead, it develops a separate projected-stationarity analysis. The appendices provide detailed recursions, concentration arguments, and expectation counterparts, making the reasoning accessible for inspection.

Critical weaknesses
  1. The tracking bound is insufficiently informative. At β1=0.9\beta_1=0.9, the explicit bound in Theorem D.1 contains a term of at least CR2CR^2, whereas the feasible-set assumption already guarantees ∥θt−θ∗∥≤R2\|\theta_t-\theta^*\|\leq R^2. This limits the significance of the claimed sharp tracking and burn-in guarantees. (See Q1 below.)

  2. The scope of tracking assumption is overstated. In the twice-differential setting, adaptive strong monotonicity implies strong convexity on Θ\Theta. Appendix C.4 only demonstrates nonconvexity outside this region. The tracking result should therefore be positioned as a locally strongly convex guarantee, rather than a genuinely nonconvex extensions.

  3. The Adam-SGD tradeoff needs stronger validation. Comparing loose upper bounds does not establish an actual performance separation, particularly when their strong-monotonicity/convexity constants differ. Moreover, the experimental learning rates fall outside the stated theoretical conditions, and additional SGDM or fixed-preconditioner baselines would help isolate the proposed mechanisms.

Questions for authors

Q1 — Non-vacuity. Theorem D.1 contains 160β12L2R2/(μ2ϵ2)160β_1^2 L^2 R^2/(\mu^2 \epsilon^2), and the assumptions imply μ≤L/ϵ\mu\leq L/\epsilon. How can the resulting guarantee improve on the trivial bound R2R^2 when β_1=0.9? Could you provide an explicit nontrivial example with all constants, or sharpen Lemma D.4 to avoid this diameter-scale persistent term?

Q2 — Scope of the tracking assumption. In the twice-differentiable setting of Appendix C, Assumption 3.1 implies at least μ\mustrong convexity on Θ\Theta. Could you give a concrete example that is genuinely nonconvex within Θ\Theta while satisfying the assumption, rather than merely nonconvex outside it?

Q3 — Actual drift dependence. The first-moment bias bound does not vanish with drift, and the second-moment discrepancy mainly measures fresh fluctuations and bias correction. After a long burn-in followed by an abrupt change in curvature or noise variance, which explicit term captures the ensuing lag on the order of 1/(1−β2)1/(1-\beta_2)? Would the interpretation persist if a bias-corrected conditional proxy were used?

Q4 — Adam versus SGD. After distinguishing the two monotonicity/convexity moduli and specifying comparable learning-rate selection and computational budgets, can you give a nontrivial comparison with explicit constants, or an analytically tractable moving quadratic that establishes an actual performance ordering? Which conclusions concern upper bounds only, and which concern realized or expected algorithmic error?

Q5 — Experimental consistency. Please report the feasible sets, selected learning rates, drift and gradient normalizations, projection operations, and precise evaluation metrics. In particular, Table 1 specifies Δt=log(t+2)\Delta_t=log(t+2) for high-drift least squares, while Figure 1 shows tracking errors around 10(−1)10^(-1). Is there an unreported rescaling, more than one update per target change, or a normalized error metric? For Lasso, is the reported quantity prediction MSE, parameter-recovery error, or distance to the regularized minimizer?

7 comments
AuthorsOpenReview ↗

Response To Reviewer N1Ez (Part 1/5)

Dear reviewer, thank you for your helpful feedback. We are glad that you found our paper to address an “important and well-motivated research question” in nonstationary optimization. We also thank you for your comments and suggestions, and would like to respond to the points you raised below.

W1/Q1. We thank the reviewer for pointing this out. We agree that indeed this first term β12L2R2/(μ2ϵ2)\beta_{1}^2L^2R^2/(\mu^2 \epsilon^2) is indeed loose even when β1\beta_{1} is sufficiently large. We can sharpen Lemma D.4 to avoid this bias term that depends on the diameter. We provide a proof below.

Recall that Lemma D.4 gives us the following decomposition: rt+1=Bt+1(1)+Nt+1(1)\boldsymbol{r}_{t+1} = \boldsymbol{B}_{t+1}^{(1)} + \boldsymbol{N}_{t+1}^{(1)}. We controlled Nt+1(1)\boldsymbol{N}_{t+1}^{(1)} via a martingale difference inequality. What remains is to sharpen Bt+1(1)\boldsymbol{B}_{t+1}^{(1)}. We define Bt+1(1):=∑k=0tw1,t+1,k(gˉk+1(θk)−gˉt+1(θt))\boldsymbol{B}_{t+1}^{(1)} := \sum_{k=0}^{t} w_{1, t+1, k} (\bar{\boldsymbol{g}}_{k+1}(\boldsymbol{\theta}_{k}) - \bar{\boldsymbol{g}}_{t+1}(\boldsymbol{\theta}_{t})). The first thing to notice is that for k<tk < t, we can telescope the quantity gˉk+1(θk)−gˉt+1(θt)=−∑s=k+1t(gˉs+1(θs)−gˉs(θs−1))\bar{\boldsymbol{g}}_{k+1}(\boldsymbol{\theta}_{k}) - \bar{\boldsymbol{g}}_{t+1}(\boldsymbol{\theta}_{t}) = -\sum_{s=k+1}^{t} (\bar{\boldsymbol{g}}_{s+1}(\boldsymbol{\theta}_{s}) - \bar{\boldsymbol{g}}_{s}(\boldsymbol{\theta}_{s-1})). Also recall the form of w1,t+1,k=(1−β1)β1t−k/(1−β1t+1)w_{1, t+1, k} = (1-\beta_{1})\beta_{1}^{t-k} / (1 - \beta_{1}^{t+1}). One can also show that ∑k=0s−1w1,t+1,k=β1t−s+1(1−β1s)/(1−β1t+1)\sum_{k=0}^{s-1} w_{1, t+1, k} = \beta_{1}^{t-s+1}(1-\beta_{1}^{s})/(1-\beta_{1}^{t+1}). Using these, we find:

\begin{align} \boldsymbol{B}_{t+1}^{(1)} = \sum_{k=0}^{t} w_{1, t+1, k} (\bar{\boldsymbol{g}}_{k+1}(\boldsymbol{\theta}_{k}) - \bar{\boldsymbol{g}}_{t+1}(\boldsymbol{\theta}_{t})) & = -\sum_{s=1}^{t} \left( \sum_{k=0}^{s-1} w_{1, t+1, k} \right) (\bar{\boldsymbol{g}}_{s+1}(\boldsymbol{\theta}_{s}) - \bar{\boldsymbol{g}}_{s}(\boldsymbol{\theta}_{s-1})) \\ &= -\sum_{s=1}^{t} \frac{\beta_{1}^{t-s+1}(1-\beta_{1}^{s})}{1-\beta_{1}^{t+1}} (\bar{\boldsymbol{g}}_{s+1}(\boldsymbol{\theta}_{s}) - \bar{\boldsymbol{g}}_{s}(\boldsymbol{\theta}_{s-1})) \\ &\leq \sum_{s=1}^{t} \beta_{1}^{t-s+1}\lVert\bar{\boldsymbol{g}}_{s+1}(\boldsymbol{\theta}_{s}) - \bar{\boldsymbol{g}}_{s}(\boldsymbol{\theta}_{s-1})\rVert, \end{align}

where the last inequality holds since for β1∈[0,1]\beta_{1} \in [0, 1], β1k\beta_{1}^{k} is decreasing in kk and as s<ts < t, we have 1−β1s≤1−β1t+11 - \beta_{1}^{s} \leq 1 - \beta_{1}^{t+1}. Now using this expression, we have:

\begin{align} \lVert\boldsymbol{B}_{t+1}^{(1)}\rVert^2 &\leq \left( \sum_{s=1}^{t} \beta_{1}^{t-s+1} \right) \left( \sum_{s=1}^{t} \beta_{1}^{t-s+1} \lVert\bar{\boldsymbol{g}}_{s+1}(\boldsymbol{\theta}_{s}) - \bar{\boldsymbol{g}}_{s}(\boldsymbol{\theta}_{s-1})\rVert^{2} \right) \\ &\leq \frac{\beta_{1}^2}{1-\beta_{1}} \sum_{s=1}^{t} \beta_{1}^{t-s} \lVert\bar{\boldsymbol{g}}_{s+1}(\boldsymbol{\theta}_{s}) - \bar{\boldsymbol{g}}_{s}(\boldsymbol{\theta}_{s-1})\rVert^{2}. \end{align}

where the first inequality holds from Cauchy-Schwarz and the last holds from 1−β1t≤11-\beta_{1}^{t} \leq 1 for all tt.

Recall in the proof of Theorem 3.1, we evaluate a term ∑ℓ=0t−1ραt−ℓ−1∥rℓ+1∥2\sum_{\ell=0}^{t-1} \rho_{\alpha}^{t-\ell-1} \lVert\boldsymbol{r}_{\ell+1}\rVert^{2}. Thus it suffices to evaluate ∑ℓ=0t−1ραt−ℓ−1∥Bℓ+1(1)∥2\sum_{\ell=0}^{t-1} \rho_{\alpha}^{t-\ell-1} \lVert\boldsymbol{B}_{\ell+1}^{(1)}\rVert^{2} as this accounts for the bias and the other term accounts for martingale differences. We first define the following gradient variation term:

\begin{align} \mathscr{G}_{t} = \sum_{s=1}^{t-1} \left( \sum_{j=0}^{t-s-1} \rho_{\alpha}^{t-s-j-1} \beta_{1}^{j} \lVert\bar{\boldsymbol{g}}_{s+1}(\boldsymbol{\theta}_{s}) - \bar{\boldsymbol{g}}_{s}(\boldsymbol{\theta}_{s-1})\rVert^{2} \right) \end{align}

Now we obtain an explicit expression for ∑ℓ=0t−1ραt−ℓ−1∥Bℓ+1(1)∥2\sum_{\ell=0}^{t-1} \rho_{\alpha}^{t-\ell-1} \lVert\boldsymbol{B}_{\ell+1}^{(1)}\rVert^{2}

\begin{align} \sum_{\ell=0}^{t-1} \rho_{\alpha}^{t-\ell-1} \lVert\boldsymbol{B}_{\ell+1}^{(1)}\rVert^{2} \leq \frac{\beta_{1}^2}{1-\beta_{1}} \sum_{\ell=0}^{t-1} \rho_{\alpha}^{t-\ell-1} \sum_{s=1}^{\ell} \beta_{1}^{\ell-s} \lVert\bar{\boldsymbol{g}}_{s+1}(\boldsymbol{\theta}_{s}) - \bar{\boldsymbol{g}}_{s}(\boldsymbol{\theta}_{s-1})\rVert^{2} = \frac{\beta_{1}^2}{1-\beta_{1}} \mathscr{G}_{t}. \end{align}

AuthorsOpenReview ↗

Response To Reviewer N1Ez (Part 2/5)

W1/Q1 (cont). We can replace the bias term with min⁡{160β12L2R2μ2ϵ2,20αβ12Gtμϵ2(1−β1)}\min\left\lbrace \frac{160\beta_{1}^{2}L^{2}R^{2}}{\mu^{2}\epsilon^{2}}, \frac{20\alpha\beta_{1}^{2}\mathscr{G}_{t}}{\mu\epsilon^{2}(1-\beta_{1})}\right\rbrace. This improves the result in term of vacuity as if ∥gˉs+1(θs)−gˉs(θs−1)∥≤Γ\lVert\bar{\boldsymbol{g}}_{s+1}(\boldsymbol{\theta}_{s}) - \bar{\boldsymbol{g}}_{s}(\boldsymbol{\theta}_{s-1})\rVert \leq \Gamma, then one can bound Gt≲Γ2/(αμ(1−β1))\mathscr{G}_{t} \lesssim \Gamma^2 / (\alpha \mu (1-\beta_{1})). We note the latter is smaller if Γ<(1−β1)LR\Gamma < (1-\beta_{1})LR which is sufficiently large β1\beta_{1}.

In particular, the improvement is the explicit dependence on the gradient variation which we believe is more informative as the dynamics of Adam under nonstationarity depend heavily on the direction/magnitude of change in gradients and matches the intuition that nearby gradient changes induce old gradient information which worsens adaptation with each contribution decreasing as the number of training iterations increase. More importantly, the refined first-moment term is now strictly smaller than the trivial diameter bound. Additionally, we should note that this change will incrementally affect the result of Theorem 3.3 and Theorem 4.1.

We hope this sufficiently addresses your concern about the vacuity of the first-moment bias term, and we will be sure to include this sharpened result in the revised manuscript.

W2/Q2. We agree with the reviewer that the tracking result should be viewed as a locally strongly convex result rather than a nonconvex guarantee. Our goal with the assumption of adaptive strong monotonicity is to show that it holds for a rather general function class, including globally nonconvex functions while being locally strongly convex only within Θ\Theta which also allows us to draw similar parallels with the results of [1] as they also assume gg is strongly convex, although everywhere on its domain which we can sufficiently restrict to Θ\Theta. We note that we make use of this assumption as strong convexity of gg is not sufficient to establish the necessary contraction required to prove Theorem 3.1 as we illustrate with Example C.5. We do not aim to position this as a genuinely nonconvex tracking result. This is exactly why we establish Theorem 4.1 as a nonconvex result. We hope this clarifies the scope of the tracking assumption.

[1] Sahu, S., Hogan, C. J., & Wells, M. T. (2026). On the provable suboptimality of momentum SGD in nonstationary stochastic optimization. Proceedings of the 43rd International Conference on Machine Learning (ICML).

Q3. In terms of β1\beta_{1}, we have addressed how to improve the dependence of β1\beta_{1} on a quantity that changes based on drift (gradient-variation) in our response to W1/Q1.

In terms of β2\beta_{2}, this is a great observation. First we note that the β2tλ2t−1\beta_{2}t\lambda_{2}^{t-1} term in Theorem 3.1 represents the initialization and bias-correction transient. Lag following arbitrary distribution shift is contained in the v~t\tilde{\boldsymbol{v}}_{t} of the predictable preconditioner. To make this more explicit, we will provide a brief proof sketch which subsequently will show ensuing lag of order 1/(1−β2)1/(1-\beta_{2}).

First recall that vt+1=β2vt+(1−β2)gt+1⊙2\boldsymbol{v}_{t+1} = \beta_{2}\boldsymbol{v}_{t} + (1-\beta_{2})\boldsymbol{g}_{t+1}^{\odot 2}. Suppose that at time τ\tau, we encounter a change in the conditional expectation of the coordinate-wise gradient i.e. E[gt+1⊙2∣Ft]=st\mathbb{E}[\boldsymbol{g}_{t+1}^{\odot 2} \mid \mathcal{F}_{t}] = \boldsymbol{s}_{t} where st=s+\boldsymbol{s}_{t} = \boldsymbol{s}^{+} for t>τt > \tau. For simplicity, we assume that s+\boldsymbol{s}^{+} is constant after τ\tau. Taking conditional expectations, we find E[vτ+1∣Fτ]=β2vτ+(1−β2)s+\mathbb{E}[\boldsymbol{v}_{\tau+1} \mid \mathcal{F}_{\tau}] = \beta_{2}\boldsymbol{v}_{\tau} + (1-\beta_{2})\boldsymbol{s}^{+}. Continuing this recursively and using the tower property, one finds that E[vτ+k∣Fτ]=β2kvτ+(1−β2k)s+\mathbb{E}[\boldsymbol{v}_{\tau+k} \mid \mathcal{F}_{\tau}] = \beta_{2}^{k}\boldsymbol{v}_{\tau} + (1-\beta_{2}^{k})\boldsymbol{s}^{+}.

Now subtracting s+\boldsymbol{s}^{+}, we find E[vτ+k∣Fτ]−s+=β2k(vτ−s+)\mathbb{E}[\boldsymbol{v}_{\tau+k} \mid \mathcal{F}_{\tau}] - \boldsymbol{s}^{+} = \beta_{2}^{k} (\boldsymbol{v}_{\tau} - \boldsymbol{s}^{+}). Suppose we want this discrepancy to be at most a fraction c∈(0,1)c \in (0,1). That is, ∥E[vτ+k∣Fτ]−s+∥≤c∥vτ−s+∥\lVert \mathbb{E}[\boldsymbol{v}_{\tau+k} \mid \mathcal{F}_{\tau}] - \boldsymbol{s}^{+} \rVert \leq c \lVert \boldsymbol{v}_{\tau} - \boldsymbol{s}^{+} \rVert. Assuming the initial discrepancy is non-zero, this implies that β2k≤c\beta_{2}^{k} \leq c which requires k≥log⁡(1/c)/−log⁡(β2)k \geq \log(1/c) / -\log(\beta_{2}). For β2\beta_{2} sufficiently close to 11, we find that −log⁡(β2)≈1−β2-\log(\beta_{2}) \approx 1 - \beta_{2}. Thus we see that k∼log⁡(1/c)/(1−β2)k \sim \log(1/c) / (1- \beta_{2}) steps are required to overcome lag caused by distribution shift. This would persist even if a bias-corrected conditional proxy was used.

AuthorsOpenReview ↗

Response To Reviewer N1Ez (Part 3/5)

W3/Q4. We thank the reviewer for this suggestion. We agree that comparing upper bounds alone does not establish an actual performance ordering between Adam and SGD. To illustrate the noise–drift tradeoff, we consider an analytically tractable moving quadratic. To isolate the first-moment mechanism, we first derive exact asymptotic expected tracking errors for SGD and a fixed-preconditioner momentum which will contain an explicit noise-drift tradeoff. Although this calculation does not include adaptive second-moment estimation, we additionally consider a two-step moving-quadratic example for standard bias-corrected Adam. This will yield a finite-time tradeoff within only two steps to illustrate the qualitative phenomenon is not restricted to fixed preconditioning.

We first consider the asymptotic result. Consider a moving quadratic Gt(θ)=(θ−ut)2/2G_{t}(\boldsymbol{\theta}) = (\boldsymbol{\theta} - u_{t})^{2} / 2 where ut=A(−1)tu_{t} = A(-1)^{t} with A>0A > 0. We obtain stochastic gradients of the form gt+1=θt−ut+1+ξt+1\boldsymbol{g}_{t+1} = \boldsymbol{\theta}_{t} - u_{t+1} + \xi_{t+1} where ξt+1\xi_{t+1} are independent, centered, bounded random variables with variance σ2\sigma^{2}. We first compare against fixed preconditioning so let p>0p > 0 be a fixed scalar preconditioner and choose matched step-sizes αSGD=αADAMp=k\alpha_{\mathrm{SGD}} = \alpha_{\mathrm{ADAM}}p = k. Note that the strong-convexity constants are μSGD=1\mu_{\mathrm{SGD}} = 1, μADAM=p\mu_{\mathrm{ADAM}} = p.

SGD: The form of the updates for SGD are as follows: θt+1=(1−k)θt+kut+1−kξt+1\boldsymbol{\theta}_{t+1} = (1-k)\boldsymbol{\theta}_{t} + ku_{t+1} -k\xi_{t+1}. Since ut=A(−1)tu_{t} = A(-1)^{t}, we know that E[θt]=b(−1)t\mathbb{E}[\boldsymbol{\theta}_{t}] = b(-1)^{t} for some b>0b > 0 as the minimizer alternates between AA and −A-A and SGD follows a stable linear recursion. Taking expectations of the SGD update and substituting quantities, one finds b=kA/(2−k)b = kA / (2-k). Thus one can compute the squared bias approximately as follows:

\begin{align} (\mathbb{E}[\boldsymbol{\theta}_{t}] - u_{t})^2 \approx \frac{4(1-k)^2}{(2-k)^2}A^2. \end{align}

For the centered iterate, we have zt+1=θt+1−E[θt+1]=(1−k)zt−kξt+1\boldsymbol{z}_{t+1} = \boldsymbol{\theta}_{t+1} - \mathbb{E}[\boldsymbol{\theta}_{t+1}] = (1-k)\boldsymbol{z}_{t} - k\xi_{t+1}. Thus squaring this expression and taking expectations, one will find E[zt+12]=(1−k)2E[zt2]+k2σ2\mathbb{E}[\boldsymbol{z}_{t+1}^2] = (1-k)^2\mathbb{E}[\boldsymbol{z}_{t}^2] + k^2 \sigma^2 (using the fact that ξt\xi_{t} is independent, centered, and has bounded variance σ2\sigma^2). Its stationary variance can then be found to be V=kσ2/(2−k)V = k\sigma^2 / (2-k) via simple algebra. Combining the squared bias and the variance, we find

\begin{align} \mathcal{E}_{\mathrm{SGD}} = \frac{4(1-k)^2}{(2-k)^2}A^2 + \frac{k\sigma^2}{2-k}. \end{align}

Fixed preconditioner Adam: Consider mt+1=β1mt+(1−β1)gt+1\boldsymbol{m}_{t+1} = \beta_{1}\boldsymbol{m}_{t} + (1-\beta_{1})\boldsymbol{g}_{t+1} and θt+1=θt−kmt+1\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_{t} - k\boldsymbol{m}_{t+1}. One will find the form of updates for fixed preconditioner Adam are as follows: θt+1=[1+β1−k(1−β1)]θt−β1θt−1+k(1−β1)ut+1−k(1−β1)ξt+1\boldsymbol{\theta}_{t+1} = [1 + \beta_{1} - k(1-\beta_{1})]\boldsymbol{\theta}_{t} - \beta_{1}\boldsymbol{\theta}_{t-1} + k(1-\beta_{1})u_{t+1} - k(1-\beta_{1})\xi_{t+1}.

Doing a similar kind of computation for bb and computing the squared tracking bias and stationary variance, one will obtain the following expression for the tracking error:

\begin{align} \mathcal{E}_{\mathrm{ADAM}} = \frac{4[1 + \beta_{1} - k(1-\beta_{1})]^2}{[2(1+\beta_{1}) - k(1-\beta_{1})]^2}A^2 + \frac{k(1+\beta_{1})}{2(1+\beta_{1}) - k(1-\beta_{1})}\sigma^2. \end{align}

These stationary expressions hold when the respective linear recursions are stable, so we require 0<k<20 < k < 2 for SGD and 0<k(1−β1)<2(1+β1)0 < k(1-\beta_{1}) < 2(1+\beta_{1}) for fixed preconditioner Adam. If we take k=0.2k = 0.2 and β1=0.9\beta_{1} = 0.9, substituting these values into the tracking errors above yields

\begin{align} \mathcal{E}_{\mathrm{SGD}} &= \frac{64}{81}A^2 + \frac{1}{9}\sigma^2 \\ \mathcal{E}_{\mathrm{ADAM}} &= \frac{35344}{35721}A^2 + \frac{19}{189}\sigma^2. \end{align}

Thus one exactly sees that ESGD<EADAM\mathcal{E}_{\mathrm{SGD}} < \mathcal{E}_{\mathrm{ADAM}} provided σ2<3560A2/189\sigma^2 < 3560A^2 / 189 and ESGD>EADAM\mathcal{E}_{\mathrm{SGD}} > \mathcal{E}_{\mathrm{ADAM}} provided σ2>3560A2/189\sigma^2 > 3560A^2 / 189, establishing an ordering on the expected algorithmic error with an explicit noise-drift tradeoff.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of our rebuttals

We sincerely thank all reviewers for their thoughtful feedback and constructive suggestions. We are encouraged that the reviewers found the research question important and well-motivated, our theoretical analysis informative, and the noise–drift tradeoff between Adam and SGD interesting and relevant to nonstationary optimization.

In response to the reviews, we have strengthened our theoretical results, provided additional guarantees and examples, and clarified the scope and implications of our analysis. In particular, we have addressed the following points:

  • We derived a refined bound that explicitly depends on temporal gradient variation rather than solely on the domain diameter, providing a more informative characterization of Adam's first-moment behavior under nonstationarity (see Reviewer N1Ez W1/Q1 and Reviewer LcAb Q2/W1).

  • We provided an explicit derivation showing how the second-moment estimator responds to distribution shifts with an adaptation lag of order O(1/(1−β2))\mathcal{O}(1/(1-\beta_2)) (see Reviewer N1Ez Q3).

  • We explained how Adam and SGD can be compared under a common function class, the necessity of adaptive strong monotonicity, and why our tracking guarantees should be interpreted as locally strongly convex rather than genuinely nonconvex (see Reviewer LcAb Q1 and Reviewer N1Ez W2/Q2).

  • Beyond comparing upper bounds, we constructed explicit moving-quadratic examples in which a performance ordering between Adam and SGD can be established in different noise–drift regimes. We also established an additional projected-stationarity guarantee for SGD under general smooth objectives to facilitate direct comparisons in the nonconvex setting (see Reviewer N1Ez W3/Q4 and Reviewer fain W1).

  • We provided additional high-probability bounds under sub-exponential, bounded conditional variance, and finite pp-th moment assumptions, and discussed how these affect the high probability rates and qualitative conclusions (see Reviewer fain Q1).

  • We will include a compact comparison table summarizing the assumptions, guarantees, and relevant prior work, simplify the main theorem statements, and provide clearer interpretations of our results. We also identified and corrected an experimental figure inconsistency and clarified the evaluation metrics and experimental setup (see Reviewer fain W1 and Reviewer N1Ez Q5/W3).

We believe these additional results and clarifications substantially strengthen the manuscript and provide a more complete understanding of the theoretical and practical implications of our work. We will incorporate these improvements into the revised manuscript. We sincerely thank the reviewers again for their time, careful consideration, and valuable suggestions and hope they consider raising their scores in light of our responses. We would be happy to address any remaining questions or concerns during the discussion period.

We would also like to sincerely thank the Area Chair for handling our submission and overseeing the review process. We hope that the additional theoretical results, examples, and clarifications provided in our responses will be taken into consideration in the final evaluation, and we would be grateful for the Area Chair's support of our work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.