Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence

• URL: http://arxiv.org/abs/2105.06697v1
• Date: Fri, 14 May 2021 08:15:18 GMT
• Title: Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence
• Authors: Jiaqi Zhang, Keyou You, Lihua Xie
• Abstract summary: This paper proposes a communication-efficient linearly convergent distributed (COLD) algorithm to solve strongly convex optimization problems. By compressing innovation vectors, COLD is able to achieve linear convergence for a class of $delta$-contracted compressors. Numerical experiments demonstrate the advantages of both algorithms under different compressors.
• Score: 23.849813231750932
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Information compression is essential to reduce communication cost in distributed optimization over peer-to-peer networks. This paper proposes a communication-efficient linearly convergent distributed (COLD) algorithm to solve strongly convex optimization problems. By compressing innovation vectors, which are the differences between decision vectors and their estimates, COLD is able to achieve linear convergence for a class of $\delta$-contracted compressors. We explicitly quantify how the compression affects the convergence rate and show that COLD matches the same rate of its uncompressed version. To accommodate a wider class of compressors that includes the binary quantizer, we further design a novel dynamical scaling mechanism and obtain the linearly convergent Dyna-COLD. Importantly, our results strictly improve existing results for the quantized consensus problem. Numerical experiments demonstrate the advantages of both algorithms under different compressors.

Related papers

• Order of Compression: A Systematic and Optimal Sequence to Combinationally Compress CNN [5.25545980258284]
  We propose a systematic and optimal sequence to apply multiple compression techniques in the most effective order. Our proposed Order of Compression significantly reduces computational costs by up to 859 times on ResNet34, with negligible accuracy loss. We believe our simple yet effective exploration of the order of compression will shed light on the practice of model compression.
  arXiv  Detail & Related papers  (2024-03-26T07:26:00Z)
• Communication-Efficient Distributed Learning with Local Immediate Error Compensation [95.6828475028581]
  We propose the Local Immediate Error Compensated SGD (LIEC-SGD) optimization algorithm. LIEC-SGD is superior to previous works in either the convergence rate or the communication cost.
  arXiv  Detail & Related papers  (2024-02-19T05:59:09Z)
• Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity [92.1840862558718]
  We introduce MARINA-P, a novel method for downlink compression, employing a collection of correlated compressors. We show that MARINA-P with permutation compressors can achieve a server-to-worker communication complexity improving with the number of workers. We introduce M3, a method combining MARINA-P with uplink compression and a momentum step, achieving bidirectional compression with provable improvements in total communication complexity as the number of workers increases.
  arXiv  Detail & Related papers  (2024-02-09T13:58:33Z)
• Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression [31.107056382542417]
  Communication compression is an essential strategy for alleviating communication overhead. We propose NEOLITHIC, a nearly optimal algorithm for compression under mild conditions.
  arXiv  Detail & Related papers  (2023-05-12T17:02:43Z)
• Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression [33.217552987061474]
  Communication compression is one of the most effective means of reducing communication. Recent advances in distributed optimization and learning have shown that communication compression is one of the most effective means of reducing communication.
  arXiv  Detail & Related papers  (2022-06-08T03:36:34Z)
• 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)
• On Arbitrary Compression for Decentralized Consensus and Stochastic Optimization over Directed Networks [0.6526824510982799]
  We propose an iterative-based algorithm that compresses messages according to a desired compression ratio. Contrary to existing literature allow arbitrary compression ratios. We show explicit convergence rates for decentralized optimization problems on smooth functions.
  arXiv  Detail & Related papers  (2022-04-18T04:41:56Z)
• Unified Multivariate Gaussian Mixture for Efficient Neural Image Compression [151.3826781154146]
  latent variables with priors and hyperpriors is an essential problem in variational image compression. We find inter-correlations and intra-correlations exist when observing latent variables in a vectorized perspective. Our model has better rate-distortion performance and an impressive $3.18times$ compression speed up.
  arXiv  Detail & Related papers  (2022-03-21T11:44:17Z)
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free! [72.31332210635524]
  Decentralized optimization methods enable on-device training of machine learning models without a central coordinator. We propose a new randomized first-order method which tackles the communication bottleneck by applying randomized compression operators. We prove that our method can solve the problems without any increase in the number of communications compared to the baseline.
  arXiv  Detail & Related papers  (2020-11-03T13:35:53Z)
• 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)
• Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
  Existing decentralized algorithms with compression mainly focus on compressing DGD-type algorithms. Motivated by primal-dual algorithms, this paper proposes first underlineLinunderlineEAr convergent. underlineDecentralized with compression, LEAD.
  arXiv  Detail & Related papers  (2020-07-01T04:35:00Z)

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.