PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparsified SGD with Memory

Sebastian U. Stich, Jean-Baptiste Cordonnier, Martin Jaggi

arXiv:1809.07599v2cs.LGcs.DCcs.DSstat.ML

TL;DR

Large-scale distributed and parallel learning is hindered by the communication cost of dense stochastic gradients, motivating compressed updates. This paper analyzes SGD with k-compression and error-compensating memory, finding vanilla-SGD convergence rates and substantially lower communication, while leaving parallel and asynchronous convergence guarantees open.

  • Problem

    Dense stochastic gradients create a major communication bottleneck in distributed and parallel training, while compressed SGD schemes had lacked theoretical convergence analysis.

  • Method

    The paper analyzes k-compressed SGD with memory that accumulates suppressed gradient information and feeds it into subsequent compressed updates.

  • Results

    MEM-SGD requires one to two orders of magnitude fewer communicated bits than QSGD while converging to the same accuracy, and its theory matches vanilla SGD’s convergence rate.

  • Takeaways & Limitations

    Sparsified SGD can reduce communication substantially without sacrificing the supported vanilla-SGD convergence rate, including for operators such as top-k and random-k.

  • Takeaways & Limitations

    The paper does not yet provide convergence guarantees for parallel and asynchronous variants of the scheme.

Abstract

from arXiv · show

Huge scale machine learning problems are nowadays tackled by distributed optimization algorithms, i.e. algorithms that leverage the compute power of many devices for training. The communication overhead is a key bottleneck that hinders perfect scalability. Various recent works proposed to use quantization or sparsification techniques to reduce the amount of data that needs to be communicated, for instance by only sending the most significant entries of the stochastic gradient (top-k sparsification). Whilst such schemes showed very promising performance in practice, they have eluded theoretical analysis so far. In this work we analyze Stochastic Gradient Descent (SGD) with k-sparsification or compression (for instance top-k or random-k) and show that this scheme converges at the same rate as vanilla SGD when equipped with error compensation (keeping track of accumulated errors in memory). That is, communication can be reduced by a factor of the dimension of the problem (sometimes even more) whilst still converging at the same rate. We present numerical experiments to illustrate the theoretical findings and the better scalability for distributed applications.

1 Introduction

SGD reduces computation relative to full gradient descent but leaves dense-gradient communication as a major bottleneck. The paper analyzes memory-based k-compression and shows that sparsified SGD can retain vanilla SGD’s convergence rate while reducing communication.

  • Motivation: Dense stochastic gradients leave communication as a major bottleneck in distributed and parallel training.The same issue arises from bandwidth and locking costs for shared parameters in multi-core systems.
  • Motivation: Compression replaces full stochastic-gradient updates with smaller quantized or sparsified updates, but aggressive compression can hurt performance.The paper considers schemes including top-k and random-k sparsification.
  • Method: Error compensation stores suppressed gradient information in memory and injects it into later compressed updates.The memory update is m_t+1 := m_t + g_t − comp(g_t), followed by transmitting comp(m_t+1 + g_t+1).
  • Contribution: The paper provides a first convergence analysis for SGD with memory and k-compression, including top-k, random-k, and ultra-sparsification with k < 1.The analysis covers k-compression operators for 0 < k ≤ d under smoothness and strong-convexity assumptions.
  • Contribution: For T = Ω(d√κ), sparsified SGD with memory has the same convergence rate as vanilla SGD.The result is established for appropriately chosen stepsizes and an averaged iterate.
  • Implications: The paper reports that the method reduces communication while preserving convergence and may support more scalable parallel or asynchronous implementations.Parallel and asynchronous variants do not yet have convergence guarantees in this work.

2 SGD with Memory

The section develops compressed SGD using k-contraction operators and error-accumulating memory, then establishes convergence guarantees under standard smoothness and strong-convexity assumptions. Memory prevents the dimension-dependent slowdown of naïve sparsification, while top-k and random-k provide communication-efficient updates.

  • Compression and sparsification operators: k-contraction operators reduce communication while satisfying a contraction property sufficient for the paper’s mathematical results.The framework covers sparsification, quantization, and other encodings; k-sparse outputs are especially relevant for efficient communication.
  • Compression and sparsification operators: Top-k and random-k are k-contraction operators that additionally produce k-sparse vectors.Top-k retains coordinates with largest magnitudes, while random-k selects a uniformly random k-element subset.
  • Variance blow-up for unbiased updates: Naïve sparsified updates can require d times more iterations than vanilla SGD when k is small.Increasing mini-batch size can offset this variance cost, but increases computation by a factor of d/k.
  • SGD with memory: Memory retains suppressed gradient information so SGD with memory converges at the same rate as vanilla SGD.The accumulated information reduces the variance of later coordinate updates compared with the naïve estimator.
  • SGD with memory: MEM-SGD updates the iterate with a compressed memory-corrected gradient and stores the difference between the scaled stochastic gradient and transmitted update.Gradients are multiplied by the stepsize when entering memory, not when retrieved.
  • Convergence results: Under smoothness, strong convexity, bounded gradient second moments, and suitable stepsizes, the analysis obtains the vanilla-SGD rate for averaged iterates.The theorem uses a k-contraction, stepsizes η_t = 8/(µ(a+t)), and parameters satisfying the stated constraints; a specific choice yields the rate after T = Ω(d/(µT)) as reported.

3 Proof Outline

