Convergence of Distributed Adaptive Optimization with Local Updates

Thanks for recognizing that our mathematical work is a solid extension to previous results! We address your concerns as follows.

W1: The assumption on $\alpha\geq 4$ is uncommon.

A1: As mentioned in Remark 1, in most previous works on high probability convergence, the noise assumptions can be divided into two categories: light tail with bounded exponential moment (sub-gaussian, sub-exponential, bounded), or finite $\alpha$-moment with $1<\alpha\leq 2$. We remark that although $\alpha\geq 4$ is rarely used in the literature, it is still substantially weaker than the sub-gaussian type assumption. And as discussed in Appendix E, if assuming only the polynomial moment is bounded, SGD fails to get a logarithmic dependence on $1/\delta$, where $\delta$ is the confidence level. Therefore, $\alpha\geq 4$ is essentially a type of heavy tailed noise assumption.

In our settings, the assumption $\alpha\geq 4$ is made to make the results much more clean and concise. In the proof, we only use this noise assumption to bound the variance of certain random variables. For instance, in eq (C.44), we need to bound the 4-th moment $\mathbb{E}\|\nabla f(x)-\text{clip}(g,\rho)\|^4$ where $g$ is the stochastic gradient. If $\alpha\geq 4$, then we can directly apply the noise assumption and get $\sigma^4$. On the other hand, if $1<\alpha< 4$, then for large $\rho$ this quantity can be bounded by $\mathcal{O}(\sigma^\alpha\rho^{4-\alpha})$ by Lemma B.2 (also refer to Lemma 5.1 in [1]). The subsequent analysis is similar but will lead to a worse dependence on $\rho$. Therefore, our techniques can be easily generalized to the case when $\alpha<4$, but the results will be much more messy, which is also beyond the scope of this paper to show the benefits of local updates in adaptive optimization.

W2: Inaccurate claims on "Local SGDM outperforms the minibatch counterparts".

A2: Thanks for the advice. The advantages of Local SGDM appear only in the large $M,K$ regime. The original statement is indeed inaccurate and we have adjusted it accordingly.

W3: The optimal choice of K and the advantages of Local SGDM over mini-batch SGDM.

A3: One doesn't need to take $K\rightarrow\infty$ to exhibit the adavantages of Local SGDM. It suffices to let $M, K$ large enough so that the noise term $\frac{\sigma}{\sqrt{MKR}}$ (or $\frac{\sigma^2}{\mu MKR}$ in strongly convex case) will be dominated. In this case, the convergence of Minibatch SGDM will be impeded by the first term in eq (4.5), which only depends on $R$. Moreover, since our convergence rate for SGDM is almost the same with SGD in [2], the discussion therein on the choice of $K$ is also valid in our setting. Hence, the theoretical adavantages of Local SGDM can be guaranteed in large $M$ and large $K$ regime.

W4: The convergence criteria of Local Adam based on $\|\cdot\|_{H_r^{-1}}$ is not meaningful.

A4: The matrix $H_r$ is indeed algorithmic-dependent and we leave the expression in Theorem 3 in the main text to in order to be consistent with previous papers. Nevertheless, in Theorem D.3 in appendix, we rigorously analyze the bound of $H_r$ and provide the convergence rate of euclidean norm of gradient, which will introduce an additional multiplier $(1+\frac{G_\infty+\sigma_\infty}{\lambda})$. From this we see that large $\lambda$ can indeed enhance the rate. However, we point out that the bound on $H_r$ there is very pessmistic and large $\lambda$ is also not aligned with common practice of Adam. We leave the impact of the choice of $\lambda$ as an interesting future work.

[1] Sadiev, Abdurakhmon, et al. "High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance." International Conference on Machine Learning. PMLR, 2023.

[2] Woodworth, Blake, et al. "Is local SGD better than minibatch SGD?." International Conference on Machine Learning. PMLR, 2020.

We are glad the reviewer finds our results solid! We address the concerns as follows.

W1: The assumption on $\alpha\geq 4$ is uncommon.

