- 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
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!
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) is indeed loose even when β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 Θ. 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 Θ, 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 L-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!