Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions

We thank the reviewer for their constructive feedback.

Q1 It would be better if the comparison between SGD and AdaGrad in convex settings is provided, for both $\ell_2$-norm measure (I guess it belongs to the existing literature) and $\ell_1$-norm stationary measure.

A1 Thank you for the suggestion. In the convex setting, a common performance metric is the function value gap, $F(\mathbf{w}) - F^*$. It has been shown that depending on the geometry of the feasible set and the sparsity of the gradients, AdaGrad's convergence bound can be either better or worse than that of SGD by a factor of $\sqrt{d}$, where $d$ is the problem's dimension. For more detailed discussions, we refer the reviewer to (Hazan, 2016; Orabona 2019). As for comparisons based on the gradient $\ell_2$-norm and $\ell_1$-norm in the convex setting, to our knowledge, this has not been explored in the literature. While our convergence results would also apply in this setting, they may not yield the tightest bounds.

Q2 The improvement of AdaGrad over SGD is demonstrated with abstract assumptions on smoothness and noise. Can the paper give a concrete example or more primitive assumptions (such as in the Abstract motivation of training neural networks) when those proposed assumptions are satisfied?

A2 Thank you for your suggestion. We note that our assumptions are relatively standard and have been adopted in prior works such as (Bernstein et al., 2018), which also provided empirical validation for Assumption 2.3b. However, as acknowledged in their paper, verifying Assumption 2.4b in practical neural network training problems can be challenging.

On the other hand, it is not hard to construct simple examples that satisfy the refined assumptions. For instance, consider the quadratic function $F(\mathbf{w}) = \sum_{i=1}^d (\frac{1}{2}L_i (w^{(i)})^2 + b_i w^{(i)})$, where $L_i>0$ and $b_i$ are scalars, and $w^{(i)}$ denotes the $i$-th coordinate of $\mathbf{w} \in \mathbb{R}^d$. We can verify that this function satisfies Assumption 2.4b. Moreover, suppose the stochastic gradient $\mathbf{g}_t$ is given by $\mathbf{g}_t = \nabla F(\mathbf{w}_t) + \mathbf{n}_t$, where $\mathbf{n}_t$ is the stochastic noise satisfying $\mathbb{E} [({n}_t^{(i)})^2] \leq \sigma_i^2$. Under these conditions, Assumption 2.3b is also satisfied.

Q3 In the non-convex setting, this paper utilizes the $\ell_1$-norm of the gradient as the stationarity measure and compares the convergence rate. When comparing different optimization algorithms, they might converge to different stationary points (such as due to initialization and implicit bias). How does the initialization impact the AdaGrad dynamics? Is there any discussion on the works for the implicit bias of SGD and AdaGrad in non-convex settings?

A3 Thank you for your suggestion. In non-convex optimization, it is indeed possible for different optimization algorithms to converge to different stationary points, leading to potentially different generalization properties. There are several recent works on the implicit bias of AdaGrad and SGD, including (Qian and Qian, 2019; Wang et al., 2021; Lyu and Li, 2020). However, our focus in this paper is on the optimization perspective, where we consider all stationary points equivalently, and exploring implicit bias lies beyond the scope of our current work.

Qian, Qian, and Xiaoyuan Qian. "The implicit bias of AdaGrad on separable data." NeurIPS 2019.

Wang, B., Meng, Q., Chen, W., and Liu, T. Y. "The implicit bias for adaptive optimization algorithms on homogeneous neural networks." ICML 2021.

Lyu, Kaifeng, and Jian Li. "Gradient Descent Maximizes the Margin of Homogeneous Neural Networks." ICLR 2020.

Q4 Even though the paper is theoretical, it would be beneficial to demonstrate the gain of dimension dependence using some numeric experiments, i.e., the gap between the AdaGrad upper bound and SGD lower bound, and their difference in iteration complexity when changing dimensions.

A4 Thank you for your suggestion. While additional numerical experiments would provide valuable insights, our focus in this paper is on establishing theoretical foundations for the advantage of coordinate-wise adaptive methods over SGD. Our assumptions are also relatively standard and have been adopted in prior work, such as (Bernstein et al., 2018). Our results provide provable guarantees for when and why these methods outperform scalar SGD and AdaGrad-norm under specific conditions, which aligns with existing empirical observations in the literature. We believe this theoretical framework sufficiently supports our claims, and we encourage future empirical work to explore these conditions in greater detail.

