PaperlayerView exact revision on arXiv

Source-linked AI summary

Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization

Zhize Li, Dmitry Kovalev, Xun Qian, Peter Richtárik

arXiv:2002.11364v2math.OCcs.DCcs.LG

TL;DR

Distributed and federated optimization faces communication bottlenecks, while compression and acceleration had not been theoretically combined. The paper introduces ACGD and ADIANA, showing accelerated compressed methods with improved single-device complexity and compressed distributed communication without hurting convergence rates.

  • Problem

    Communication across distributed and federated networks is a training bottleneck, while gradient compression and acceleration had not been successfully combined in theoretically supported methods.

  • Method

    The paper develops ACGD for single-device optimization and ADIANA for distributed optimization, combining gradient compression with acceleration.

  • Results

    ACGD improves the complexity of compressed gradient descent, while ADIANA retains the convergence rate of non-compressed accelerated gradient descent with cheaper communication.

  • Takeaways & Limitations

    ADIANA is better suited to federated optimization because compression reduces communication cost without hurting the convergence rate.

  • Takeaways & Limitations

    The paper situates its contribution amid limited theory for local methods, including no known communication-complexity improvement from local steps in the cited full-gradient setting.

Abstract

from arXiv · show

Due to the high communication cost in distributed and federated learning problems, methods relying on compression of communicated messages are becoming increasingly popular. While in other contexts the best performing gradient-type methods invariably rely on some form of acceleration/momentum to reduce the number of iterations, there are no methods which combine the benefits of both gradient compression and acceleration. In this paper, we remedy this situation and propose the first accelerated compressed gradient descent (ACGD) methods. In the single machine regime, we prove that ACGD enjoys the rate $O\Big((1+ω)\sqrt{\frac{L}μ}\log \frac{1}ε\Big)$ for $μ$-strongly convex problems and $O\Big((1+ω)\sqrt{\frac{L}ε}\Big)$ for convex problems, respectively, where $ω$ is the compression parameter. Our results improve upon the existing non-accelerated rates $O\Big((1+ω)\frac{L}μ\log \frac{1}ε\Big)$ and $O\Big((1+ω)\frac{L}ε\Big)$, respectively, and recover the optimal rates of accelerated gradient descent as a special case when no compression ($ω=0$) is applied. We further propose a distributed variant of ACGD (called ADIANA) and prove the convergence rate $\widetilde{O}\Big(ω+\sqrt{\frac{L}μ}+\sqrt{\big(\fracω{n}+\sqrt{\fracω{n}}\big)\frac{ωL}μ}\Big)$, where $n$ is the number of devices/workers and $\widetilde{O}$ hides the logarithmic factor $\log \frac{1}ε$. This improves upon the previous best result $\widetilde{O}\Big(ω+ \frac{L}μ+\frac{ωL}{nμ} \Big)$ achieved by the DIANA method of Mishchenko et al. (2019). Finally, we conduct several experiments on real-world datasets which corroborate our theoretical results and confirm the practical superiority of our accelerated methods.

1. Introduction

Federated optimization trains models across heterogeneous devices, but communication is a central bottleneck. Existing local and compressed methods address communication differently, while accelerated compressed methods remain an important gap.

  • Optimization setting: Federated learning typically solves a distributed optimization problem with smooth device-specific losses and a possibly nonsmooth regularizer.Each f_i represents the loss associated with data stored on device i, while ψ is the regularizer.
  • Communication bottlenecks: Communication across distributed and federated networks is a training bottleneck, motivating fewer rounds and smaller messages.Local computation reduces communication frequency, whereas compression reduces message size.
  • Local methods: Local methods lack theoretical evidence of better communication complexity than standard non-local methods.This limitation is especially relevant under heterogeneous data, a key federated-learning regime.
  • Compressed communication: Compression methods can improve total communication complexity over comparable uncompressed baselines, although compressed gradient descent may increase communication rounds.Variance reduction can control compression-induced variance, and DIANA can preserve rounds up to a compression threshold while reducing transmitted bits.
  • Compressed communication: DIANA retains gradient-descent communication rounds while saving bit transmission per round, with larger ω permitting more compression.Its iteration behavior is characterized using the condition number and compression parameter.

2. Contributions

