A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD

Dear Reviewer LTUb,

We sincerely appreciate your thorough evaluation of our manuscript and your positive feedback. Your recognition of our theoretical framework and the establishment of convergence rates for Adam under weak assumptions is highly encouraging.

We acknowledge your suggestion to include an application example demonstrating the practical implications of our theoretical findings. While our primary focus has been on the theoretical aspects, we understand the value of illustrating how our results can address scenarios previously unmanageable by earlier works. In response, we plan to incorporate a relevant application example in our revised manuscript to highlight the practical applicability of our theoretical contributions.

Thank you once again for your insightful comments and for your recommendation to accept our work. Your feedback has been instrumental in enhancing the quality and impact of our manuscript.

Sincerely,

Authors of Paper 1314

Rebuttal to Reviewer nypN

Dear Reviewer nypN,

Thank you very much for your thoughtful feedback and constructive comments on our manuscript. We sincerely appreciate the time and effort you have put into reviewing our work. We are grateful for your insights, and we have carefully addressed each of your points below in the hope of clarifying our contributions and improving the manuscript.

1. Dependence on Dimensionality and $\beta_1$ in Theorem 3.1

You raised a question regarding the dependence on dimensionality and $\beta_1$ in Theorem 3.1. Specifically, you asked about the formal version of the sample complexity result in the theorem.

Response: In Theorem 3.1, the sample complexity result concerning $1-\beta_1$ and the dimension $d$ is of the order $\mathcal{O}\left(\frac{d}{(1-\beta_1)^2}\right)$. This result is consistent with previous works on the convergence of Adam, such as [1]. We would like to emphasize that while it is possible to remove the dependence on the dimension $d$, we cannot avoid reintroducing the dependence on the inverse of the smoothing factor, which is $\mathcal{O}(\text{poly}(1/\mu))$. This is a well-known consensus in previous studies [2]. We hope this clarification addresses your concern.

2. Extension of Results to Other Smoothness Settings

You asked whether our results could be extended to other smoothness settings, as in [3, 4, 5], and whether this could potentially remove the additional dependence on dimensionality, helping to bridge the gap between SGD and Adam.

Response: We believe that it is highly probable to extend our results to other smoothness settings, and we are excited about exploring this in future work. However, we must admit that this area was not covered in our previous research, and therefore, we cannot provide a definitive answer at this moment. Nonetheless, we plan to address this issue in our future research, where we will explore the possibility of extending our results to more general smoothness assumptions and examine whether the additional dependence on dimensionality can be removed.

3. General Smoothness Cases (e.g., $L_0-L_1$ Smoothness)

You inquired whether our proof can extend to more general smoothness cases, such as $L_0-L_1$ smoothness.

Response: We are currently investigating this direction and have made some progress. Specifically, we have made the following two extensions so far:

1. For $(L_0-L_0.5)$ smooth functions: We can derive convergence results for Adam under the traditional second-moment-based ABC inequality. However, the sample complexity still shows dependence on the inverse of the smoothing factor $1/\mu$, though we can eliminate the dependence on the dimension $d$.

2. For $(L_0-L_1)$ smooth functions: At this stage, our methods are unable to extend the convergence results under the traditional second-moment-based ABC inequality. However, we can obtain convergence results under the traditional second-moment Bounded Variance condition. It is worth noting that, as of now, there are no known results for Adam’s convergence under $(L_0-L_1)$ smoothness with the traditional second-moment Bounded Variance condition.

We are continuing to investigate these extensions and will include them in future work. We greatly appreciate your interest in this aspect and will strive to address it in subsequent studies.

4. Additional Comments and Acknowledgements

We sincerely appreciate your review, which has helped us identify areas for clarification and potential improvement. We value your suggestions and will ensure that these aspects are thoroughly explored in our future research. Your feedback has significantly contributed to the refinement of our manuscript, and we hope that the revisions we have made have addressed your concerns effectively.

If you have any further questions or suggestions, please do not hesitate to reach out. We are more than happy to discuss any aspects of our work in greater detail. Once again, thank you for your careful review and constructive feedback.

We look forward to your final assessment.

[1] Bohan Wang, Jingwen Fu, Huishuai Zhang, Nanning Zheng, and Wei Chen. Closing the gap be- tween the upper bound and lower bound of Adam’s iteration complexity. Advances in Neural Information Processing Systems, 36, 2024a.