We thank the reviewer for their constructive feedback.

Q1 The refined assumptions used are not particularly novel; similar approaches have been explored in previous works. Additionally, the use of the L1-norm for the theoretical analysis has been discussed in recent literature, limiting the paper's overall novelty.

A1 Thank you for your feedback. We acknowledge that the refined assumptions and the use of the $\ell_1$-norm have been explored in prior works. However, the key novelty of our paper lies in our complexity lower bound results. To the best of our knowledge, this is the first work to establish lower bounds in terms of the $\ell_1$-norm while explicitly highlighting the dimensional dependence in the convergence rate. Moreover, our approach is distinct from standard techniques for deriving lower bounds in optimization, such as those based on the zero-chain constructions [Carmon et al., 2020; Arjevani et al., 2023], which focus on dimension-free lower bounds. By directly comparing the lower bound for SGD with the upper bound for AdaGrad, we are also able to establish a provable advantage of AdaGrad over SGD in the non-convex setting, which, to our knowledge, is the first in the literature.

Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 2020.

Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 2023.

Q2 The authors have already highlighted the main differences between this paper and [1], noting that [1] examines the upper bound for SGD, while this paper focuses on the lower bound. However, despite this distinction, the two papers remain quite similar. A more in-depth discussion of the unique techniques or specific analytical steps that differentiate this work would enhance the clarity and contribution of the paper.

A2 Thank you for your question. First, we would like to note that paper [1] appeared on arXiv two weeks after the initial version of our paper was online. While there are some overlapping contributions, we consider [1] to be concurrent and independent work. Therefore, it should not be viewed as a weakness of our paper.

Specifically, as we discussed in our introduction, the authors of [1] considered the convergence of AdaGrad under anisotropic smoothness and noise assumptions, similar to our refined assumptions 2.3b and 2.4b. They also established an upper bound on AdaGrad’s convergence in terms of the gradient’s $\ell_1$-norm, comparable to our Theorem 3.1.

A key distinction, however, lies in how the two works compare AdaGrad and SGD. To demonstrate AdaGrad's advantages over SGD, the authors in [1] rely on the classical upper bound for SGD using $\ell_2$-norm under standard smoothness and noise assumptions. This may not be the most fair comparison, as a direct analysis of SGD in terms of $\ell_1$-norm with refined assumptions could potentially yield a stronger bound. Essentially, they are comparing an upper bound for AdaGrad against an upper bound for SGD, which could be loose. In contrast, our work provides a lower bound for SGD, allowing us to directly compare AdaGrad’s upper bound with SGD’s lower bound to demonstrate a clear advantage for AdaGrad. Moreover, we validate the tightness of our AdaGrad upper bound through two lower specific bounds: one tailored to AdaGrad and another applicable to deterministic first-order methods.

Q3 The lack of experimental validation is a significant shortcoming. While the paper emphasizes theoretical analysis, some empirical results would be beneficial. Demonstrating that AdaGrad reduces the bound of SGD by a factor of d through experiments—especially by varying the value of d—would greatly support the theoretical claims.

A3 Thank you for your suggestion. While additional numerical experiments would provide valuable insights, our focus in this paper is on establishing theoretical foundations for the advantage of coordinate-wise adaptive methods over SGD. Our results provide provable guarantees for when and why these methods outperform SGD and AdaGrad-norm under specific conditions, which aligns with existing empirical observations in the literature. We believe this theoretical framework sufficiently supports our claims, and we encourage future empirical work to explore these conditions in greater detail.

We thank the reviewer for their constructive feedback.

Q1 When comparing with SGD, especially when the lower bound utilizes new coordinate-wise smoothness, one should also consider a coordinate wise version of SGD as a baseline i.e. SGD with stepsize $\eta_i = \Theta(1/L_i)$ for each $i \in [d]$.