The paper combines communication compression with acceleration through ACGD for single-device optimization and ADIANA for distributed optimization. These methods are designed to reduce communication-round complexity while retaining compressed communication.

  • Gradient compression and acceleration had not previously been combined in theoretically supported gradient-type methods.The paper motivates this gap by contrasting compression's communication savings with acceleration's iteration reductions.
  • Single device setting: The paper introduces ACGD for smooth convex and strongly convex single-device problems.ACGD is presented as an accelerated compressed gradient descent method for the unconstrained smooth minimization setting.
  • Single device setting: ACGD improves the strongly convex and convex complexity results previously established for non-accelerated compressed gradient descent.The supplied passages state the improvement for both regimes, with results summarized in Table 1.
  • Distributed setting: The distributed method ADIANA combines acceleration, compression, and DIANA-like variance reduction for problems with multiple devices and regularization.Local shifted gradients are compressed, aggregated into a stochastic estimator, and variance reduction addresses compression noise.
  • Distributed setting: ADIANA improves upon the non-accelerated DIANA rate in both regimes ω > n and ω < n.The paper also reports a reduced rate when ω ≤ n^1/3, a regime described as common in federated learning.
  • Distributed setting: With compression, ADIANA can match the communication-round count of non-compressed accelerated gradient descent while using cheaper communication.The paper identifies this property as making ADIANA better suited for federated optimization.

3. Randomized Compression Operators

The paper models randomized gradient compression through unbiased operators with bounded relative variance and illustrates the framework using sparsification and quantization. The compression parameter measures the operator's noise or compression level, with no compression corresponding to ω = 0.

  • An ω-compression operator is a randomized map used to compress gradients while satisfying the paper's compression conditions.The conditions require unbiasedness and variance bounded relative to the compressed vector's magnitude.
  • Examples: Random sparsification selects k nonzero coordinates uniformly from a d-dimensional vector.Its compression parameter is ω = d/k − 1, and k = d gives ω = 0.
  • Examples: Quantization represents vector coordinates through randomized magnitude levels determined by the vector norm and parameters p and s.QSGD is identified as the special case using p = 2.

4. Accelerated CGD: Single Machine

This section introduces ACGD, the first accelerated compressed gradient method, and establishes accelerated convergence guarantees for convex and strongly convex single-machine problems.

  • CGD baseline: CGD has established non-accelerated convergence results for strongly convex and convex problems.The section also supplies a convex-case convergence result not found in the literature.
  • ACGD algorithm: ACGD is proposed as the first method combining acceleration with compressed gradient descent.It is inspired by Nesterov’s accelerated gradient descent and FISTA.
  • Convex case: Theorem 2 establishes ACGD convergence for convex smooth objectives under specified parameter choices.The theorem uses θ_k = k/(k + 2), β_k ≡ 0, and γ_k = 2p/(k + 2).
  • Strongly convex case: Theorem 3 establishes ACGD convergence for strongly convex smooth objectives under the compression assumptions.The theorem states the strongly convex guarantee for the parameterized ACGD method.
  • Optimality connections: When ω = 0, ACGD recovers standard optimal accelerated-gradient rates and matches accelerated randomized coordinate descent under random-k sparsification.The latter recovery holds under the same standard smoothness assumptions.

5. Accelerated CGD: Distributed Setting

The distributed method ADIANA combines acceleration with variance reduction for compressed multi-machine optimization, using shifted local gradients to control compression variance.

  • Distributed setting: Multiple nodes and a regularizer introduce additional challenges beyond the single-machine setting.The distributed section therefore addresses the general problem with n > 1 and nontrivial ψ.
  • ADIANA method: ADIANA combines acceleration and variance reduction as an accelerated version of DIANA.Each machine computes a local gradient and shifted version, while the server aggregates compressed messages into a stochastic gradient estimator.
  • Variance reduction: Adaptive shift terms reduce the variance introduced by compression throughout the iterative process.Without compression, the shifts can be set to zero.
  • Method design: ADIANA modifies variance-reduced compression for acceleration and uses a randomized update rule for an auxiliary variable.The method builds on prior non-accelerated variance-reduction approaches.
  • Convergence theory: Theorem 4 provides the main strongly convex convergence result for ADIANA under smooth local objectives and an ω-compression operator.Its proof combines a key Lyapunov inequality with additional lemmas controlling auxiliary terms and compression variance.
  • Comparison: The authors state that ADIANA’s rate is vastly superior to non-accelerated distributed compressed gradient methods, including DIANA.The comparison is made against the distributed compressed-gradient baselines discussed in the paper.

6. Experiments

