PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Distributed Learning with Gradient Quantization and Variance Reduction

Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, Peter Richtárik

arXiv:1904.05115v1math.OC

TL;DR

Distributed learning faces a communication bottleneck, and compressing updates introduces variance that can affect convergence. The paper analyzes general compression operators and develops variance-reduced schemes for quantized communication. It reports that an appropriate choice of quantization variance can recover the rate of unquantized variance-reduced methods.

  • Problem

    Communication between workers is a major limiting factor in large-scale applications, motivating smaller exchanged messages in distributed optimization.

    Source: §1.1 · p. 1, §1 · p. 1

  • Method

    The paper analyzes arbitrary compression operators and develops variance-reduced distributed methods that support quantized communication.

    Source: §1.2 · p. 2

  • Results

    With ω = O(min{n, m}), VR-DIANA's rate becomes identical to that of vanilla variance-reduced schemes without quantization.

    Source: Then under Assumption 2 and 3 · p. 7

  • Takeaways & Limitations

    Choosing the quantization operator appropriately yields communication-efficient schemes that the authors report converge as fast as their communication-intensive counterparts.

    Source: §9 · p. 9

    The analysis assumes equal component counts across machines for simplicity; with unequal counts, the rates use max_i m_i instead of m.

    Source: §6 · p. 5

Abstract

from arXiv · show

We consider distributed optimization where the objective function is spread among different devices, each sending incremental model updates to a central server. To alleviate the communication bottleneck, recent work proposed various schemes to compress (e.g.\ quantize or sparsify) the gradients, thereby introducing additional variance $\omega \geq 1$ that might slow down convergence. For strongly convex functions with condition number $\kappa$ distributed among $n$ machines, we (i) give a scheme that converges in $\mathcal{O}((\kappa + \kappa \frac{\omega}{n} + \omega)$ $\log (1/\epsilon))$ steps to a neighborhood of the optimal solution. For objective functions with a finite-sum structure, each worker having less than $m$ components, we (ii) present novel variance reduced schemes that converge in $\mathcal{O}((\kappa + \kappa \frac{\omega}{n} + \omega + m)\log(1/\epsilon))$ steps to arbitrary accuracy $\epsilon > 0$. These are the first methods that achieve linear convergence for arbitrary quantized updates. We also (iii) give analysis for the weakly convex and non-convex cases and (iv) verify in experiments that our novel variance reduced schemes are more efficient than the baselines.

1. Introduction

The paper studies distributed optimization, where large-scale training makes communication between workers a bottleneck. It generalizes compression methods and develops variance-reduced schemes, with convergence analyses across convexity settings and experiments reporting communication savings.

1. Introduction

  • Data-parallel optimization distributes training data across compute nodes, while communication between workers can limit large-scale applications.Source: §1 · p. 1, §1.1 · p. 1

1.2. Contributions

  • The paper generalizes distributed optimization methods to arbitrary compression operators, including quantization and sparsification, rather than tying them to one class.The authors say this flexibility lets operators be chosen for available system resources and can offer training-time gains over the previous method tied to a single class.Source: §1.2 · p. 2
  • The variance-reduced extensions converge to the optimum without loss in convergence rate, overcoming restrictions on quantization and periodic exact-gradient communication.The cited prior quantized SVRG method required exact epoch gradients; the paper says its methods overcome that restriction and also support SAGA.Source: §1.2 · p. 2
  • The paper analyzes its schemes for strongly convex, weakly convex, and non-convex settings, recovering respective rates of earlier uncompressed schemes.Source: §1.2 · p. 2
  • The experiments report performance on par with baselines in iterations but considerable savings in total communication cost.Source: §1.2 · p. 2

2. Related Work

Related work spans practical gradient compression, theoretical analyses of quantization in distributed learning, and variance-reduced methods. The paper positions its approach against these lines while distinguishing communication-reduction strategies it does not study.

2. Related Work

  • Gradient compression has been used in practical heuristics such as 1BitSGD (Seide et al., 2014; Strom, 2015), while this review focuses on methods with convergence guarantees.Source: §2 · p. 2

