TAMUNA: Doubly Accelerated Distributed Optimization with Local Training, Compression, and Partial Participation

• URL: http://arxiv.org/abs/2302.09832v3
• Date: Sat, 27 Apr 2024 13:55:25 GMT
• Title: TAMUNA: Doubly Accelerated Distributed Optimization with Local Training, Compression, and Partial Participation
• Authors: Laurent Condat, Ivan Agarský, Grigory Malinovsky, Peter Richtárik,
• Abstract summary: In distributed optimization and learning, several machines alternate between local computations in parallel and communication with a distant server. We propose TAMUNA, the first algorithm for distributed optimization that leveraged the two strategies of local training and compression jointly and allows for partial participation.
• Score: 53.84175614198885
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In distributed optimization and learning, several machines alternate between local computations in parallel and communication with a distant server. Communication is usually slow and costly and forms the main bottleneck. This is particularly true in federated learning, where a large number of users collaborate toward a global training task. In addition, it is desirable for a robust algorithm to allow for partial participation, since it is often the case that some clients are not able to participate to the entire process and are idle at certain times. Two strategies are popular to reduce the communication burden: 1) local training, which consists in communicating less frequently, or equivalently performing more local computations between the communication rounds; and 2) compression, whereby compressed information instead of full-dimensional vectors is communicated. We propose TAMUNA, the first algorithm for distributed optimization that leveraged the two strategies of local training and compression jointly and allows for partial participation. In the strongly convex setting, TAMUNA converges linearly to the exact solution and provably benefits from the two mechanisms: it exhibits a doubly-accelerated convergence rate, with respect to the condition number of the functions and the model dimension.

Related papers

• LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression [8.37672888329615]
  We introduce LoCoDL, a communication-efficient algorithm that leverages the two popular and effective techniques of Local training, which reduces the communication frequency, and Compression, in which short bitstreams are sent instead of full-dimensional vectors of floats. LoCoDL provably benefits from local training and compression and enjoys a doubly-accelerated communication complexity, with respect to the condition number of the functions and the model dimension, in the general heterogenous regime with strongly convex functions.
  arXiv  Detail & Related papers  (2024-03-07T09:22:50Z)
• Optimal Data Splitting in Distributed Optimization for Machine Learning [85.99744701008802]
  This study focuses on an optimal ratio of distributed data between the server and local machines for any costs of communications and local computations. The running times of the network are compared between uniform and optimal distributions. The superior theoretical performance of our solutions is experimentally validated.
  arXiv  Detail & Related papers  (2024-01-15T16:30:12Z)
• Communication-Efficient Decentralized Federated Learning via One-Bit Compressive Sensing [52.402550431781805]
  Decentralized federated learning (DFL) has gained popularity due to its practicality across various applications. Compared to the centralized version, training a shared model among a large number of nodes in DFL is more challenging. We develop a novel algorithm based on the framework of the inexact alternating direction method (iADM)
  arXiv  Detail & Related papers  (2023-08-31T12:22:40Z)
• Explicit Personalization and Local Training: Double Communication Acceleration in Federated Learning [7.691755449724637]
  A common strategy to curtail communication costs is Local Training, which consists in performing multiple local gradient descent steps between successive communication rounds. We introduce Scafflix, a novel algorithm that efficiently integrates explicit personalization with local training.
  arXiv  Detail & Related papers  (2023-05-22T15:58:01Z)
• Provably Doubly Accelerated Federated Learning: The First Theoretically Successful Combination of Local Training and Compressed Communication [7.691755449724637]
  We propose the first algorithm for distributed optimization and federated learning. Our algorithm converges linearly to an exact solution, with a doubly accelerated rate.
  arXiv  Detail & Related papers  (2022-10-24T14:13:54Z)
• DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training [84.81043932706375]
  We propose a novel personalized federated learning framework in a decentralized (peer-to-peer) communication protocol named Dis-PFL. Dis-PFL employs personalized sparse masks to customize sparse local models on the edge. We demonstrate that our method can easily adapt to heterogeneous local clients with varying computation complexities.
  arXiv  Detail & Related papers  (2022-06-01T02:20:57Z)
• Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
  Local methods are one of the promising approaches to reduce communication time. We show that the communication complexity is better than non-local methods when the local datasets is smaller than the smoothness local loss.
  arXiv  Detail & Related papers  (2022-02-12T15:12:17Z)
• On Second-order Optimization Methods for Federated Learning [59.787198516188425]
  We evaluate the performance of several second-order distributed methods with local steps in the federated learning setting. We propose a novel variant that uses second-order local information for updates and a global line search to counteract the resulting local specificity.
  arXiv  Detail & Related papers  (2021-09-06T12:04:08Z)
• FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learning [24.812767482563878]
  Federated learning (FL) aims to minimize the communication complexity of training a model over heterogeneous data distributed across many clients. We propose FedChain, an algorithmic framework that combines the strengths of local methods and global methods to achieve fast convergence in terms of R.
  arXiv  Detail & Related papers  (2021-08-16T02:57:06Z)
• Communication-Efficient Decentralized Learning with Sparsification and Adaptive Peer Selection [13.963329236804586]
  We introduce a novel decentralized training algorithm with the following key features. Each worker only needs to communicate with a single peer at each communication round with a highly compressed model. Experimental results show that our algorithm significantly reduces the communication traffic and generally selects relatively high bandwidth peers.
  arXiv  Detail & Related papers  (2020-02-22T12:31:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.