Communication-efficient Algorithms Under Generalized Smoothness Assumptions

Authors: Sarit Khirirat, Abdurakhmon Sadiev, Artem Riabinin, Eduard Gorbunov, Peter Richtárik
Primary area: optimization
Keywords: Error Feedback; Distributed Learning; Generalized Smoothness; Nonconvex Optimization

Abstract:
We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. 
Despite their popularity and efficiency in training deep neural networks, traditional analyses of error feedback algorithms rely on the smoothness assumption that does not capture the properties of objective functions in these  problems. 
Rather, these problems have recently been shown to satisfy generalized smoothness assumptions, and the theoretical understanding of error feedback algorithms under these assumptions remains largely unexplored. 
Moreover, to the best of our knowledge, all existing analyses under generalized smoothness either i) focus on single-node settings or ii) make unrealistically strong assumptions for distributed settings, such as requiring data heterogeneity, and almost surely bounded stochastic gradient noise variance. 
In this paper, we propose distributed error feedback algorithms that utilize normalization to achieve the $\mathcal{O}(1/\sqrt{K})$ convergence rate for nonconvex problems under generalized smoothness. Our analyses apply for distributed settings without data heterogeneity conditions, and enable stepsize tuning that is independent of problem parameters. 
Additionally, we provide strong convergence guarantees of normalized error feedback algorithms for stochastic settings. 
Finally, we show that normalized EF21, due to its larger allowable stepsizes, outperforms EF21 on various tasks, including the minimization of polynomial functions, logistic regression, and ResNet-20 training.

Decision: reject
Reviewer scores: 5, 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1730489538449

thread_type:
official_review

<thread_object>
creator: reviewer_lkh1

<content>
summary:
This paper mainly considers the normalized EF21 algorithm in distributed settings. It generalizes the existing EF21 algorithm to the $(L_0,L_1)$-smoothness settings and achieves comparable convergence results. In the stochastic settings, the paper incorporates momentum into the algorithm to control the effect of gradient variance. Experimental results are generally consistent with the theoretical claims.

strengths:
1. The paper is well-written and easy to follow. The notation definitions are clear.

2. The theorems are clear and complete. The theoretical results are novel and seem to be sound.

weaknesses:
1. This is a technical solid paper, however, the technical novelty appears limited. I briefly went through the proof and my impression is that the proof primarily combines existing tools on $(L_0,L_1)$-smoothness, error feedback, and analysis of normalized gradient descent with momentum. These are well-established techniques, and the results, while solid, are not particularly surprising. It is possible that I overlooked something important, and I would appreciate it if you would point it out and allocate some space to briefly talk about the technical novelty in this case.

2. I am not sure why Theorem 2 implies the results of NSGD-M as the author mentioned in line 406. There is a mismatch that when $\sigma=0$, i.e. the deterministic case, the order of Theorem 2 is still $\mathcal{O}(T^{-1/4})$, while Theorem 1 in (Cutkosky \& Mehta, 2020) is $\mathcal{O}(T^{-1/2})$. I think maybe you should follow (Cutkosky \& Mehta, 2020) to allow a step size order shift regarding the magnitude of $\sigma$ to fix this.

[1] Ashok Cutkosky, and Harsh Mehta. "Momentum improves normalized sgd." International conference on machine learning. PMLR, 2020.

questions:
1. In Figure 1, it seems that EF21 (without normalization) converges faster in the first place. Could you provide some explanations or comments for this, as it seems this figure may not be strong enough to prove the efficiency of normalized EF21?

2. I am curious whether clipped EF21 rather than normalized EF21 is also applicable to the $(L_0,L_1)$-smoothness setting in the paper.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730688993115

thread_type:
official_review

<thread_object>
creator: reviewer_uygz

<content>
summary:
This paper presents the first convergence proof for normalized error feedback algorithms under generalized smoothness, a condition more applicable to a range of machine learning problems than traditional smoothness assumptions. Existing analyses either focus on single-node setups or make unrealistic assumptions (e.g., data heterogeneity) for distributed settings. Here, the authors propose distributed error feedback algorithms with normalization, achieving an $\(O(1/\sqrt{K})\) $ convergence rate for nonconvex problems without requiring data heterogeneity. The approach also enables stepsize tuning independent of problem parameters. Empirical results show that normalized EF21, which allows larger stepsizes, outperforms EF21 across tasks like polynomial minimization, logistic regression, and ResNet-20 training.

strengths:
1 The paper clearly articulates the limitations of previous approaches and their constraints in proof, while explicitly highlighting the improvements and increased generalizability introduced by the proposed method.