[2] Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of Adam under relaxed assump- tions. Advances in Neural Information Processing Systems, 36, 2024.

[3] Bernstein J, Wang Y X, Azizzadenesheli K, et al. signSGD: Compressed optimisation for non-convex problems. International Conference on Machine Learning. PMLR, 2018: 560-569.

[4] Liu Y, Pan R, Zhang T. AdaGrad under Anisotropic Smoothness. arXiv preprint arXiv:2406.15244, 2024.

[5] Xie S, Mohamadi M A, Li Z. Adam Exploits $\mathcal{l}_\infty$-geometry of Loss Landscape via Coordinate-wise Adaptivity. arXiv preprint arXiv:2410.08198, 2024.

Sincerely,

Authors of Paper 1314

Dear Reviewer JhWZ,

Thank you for your thoughtful and constructive feedback on our paper. We greatly appreciate the time and effort you’ve put into reviewing our work. We carefully considered your comments, and we would like to address the main concern regarding the differences between our approach and the paper by Hong and Lin (2024), as well as clarify the analytical techniques and assumptions used in our paper.

In the paper by Hong and Lin (2024), the authors introduce an affine noise variance assumption that differs from the traditional second-moment-based affine noise variance assumption:

Instead, they strengthen the concentration property of the random variables by assuming the following (their Assumption A.3) :

Their proof is heavily dependent on this condition, making their approach inapplicable for analyzing the traditional second-moment-based affine variance noise conditions. For a detailed explanation, please refer to their open-access paper: Hong and Lin, 2024.

Hong and Lin's proof relies extensively on Lemma B.6, which is proven using concentration inequalities (shown in their Appendix D.2). Under the Exponential-tailed Affine Variance Noise Condition, these inequalities yield an $O(\ln T)$ order factor for the sample complexity term $\mathcal{M}_T$. However, when considering traditional affine variance noise conditions based solely on second-order moment assumptions, only an $O(\text{poly}(T))$ factor can be derived for $\mathcal{M}_T$, which may not yield the desired results.

Our paper employs the ABC inequality, which is even weaker than traditional affine variance noise conditions. This necessitates fundamentally different analytical methods, particularly based on discrete Martingale analysis, distinguishing our approach from that of Hong and Lin (2024).

Thank you again for your time and thoughtful evaluation of our work. If you have any further questions, please don't hesitate to discuss them with us.

Sincerely,

Authors of Paper 1314

Dear Reviewer,

We sincerely appreciate your thorough evaluation of our manuscript and your insightful feedback. Your recognition of our theoretical framework is highly encouraging.

Incorporation of Assumption Comparisons into the Main Text:

We acknowledge your suggestion to move the discussion comparing our assumptions, particularly the ABC inequality, with previous ones from the appendix to the main body of the paper. We agree that this adjustment will enhance the clarity and accessibility of our work. In the revised manuscript, we will integrate this discussion into the main text, providing a concise comparison and highlighting the theoretical insights gained from using the ABC inequality. Additionally, we will discuss parallel results in stochastic gradient descent (SGD) analyses that employ similar assumptions to further contextualize our contributions.

Clarification on the Behavior of Adam When $\beta_{2,t}$ Does Not Approach 1:

Regarding your concern about the definition of the hyperparameter $\beta_{2,t}$ converging to 1, we appreciate the opportunity to clarify this point. In scenarios where $\beta_{2,t}$ does not approach 1, Adam's convergence behavior differs. Specifically, under such conditions, Adam may only ensure that the gradient converges to a small neighborhood around zero rather than exactly to zero. To achieve convergence of the gradient to zero, it is necessary for $\beta_{2,t}$ to approach 1. This requirement has been highlighted in previous studies, such as the work by [1] on the convergence of Adam. In our current paper, we focused on aligning Adam's convergence results with those of SGD, which led us to adopt the condition where $\beta_{2,t}$ approaches 1. We acknowledge that this aspect was not explicitly discussed in our manuscript, and we will address this omission in future research by exploring scenarios where $\beta_{2,t}$ does not approach 1.

Thank you once again for your valuable comments and suggestions. Your feedback has been instrumental in improving the clarity and depth of our work.

[1] Zhang Y, Chen C, Shi N, et al. Adam can converge without any modification on update rules[J]. Advances in neural information processing systems, 2022, 35: 28386-28399.

Sincerely,

Authors of Paper 1314