Communication-efficient Algorithms Under Generalized Smoothness Assumptions

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?

We believe that Figure 1 supports the efficiency of normalized EF21, as it demonstrates that for minimizing polynomial functions, normalized EF21 allows for larger stepsizes and achieves a faster convergence rate compared to EF21. Specifically, to reach $\Vert \nabla f(x)\Vert^2 = 10^{-4}$, normalized EF21 requires roughly half the number of iterations as EF21 for different sets of hyper-parameters.

In the rightmost plot, EF21 initially converges faster than normalized EF21 due to the small stepsize $\gamma_0 / \sqrt{K+1}$ for normalized EF21 at the beginning (when $K = 16,000$). Despite this, normalized EF21 ultimately achieves higher solution accuracy than EF21.

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 out and allocate some space to briefly talk about the technical novelty in this case.

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.

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

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?

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.

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?

Relaxing the Uniformly Bounded Data Heterogeneity Assumption. Our results for normalized EF21 in both deterministic and stochastic distributed optimization do not rely on the uniformly bounded data heterogeneity assumption, unlike the works of Crawshaw et al. (2024) and Liu et al. (2022). Instead, our convergence bounds in Theorems 1 and 2 include an additive constant related to $\delta^{\inf} := f^{\inf} - \frac{1}{n} \sum_i f_i^{\inf}$, which quantifies data heterogeneity.

Uniformly Bounded Data Heterogeneity: Pessimistic but Avoidable. The uniformly bounded data heterogeneity assumption is often used to analyze federated learning algorithms, both under traditional smoothness and generalized smoothness, as analyzed by Crawshaw et al. (2024) and Liu et al. (2022). However, this assumption has been shown by [1] to be overly pessimistic for modeling real-world data heterogeneity. It is possible to rather analyze federated learning algorithms without imposing these uniformly bounded data heterogeneity under traditional smoothness, such as FedAvg (or Local SGD) by [2], and FedProx by [3]. We believe an interesting and open problem remains. That is, developing federated algorithms with compressed communication under generalized smoothness, and analyzing their convergence without relying on the uniformly bounded heterogeneity assumption.

[1] Wang, Jianyu, et al. "On the unreasonable effectiveness of federated averaging with heterogeneous data." arXiv preprint arXiv:2206.04723 (2022).

[2] Gorbunov, Eduard, Filip Hanzely, and Peter Richtárik. "Local sgd: Unified theory and new efficient methods." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

[3] Yuan, Xiaotong, and Ping Li. "On convergence of FedProx: Local dissimilarity invariant bounds, non-smoothness and beyond." Advances in Neural Information Processing Systems 35 (2022): 10752-10765.

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.

Assumptions 1 and 2 are standard for deriving distributed optimization, satisfied by many machine learning problems, and imposed to model data heterogeneity.

• Assumptions 1 and 2 are standard for distributed optimization: Assumptions 1 and 2 are standard for deriving distributed stochastic gradient descent for nonconvex, $L$-smooth problems, e.g., [1].

• Assumptions 1 and 2 are satisfied by many machine learning problems: Many machine learning problems can be cast into optimization problems with non-negative objective functions, such as squared error loss in linear regression, logistic loss in logistic regression, and cross-entropy loss in neural network training. If $f(x)$ and each $f_i(x)$ are non-negative, then Assumptions 1 and 2 imply $f^{\inf} = f_i^{\inf} = 0$. This leads to our convergence bounds without an additive constant related to data heterogeneity, i.e., $\delta^{\inf} = 0$.

• Assumptions 1 and 2 model data heterogeneity: Assumptions 1 and 2 are required to model data heterogeneity. Instead of imposing a uniformly bounded data heterogeneity condition, our convergence bounds include an additive constant related to $\delta^{\inf} := f^{\inf} - \frac{1}{n} \sum_i f_i^{\inf}$, which quantifies data heterogeneity.

[1] Khaled, Ahmed and Peter Richtárik. “Better Theory for SGD in the Nonconvex World.” In Transactions on Machine Learning Research, 2023. P. 2835-8856.

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.

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.

Concern 2) Empirical results only compare normalized EF21 against EF21, not against other federated algorithms, such as FedAvg, CHOCO-SGD, Momentum-based algorithms, etc.

We believe this concern is minor, as also suggested by Reviewer nRsr.

Empirical Comparisons Between Normalized EF21 and EF21. We focus our comparisons on normalized EF21 and EF21, because these algorithms are most relevant to our research scope. Our empirical results demonstrate that, for solving generalized smooth problems, incorporating normalization into EF21 is essential to enable larger step sizes and achieve faster convergence rates.

Comparisons Against Other Algorithms. Comparisons between normalized EF21 and other federated (e.g., FedAvg) or decentralized algorithms (e.g., CHOCO-SGD) fall outside the scope of our study. This is because normalized EF21 performs a single local update, unlike FedAvg, and also requires a central server to maintain the global solution, unlike CHOCO-SGD. However, we believe that extending normalized EF21 for federated and decentralized optimization is an important future research direction. For instance, it remains an open challenge to design and analyze federated algorithms with compressed communication under generalized smoothness without relying on additional restrictive assumptions, such as uniformly bounded heterogeneity (as discussed by Crawshaw et al., 2024, and Liu et al., 2022).