2.1. Quantization and Sparsification

  • Random dithering uses unbiased randomized rounding; sparsification can preserve only a constant number of coordinates, while error compensation can tolerate higher quantization variance.The text also notes that deterministic masking has experimentally outperformed random techniques, though biased schemes were harder to analyze.Source: §2.1 · p. 2

2.2. Quantization in Distributed Learning

  • Centralized quantized methods have reported convergence to neighborhoods, while decentralized analyses impose restrictions on compression or function class.The cited centralized studies include convergence to a neighborhood of an optimum or stationary point; decentralized work considered rigid compression assumptions or only strongly convex functions.Source: §2.2 · p. 3

2.3. Quantization and Variance Reduction

  • The paper extends quantization to both SVRG and SAGA, addressing earlier reliance on exact epoch gradients or high-precision quantization.It also analyzes an SVRG variant with random rather than fixed epoch lengths.Source: §2.3 · p. 3

2.4. Orthogonal Approaches

  • Other communication-reduction approaches increase minibatches, define local worker problems, reduce communication frequency, or distribute along features; the paper does not consider them.Source: §2.4 · p. 3

3. General Definitions

The definitions establish the strong-convexity and smoothness conditions used to characterize objective functions, alongside the regularizer in the optimization setting.

3. General Definitions

  • A differentiable function is μ-strongly convex when it satisfies the stated inequality for every pair of points.Source: §3 · p. 3
  • A differentiable function is L-smooth when it satisfies the stated inequality for every pair of points.Source: §3 · p. 3
  • The optimization setting permits a closed convex regularizer R and a positive parameter γ.Source: §3 · p. 3

4. Quantization Operators

The paper treats quantization operators through a bounded-variance condition and recommends choosing operators that also compress messages. It discusses random dithering, sparsification, and block quantization as examples.

4. Quantization Operators

  • An ω-quantization operator is defined by the stated expectation and variance properties, with expectation taken over the operator's internal randomness.The definition itself imposes no further restrictions, but the paper advises choosing operators whose outputs are cheaper to encode than their inputs.Source: §4 · p. 3
  • The analysis extends a bound previously proven for p = 2 to arbitrary p ≥ 1.Source: §4 · p. 4
  • The examples include random sparsification with variance parameter ω = d/r − 1 and block quantization that applies random dithering to each block.For block quantization, the text specifies equal block sizes and p = 2, s = 1; the displayed bound is incomplete in the supplied passage.Source: §4 · p. 4

5. DIANA with Arbitrary Quantization

DIANA extends its quantization analysis to arbitrary ω-quantization operators and uses worker state to reduce quantization variance. Under the section’s assumptions, the analysis establishes linear convergence.

5.1. DIANA

  • Arbitrary ω-quantization operators extend DIANA beyond the random-dithering operators with p ≥ 1 and s = 1 considered by Mishchenko et al. (2018).Source: §5.1 · p. 4
  • Directly quantizing stochastic gradients can leave noise even at the optimum and generally fails to converge with nontrivial regularizers; DIANA instead maintains worker state h_i.The state is intended to converge to the local gradient at the optimum, reducing quantization variance.Source: §5.1 · p. 4

5.2. Convergence of Algorithm 1

  • With strongly convex, smooth objectives and bounded stochastic-gradient variance, Theorem 1 establishes linear convergence for Algorithm 1 with arbitrary ω-quantization.The theorem’s stated conditions include α ≤ 1/(ω + 1), c ≥ 4ω/(αn), and γ ≤ α/(2μ).Source: §5.2 · p. 4

6. Variance Reduction for Quantized Updates

The section introduces variance-reduced methods for finite-sum objectives to address DIANA’s convergence only to a neighborhood. Equal component counts across workers simplify the analysis; unequal counts replace m in the rates with the largest worker count.

6. Variance Reduction for Quantized Updates

  • For finite-sum objectives, the paper introduces variance-reduced methods with quantized gradient updates.Source: §6 · p. 5
  • DIANA’s linear convergence guarantee reaches only a neighborhood whose size depends on the average stochastic-gradient variance σ².Source: §6 · p. 5
  • Equal component counts m across workers are assumed for simplicity; with unequal counts, the rates use max_i m_i instead.Here m_i is the number of functions on worker i.Source: §6 · p. 5

