Problem-dependent convergence bounds for randomized linear gradient compression

• URL: http://arxiv.org/abs/2411.12898v1
• Date: Tue, 19 Nov 2024 22:26:42 GMT
• Title: Problem-dependent convergence bounds for randomized linear gradient compression
• Authors: Thomas Flynn, Patrick Johnstone, Shinjae Yoo,
• Abstract summary: 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.
• Score: 4.656302602746228
• License:
• Abstract: In distributed optimization, the communication of model updates can be a performance bottleneck. Consequently, gradient compression has been proposed as a means of increasing optimization throughput. In general, due to information loss, compression introduces a penalty on the number of iterations needed to reach a solution. In this work, we investigate how the iteration penalty depends on the interaction between compression and problem structure, in the context of non-convex stochastic optimization. We focus on linear compression schemes, where compression and decompression can be modeled as multiplication with a random matrix. We consider several distributions of matrices, among them random orthogonal matrices and matrices with random Gaussian entries. We find that in each case, the impact of compression on convergence can be quantified in terms of the norm of the Hessian of the objective, using a norm defined by the compression scheme. The analysis reveals that in certain cases, compression performance is related to low-rank structure or other spectral properties of the problem. In these cases, our bounds predict that the penalty introduced by compression is significantly reduced compared to worst-case bounds that only consider the compression level, ignoring problem data. We verify the theoretical findings on several optimization problems, including fine-tuning an image classification model.

Related papers

• 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)
• Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth [83.15263499262824]
  We prove that gradient descent converges to a solution that completely disregards the sparse structure of the input. We show how to improve upon Gaussian performance for the compression of sparse data by adding a denoising function to a shallow architecture. We validate our findings on image datasets, such as CIFAR-10 and MNIST.
  arXiv  Detail & Related papers  (2024-02-07T16:32:29Z)
• Compression with Exact Error Distribution for Federated Learning [33.74795273515338]
  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.
  arXiv  Detail & Related papers  (2023-10-31T17:48:22Z)
• Shifted Compression Framework: Generalizations and Improvements [2.2147691173934967]
  Communication is one of the key bottlenecks in the distributed training of large-scale machine learning models. Lossy compression of exchanged information, such as gradients or models, is one of the most effective instruments to alleviate this issue.
  arXiv  Detail & Related papers  (2022-06-21T15:00:04Z)
• 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)
• 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)
• Towards Compact CNNs via Collaborative Compression [166.86915086497433]
  We propose a Collaborative Compression scheme, which joints channel pruning and tensor decomposition to compress CNN models. We achieve 52.9% FLOPs reduction by removing 48.4% parameters on ResNet-50 with only a Top-1 accuracy drop of 0.56% on ImageNet 2012.
  arXiv  Detail & Related papers  (2021-05-24T12:07:38Z)
• Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence [23.849813231750932]
  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.
  arXiv  Detail & Related papers  (2021-05-14T08:15:18Z)
• 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)
• 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.