AdaGrad under Anisotropic Smoothness

Thank you very much for the careful reading and insightful opinions. Below we would like to provide some discussions on the points.

Weakness 1 & 2: SGD convergence can depend on $|| w_0 - w _ * ||_2$.

Thanks for the insightful question. It is true that the SGD convergence can actually depend on $|| w_0 - w_* ||_2$, but only when the step size is chosen to be $\eta_t \equiv \eta = \mathcal{O}(\frac{1}{\sqrt{T}})$ because we consider a constrained optimization case in convex settings as mentioned in Assumption 3.1. However, it is common and usually more efficient to use a larger step size sequence with $\eta_t = \mathcal{O}(\frac{1}{\sqrt{t}})$ in this setting, which leads to dependence on $D_2$ of the convergence rate (as in Theorem D.1).

Weakness 3: Theorem 4.1 assumes that $\mathbf{L}_1=0$, which sounds a bit strong assumption.

Thanks a lot for pointing out. We would like to first apologize for this typo in Theorem 4.1 as $\mathbf{L}_1$ should not appear and we are actually employing Assumption 3.3 here. We didn't use the more general assumption with $\mathbf{L}_1 \neq 0$ in the convex setting mainly because we want to use this simpler convex setting to make it easier for readers to understand how the anisotropic assumptions can help describe the convergence of AdaGrad. Also, for a lot of popular convex machine learning problems, e.g. linear and logistic regression, the smoothness with $\mathbf{L}_1=0$ is sufficient to describe the settings well.

Weakness 4: It was confusing which term corresponds to "bias term" in line 272.

Thank you very much for noting the issue. The bias term in line 272 mainly refers to the $\mathcal{O}(1/T)$ term in the convergence rate, which is irrelevant with the noise and corresponds to the convergence of bias in training dynamics. We have made corresponding modifications to make this clearer in our new revision.

Dear Reviewer JNL4,

We deeply appreciate your insightful suggestions and helpful comments. It has been an honor to receive your feedback and to know that you recognize our contribution.

Your assistance in clarifying potential concerns with our manuscript has been invaluable, and we have worked diligently to address them in our response and our new revision. As the discussion period deadline approaches, we would greatly value any further feedback you might have on our response. Your input is crucial in helping us address any remaining concerns.

We fully understand your busy schedule and are sincerely grateful for the effort you have already dedicated to enhancing our work. We look forward to hearing any additional thoughts you may have.

Thank you once again for your guidance and support.

Best,

Submission 8883 authors

The reviewer thanks the authors for the response.

However, it is common and usually more efficient to use a larger step size sequence with $\eta_t = \mathcal{O} (\frac{1}{\sqrt{t}})$ in this setting, which leads to dependence on $D_2$ of the convergence rate (as in Theorem D.1).

The reviewer can not agree with this comment so far. Theorem 5.7 in [1] showed that SGD with $\eta = \frac{1}{4 L \sqrt{t+1}}$ can converge with the rate that does not depend on $D_2$. Please correct me if the reviewer misunderstood.

The reviewer knows that the many existing analyses of the adaptive stepsize, e.g., AdaGrad, also assumed that the set of feasible solutions is bounded, and their convergence rates depend on the diameter of the set of feasible solutions. Thus, the reviewer believes this is a presentation issue and not a critical issue in this paper, but the reviewer feels that it is not fair to compare the rate of SGD shown in Eq. (6) and the rate shown in Theorem 4.1 since we can replace $D_2$ with $\| w_0 - w^\star \|$ in the rate shown in Eq. (6).

Even taking the above points into consideration, the reviewers feel that this paper is overall worthy of being accepted. The reviewer would like to keep the score, which is already positive.

Reference

[1] Garrigos et. al., Handbook of Convergence Theorems for (Stochastic) Gradient Methods, In arXiv 2024

We would like to express our appreciation for the reviewer's effort in checking our paper. Thanks! We are happy to provide the following discussions regarding the mentioned points.

Weakness 1: The results are not surprising, and hence I didn't find the analysis/statements to be novel.

Thanks for the comment. We would like to also make some further clarifications of the novelty of this work:

1. To our knowledge, this result is the first one that theoretically shows the benefits of coordinate-wise step size in the general smooth optimization settings. The result is as expected based on numerous empirical observations, but being the first one to concretely lay the foundation to bridge theory and practice is also important, which can shed light on a more rigorous understanding of the effectiveness of adaptive gradient methods and inspire even more efficient algorithms in the future.

2. Regarding the technical novelty, as we have discussed in Remark 5.4, our analysis refers to the main line of existing results but incorporates better proof techniques to enable more general assumptions and clean results.

Weakness 2: In addition to reviewing Adagrad analyses, it would be helpful to review anisotropic analysis.