A1: As mentioned in Remark 1, in most previous works on high probability convergence, the noise assumptions can be divided into two categories: light tail with bounded exponential moment (sub-gaussian, sub-exponential, bounded), or finite $\alpha$-moment with $1<\alpha\leq 2$. We remark that although $\alpha\geq 4$ is rarely used in the literature, it is still substantially weaker than the sub-gaussian type assumption. And as discussed in Appendix E, if assuming only the polynomial moment is bounded, SGD fails to get a logarithmic dependence on $1/\delta$, where $\delta$ is the confidence level. Therefore, $\alpha\geq 4$ is essentially a type of heavy tailed noise assumption.

In our settings, the assumption $\alpha\geq 4$ is made to make the results much more clean and concise. In the proof, we only use this noise assumption to bound the variance of certain random variables. For instance, in eq (C.44), we need to bound the 4-th moment $\mathbb{E}\|\nabla f(x)-\text{clip}(g,\rho)\|^4$ where $g$ is the stochastic gradient. If $\alpha\geq 4$, then we can directly apply the noise assumption and get $\sigma^4$. On the other hand, if $1<\alpha< 4$, then for large $\rho$ this quantity can be bounded by $\mathcal{O}(\sigma^\alpha\rho^{4-\alpha})$ by Lemma B.2 (also refer to Lemma 5.1 in [1]). The subsequent analysis is similar but will lead to a worse dependence on $\rho$. Therefore, our techniques can be easily generalized to the case when $\alpha<4$, but the results will be much more messy, which is also beyond the scope of this paper to show the benefits of local updates in adaptive optimization.

W2: The lack of clear dependence on $\beta_1$.

A2: Thanks for the advice. We omit $\beta_1$ to make the results more concise. In fact we keep the dependence on $\beta_1$ in the main theorems in appendix (Theorem C.3, Theorem D.1), based on which we obtain the ultimate convergence rate by plugging in the parameters. We will also make this more clear in the main text.

W3: The assumptions implies that the set of feasbile solutions are bounded.

A3: Our Assumption 2,4,5 is mainly following the previous work ([1]). We admit that this type of assumptions is still restricted in some sense, but it is much more general than the commonly used global smoothness (convexity) assumption, which is the case when $\Omega=\mathbb{R}^d$. We hope future works can explore more relaxed assumptions.

[1] Sadiev, Abdurakhmon, et al. "High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance." International Conference on Machine Learning. PMLR, 2023.

The reviewer thank the authors for their response.

The reviewer agrees with Reviewer FvoJ and still believes that it would be better to add the results with $\alpha < 4$ if the authors would like to say "our analysis methods can be easily extended to the case where $\alpha < 4$" in Remark 1. The reviewer personally believes that the authors must not say it is easy without showing the results with $\alpha < 4$ since it might cause trouble for future studies that consider the case with $\alpha < 4$.

Thanks for regarding our work as an important theoretical contribution to understand the empirical success of Adam with local step! We address your concerns as follows.

W1: The paper addresses only the homogeneous data case.

A1: We'd like to mention that homogeneous case is practical for distributed training of large language models, where a huge dataset is often assigned to multiple computation nodes in a homogeneous way. The heterogeneous case is definitely another interesting topic but the analysis will also get more challenging as well. We hope this work can inspire more researches on the local updates in heterogenous case.

W2: The noise assumptions on $\alpha\geq 4$ are restrictive compared to previous works.

A2: As mentioned in Remark 1, in most previous works on high probability convergence, the noise assumptions can be divided into two categories: light tail with bounded exponential moment (sub-gaussian, sub-exponential, bounded), or finite $\alpha$-moment with $1<\alpha\leq 2$. We remark that although $\alpha\geq 4$ is rarely used in the literature, it is still substantially weaker than the sub-gaussian type assumption. And as discussed in Appendix E, if assuming only the polynomial moment is bounded, SGD fails to get a logarithmic dependence on $1/\delta$, where $\delta$ is the confidence level. Therefore, $\alpha\geq 4$ is essentially a type of heavy tailed noise assumption.