Experiments compare ADIANA with DCGD and DIANA across four datasets and three compression operators, showing the fastest convergence for ADIANA in the main compressed comparisons.

  • Experimental setup: The experiments evaluate regularized logistic regression on four LIBSVM datasets: a5a, mushrooms, a9a, and w6a.Some experiments are provided in the appendix.
  • Compression operators: Three compressors are tested: random sparsification, random dithering, and natural compression.The communication budgets are specified in bits per iteration for each operator.
  • Experimental setup: The evaluation uses theoretical parameters for DCGD, DIANA, and ADIANA, with 20 machines by default.The plotted quantity is the optimality loss gap against the number of communicated bits.
  • Compressed comparisons: ADIANA converges fastest for all three compressors, while natural compression uses fewer communication bits than random dithering and random sparsification.DCGD reaches only a neighborhood of the optimum, whereas DIANA and ADIANA converge to the optimal solution.
  • Compression efficiency: For random dithering and natural compression, ADIANA is about twice as fast as its uncompressed version and faster than DIANA with or without compression.For random sparsification, DIANA outperforms its uncompressed version, while ADIANA performs worse than its uncompressed version.

A. Missing Proofs

The appendix provides detailed proofs for Theorems 1–4.

  • Proofs: Detailed proofs for Theorems 1–4 are provided in the appendix.

A.1. Proof of Theorem 1

The proof establishes the convex convergence guarantee for CGD by combining smoothness, compression, and a specific step size. It concludes an ε-solution after a complexity bound stated in the theorem.

  • Theorem 1 analyzes convex f with an L-Lipschitz gradient under compression operator C satisfying (5).
  • The proof uses smoothness inequalities and a weighted combination of recurrences to cancel the term ∥∇f(xk)∥2.
  • The analysis sums the resulting inequality across iterations and uses monotonicity of the expected objective gap.
  • The step size η = 1/((1+ω)L) is used to simplify the final bound and obtain the stated ε-solution complexity.

A.2. Proof of Theorems 2 and 3

This section proves the accelerated single-machine guarantees for convex and strongly convex objectives using a shared key lemma. The lemma combines parameter conditions, smoothness or strong convexity, and the compression property.

  • Key lemma: The key lemma imposes relations among ηk, θk, βk, γk, and p, including p ≥ (1+Lηk)(1+ω).
  • Convex case: For convex f, ACGD uses ηk ≡ 1/L, θk = 1 − 2/(k+2), βk ≡ 0, γk = 2p/(k+2), and p = 1 + ω.
  • Convex case: ACGD finds an ε-solution for the convex case within k = O(...), as stated by Theorem 2.
  • Strongly convex case: The strongly convex analysis restates Theorem 3 and concludes an ε-solution in function value or squared distance after the derived iteration bound.
  • Key lemma: The proof derives an expected-distance identity and cancels inner products using smoothness and strong convexity of f.

A.3. Proof of Theorem 4

The distributed proof establishes ADIANA’s strongly convex convergence by constructing a Lyapunov analysis supported by several lemmas. Its parameters incorporate smoothness, strong convexity, compression, and the number of machines.

  • The proof combines Lemmas 2–5 in a Lyapunov inequality and telescopes it across iterations.
  • The lemmas control compressed updates, auxiliary variables, and the algorithm’s randomized state using the compression property and Cauchy–Schwarz inequality.
  • Theorem 4 assumes μ-strong convexity, L-Lipschitz gradients for all fi, and a compression operator satisfying (5).
  • ADIANA reaches an ε-solution measured by E[∥zk − x∗∥2] ≤ ε within the theorem’s iteration bound, where n is the number of parallel machines.

B. Extra Experiments

The extra experiments compare ADIANA with DIANA and DCGD across datasets, compressors, compression settings, and node counts. ADIANA converges fastest across the three compressors, while its advantage over uncompressed methods depends on the compressor.

  • Comparison across compressors: The experiments compare ADIANA, DIANA, and DCGD on a9a and w6a using random sparsification, random dithering, and natural compression.
  • Comparison across compressors: ADIANA converges fastest for all three compressors, while natural compression uses fewer communication bits than random dithering and random sparsification.
  • Compression efficiency: For random dithering and natural compression, ADIANA is about twice faster than its uncompressed version and much faster than DIANA with or without compression.
  • Varying node counts: The node-count experiment evaluates ADIANA with random dithering and natural compression on a9a and w6a, multiplying transmitted bits by the number of nodes.
Loading 2002.11364v2…