Online learning meets Adam: The Road of Interpretable Adaptive Optimizer Design

We thank reviewer ecRp for the valuable feedback. Below, we try to address each of the reviewer’s concerns in detail.

1. $*Theorem B.2 of (Ahn et al 2024)*$ We thank the reviewer for pointing out this clarity issue. Theorem B.2 in [1] includes the term $\max_{t \in [1, T]}|\Delta_{t}|$, which is the source of the clipping operation in the following work [2]. This result indicates that the upper bound on regret depends on the maximum value of the incremental $|\Delta_{t}|$. However, rather than providing a generalized formula, a problem-dependent characteristic (value) is expected in a bound. Thus, in the following work, [2] proposes an explicit clipping strategy to achieve a clear upper bound.
   This background motivates our own approach, where we address this issue and remove the need for such unrealistic clipping. We hope this addresses the main concern.

2. $*last-iterate guarantee*$ Considering the result of last-iterate convergence of SGD for convex problem in [1], it shows that $\mathbb{E}[f(x_{T}) - f(x^{\star})] \leq \text{Constant}$ (also the high probability version: $f(x_{T}) - f(x^{\star}) \leq \text{Constant}$ with some probability). Our statement on the last-iterate guarantee offers the insight that the last iterate has a higher likelihood of being selected compared to other iterations, distinguishing it from the last-iterate guarantee statements in [3,4]. We have clarified this distinction in the revised paper on line 452. We believe this approach aligns with practical practice, where the final few iterations are typically prioritized and guaranteed. And, it improves from the previous result in [3] that spreads convergence evenly across all iterations, and offers useful insights for future research in this area.

3. $*insights on Adam*$ We thank the reviewer for pointing out this clarity issue. This work emphasizes a more interpretable design principle for Adam, refining prior results by eliminating the unrealistic clipping operation through initially analyzing the involvement of $\beta_{2}$ and offering the insight that the last iterate has a higher likelihood of being selected compared to other iterations, which also improves from previous work.
   We acknowledge that a critical question remains: “Why is Adam effective?”. Prior research, as noted, suggests that “SGD achieves the minimax optimal convergence rate under smooth nonconvex conditions,” yet Adam often outperforms SGD in practice. The effectiveness of Adam over other methods is another emerging topic in analyzing Adam, however, this work initially focuses on interpretable Adam design and does not provide such insights. We do hold great interest in expanding on this topic in future work.

4. $*hyperparameter*$ As noted in the discussion, the practical values typically used ($\beta, \beta_{2}$) in applications do not conform to the theoretical conditions, a limitation also observed in prior work [1]. This presents an interesting avenue for future investigation.

[1] Ahn, Kwangjun, et al. "Understanding Adam optimizer via online learning of updates: Adam is FTRL in disguise." arXiv preprint arXiv:2402.01567 (2024).

[2] Kwangjun Ahn and Ashok Cutkosky. Adam with model exponential moving average is effective for nonconvex optimization. arXiv preprint arXiv:2405.18199, 2024.

[3] Liu, Zijian, and Zhengyuan Zhou. "Revisiting the last-iterate convergence of stochastic gradient methods." arXiv preprint arXiv:2312.08531 (2023).

[4] Xiaoyu Li, Mingrui Liu, and Francesco Orabona. On the last iterate convergence of momentum methods. In International Conference on Algorithmic Learning Theory, pp. 699–717. PMLR, 2022.

We thank the reviewer JZLb for the positive feedback. Below we try to address the questions of the reviewer.

1. $*Assumptions in this work and results of prior work*$ In our study, particularly in the fourth point of Assumption 2.1, the bounded variance assumption for the stochastic gradient, combined with the G-Lipschitz assumption, implies a bounded gradient. Assumption 2.2 further constrains the power of the comparator $u$. These assumptions align with standard conditions for online-to-nonconvex conversions, as referenced in line 106.
   Additionally, our work examines the classical Adam algorithm through an online learning framework, which introduces some differences in assumptions compared to prior research that typically assumes smooth nonconvex conditions, as mentioned in the related work section. Since we focus specifically on the online learning approach, we have not conducted an extensive survey of results under the smooth nonconvex assumption, but we plan to expand on this aspect upon acceptance.

2. $*comparison with full ADAM algorithm*$ In the discussion section, the discrepancy between the Adam update and the clip-free FTRL update is noted, specifically the absence of bias correction terms in the clip-free FTRL formulation.

3. $*Minor comments*$ Thank you for identifying these clarity issues. The modifications have been implemented in the revised manuscript.

We sincerely thank reviewer ezs8 for the feedback. Below, we try to address each of the reviewer’s concerns in detail.

