ADOPT: Modified Adam Can Converge with the Optimal Rate with Any Hyperparameters

Thank you for your insightful comments. We will answer your questions to address your concerns. Please also refer to the general response, in which the revision during the rebuttal period is explained.

Our assumptions seem stronger than existing analyses on Adam

As you mentioned, our Assumption 4 requires the true gradient $\nabla f$ to be bounded although the stochastic gradient $g$ does not need to be bounded. Hence, the difference between Assumptions 4 and 5 is that Assumptions 4 does not assume the gradient noise $\|| g - \nabla f \||$ to be bounded; instead, it assumes the variance of the stochastic gradient, i.e., $\mathbb{E} [ \|| g - \nabla f \||^2 ]$, to be bounded, which is weaker than the bounded noise assumption.

Although Li et al. (2023) do not assume the true gradient $\nabla f$ to be bounded, they instead assume that the gradient noise $\|| g - \nabla f \||$ is bounded, which is not assumed in our analysis. They also provide a result where the bounded noise assumption is relaxed to a sub-Gaussian noise norm assumption, but the convergence rate gets a little worse in that case.

Therefore, our assumptions are not quite stronger in total compared to existing analyses on Adam (e.g., Li et al. (2023)), and our result of ADOPT's optimal convergence without depending hyperparameters is much stronger than existing results on Adam, which require problem-dependent tuning of hyperparameters. We also discuss the relation to existing analyses in detail in the general response and Appendix A in the revised paper, so please also refer to them.

Counter example in the case of random shuffling

Thank you for pointing it out. We did not recognize that there is a counter example where ADOPT cannot converge when applying without-replacement sampling (a.k.a. random shuffling) instead of with-replacement sampling. Since random shuffling violates Assumption 2, it is out of scope of our theory; hence the existence of such a counter example does not contradict to our theoretical findings. However, as you mentioned, practitioners often use random shuffling, so we have come to think that the existence of a counter example in the random shuffling setting should be mentioned in the paper. Therefore, we have added a discussion on it in Appendix B in the revised version.

We would like to emphasize again that the non-convergent issue in such a counter example can be easily avoided by using with-replacement sampling. Moreover, the difference between with- and without-replacement sampling becomes negligible when the dataset size is large enough, so it does not affect the practical performance very much. In fact, our experiments except for the toy example are performed using without-replacement sampling, but divergent behaviors are not observed.

We would be glad to respond to any further questions and comments that you may have.

Thanks.

Thank you again for your efforts in reviewing our paper and your constructive comments. The discussion period will end soon, so please let us know if you have further comments about our reply to your feedback.

Thanks.

Thank you for your insightful comments. We will answer your questions to address your concerns. Please also refer to the general response, in which the revision during the rebuttal period is explained.

On the assumptions of our analysis compared to existing ones

As you mentioned, our Assumption 4 is stronger than the growth condition adopted in Zhang et al. (2022). Zhang et al. (2022) instead assume that the stochastic gradient $g$ is Lipschitz continuous, which is a stronger assumption than ours, in which only the true gradient $\nabla f$ is assumed to be Lipschitz. Moreover, Zhang et al. (2022) focus on the finite-sum problems, whereas we deal with general nonconvex problems. Therefore, our assumptions are not quite stronger in total compared to existing analyses on Adam, and our result of ADOPT's optimal convergence without depending hyperparameters is much stronger than existing results on Adam, which require problem-dependent tuning of hyperparameters. We also discuss the relation to existing analyses in detail in the general response and Appendix A in the revised paper, so please also refer to them.

Proof technique seems to be similar to that of Zhou et al. (2019)

Zhou et al. (2019) only consider a single convex optimization problem in their analysis, but our analysis deals with general smooth nonconvex optimization problems; hence the scope of our analysis is much broader than theirs. Moreover, techniques used for the proofs are also very different, so we think that our theoretical contribution is not minor compared to Zhou et al. (2019). About the theoretical contribution, we have added a detailed discussion in the general response and Appendix A in the revised paper, so please also refer to it.

Experimental gain seems marginal and error bars are missing in Tables 1 and 2

In the revised version, we have added error bars in Tables 1 and 2, which may help to show that the experimental gain is not so marginal. In addition, to clearly show the superiority of ADOPT over Adam (and AMSGrad), we have revised the toy experiment. Please see the general response for a detailed experimental settings. This experiment clearly shows that Adam tends to fail to converge when the gradient noise is large, even if $\beta_2$ is chosen to be close to 1 (e.g., 0.999), whereas ADOPT can always converge to the solution without careful tuning of hyperparameters.

We would be glad to respond to any further questions and comments that you may have.