A1 Thank you for your suggestion. We agree that the coordinate-wise version of SGD could serve as an idealized baseline for AdaGrad. However, this algorithm is impractical because the coordinate-wise Lipschitz constants $L_i$ are typically unknown. If we treat these coordinate-wise step sizes as hyperparameters and rely on manual tuning, this process becomes intractable as the number of the hyperparameters scales with the problem's dimension. Hence, to our knowledge, unlike the vanilla SGD, such coordinate-wise SGD has not been successfully used for practical problems. We also wish to emphasize that our focus is to demonstrate the advantage of AdaGrad over SGD in the non-convex setting, which remains a challenging open problem [Chen & Hazan, 2024]. While we agree that the ability to automatically adapt to Lipschitz constants is a key advantage of AdaGrad, its coordinate-wise nature is also essential to understanding its gains over SGD.

Q2 The worst-case comparison on lines 358-362 is not clear: For example, if $\sigma_i = 1$ for all $i$, then $\\|\sigma\\|_2 = \sqrt{d}$ and $\\|\sigma\\|_1 =d$. There, the dimensional dependency is still $d$ and not $\sqrt{d}$. What am I missing?

A2 We apologize for the confusion. In this discussion, our aim is to present our convergence bounds under the standard assumptions (i.e., Assumption 2.3a and Assumption 2.4a), to facilitate the comparison with existing results. In the worst case, this yields the bound $\\tilde{\\mathcal{O}}\\Bigl(\\sqrt{\\frac{d\\|\mathbf{L}\\|\_{\\infty}\\Delta\_F}{T}} + \sqrt{d}\left({\frac{{\\|\boldsymbol{\sigma}\\|^{2}\_{2} {\\|\mathbf{L}\\|\_{\infty}\Delta_F}}}{{T}}} \right)^{\frac{1}{4}} + \frac{{\sqrt{d}\\|\boldsymbol{\sigma}\\|\_2}}{T^{\frac{1}{4}}}\Bigr)$. Therefore, if we focus on the explicit dependence on the dimension, ignoring $\\|\mathbf{L}\\|_{\infty}$, $\\|\boldsymbol{\sigma}\\|_2$ and $\Delta_F$ as is common in prior work, this bound simplifies to $\tilde{\mathcal{O}}(\frac{\sqrt{d}}{\sqrt{T}} + \frac{\sqrt{d}}{T^{1/4}})$. We will clarify this point further in the revision.

Q3 Previous work [Liu et al. 2023] provides $\ell_1$-norm convergence in high probability for sub-Gaussian coordinate-wise noise for AdaGrad. There, I don't think it's fair to compare results in high probability with results converge in expectation (in the related works section and Appendix A).

A3 Thank you for pointing this out. We will revise our paper to clarify that the results in [Liu et al., 2023] are high-probability convergence results and thus not directly comparable to the in-expectation results presented in our work.

Q4 The comparison between AdaGrad and SGD on lines 512-516 is not too convincing. The authors should also comment on the setting when AdaGrad is worse than SGD and discuss the reason behind that.

A4 We would like to clarify that our comparison on lines 512-516 focuses on the upper complexity bound of AdaGrad versus the lower complexity bound of SGD. Specifically, we showed that when the vector $\boldsymbol{\sigma}$ is sparse ($\phi(\boldsymbol{\sigma}) \approx 1/d$) and the noise variance vector is aligned with the smoothness vector ($R \approx 1$), the upper bound of AdaGrad is below the lower bound of SGD, establishing a provable advantage for AdaGrad. Conversely, when $\phi(\boldsymbol{\sigma}) \approx 1$ and $R \approx 0$, the upper bound of AdaGrad is worse than the lower bound of SGD; however, this does not necessarily mean that AdaGrad performs worse than SGD, as neither bound may be exactly tight.

We thank the reviewers for their insightful feedback.

Q1 The provable advantage is clear in the deterministic setting, while for the stochastic setting, the benefit depends, it could be even worse. In real-world applications, it is unknown whether the noise is sparse and aligns with the smoothness parameters.