19 end

The section’s variance-reduced methods quantize gradient differences rather than full gradient aggregates, enabling convergence to arbitrary accuracy. It presents SAGA-, SVRG-, and L-SVRG-based algorithms and gives convergence results across convexity settings.

19 end

  • Variance-reduced methods converge linearly for arbitrary accuracy ε > 0, unlike the neighborhood guarantee tied to stochastic-gradient variance.Source: §19 · p. 5

6.1. The main challenge

  • Quantizing the aggregate of worker gradients can produce arbitrarily large error, even at the optimum, and fails to achieve variance reduction.Source: §6.1 · pp. 5–6
  • Workers maintain state h_i and quantize gradient differences; proving that this state approaches the local gradient at the optimum yields a variance-reduced method exchanging only quantized updates.Source: §6.1 · p. 6

6.2. Three new algorithms

  • Three variants build on SAGA, SVRG, and L-SVRG; the analysis gives global linear convergence for strongly convex problems and O(1/k) convergence for convex and non-convex cases.Setting ω = 1 recovers the original complexity results for all three algorithms; unlike an earlier SVRG-based scheme, these methods communicate only quantized vectors.Source: §6.2 · p. 6

7. Convergence of VR-DIANA (Algorithm 2)

VR-DIANA’s convergence analysis covers strongly convex, convex, and non-convex settings. In the finite-sum setting, quantization adds rate overhead, but suitable variance levels can preserve the unquantized rate.

7.1. Strongly convex case

  • The strongly convex analysis assumes L-smooth finite-sum components and, in one theorem, strongly convex worker objectives with convex components.The section also states a separate component-convexity assumption for another result.Source: §7 · p. 6

Then under Assumption 2 and 3

  • For finite-sum objectives, quantization adds an additive rate component and a more consequential multiplicative κω/n component.Choosing ω=O(min{n,m}) makes VR-DIANA’s rate identical to that of variance-reduced schemes without quantization.Source: Then under Assumption 2 and 3 · p. 7
  • For the strongly convex finite-sum result, the paper compares variance-reduced rates with SAGA or SVRG and reports that quantization overhead can be controlled by choosing ω=O(min{n,m}).The table assumes ω≤m (or ω≤m^(2/3) for the non-convex case); for block quantization, it reports an unquantized convergence rate and communication savings of at least d/n when d≥n.Source: Then under Assumption 2 and 3 · p. 7, Table 1 · p. 7

7.2. Convex case

  • Under Assumptions 2 and 4, a uniformly sampled iterate of Algorithm 2 has the stated convex-case convergence guarantee.When ω=O(min{m,n}), the convergence rate is not worsened compared with a scheme without quantization.Source: §7.2 · p. 7

7.3. Non-convex case

  • In the non-convex case, quantization trades iteration complexity against communication complexity.For ω≤m^(2/3), iteration complexity is O(ω^(1/2)) with other terms fixed, while communication complexity is proportional to the number of nonzeros, which decreases as O(1/ω) for random dithering and random sparsification.Source: §7.3 · p. 7

8. Experiments

The experiments evaluate distributed logistic regression on LIBSVM datasets and compare quantized variance-reduced methods with baselines. They report that parameter α is generally easy to tune, while very small values can slow convergence.

8. Experiments

  • The experiments use ℓ2-regularized logistic regression on LIBSVM datasets, a setting chosen because some comparison methods lack guarantees for non-convex or non-smooth objectives.The regularization parameter λ2 is set to order 1/(nm).Source: §8 · p. 8
  • Convergence is roughly similar across many α choices, but tiny values slow it substantially.With ω−1=2·10−2, the authors observe almost no difference among α values {10−2, 10−3, 5·10−4}.Source: §8 · p. 8
  • The comparisons include VR-DIANA and Diana-SGD against QSVRG on mushrooms and a5a; TernGrad-Adam was slowest in the experiments and appears only in Figure 1.Figure 3 plots functional suboptimality over time and distance to the solution over iterations.Source: §8 · p. 8, Figure 3 · p. 9

9. Conclusion

The paper analyzes distributed algorithms for quantized worker communication and develops variance-reduced methods with convergence analysis across convexity settings. Its conclusion emphasizes choosing compression to retain the rates of communication-intensive counterparts.