Thanks.

Thank you again for your efforts in reviewing our paper and your constructive comments. The discussion period will end soon, so please let us know if you have further comments about our reply to your feedback.

Thanks.

Thank you for your insightful comments. We will answer your questions to address your concerns. Please also refer to the general response, in which the revision during the rebuttal period is explained.

Convergence bounds are too loose

We agree that the bounds in the original submission were too loose to be meaningful, so we have revised the theorems to derive tighter bounds. We believe that this will address your main concern.

Ablation study on each algorithmic modification

Thank you for an insightful suggestion. We have added an ablation study on algorithmic modifications from Adam to ADOPT in Section 5. As can be seen in Figure 2 in the revised paper, ADOPT fails to converge if either of the two modifications (i.e., decorrelation between $g_t$ and $v$, and change of order of momentum and scaling operation) is not applied. This result aligns with the theoretical finding, and helps it to be more convincing.

Large variance of empirical results

In Figure 1 of the original submission, ADOPT seems to have high variance when $\sigma = 10$ compared to Adam and AMSGrad, but we do not think that it is not because ADOPT is less robust. First of all, Adam does not even converge to the correct solution, so the variance comparison is less meaningful. As for AMSGrad, its variance seems lower than ADOPT, but this is because $v_t$ of AMSGrad is non-decreasing in terms of $t$, so the effective learning rate tends to be lower than ADOPT. If the learning rate of ADOPT is set to a lower value, the variance of ADOPT will also decrease.

In addition, ADOPT's high variance in Figure 3 of the original submission is just due to the nature of deep reinforcement learning (RL). In deep RL, the variance tends to be larger as the agent obtains high reward, so this phenomenon is quite natural.

Moreover, in the revision during the rebuttal period, we have added error bars in Tables 1 and 2, and we observe that the variance of ADOPT is not higher than baselines (e.g., AdamW).

On the bias correction technique

In fact, we have tried to add the bias correction technique of Adam to our ADOPT, and it empirically worked well. However, it did not bring performance improvement (also did not harm the performance) in practice, so we exclude it from our implementation for simplicity. Our hypothesis on why the bias correction is less meaningful for ADOPT is that $v_t$ is initialized to $1$ for ADOPT to prevent it from being too small at the first parameter update, so the effect of bias correction is limited compared to Adam. Moreover, as for the momentum $m_t$, initialization with $0$ works like a warm-up of the learning rate, so it may have a positive effect for stable training especially in the early phase of optimization. Although there might be a better way to introduce a technique like the bias correction for ADOPT, we leave it for future work. We have added a discussion on the bias correction in Appendix C in the revised version.

We would be glad to respond to any further questions and comments that you may have.

Thanks.

Thank you again for your efforts in reviewing our paper and your constructive comments. The discussion period will end soon, so please let us know if you have further comments about our reply to your feedback.

Thanks.

Thank you for your insightful comments. We will answer your questions to address your concerns. Please also check the general response, in which the revision during the rebuttal period is explained.

On theoretical contribution

As you mentioned, some previous works (e.g., Zhang et al. (2022)) demonstrate that the original Adam can converge without any modifications. However, they require to choose hyperparameters (e.g., $\beta_1$ and $\beta_2$) in a problem-dependent manner, as we stated in Sections 1 and 2.2. This constraint is problematic even in a practical sense, because we do not have access to the problem-specific parameters (e.g., $L$ and $G$ in our paper), so we need to heuristically tune the hyperparameters for each problem. Hence, to assure the convergence in general cases, algorithmic modifications are still essential as pointed out by Reddi et al. (2018). Although there have been some investigations on modifying Adam to assure convergence (e.g., AMSGrad), such methods require additional assumptions (e.g., bounded stochastic gradient) for convergence guarantees. Our theoretical contribution is on demystifying the fundamental cause of divergence of Adam, and proposing a modification without imposing a strong assumption like bounded stochastic gradient.

To clarify these points, we have added a detailed discussion in Appendix A in the revised paper, so please also refer to it for more details.

Empirical investigations on hyperparameter sensitivity

We agree that our original experiments lacked the comparison of hyperparameter sensitivity between Adam and ADOPT, so we have revised our toy experiment in Section 5 (see the general response for detailed settings). In the experiment, we observe that Adam's convergence is sensitive to the choice of $\beta_2$ depending on the problem setting, whereas our ADOPT successfully converge without depending on the hyperparameter choice.

We would be glad to respond to any further questions and comments that you may have.

Thanks.

Thank you again for your efforts in reviewing our paper and your constructive comments. The discussion period will end soon, so please let us know if you have further comments about our reply to your feedback.

Thanks.