Accelerated Distributed Optimization with Compression and Error Feedback

Yuan Gao, Anton Rodomanov, Jeremy Rack, Sebastian U. Stich · 2025

Read Accelerated Distributed Optimization with Compression and Error Feedback by Yuan Gao, Anton Rodomanov, Jeremy Rack, Sebastian U. Stich (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-08427.txt.

Introduction

Yuan Gao and co-authors present a 2025 study on training large models across many machines without swamping the network. Each machine sends squeezed updates to a central server, which saves time but can slow learning. Their new method, called ADEF, blends speed-up tricks with a way to correct for what squeezing loses.

Math proofs show the method reaches the best known fast rate for this kind of training in the broad convex case. Computer tests backed the proofs and showed lower traffic for the same speed. Cheaper traffic matters because moving data, not math, is often the slow part of big training runs.

Catalog record

CREATORYuan Gao, Anton Rodomanov, Jeremy Rack, Sebastian U. Stich
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-08427

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Accelerated Distributed Optimization with Compression and Error Feedback Yuan Gao, Anton Rodomanov, Jeremy Rack, Sebastian U. Stich Abstract Modern machine learning tasks often involve massive datasets and models, necessitating distributed optimization algorithms with reduced communication overhead. Communication compression, where clients transmit compressed updates to a central server, has emerged as a key technique to mitigate communication bottlenecks. However, the theoretical understanding of stochastic distributed optimization with contractive compression remains limited, particularly in conjunction with Nesterov acceleration—a cornerstone for achieving faster convergence in optimization. In this paper, we propose a novel algorithm, ADEF ( A ccelerated D istributed E rror F eedback), which integrates Nesterov acceleration, contractive compression, error feedback, and gradient difference compression. We prove that ADEF achieves the first accelerated convergence rate for stochastic distributed optimization with contractive compression in the general convex regime. Numerical experiments validate our theoretical findings and demonstrate the practical efficacy of ADEF in reducing communication costs while maintaining fast convergence. 1 Introduction Gradient methods are the workhorses of the modern machine learning paradigm. They are the backbone for training modern machine learning models. With the rapidly growing sizes of the datasets and models, distributed training has become a necessity as accumulating the entire dataset on a single central machine is simply infeasible. Much of the recent breakthrough models are trained in such a distributed fashion, e.g. large language models ( Shoeybi et al., 2019 ) , generative models ( Ramesh et al., 2021 ; Ramesh et al., 2022 ) , and others ( Wang et al., 2020 ) , where data are distributed across different clients/workers and model updates are coordinated by a parameter server. Another instances of distributed optimization is the federated learning setting ( Konečný et al., 2016 ; Kairouz et al., 2019 ) , where clients (e.g. edge devices or hospitals) jointly train a model without sharing their local data. One of the key challenges in distributed optimization is the communication bottleneck —the cost of transmitting large model updates between clients and the server ( Seide et al., 2014 ; Strom, 2015 ) . To address this, communication compression has emerged as a practical solution, where updates are transmitted in a compressed format to reduce communication overhead. Contractive compression (see Definition 2.1 ), despite being potentially biased, has been shown to outperform unbiased compression schemes in practice ( Lin et al., 2018 ; Sun et al., 2019 ; Vogels et al., 2019 ) and offers favorable theoretical properties ( Stich et al., 2018 ; Albasyoni et al., 2020 ; Beznosikov et al., 2023 ) . However, naive aggregation of compressed updates can lead to divergence ( Beznosikov et al., 2023 ) . To mitigate this, Error Feedback (EF) ( Seide et al., 2014 ) has been proposed as an effective remedy, compensating for compression errors ( Stich et al., 2018 ; Karimireddy et al., 2019 ) . EF and its variants (e.g., PowerSGD by Vogels et al. (2019) ) have been widely adopted in practice, integrated into popular deep learning frameworks such as PyTorch ( Paszke et al., 2019 ) , and deployed to train state-of-the-art transformer models ( Ramesh et al., 2021 ) . Despite the empirical success of EF and contractive compression, their theoretical understanding remains incomplete. Early theoretical studies of EF ( Stich et al., 2018 ; Karimireddy et al., 2019 ) primarily focus on single-client or homogeneous settings. Recent works have extended EF to heterogeneous datasets using bias correction mechanisms ( Fatkhullin et al., 2023 ; Gao et al., 2024 ) , while the initial explorations often require additional unbiased compression or suffering from divergence in stochastic settings ( Mishchenko et al., 2019 ; Richtárik et al., 2021 ) . On the other hand, most of these advances are made with unaccelerated methods. Nesterov acceleration ( Nesterov, 1983 ) is one of the most important algorithmic tools for achieving faster convergence rates for deterministic and stochastic first order methods in the convex regime. However, its integration with EF and contractive compression in the general convex regime remains largely unexplored. Existing works on accelerated methods with compression primarily focus on deterministic or strongly convex settings ( Li et al., 2020 ; Qian et al., 2021a ; Bylinkin and Beznosikov, 2024 ) , rely on unbiased compression ( Li and Richtárik, 2021 ) , or effectively function as uncompressed methods ( He et al., 2023 ) . 1 1 1 We explain this in more details in Section 2.2 and Appendix F . Consequently, the question of whether Nesterov acceleration can be achieved alongside contractive compression in the general convex regime remains open. 1.1 Contribution In this paper, we partially address the aforementioned gap by proposing ADEF ( A ccelerated D istributed E rror F eedback), which integrates Nesterov acceleration, contractive compression, and bias-corrected error feedback in the stochastic and general convex regime. Our contributions are as follows: • Algorithm: We introduce ADEF , a novel algorithm for accelerated distributed optimization that combines Nesterov acceleration with contractive compression, error feedback, and gradient difference compression. • General theoretical framework (acceleration with inexact updates): We develop a general and versatile analysis framework for accelerated methods with inexact updates, which is of independent interest to the optimization and machine learning communities. This framework rigorously handles errors arising from compression, stochasticity, and other inexactness in distributed optimization. We demonstrate the flexibility of our framework by applying it to analyze other algorithms and compression techniques. This highlights the robustness of our approach and its potential to inspire future advances in distributed optimization. • Breakthrough theoretical results: Using our framework, we prove that ADEF is the first distributed optimization algorithm to achieve accelerated convergence rates under contractive compression in the general convex regime. This result bridges a critical gap in the theoretical understanding of communication-efficient optimization and acceleration, overcoming longstanding challenges in the field. Numerical evaluation: We conduct extensive numerical experiments to validate our theoretical findings. The results demonstrate that ADEF significantly reduces communication costs while achieving state-of-the-art convergence performance. By bridging the gap between communication-efficient distributed optimization and accelerated convergence, ADEF opens new avenues for scalable and efficient training of large-scale machine learning models. 2 Communication Compression and Accelerated Methods Table 1 : Comparison of key existing works on stochastic distributed optimization with contractive compression in the general convex regime. We compare the rates in terms of the number of communication rounds from the client to the server, when the local oracle complexities are minized. For simplicity, we assume that L=\ell=L_{\max} . Algorithm \textbf{Acc}^{\rm(a)} \textbf{No BGS}^{\rm(b)} # Comm. Rounds # Local Oracle Calls Lower Bound ( He et al., 2023 ) - - \Omega\left(\frac{R_{0}^{2}\sigma^{2}}{n\varepsilon^{2}}+\frac{\sqrt{LR_{0}^{2}}}{\delta\sqrt{\varepsilon}}\right) \Omega\left(\frac{R_{0}^{2}\sigma^{2}}{n\varepsilon^{2}}+\frac{\sqrt{LR_{0}^{2}}}{\sqrt{\varepsilon}}\right) EF ( Karimireddy et al., 2019 ) No No \mathcal{O}\left(\frac{R_{0}^{2}\sigma^{2}}{n\varepsilon^{2}}+\frac{\sqrt{L}R_{0}^{2}(\frac{\zeta}{\sqrt{\delta}}+\sigma)}{\sqrt{\delta}\varepsilon^{\nicefrac{{3}}{{2}}}}+\frac{LR_{0}^{2}}{\delta\varepsilon}\right) \mathcal{O}\left(\frac{R_{0}^{2}\sigma^{2}}{n\varepsilon^{2}}+\frac{\sqrt{L}R_{0}^{2}(\frac{\zeta}{\sqrt{\delta}}+\sigma)}{\sqrt{\delta}\varepsilon^{\nicefrac{{3}}{{2}}}}+\frac{LR_{0}^{2}}{\delta\varepsilon}\right) EControl ( Gao et al., 2024 ) No Yes \mathcal{O}\left(\frac{R_{0}^{2}\sigma^{2}}{n\varepsilon^{2}}+\frac{\sqrt{L}R_{0}^{2}\sigma}{\delta^{2}\varepsilon^{\nicefrac{{3}}{{2}}}}+\frac{LR_{0}^{2}}{\delta\varepsilon}\right) \mathcal{O}\left(\frac{R_{0}^{2}\sigma^{2}}{n\varepsilon^{2}}+\frac{\sqrt{L}R_{0}^{2}\sigma}{\delta^{2}\varepsilon^{\nicefrac{{3}}{{2}}}}+\frac{LR_{0}^{2}}{\delta\varepsilon}\right) \text{{\sf NEOLITHIC} }^{\rm(c)} ( He et al., 2023 ) Yes No \widetilde{\mathcal{O}}\left(\frac{R_{0}^{2}\sigma^{2}}{\delta n\varepsilon^{2}}+\frac{\sqrt{LR_{0}^{2}}}{\delta\sqrt{\varepsilon}}\right)^{\rm(d)} \mathcal{O}\left(\frac{R_{0}^{2}\sigma^{2}}{n\varepsilon^{2}}+\frac{\sqrt{LR_{0}^{2}}}{\sqrt{\varepsilon}}\right) ADEF new Yes Yes \mathcal{O}\left(\frac{R_{0}^{2}\sigma^{2}}{n\varepsilon^{2}}+\frac{\sqrt{L}R_{0}^{2}\sigma}{\delta^{2}\varepsilon^{\nicefrac{{3}}{{2}}}}+\frac{\sqrt{LR_{0}^{2}}}{\delta^{2}\sqrt{\varepsilon}}\right) \mathcal{O}\left(\frac{R_{0}^{2}\sigma^{2}}{n\varepsilon^{2}}+\frac{\sqrt{L}R_{0}^{2}\sigma}{\delta^{2}\varepsilon^{\nicefrac{{3}}{{2}}}}+\frac{\sqrt{LR_{0}^{2}}}{\delta^{2}\sqrt{\varepsilon}}\right) • (a) Acc stands for accelerated methods. • (b) BGS stands for Bounded Gradient Similarity assumption: \frac{1}{n}\sum_{i=1}^{n}\left\lVert\nabla f_{i}(\mathbf{x})-\nabla f(\mathbf{x})\right\rVert^{2}\leq\zeta^{2},\forall\mathbf{x}\in\mathbb{R}^{d} . See also Assumption D.1 . • (c) He et al. (2023) presented their rates when batch size is \max\{\frac{4}{\delta}\ln(\frac{4}{\delta}),\frac{1}{\delta}\ln(24\kappa+\frac{25n^{2}\kappa^{3}\zeta^{4}}{\sigma^{4}}+5n\kappa^{\nicefrac{{3}}{{2}}})\} where \kappa is the total number of updates at the server. We present the rate, as is the

Read the complete text