2 This paper presents the first convergence proof for normalized error feedback algorithms under generalized smoothness in a decentralized setting, filling an existing theoretical gap on this issue.

3 The proof appears to follow a standard framework for decentralized problems, making it fairly credible.

weaknesses:
1 The algorithm itself does not present significant innovation, as it primarily combines the standard EF21 with a normalization technique.

questions:
Could you explain the specific challenges encountered in the proof after changing the assumptions and incorporating the normalization step, and how these challenges were addressed?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730870054718

thread_type:
official_review

<thread_object>
creator: reviewer_5w1g

<content>
summary:
**Summary.** The authors present the convergence guarantees for normalized error feedback algorithms for minimizing objectives satisfying generalized smoothness assumption. The proposed algorithm achieves $O(1/\sqrt{K})$ convergence rate for minimizing nonconvex problems. The authors also extend the analysis to stochastic settings. Finally, the authors show via numerical experiments that normalized EF21 outperforms EF21 on various tasks.

strengths:
**Strengths.** Here, I list the major strengths of the paper. 

- The authors present the first analysis of normalized error feedback algorithms in a distributed setting for minimizing non-convex objectives satisfying generalized smoothness conditions. The proposed algorithm matches the guarantees of the standard error feedback algorithms under classical smoothness assumptions. 

-  The authors also show convergence under the stochastic settings. 
- The authors numerically evaluate the performance of the proposed algorithm.

weaknesses:
**Weaknesses.** Here, I list my major concerns and comments. 

- The discussion on the requirement of heterogeneity assumption by the earlier algorithms and the proposed algorithm not requiring the assumption is slightly misleading. In my understanding, heterogeneity assumption is usually needed if the local machines conduct multiple updates while the proposed algorithm, Normalized EF21, only conducts a single local update. So naturally the heterogeneity assumption is not required in contrast to the works of Crawshaw et al. (2024) and Liu et al. (2022) where the local machines conduct multiple local updates.  The authors should clarify the connection between their single local update approach and the lack of heterogeneity assumptions. Additionally, how does the proposed algorithm perform with multiple local updates, and whether heterogeneity assumptions would then become necessary?

- Why both Assumptions 1 and 2 are required? Assumption 2 implies Assumption 1, moreover, I believe it should be possible to conduct analysis only with Assumption 1.  Please justify the inclusion of both assumptions or revise the analysis to rely only on Assumption 1 if possible.

- For the stochastic setting, usually, the speed-up with the number of clients in the performance is desired. However, the presented analysis does not capture the effect of the number of clients on the performance.  Does the proposed algorithm achieve linear speed-up with the number of clients? Please analyze or discuss the scalability of the proposed algorithm with respect to the number of clients.

- In Theorem 1, is there an upper bound on the requirement of $\gamma_0$? Why such a bound is not necessary for Theorem 1 but is required in Theorem 2?
 
- The presented numerical results are very weak. The authors have compared the performance of their algorithm only against the EF21 algorithm. However, there are several federated baselines (with and without compression) against whom the authors should compare their algorithm. For example, the baselines like FedAvg, CHOCO-SGD, Momentum based algorithms, etc.

questions:
Please see the weaknesses above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731048186486

thread_type:
official_review

<thread_object>
creator: reviewer_nrsr

<content>
summary:
This paper proposes normalized error feedback algorithms across a variety of settings and provides convergence guarantees for this family of algorithms. The paper also provides experimental results on various settings such as logistic regression with non-convex regularizer. Notably, the convergence guarantees only rely on the general smoothness condition, which is a generalization of the classical smoothness condition.

strengths:
The paper relaxes the classical smoothness condition to the generalized smoothness condition. Furthermore, the convergence guarantee is competitive and matches the SOTA.

weaknesses:
My main concern with this paper is the only notable contribution is the relaxation from the classical smoothness condition to the generalized smoothness condition. While it is indeed an interesting result, the analysis is known from Chen et al. 2023 and various other works. And so, the theoretical analysis is not too impressive.

The empirical settings are a bit limited and not well-motivated but this is only a minor point.

The paper does not present well the communication aspect of the algorithm, nor its proof idea.

Minor comment:
- The word "expectation" should be capitalized in Table 1.

questions:
- The paper does not present the communication-efficient aspect of the algorithm well, and it is not clear what is the communication protocol. The paper should state this explicitly. Furthermore, there is no analysis on the communication complexity. Is it the same as the sample complexity?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732008866173

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We thank all reviewers for appreciating our contributions on providing the first convergence analysis for normalized error feedback algorithms for distributed optimization under generalized smoothness. In particular, Reviewer nRsr, 5w1G, and Uygz highlights that our novel convergence results of normalized error feedback algorithms under $(L_0,L_1)$-smoothness match prior results of standard error feedback algorithms under traditional smoothness. 

