PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Learning with Compressed Gradient Differences

Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, Peter Richtárik

arXiv:1901.09269v3cs.LGmath.OCstat.ML

TL;DR

Distributed optimization must reduce communication costs while addressing heterogeneous data and varied optimization requirements. The paper proposes DIANA, which compresses gradient differences, and analyzes its convergence in strongly convex and nonconvex settings alongside quantization and block-quantization choices. The supplied passages report iteration-complexity results for the nonconvex case and discuss assumptions and implementation guidance.

  • Problem

    Distributed learning faces a communication bottleneck, while applications also require support for heterogeneous local data, non-smooth regularizers, momentum, and nonconvex objectives.

  • Method

    DIANA compresses gradient differences and maintains auxiliary vectors that learn each worker's gradient at the optimum, with a momentum modification also proposed.

  • Results

    DIANA is analyzed in strongly convex and nonconvex settings, including a nonconvex iteration-complexity guarantee, while the paper also develops theory for block quantization and applies its analysis to TernGrad.

  • Takeaways & Limitations

    The analysis supports compressed distributed optimization across heterogeneous workers and provides theoretical guidance for block or layer quantization.

  • Takeaways & Limitations

    The nonconvex analysis omits a right-hand-side term because including it would overcomplicate the theory without providing more insight.

Abstract

from arXiv · show

Training large machine learning models requires a distributed computing approach, with communication of the model updates being the bottleneck. For this reason, several methods based on the compression (e.g., sparsification and/or quantization) of updates were recently proposed, including QSGD (Alistarh et al., 2017), TernGrad (Wen et al., 2017), SignSGD (Bernstein et al., 2018), and DQGD (Khirirat et al., 2018). However, none of these methods are able to learn the gradients, which renders them incapable of converging to the true optimum in the batch mode. In this work we propose a new distributed learning method -- DIANA -- which resolves this issue via compression of gradient differences. We perform a theoretical analysis in the strongly convex and nonconvex settings and show that our rates are superior to existing rates. We also provide theory to support non-smooth regularizers study the difference between quantization schemes. Our analysis of block-quantization and differences between $\ell_2$ and $\ell_{\infty}$ quantization closes the gaps in theory and practice. Finally, by applying our analysis technique to TernGrad, we establish the first convergence rate for this method.

1. Introduction

Distributed optimization addresses the growing need to train large models across workers, but communication can dominate computation. The paper motivates compressed updates and a broadly applicable formulation covering heterogeneous local data, regularization, and diverse optimization settings.

  • Distributed optimization: Distributed training assigns local-data updates to workers, aggregates them at a parameter server, and repeatedly broadcasts the aggregate.This parallel process supports large-model training but requires recurring communication.
  • Design requirements: Distributed methods should be versatile, efficient, and scale linearly with available resources across applications with different requirements.The motivating settings include federated learning, sparse solutions, proximable regularization, momentum, and nonconvex convergence.
  • Communication bottleneck: Communication is often much slower than stochastic updates, creating a central trade-off between communication and computation in distributed optimization.The paper identifies communication as a bottleneck in typical distributed architectures.
  • Compressed updates: Compressed SGD updates use randomized sparsification and/or quantization, but prior work leaves open questions about block quantization and assumptions on data availability.The discussion contrasts QSGD and TernGrad analyses, including their differing norm choices and data assumptions.
  • Problem formulation: The target problem is regularized empirical risk minimization with local losses fi and a proper closed convex regularizer R, without assuming similarity among distributions D1, . . . , Dn.This formulation allows worker data distributions to be heterogeneous.

2. Contributions

DIANA compresses gradient differences rather than gradients, using learned worker memories to reduce compression error near the optimum. The paper analyzes its convergence and extends the analysis to existing quantized methods.

  • 2. Contributions: DIANA compresses gradient differences, which converge to zero as iterates approach the optimum, instead of compressing gradients directly.Worker memories learn the local gradients at the optimum, enabling this difference-based compression.
  • 2. Contributions: The method introduces memory vectors that converge to each worker’s gradient at the optimum and adds a momentum modification for practicality.The memory update rule supports gradient learning while momentum changes the update direction.
  • 2. Contributions: DIANA is analyzed for smooth strongly convex problems with arbitrary closed convex regularizers and for smooth nonconvex problems.The stated results include iteration-complexity guarantees in both settings.
  • 2. Contributions: The analysis establishes a convergence rate for TernGrad and provides new analysis for 1-bit QSGD and block quantization.The comparisons cover multiple regularized and nonconvex settings.