The proof combines a virtual perturbed iterate with bounds on the memory norm and a weighted averaging argument. These components control compression error and derive the convergence guarantee for the actual iterates.

  • Perturbed iterate analysis: The proof introduces a virtual sequence to analyze the compressed iterates through a perturbed-iterate framework.The virtual sequence uses the same iterates, stepsizes, and sampled indices as the algorithm.
  • Bounding the memory: A memory-norm bound is derived using the contraction property of the compression operators.This controls the accumulated information retained by the algorithm.
  • Optimal averaging: Quadratically increasing weights are used to average iterates and obtain the optimal convergence rate.The averaging lemma combines nonnegative error and iterate sequences under the theorem’s stepsize schedule.
  • Proof combination: The theorem follows by combining the three lemmas with convexity of the objective.The resulting bound is expressed for the weighted average of the generated iterates.

4 Experiments

The experiments evaluate MEM-SGD on dense and sparse logistic-regression datasets, testing convergence, communication efficiency, QSGD comparisons, and multicore scaling. Results show strong sparsification performance, with substantial communication reductions and competitive convergence and speedup.

  • 4.1 Experimental Setup: Experiments evaluate MEM-SGD on the dense epsilon and sparse RCV1 datasets using logistic regression with L2 regularization.The implementation prioritizes readability and reports convergence per iteration and relative speedups rather than wall-clock time.
  • 4.2 Verifying the Theory: Top-k consistently outperforms rand-k and sometimes outperforms vanilla SGD in convergence experiments.The experiments use k ∈ {1, 2, 3} for epsilon and k ∈ {10, 20, 30} for RCV1.
  • 4.2 Verifying the Theory: 103-fold lower communication is achieved by top1 on epsilon, while top10 on RCV1 improves communication by approximately one order of magnitude over SGD.The reported gains differ because RCV1 gradients can already exploit the dataset’s sparsity.
  • 4.3 Comparison with QSGD: MEM-SGD with top1 converges as fast as QSGD at 8 and 4 bits while transmitting two orders of magnitude fewer bits.The comparison uses QSGD quantization levels with b ∈ {2, 4, 8}.
  • 4.4 Multicore experiment: Both sparsified SGD and vanilla SGD show linear speedup with increasing core count, while parallel MEM-SGD scales better on RCV1 than lock-free asynchronous SGD.The multicore experiment runs on a single 24-core processor without inter-node communication.

5 Conclusion

The paper establishes convergence guarantees for sparsified SGD and reports substantial communication savings, with implications for parallel and distributed implementations.

  • 5 Conclusion: The paper provides a concise convergence analysis of sparsified SGD that updates only a constant number of coordinates per iteration.The analysis shows that this communication-efficient method retains the same convergence rate in stochastic-gradient computations.
  • 5 Conclusion: MEM-SGD requires one to two orders of magnitude fewer communicated bits than QSGD while converging to the same accuracy.In serial experiments, top-k sparsification outperforms random sparsification.
  • 5 Conclusion: Theoretical insights from MEM-SGD may facilitate analysis in parallel and distributed settings and support asynchronous implementations beyond strict sparsity assumptions.The paper also notes practical applicability to bandwidth- and memory-limited systems such as multi-GPU training.

A.1 Useful facts

This appendix collects operator properties and stepsize facts used in the analysis, including expectation-based identities and bounds for η_t.

  • A.1 Useful facts: Lemma A.1 establishes a property for top-k and rand-k compression operators applied to vectors in R^d.The proof derives the result from the operators’ definitions and expectation.
  • A.1 Useful facts: Lemma A.2 bounds the squared stepsize η_t^2 when η_t = 1/(c+t) and c ≥ 1.The bound follows from an explicit algebraic inequality involving c and t.

A.2 Proof of the Main Theorem

The proof combines update equations, auxiliary lemmas, convexity and smoothness inequalities, and recursively weighted bounds to establish the main theorem.

  • A.2 Proof of the Main Theorem: The final bounds use smoothness and auxiliary lemmas to control gradient-related terms before deriving the stated result.The argument combines these estimates with equation (26) and concludes with (12).
  • A.2 Proof of the Main Theorem: The induction argument handles an initial regime through a threshold t_0 and uses the condition on a to combine the resulting estimates.The proof explicitly separates small-t reasoning before concluding the bound.
  • A.2 Proof of the Main Theorem: The analysis recursively substitutes the sequence, multiplies by weights w_t, and upper-bounds the resulting terms.These steps organize the proof around polynomial expressions in T and a.
  • A.2 Proof of the Main Theorem: Strong convexity, norm inequalities, smoothness, and inner-product bounds control the remaining terms in the convergence estimate.The proof introduces e_t = E[f(x_t) − f⋆] and combines the estimates to obtain the claim with (12).

B Experiments

The experiments tune the learning rate for fair comparison and quantify communication requirements for QSGD across dense and sparse datasets.

  • B Experiments: The experiments fix the learning rate to γ0/(1 + γ0λt)^−1 and grid-search γ0 separately for MEM-SGD and QSGD.The selected values are displayed in Figure 5, whose top and bottom rows correspond to RCV1-test and epsilon.
  • B Experiments: Figure 5 selects γ0 values corresponding to the lowest curves for use in section 4.3.The hyperparameter search is reported separately for RCV1-test and epsilon.
  • B Experiments: QSGD communication depends on the gradient dimension d and the number of quantization levels s, with alternative expressions for naïve and Elias encodings.The sparse RCV1-test comparison assumes QSGD sends only quantized nonzero coordinates with their indexes.
Loading 1809.07599v2…