Next, we would like to address two main concerns shared among the reviewers. 

> **Concern 1) Convergence results rely on the analyses known from prior works, e.g. Chen et al. 2023. Technical novelty appears limited, because technical proof relies on well-established techniques on  $(L_0,L_1)$-smoothness, error feedback, and analysis of normalized gradient descent with momentum.**

Our paper addresses the open problem of studying communication-compression algorithms under generalized smoothness. Our convergence analysis introduces novel proof techniques that differ significantly from prior literature on communication-compression algorithms.

**Unexplored Theoretical Understanding.**  Theoretical analysis of error feedback algorithms under generalized smoothness remains largely unexplored. Prior studies predominantly assume **traditional smoothness** to establish convergence guarantees for such algorithms.

**Emerging Research on Generalized Smoothness.**  The analysis of gradient-based algorithms under generalized smoothness has gained recent attention only within the last five years. The **generalized smoothness condition** was first proposed by Zhang et al. (2020b) and later refined by Chen et al. (2023) to cover a broader range of machine learning problems. Very recent works, including Chen et al. (2023), Koloskova et al. (2023), and Hübler et al. (2024), have imposed generalized smoothness to analyze gradient-based algorithms.  

**The Role of Normalization in EF21 Under Generalized Smoothness.**  While the original EF21 designed for traditional $L$-smoothness can be extended to generalized $(L_0, L_1)$-smoothness, its performance is limited without normalization. Specifically:  

- Under generalized smoothness, deriving the convergence of EF21 can be done by proving $\Vert \nabla f(x) \Vert \leq B$, allowing the smoothness constant to be defined as $L := L_0 + L_1B$. However, this smoothness constant $L$ can be potentially small, resulting in slower convergence for EF21, as its step size is constrained to $\gamma = \mathcal{O}(1/L)$ to ensure theoretical convergence.  

- In contrast, normalized EF21 benefits from a step size of $\gamma = \gamma_0 / \sqrt{K+1}$, where $\gamma_0, K > 0$. This enables faster convergence, as demonstrated in our experiments for minimizing polynomial functions in Figure 1, and for solving non-convex logistic regression problems in Figure 2. 


**Novel Proof Techniques for EF21 under Generalized Smoothness.**  Our analysis demonstrates that normalized EF21 achieves a convergence rate under generalized smoothness equivalent to EF21 under traditional smoothness. However, our proof techniques differ from these previous works.

**Lyapunov Function Innovation:**  We rely on different Lyapunov functions. For **EF21**, we use the Lyapunov function $V^k := f(x^k) - f^{\inf} + \frac{A}{n} \sum_{i=1}^n \Vert \nabla f_i(x^k) - v_i^k \Vert$, unlike Richtárik et al. (2021), which uses $V^k := f(x^k) - f^{\inf} + \frac{B}{n} \sum_{i=1}^n \Vert \nabla f_i(x^k) - v_i^k \Vert^2$.  For **EF21-SGDM**, we adopt $V^k := f(x^k) - f^{\inf} + \frac{C}{n} \sum_{i=1}^n \Vert v_i^k - g_i^k \Vert$, unlike Fatkhullin et al. (2024), which utilizes $V^k := f(x^k) - f^{\inf} + \frac{D}{n} \sum_{i=1}^n \Vert v_i^k - g_i^k \Vert^2 + \frac{E}{n} \sum_{i=1}^n \Vert g_i^k - \nabla f_i(x^k) \Vert^2$.

**Convergence Rate Derivation:** These novel Lyapunov functions necessitate the development of new techniques to derive convergence rates that match those presented in the prior works. We employ **Lemma 2** to handle generalized smoothness. To obtain convergence rates for EF21 and EF21-SGDM, we use **Lemmas 4 and 9**, respectively, which align with the rates achieved by Richtárik et al. (2021) and Fatkhullin et al. (2024).

Our approach not only builds on existing research but also introduces novel analysis techniques to expand the theoretical understanding of communication-compression algorithms under generalized smoothness.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper presents a convergence proof for normalized error feedback algorithms under generalized smoothness. Existing analysis either focus on single-node setups or make unrealistic assumptions (e.g., data heterogeneity) for distributed settings. The authors propose a distributed error feedback algorithms with normalization, achieving an $(O(1/\sqrt{K})) $ convergence rate for nonconvex problems without requiring data heterogeneity. All the reviewers agreed that the paper has merits, nevertheless none of them was enthusiastic enough to champion the paper to get accepted.