3. The Algorithm

DIANA maintains local gradient memories and communicates unbiased quantized differences rather than full stochastic gradients. Its quantization and coding choices control communication cost, while the framework also unifies QSGD and TernGrad as special cases.

  • 3. The Algorithm: Each node computes an unbiased stochastic gradient, forms its difference from a maintained memory vector, and quantizes that difference for communication.The server combines memories and transmitted differences into an unbiased full-gradient estimator.
  • 3. The Algorithm: The p-quantization operator produces a random vector whose entries use the signed norm-scaled values selected by Bernoulli variables.The operator is defined for p ≥ 1 and is unbiased under the stated construction.
  • 3. The Algorithm: Block quantization allows communication to be tuned through the quantization norm and the choice of parameter blocks.The method targets transmitted vectors that are easier to communicate than full-dimensional vectors.
  • 3. The Algorithm: Elias coding bounds the communication needed for a quantized difference using its sparsity and the bit width b.The expected sparsity theorem provides an upper bound for this communication cost.
  • 3. The Algorithm: With zero memory initialization and α = 0, DIANA reduces to 1-bit QSGD or TernGrad for p = 2 or p = ∞, respectively.The shared analysis covers smooth strongly convex and smooth nonconvex cases, including momentum variants.

4. Theory: Strongly Convex Case

In the strongly convex setting, DIANA uses a Lyapunov function combining optimization error and memory error. The analysis shows convergence while the memories learn the gradients at the optimum.

  • 4. Theory: Strongly Convex Case: The strongly convex analysis assumes L-smooth and µ-strongly convex functions and uses a Lyapunov function combining distance to the solution with memory errors.Both terms are designed to approach zero during the algorithm’s run.
  • 4. Theory: Strongly Convex Case: The quantization parameter αp increases with p and decreases with dimension d, with α1 ≤ α2 ≤ α∞.The analysis gives explicit relationships for p = 1 and p = 2 across dimensions.
  • 4. Theory: Strongly Convex Case: The theorem guarantees that the Lyapunov function reaches an ε-dependent neighborhood after a logarithmic number of iterations under suitable stepsizes.The bound is expressed through γ, µ, and the initial Lyapunov value.
  • 4. Theory: Strongly Convex Case: The memory-error terms converge to zero, so compressed gradient differences allow the method to learn each worker’s gradient at the optimum.This is identified as a key distinction from prior work.
  • 4. Theory: Strongly Convex Case: The convergence proof couples the iterate error recursion with a recursion for the gradient-estimation and memory errors.Unrolling the combined recursions yields the theorem’s guarantee.

Corollary

For strongly convex problems, the leading complexity term decreases with the quantization norm parameter, making ℓ∞ quantization optimal in the stated bound. Under a model-size condition, DIANA matches gradient descent’s linear rate, and block quantization can preserve SGD speed while reducing communicated precision.

  • Corollary: 1/γµ = max {2/αp, (κ + 1) (1/2 − 1/n + 1/nαp)} is the leading complexity term, and it decreases with p.The resulting bound identifies p = +∞ as the optimal choice.
  • Corollary: p = +∞ is therefore the optimal quantization choice for the stated strongly convex leading-term bound.The condition number is κ := L/µ, and logarithmic dependence on 1/ϵ is suppressed in Table 3.
  • Corollary: When d = O(min{κ2, n2}), DIANA with p ≥ 2 has linear rate O(κ log(1/ϵ)), matching gradient descent.This matching result applies when the model size is not too large relative to the condition number and worker count.
  • Corollary: Quantization increases iteration complexity by about d/n, but blocks of size n2 reduce this factor to 1.With about 100 workers and blocks of about 10,000 parameters, the stated example communicates bits instead of floats while working as fast as SGD.
  • Corollary: The paper also includes a decreasing-step-size result with an O(1/k) rate under bounded gradient noise.The accompanying theorem specifies a decreasing stepsize schedule.

5. Theory: Nonconvex Case