A1 In the stochastic setting, the comparison between the upper bound of AdaGrad and the lower bound of SGD depends on two key quantities: $\phi(\boldsymbol{\sigma}) = \frac{\\|\boldsymbol{\sigma}\\|^2_1}{d \\|\boldsymbol{\sigma}\\|^2_2}$, which measures the density of the vector $\boldsymbol{\sigma}$, and $R = \frac{\sum_{i=1}^d \sigma_i \sqrt{L_i}}{\|\boldsymbol{\sigma}\|_2 \sqrt{\\|\mathbf{L}\\|_1}}$, which represents the cosine similarity between the vectors $[\sigma_1, \dots, \sigma_d] \in \mathbb{R}^d$ and $[\sqrt{L_1}, \dots, \sqrt{L_d}] \in \mathbb{R}^d$. When the vector $\boldsymbol{\sigma}$ is sparse ($\phi(\mathbf{\boldsymbol{\sigma}}) \approx 1/d$) and the two vectors $[\sigma_1, \dots, \sigma_d]$ and $[\sqrt{L_1}, \dots, \sqrt{L_d}]$ are aligned ($R \approx 1$), AdaGrad reduces the bound of SGD by a factor of $d$. Conversely, when $\phi(\mathbf{\boldsymbol{\sigma}}) \approx 1$ and $R \approx 0$, our upper bound for AdaGrad can indeed be worse than the lower bound of SGD, but this does not imply AdaGrad performs worse than SGD.

In addition, we note that AdaGrad is not expected to outperform SGD in all scenarios. For instance, in the standard online convex optimization setting, it is known that under certain geometry of the feasible set and gradient density conditions, the rate of AdaGrad can be worse than SGD by a factor of $\sqrt{d}$. To the best of our knowledge, our work is the first to identify a specific scenario in which AdaGrad demonstrates a provable advantage over SGD in a non-convex setting.

Q2 It’s unclear why $L_1$-norm convergence is considered a better measure, if not to artificially distinguish between SGD and AdaGrad. Since adaptive methods generally exhibit faster convergence in practice, is there a rationale behind why the $L_1$-norm result aligns more closely with the observations?

A2 This is a good question. We acknowledge that the choice of the $\ell_1$-norm is primarily motivated by theoretical considerations, and in practice, one may still observe a performance gain of AdaGrad over SGD when the gradient $\ell_2$-norm is used. However, formalizing this improvement using $\ell_2$-norm theoretically is challenging, as we explain below.

This difficulty stems from the use of a worst-case complexity analysis (which is standard in optimization literature), and the selection of a stationarity metric affects the class of "worst-case functions" considered. As shown in Theorem 2.1, when the gradient $\ell_2$-norm is chosen as the stationarity metric, the worst-case function for any deterministic first-order method is effectively one-dimensional. Intuitively, SGD and AdaGrad achieve a similar performance on such functions, and thus the advantage of AdaGrad will not be reflected in the wrost-case complexity bound. Conversely, when the gradient $\ell_1$-norm is used as the stationarity metric, the worst-case function is a $d$-dimensional function with an imbalance across the coordinates (see Theorem 4.1), where it is necessary to make progress in all coordinates to achieve low loss. In this setting, the coordinate-wise nature of AdaGrad allows it to outperform SGD as established in our paper.

One might intuitively argue that the worst-case function in the $\ell_1$-norm setup aligns more closely with practical loss functions, as achieving a low loss requires the algorithm to make progress across all coordinates. However, formally verifying this alignment remains challenging, and we leave it as a direction for future work.

Q3 Can we achieve similar advantages if SGD employs a coordinate-wise stepsize, such as $1/(L_i \sqrt{T})$ for the $i$-th coordinate?

A3 Good question. In theory, using coordainte-wise step sizes of $\eta_i = 1/(L_i \sqrt{T})$ in SGD would lead to a convergence rate comparable to AdaGrad. However, this algorithm is impractical because the coordinate-wise Lipschitz constants $L_i$ are typically unknown. If we treat these coordinate-wise step sizes as hyperparameters and rely on manual tuning, this process becomes intractable as the number of the hyperparameters scales with the problem's dimension. In contrast, AdaGrad automatically adjusts the step size for each coordinate based on past observed stochastic gradients, requiring minimal tuning effort.