This is certainly a good suggestion! Beyond AdaGrad, we have also discussed sign-based optimization methods that uses anisotropic smoothness assumptions, existing understanding of advantages of adaptive gradient methods in Section 2. In our new revision, we additionally add some more discussions on coordinate descent and other related work might employ the anisotropic smoothness assumption.

Weakness 3: Some results that can make the work more impressive.

Thanks a lot for the insightful suggestions. A lower bound for the adaptivity over dimensions can be of interest to see whether adaptive gradient methods are good enough and whether we can, as the reviewer pointed out, design even faster algorithms.

However, as these investigations might be beyond our topic in this paper, we will carefully consider these topics as possible future directions. Thanks again for the suggestion!

We would like to extend our sincere appreciation to the reviewer for all the constructive and positive feedback on our contribution. Many thanks!

Question 1: What is the impact of overparametrization to the results in this work?

Thanks for the insightful suggestion! We add a part in the paper discussing the impact of over-parameterization in convex settings in Appendix E.1. Basically, we consider the noise $\sigma_*$ only on $w_*$, the optimum manifold. In this case, we change the anisotropic smoothness to be expected anisotropic smoothness and obtain convergence results under these adjusted assumptions. By this setting, we have the following convergence rate for over-parameterized models (which usually result in interpolation of the data and thus $\sigma_* = E[|\nabla_{w} f(w_*;\xi)|] = 0$): $\mathcal{O}\left( \frac{||L_*|| _ 1 D_\infty^2}{T} \right)$ where $L_* \in \mathbb{R}^d$ is the anisotropic expected smoothness. Therefore, we basically improve the convergence rate to $\mathcal{O}(1/T)$ for over-parameterized models.

Question 2: It is also important to see how well the convergence of the loss (or gradients) are controlled by these coefficients and norms.

Thanks for the constructive suggestion. We will definitely include the mentioned results in our final revision.

Question 3: It is better to show how the loss converges and how do the authors select hyperparameters.

Thanks for the helpful comment. We include the corresponding results in Table 3 and Figure 2 for loss convergence and Appendix A for the parameter selection.

We thank the reviewer for the insightful comments and questions. We would like to provide the following discussions regarding the weakness part and questions.

Weakness: Assumptions limits the applicability to the setting of interests, as neural networks.

We appreciate the reviewer's idea that theoretical assumptions can limit the application of the theory. But we also want to kindly note that our key novel assumption, the anisotropic generalized smoothness assumption has been verified by GPT-2 experiments in Figure 1, which provide a certain degree of evidence for bridging the theory and practice in realistic settings like training neural networks.

Question: Better Comparison with (Maladkar et. al. 2024).

Thanks for the question. The starting point of this work and Maladkar et. al. (2024) is quite similar in that we both utilize anisotropic smoothness assumptions to obtain better convergence results for AdaGrad. However, there are some major differences between the two papers.

1. As we noted in the paper, our results apply to the anisotropic generalized smoothness settings. This is a more general setting that can well describe practical neural network training (as shown in Figure 1) and covers the results in Maladkar et. al. (2024).

2. We include a convex part in our paper, which is a simpler case for illustrating the power of anisotropic assumptions. Based on this part and our new assumption and theory, we also did various empirical verifications in the experiment part, which provides strong evidence for our theory.

3. We also note that compared to ours, Maladkar et. al. (2024) introduced a lower bound for gradient $\ell_1$-norm convergence of SGD under nonconvex anisotropic assumptions, which may help a more rigorous comparison between SGD and AdaGrad in the nonconvex case. However, as we have discussed in Section 4, it's not clear whether $\ell_1$-norm is a better convergence measure and it actually depends on the properties of the training curvature.

To conclude, both the work contribute to a better theoretical understanding of the benefits of adaptive gradient methods.

We have also included this more detailed discussion in our revision. Thanks again for the constructive suggestion.

Question: Is much work required to generalize to Adam?

We believe generalization to Adam should be applicable, but technical issues remain. Basically the main problem is how to deal with the momentum together with the adaptive gradient preconditioner in the stochastic nonconvex cases, which makes most Adam analysis worse than AdaGrad ones, in terms of worse convergence rates and/or stricter noise assumptions. Because of the failure to prove the benefits of adding the momentum term, currently, we think an extension to Adam might only provide little insight. However, this should definitely be a good future direction.

Dear Reviewer FCcu,

We deeply appreciate your insightful suggestions and helpful comments. It has been an honor to receive your feedback and to know that you recognize our contribution.

Your assistance in making a more detailed related work and discussion on further extensions has been invaluable, and we have worked diligently to address this in our response and our new revision. As the discussion period deadline approaches, we would greatly value any further feedback you might have on our response. Your input is crucial in helping us address any remaining concerns.

We fully understand your busy schedule and are sincerely grateful for the effort you have already dedicated to enhancing our work. We look forward to hearing any additional thoughts you may have.

Thank you once again for your guidance and support.

Best,

Submission 8883 authors