The nonconvex analysis assumes bounded data dissimilarity and establishes convergence guarantees for DIANA under smooth objectives with constant regularization. The resulting complexity depends on the quantization parameters and can match SGD under stated conditions.

  • Assumptions: The bounded data-dissimilarity assumption holds with ζ = 0 when all worker objectives differ only by additive constants.The analysis can be extended with an additional O(∥∇f(x)∥2) term, but the paper says this would add complexity without more insight.
  • Assumptions: DIANA’s nonconvex analysis assumes a smooth objective, constant regularizer, bounded data dissimilarity, constant stepsizes, and a randomly selected output iterate.The bounded-dissimilarity assumption is needed because nonconvex solutions are not unique and gradients cannot be bounded using the gradient at an optimum.
  • Convergence result: DIANA’s nonconvex result provides an iteration-complexity bound for reaching a prescribed expected gradient-norm accuracy.The supplied theorem statement specifies the Lyapunov quantity and parameter restrictions but does not expose the complete bound.
  • Convergence result: The nonconvex analysis allows the final accuracy to be bounded after K iterations, with the bound determined by the theorem’s parameters and quantization choices.The supplied passage states the existence of a final-accuracy bound but omits its full displayed expression.
  • Convergence result: Under stated conditions, the resulting complexity can have the same order as SGD, with sufficiently large mini-batches or block sizes O(n^2) supporting the required conditions.The paper identifies these as examples satisfying the relevant alternatives in the complexity analysis.

6. Implementation and Experiments

The experiments study block and norm choices, distributed implementation, and comparisons with compressed and uncompressed baselines. DIANA performs strongly in the reported optimization tests, while communication scaling can exhibit architecture-dependent behavior.

  • Quantization design: Block or layer quantization is recommended for large vectors because it avoids undersampling coordinates with different scales and can yield superlinear acceleration theoretically.The motivation is especially relevant to deep networks whose layers have different parameter scales.
  • Quantization design: In convex experiments, the optimal α values were usually near min_i 1/√d_i, minimizing over block sizes d_i.This reports the empirical tuning pattern for the quantization parameter.
  • Experiments: In the logistic-regression experiment on mushrooms, DIANA with momentum was compared against QSGD, TernGrad, and DQGD using MPI implementations.The setup used logistic loss with an ℓ2 penalty and examined α, norm type, worker count, and block size.
  • Distributed implementation: The 2-bit DIANA communication comparison used images per second across GPU/MPI counts against 32-bit floating-point reduce, but scaling degraded beyond architecture-dependent process counts.The reported degradation affected AlexNet beyond 64 and VGG beyond 32 MPI processes in the described setup.
  • Experiments: On Cifar10, DIANA and SGD significantly outperformed QSGD and TernGrad in the best runs across tested hyperparameters.The comparison used training and testing accuracy over three epochs with eight workers.

7. Discussion

The paper presents DIANA as a compressed distributed optimization method that learns gradient information through compressed differences. It also develops block quantization theory, including unbiasedness and variance characterization.

  • DIANA: DIANA’s key feature is linear convergence in expectation to the exact optimum for strongly convex problems with full local gradients and heterogeneous workers.The paper frames this as the central reason for DIANA’s subsequent extensions.
  • Block p-quantization: The paper introduces block quantization because separately quantizing blocks can provide better practical properties than quantizing a full vector.The discussion connects this operator to the subsequent variance analysis.
  • Block p-quantization: Block p-quantization partitions a vector into blocks and quantizes each block separately, with full quantization recovered when there is one block.The construction does not require independence among block quantizations or their auxiliary random variables.
  • Block p-quantization: The block p-quantization estimator is unbiased, and the paper gives an explicit variance formula involving each block’s norms.The quantity Ψ_l(x) is defined from the ℓ1, ℓp, and ℓ2 norms of block l.

Appendix D. Proof of Lemma 4.3

The appendix develops technical bounds for quantization variance, distributed finite-sum structure, and DIANA’s Lyapunov recursion. It also derives node-count and parameter choices used in the convergence analysis.

  • Quantization bounds: The quantization factor α_p(d) increases with p and decreases with dimension d.This monotonicity is established through norm relationships and supports comparisons among quantization norms.
  • Distributed finite sums: A finite-sum empirical-risk problem can be partitioned across n workers, with each worker objective retaining smoothness and strong convexity.This embeds large finite-sum problems into the distributed optimization framework.
  • Optimal number of nodes: For p = 2, the iteration-complexity expression yields an optimal node count n*(d) that increases with model dimension.The appendix concludes that larger models justify using more nodes, other factors being equal.
  • Proof structure: The proof combines proximal nonexpansiveness, conditional expectations, variance identities, and a Lyapunov recursion before unrolling the recurrence.The resulting convergence argument uses the identities established in the preceding lemmas.
  • Noisy gradients: The appendix analyzes decreasing stepsizes under bounded gradient noise, with the noise level represented by the gradient standard deviation σ.The theorem assumes smooth strong convexity and imposes lower bounds on the stepsize parameter θ.