9. Conclusion

  • The paper develops variance-reduced methods for quantized communication and gives convergence rates for strongly convex, convex, and non-convex settings.The analysis is not tied to a specific quantization scheme and supports choosing an operator suited to the system’s resources.Source: §9 · p. 9

A. Extra Experiments

The appendix reports extra experiments on block-size effects, restates frequently used notation, and collects basic identities and expectation conventions.

A. Extra Experiments

  • ℓ2 dithering is noisier and more sensitive to block size, while full-vector quantization often preserves iteration complexity and improves communication time.The experiments use 1-bit random dithering on Gisette with 20 workers; the first two columns show convergence over time and the last two over epochs.Source: Figure 4 · p. 12

B. Notation Table

C. Basic Identities and Inequalities

  • The appendix lists identities for variance decomposition, Jensen’s inequality, independent random variables, smooth strongly convex functions, and prox non-expansiveness.For VR-DIANA and SVRG-DIANA, conditional expectations are denoted E[X]; unconditional expectations are identified when used.Source: C. Basic Identities and Inequalities · p. 14

D. DIANA with general quantization operators, Proof of Theorem 1

This section develops convergence-proof bounds for DIANA and variance-reduced variants across strongly convex, convex, and non-convex settings. The analyses use estimator and Lyapunov arguments and include parameterized random-iterate guarantees and a recurrence-comparison lemma.

D. DIANA with general quantization operators, Proof of Theorem 1

E. Variance Reduced Diana—L-SVRG method and SAGA proof

E.1. Strongly convex case

  • For the strongly convex case, Lemmas 4–7 bound second moments of x_k, H_k, D_k, and g_k, with the H_k bound requiring α(ω + 1) ≤ 1.These bounds are combined in the proof of Theorem 2.Source: §E.1 · pp. 17–20

E.2. Convex case

  • Theorem 3’s convex-case proof sums an iteration inequality and returns a uniformly random iterate from the first k iterates.The proof uses the μ = 0 case of (30).Source: §E.2 · p. 21

E.3. Non-convex case

  • Theorem 5 considers Algorithm 2 with ω-quantization Q and stepsize α ≤ 1/(ω + 1), choosing any p > 0 to define the Lyapunov function.Source: §E.3 · p. 21

Then under Assumption 2

  • Under Assumption 2, the proof of Theorem 4 selects p and α and bounds a recursion matrix using m, ω, and L.The proof also establishes intermediate bounds for W_k and F_k.Source: Then under Assumption 2 · pp. 22, 23, 25, 26

F.1. Strongly convex case

  • Under Assumptions 2 and 3, Theorem 6 establishes linear convergence for Algorithm 3 when α ≤ 1/(ω + 1).Corollary 5 also specifies parameter choices for this strongly convex case.Source: §F.1 · p. 27

F.2. Convex case

  • Under Assumptions 2 and 4, Theorem 7 analyzes a uniformly random iterate of Algorithm 3 for α ≤ 1/(ω + 1).The theorem uses p_r = 1/l for r = 0, 1, . . . , l − 1; its stated bound is not legible in the supplied passage.Source: §F.2 · p. 30
  • In the convex case, the proof uses epoch size l=m and stepsize α=1/(ω+1) to target expected suboptimality at most ε.Source: §F.2 · p. 30

F.3. Non-convex case

  • For non-convex Algorithm 3 with ω-quantization, Theorem 8 assumes α≤1/(ω+1) and introduces a Lyapunov function.Source: §F.3 · p. 30

Then under Assumption 2

  • Under Assumption 2, Theorem 9 uses α=1/(ω+1) and a uniformly sampled iterate of Algorithm 3 for its guarantee.The theorem states that the sampled iterate is drawn uniformly from {x0, x1, . . . , xk−1}.Source: Then under Assumption 2 · p. 31

G. Technical Lemma

  • The technical lemma compares nonnegative 2×2 affine recurrences coordinate-wise and provides an eigenvalue-based bound when the perturbed matrix has positive real eigenvalues.Source: G. Technical Lemma · p. 36

Related papers

Loading 1904.05115v1…