1. $*The selection of$a$*$ We thank the reviewer for pointing out the boundary condition issue where $||v_{t}||^{2} = 0$, i.e., the squared norm of stochastic gradient after conversion, which results in an undefined value for $a$.Generally, a zero stochastic gradient aligns with the stopping criterion in standard optimization methods. However, for the online learning method discussed here, $v_{t} = 0$ is also `problematic’, as it yields a zero linear loss, i.e., $\ell_{t}(\cdot) = \langle v_{t}, \rangle = 0$. This does not provide feedback to inform the next update. Fortunately, zero loss, which does not impact the regret bound, offers some flexibility in handling boundary values.
   To maintain consistency with the proofs of Lemma 4.1 and Theorem 4.2, we propose skipping updates when zero loss is encountered: if $v_{t} =\mathbf{0}$, we freeze the updating of index $t$, which results in omitting the zero term from subsequent summations and keeping the intermediate state at step $t+1$ identical to that at step $t$. This ensures that $\alpha_{t+1} \leq \alpha_{t}$, consistent with Lemma 4.1. Meanwhile, by removing zero-error loss terms, subsequent steps inherit the immediate state and continue updating according to the iterative rule, as required by Theorem 4.2. These modifications are now reflected in the revised paper on lines 268 and 678.

2. $*$\sqrt{1 - \beta_{2*}$instead of$1 - \beta_{2}} We thank the reviewer for this correction, which has been addressed in the revised text at lines 879 and 304.

3. $*last-iterate guarantee*$ Considering the result of last-iterate convergence of SGD for convex problem in [1], it shows that $\mathbb{E}[f(x_{T}) - f(x^{\star})] \leq \text{Constant}$ (also the high probability version: $f(x_{T}) - f(x^{\star}) \leq \text{Constant}$ with some probability). Our statement on the last-iterate guarantee offers the insight that the last iterate has a higher likelihood of being selected compared to other iterations, distinguishing it from the last-iterate guarantee statements in [1,2].
   We have clarified this distinction in the revised paper on line 452. We believe this approach aligns with practical practice, where the final few iterations are typically prioritized and guaranteed. And, it improves from previous result in [3] that spreads convergence evenly across all iterations, and offers useful insights for future research in this area.

4. $*stylistic comment*$ All suggested stylistic changes have been incorporated in the revised manuscript.

Once again, we thank reviewer ezs8 for the valuable feedback and welcome any further suggestions.

[1] Liu, Zijian, and Zhengyuan Zhou. "Revisiting the last-iterate convergence of stochastic gradient methods." arXiv preprint arXiv:2312.08531 (2023).

[2] Xiaoyu Li, Mingrui Liu, and Francesco Orabona. On the last iterate convergence of momentum methods. In International Conference on Algorithmic Learning Theory, pp. 699–717. PMLR, 2022.

[3] Kwangjun Ahn and Ashok Cutkosky. Adam with model exponential moving average is effective for nonconvex optimization. arXiv preprint arXiv:2405.18199, 2024.

We sincerely thank reviewer GbeF for the feedback. Below, we try to address each of the reviewer’s concerns in detail.

1. $*$\beta_{2* as a constant} We thank the reviewer for pointing out this issue. In the revised manuscript, we specify that $\beta_{2}$ belongs to a specific range rather than being time-variant. This change, reflected in line 696 of the revised manuscript, adjusts our findings, particularly in the setting of $\beta_{2}$, where its magnitude is now $\mathcal{O}(1 - \frac{1}{T})$, compared to the previous time-variant $\mathcal{O}(1 - \frac{1}{t})$. We hope this addresses the main concern raised.

2. $*correction at line 698*$ We thank the reviewer for this correction, which has been addressed in the revised text at line 696.

3. $*denpendance on$\eta$*$ The parameter $\eta$ is tunable and typically selected manually. Consistent with prior work, the optimal value of $\eta$ depends on specific problem characteristics. For our study, we set $\eta = 0.38D$ to achieve the regret bound presented in Theorem 4.2, as outlined in line 876.

4. $*upper bound of$v_{t*} In the conversion of the online learning method to an optimization algorithm, the environment feedback $v_{t}$ represents the stochastic gradient. In our work, particularly in the fourth point of Assumption 2.1, the bounded variance assumption for the stochastic gradient combined with the G-Lipschitz assumption does imply an upper bound. It is worth mentioning that Assumption 2.1 contains the standard conditions for non-convex and non-smooth optimization, as referenced in line 106.

Once again, we thank reviewer GbeF for the valuable comments and welcome any additional suggestions.