Appendix J. Nonconvex analysis

The appendix develops convergence analyses for nonconvex settings, including momentum variants and TernGrad. It also extends the quantization analysis beyond the original TernGrad choice.

  • Nonconvex convergence: The nonconvex analysis uses smoothness, bounded-noise assumptions, stepsize restrictions, and random selection of an iterate.The proofs derive bounds by constructing recurrences, summing them telescopically, and relating the result to expected gradient norms.
  • Proof strategy: The proof introduces virtual iterates whose recursion follows a scaled compressed-gradient update, enabling a more convenient smoothness bound.The virtual sequence is a slight perturbation of the actual iterate sequence.
  • TernGrad analysis: TernGrad is represented as a special DIANA case with zero memory correction, α = 0, and p = ∞.This identification lets the DIANA lemmas apply to TernGrad iterates under the stated assumptions.
  • TernGrad analysis: The analysis generalizes TernGrad beyond its original ℓ∞ sampling choice and establishes convergence guarantees where the original paper provided no convergence rate.The appendix states that the method can be analyzed for generalized quantization parameters rather than only p = ∞.
  • Convergence guarantees: The resulting bounds are expressed through expected gradient norms or final accuracy under conditions on smoothness, regularization, stepsizes, and momentum parameters.The appendix includes separate theorem statements for constant regularizers, momentum, and strongly convex special cases.

L.5. Strongly convex analysis

This section combines strongly convex convergence results with experiments on quantization and distributed implementation. It examines how regularization, block size, communication strategy, and quantization norm affect performance.

  • Strongly convex convergence: The strongly convex analysis assumes smooth local functions and derives convergence results for Algorithm 2 under bounded noise and specified stepsizes.The theorem statements include constant-regularizer and bounded-noise settings.
  • Rosenbrock experiment: The Rosenbrock experiment uses two workers and compares DIANA, QSGD, and TernGrad with carefully tuned parameters.The gradients are deterministic, and QSGD uses its 1-bit version.
  • Rosenbrock experiment: DIANA vastly outperforms the competing methods on the illustrated nonconvex Rosenbrock problem.The comparison uses the decomposed two-worker objective described in the experiment.
  • Quantization experiments: For logistic regression with ℓ1 and ℓ2 penalties, the experiments compare optimal parameters for ℓ2 and ℓ∞ quantization.The ℓ1 penalty is adjusted to produce an approximately 20% nonzero solution.
  • Quantization experiments: The choice of α is not important when it is sufficiently small, while optimal block size depends on quantization norm and regularization.For ℓ∞ quantization, full quantization performs best; for ℓ2 quantization, larger regularization favors block size approximately 25, whereas smaller regularization favors smaller blocks.
  • Distributed implementation: The implementation uses MPI collectives on a Cray Aries network, with Gather outperforming point-to-point communication and Multi-Gather improving scaling for shorter vectors.The experiments report irregular scaling for 2-bit Gather under the Cray MPI implementation.

M.5. Diana vs. TenGrad, SGD and QSGD

The experiments compare DIANA with QSGD, TernGrad, and SGD across communication and neural-network training settings. DIANA-MultiGather improves communication scaling, while DIANA performs competitively or best in the reported training comparisons.

  • Communication performance: DIANA-MultiGather improves the scaling of 2-bit Gather communication relative to the irregular behavior observed for standard Gather.The strategy repeatedly gathers shorter vectors and is evaluated against MPI Reduce with 32-bit floats.
  • Communication performance: The communication comparison uses 2 bits per dimension for DIANA and 32-bit floating-point reduction across varying MPI process counts.The reported scaling issue affects AlexNet and VGG-A beyond 64 and 32 MPI processes, respectively.
  • Training experiments: The neural-network experiments evaluate QSGD, TernGrad, SGD with momentum, and DIANA on MNIST and CIFAR10 using eight workers and multiple hyperparameters.The study varies learning rates, quantization bucket sizes, quantization levels, momentum, α, and quantization norm.
  • Training experiments: On MNIST-Convex and MNIST-DNN, momentum-enabled SGD and DIANA dominate the other tested algorithms.For CIFAR10-DNN, DIANA and SGD significantly outperform the other methods.
  • Sparsity evolution: For MNIST-DNN, the quantized gradients appear to become sparser as training progresses.The sparsity evolution is shown for DIANA, QSGD, and TernGrad across the three evaluated problems.
Loading 1901.09269v3…