Compression with Exact Error Distribution for Federated Learning

• URL: http://arxiv.org/abs/2310.20682v1
• Date: Tue, 31 Oct 2023 17:48:22 GMT
• Title: Compression with Exact Error Distribution for Federated Learning
• Authors: Mahmoud Hegazy, R\'emi Leluc, Cheuk Ting Li, Aymeric Dieuleveut
• Abstract summary: We present and analyze different aggregation schemes based on layered quantizers achieving exact error distribution. We provide different methods to leverage the proposed compression schemes to obtain compression-for-free in differential privacy applications.
• Score: 33.74795273515338
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Compression schemes have been extensively used in Federated Learning (FL) to reduce the communication cost of distributed learning. While most approaches rely on a bounded variance assumption of the noise produced by the compressor, this paper investigates the use of compression and aggregation schemes that produce a specific error distribution, e.g., Gaussian or Laplace, on the aggregated data. We present and analyze different aggregation schemes based on layered quantizers achieving exact error distribution. We provide different methods to leverage the proposed compression schemes to obtain compression-for-free in differential privacy applications. Our general compression methods can recover and improve standard FL schemes with Gaussian perturbations such as Langevin dynamics and randomized smoothing.

Related papers

• Problem-dependent convergence bounds for randomized linear gradient compression [4.656302602746228]
  In distributed optimization, the communication model updates can be a performance bottleneck. gradient compression has been proposed as a means of increasing optimization. We study how the impact of compression on throughput can be in terms of the norm of the Hessian objective.
  arXiv  Detail & Related papers  (2024-11-19T22:26:42Z)
• Differential error feedback for communication-efficient decentralized learning [48.924131251745266]
  We propose a new decentralized communication-efficient learning approach that blends differential quantization with error feedback. We show that the resulting communication-efficient strategy is stable both in terms of mean-square error and average bit rate. The results establish that, in the small step-size regime and with a finite number of bits, it is possible to attain the performance achievable in the absence of compression.
  arXiv  Detail & Related papers  (2024-06-26T15:11:26Z)
• Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance [55.01966743652196]
  We propose a novel algorithm for distributed gradient descent (SGD) with compressed gradient communication in the parameter-server framework. Our gradient compression technique, named flattened one-bit gradient descent (FO-SGD), relies on two simple algorithmic ideas.
  arXiv  Detail & Related papers  (2024-05-17T21:17:27Z)
• Optimal Compression of Unit Norm Vectors in the High Distortion Regime [30.6205706348233]
  We investigate the method for compressing a unit norm vector into the minimum number of bits, while still allowing for some acceptable level of distortion in recovery. Our study considers both biased and unbiased compression methods and determines the optimal compression rates. While the results are a mix of new and known, they are compiled in this paper for completeness.
  arXiv  Detail & Related papers  (2023-07-16T04:23:57Z)
• Unrolled Compressed Blind-Deconvolution [77.88847247301682]
  sparse multichannel blind deconvolution (S-MBD) arises frequently in many engineering applications such as radar/sonar/ultrasound imaging. We propose a compression method that enables blind recovery from much fewer measurements with respect to the full received signal in time.
  arXiv  Detail & Related papers  (2022-09-28T15:16:58Z)
• EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization [7.691755449724637]
  In distributed or federated optimization and learning, communication between the different computing units is often the bottleneck. There are two classes of compression operators and separate algorithms making use of them. We propose a new algorithm, recovering DIANA and EF21 as particular cases.
  arXiv  Detail & Related papers  (2022-05-09T10:44:23Z)
• Federated Random Reshuffling with Compression and Variance Reduction [0.0]
  Random Reshuffling (RR) is an immensely popular method for training supervised machine learning models via empirical risk minimization. It is embedded and often set as default in standard machine learning software. We introduce three new algorithms to improve FedRR further: one for taming the variance coming from shuffling and the other for taming the variance due to compression.
  arXiv  Detail & Related papers  (2022-05-08T16:46:11Z)
• Distributed Methods with Absolute Compression and Error Compensation [1.52292571922932]
  Communication compression is a powerful approach to alleviating this issue. In this paper, we generalize the analysis of EC-SGD with absolute compression to the arbitrary sampling strategy. Our rates improve upon the previously known ones in this setting.
  arXiv  Detail & Related papers  (2022-03-04T15:41:14Z)
• Communication-Efficient Federated Learning via Quantized Compressed Sensing [82.10695943017907]
  The presented framework consists of gradient compression for wireless devices and gradient reconstruction for a parameter server. Thanks to gradient sparsification and quantization, our strategy can achieve a higher compression ratio than one-bit gradient compression. We demonstrate that the framework achieves almost identical performance with the case that performs no compression.
  arXiv  Detail & Related papers  (2021-11-30T02:13:54Z)
• PowerGossip: Practical Low-Rank Communication Compression in Decentralized Deep Learning [62.440827696638664]
  We introduce a simple algorithm that directly compresses the model differences between neighboring workers. Inspired by the PowerSGD for centralized deep learning, this algorithm uses power steps to maximize the information transferred per bit.
  arXiv  Detail & Related papers  (2020-08-04T09:14:52Z)
• On Biased Compression for Distributed Learning [55.89300593805943]
  We show for the first time that biased compressors can lead to linear convergence rates both in the single node and distributed settings. We propose several new biased compressors with promising theoretical guarantees and practical performance.
  arXiv  Detail & Related papers  (2020-02-27T19:52:24Z)

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.