In our settings, the assumption $\alpha\geq 4$ is made to make the results much more clean and concise. In the proof, we only use this noise assumption to bound the variance of certain random variables. For instance, in eq (C.44), we need to bound the 4-th moment $\mathbb{E}\|\nabla f(x)-\text{clip}(g,\rho)\|^4$ where $g$ is the stochastic gradient. If $\alpha\geq 4$, then we can directly apply the noise assumption and get $\sigma^4$. On the other hand, if $1<\alpha< 4$, then for large $\rho$ this quantity can be bounded by $\mathcal{O}(\sigma^\alpha\rho^{4-\alpha})$ by Lemma B.2 (also refer to Lemma 5.1 in [1]). The subsequent analysis is similar but will lead to a worse dependence on $\rho$. Therefore, our techniques can be easily generalized to the case when $\alpha<4$, but the results will be much more messy, which is also beyond the scope of this paper to show the benefits of local updates in adaptive optimization.

Q1: What are the theoretical advantages of adaptive methods over non-adaptive one?

A3: In fact, even in centralized case (single machine), we are still not aware of any theoretical convergence result that can show the benefits of adaptive methods over non-adaptive one. Nevertheless, given the strong widespread practical improvements of Adam over SGD, we believe it is a useful first step to show that adaptive methods perform at least as well as SGD. Likely more assumptions would be necessary to show the theoretical improvements. This is still an interesting open question and we hope our work can motivate related researches.

Q2: The statement "the first end-to-end convergence guarantee for distributed adaptive algorithms with local iterations" is not accurate.

A4: Thanks for sharing these references and we have included them in the revision. Here "end-to-end" refers to the common gradient based local optimizer, instead of the exact proximal operator in [2,3], which is inaccessible in most cases. Also the "adaptive" means Adam-like algorithms. We will make this statement more precise.

[1] Sadiev, Abdurakhmon, et al. "High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance." International Conference on Machine Learning. PMLR, 2023.

[2] Li, Hanmin, Kirill Acharya, and Peter Richtarik. "The Power of Extrapolation in Federated Learning." arXiv preprint arXiv:2405.13766 (2024).

[3] Anyszka, Wojciech, et al. "Tighter Performance Theory of FedExProx." arXiv preprint arXiv:2410.15368 (2024).

Q5: How to interprete the convergence criteria of Local Adam based on $\|\cdot\|_{H_r^{-1}}$? In what way will it be affected by the choice of $\lambda$?

A5: The matrix $H_r$ is indeed algorithmic-dependent and we leave the expression in Theorem 3 in the main text to in order to be consistent with previous papers. Nevertheless, in Theorem D.3 in appendix, we rigorously analyze the bound of $H_r$ and provide the convergence rate of euclidean norm of gradient, which will introduce an additional multiplier $(1+\frac{G_\infty+\sigma_\infty}{\lambda})$. From this we see that large $\lambda$ can indeed enhance the rate. However, we point out that the bound on $H_r$ there is very pessmistic and large $\lambda$ is also not aligned with common practice of Adam. We leave the impact of the choice of $\lambda$ as an interesting future work.

[1] Zhang, Jingzhao, et al. "Why are adaptive methods good for attention models?." Advances in Neural Information Processing Systems 33 (2020): 15383-15393.

[2] Sadiev, Abdurakhmon, et al. "High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance." International Conference on Machine Learning. PMLR, 2023.

Thanks for appreciating our technical contributions! We address your concerns as follows.

Q1: The in-expectation convergence is stronger than the high probability convergence due to the Markov inequality.

A1: We kindly disagree with the point that in-expectation result is stronger than high probability one. By Markov inequality, the in-expectation bound can indeed be transferred to high probability bound, but with $\mathcal{O}(\frac{1}{\delta})$ depedence, where $\delta$ is the confidence level. This is much worse than our result which has $\mathcal{O}(poly(\log\frac{1}{\delta}))$ dependence. On the other hand, if we have high probability convergence bound depending only on $\log\frac{1}{\delta}$, then we can easily bound the expectation by $\mathbb{E}[X]=\int_0^\infty \mathbb{P}(X\geq x)dx$ for any non-negative random variable $X$. Therefore, the high probability result is generally stronger than the in-expectation result.

Q2: All the theorems are based on Assumption 2, which is just the usual smoothness assumption instead of $(L_0,L_1)$ smoothness.

A2: We'd like to point out that Assumption 2 is much weaker than the usual smoothness assumption since we only have a bounded smoothness $L$ in a subset $\Omega$ of $\mathbb{R}^d$, where $\Omega$ is usually definded as a sub-level set of the loss function in our theorems. We remark that it is substantially differnt from the usual global smoothness. As have mentioned in line 238-245 and the footmark therein, our assumption can be implied by $(L_0, L_1)$ for a given sub-level set $\Omega$, and in general, it is a non-trival part of our analysis to show that the iterates stay in $\Omega$ with high probably. Hence $(L_0,L_1)$ smoothness can be covered by Assumption 2.

Q3: How can entrywise noise bound in Assumption 3 be translated to the usual norm bound? How to interprete the assumption $\||\boldsymbol{\sigma}\||_{2\alpha} d^{\frac{1}{2}-\frac{1}{2\alpha}}=\mathcal{O}(\sigma)$ in terms of dimension dependence?

A3: As we aim to deal with entry-wise clipping operator, it is natural to assume entry-wise noise bound instead of common norm bound ([1]). In Assumption 3, when $\alpha\geq 2$, we will have $\mathbb{E}\||\nabla F(x;\xi) - \nabla f(x)\||^\alpha\leq \||\boldsymbol{\sigma}\||^\alpha=\sigma^\alpha$ by Holder inequality, where $\||\cdot\||$ is the $\ell_2$ norm. Additionally, if the noise is isotropic so that $\sigma_i\asymp \sigma_1$ for any $1\leq i\leq d$, then we have $\||\boldsymbol{\sigma}\||\_{2\alpha}=(\sum_i\sigma_i^{2\alpha})^{\frac{1}{2\alpha}}\asymp d^{\frac{1}{2\alpha}}\sigma_1\asymp d^{\frac{1}{2\alpha}-\frac{1}{2}}\sigma$. Therefore, the assumption $\||\boldsymbol{\sigma}\||_{2\alpha} d^{\frac{1}{2}-\frac{1}{2\alpha}}=\mathcal{O}(\sigma)$ does not introduce additional dimension dependence term.

Q4: Why to assume $\alpha\geq 4$?

A4: As mentioned in Remark 1, in most previous works on high probability convergence, the noise assumptions can be divided into two categories: light tail with bounded exponential moment (sub-gaussian, sub-exponential, bounded), or finite $\alpha$-moment with $1<\alpha\leq 2$. We remark that although $\alpha\geq 4$ is rarely used in the literature, it is still substantially weaker than the sub-gaussian type assumption. And as discussed in Appendix E, if assuming only the polynomial moment is bounded, SGD fails to get a logarithmic dependence on $1/\delta$, where $\delta$ is the confidence level. Therefore, $\alpha\geq 4$ is essentially a type of heavy tailed noise assumption.

In our settings, the assumption $\alpha\geq 4$ is made to make the results much more clean and concise. In the proof, we only use this noise assumption to bound the variance of certain random variables. For instance, in eq (C.44), we need to bound the 4-th moment $\mathbb{E}\|\nabla f(x)-\text{clip}(g,\rho)\|^4$ where $g$ is the stochastic gradient. If $\alpha\geq 4$, then we can directly apply the noise assumption and get $\sigma^4$. On the other hand, if $1<\alpha< 4$, then for large $\rho$ this quantity can be bounded by $\mathcal{O}(\sigma^\alpha\rho^{4-\alpha})$ by Lemma B.2 (also refer to Lemma 5.1 in [1]). The subsequent analysis is similar but will lead to a worse dependence on $\rho$. Therefore, our techniques can be easily generalized to the case when $\alpha<4$, but the results will be much more messy, which is also beyond the scope of this paper to show the benefits of local updates in adaptive optimization.