PaperlayerView exact revision on arXiv

Source-linked AI summary

Gradient Coding from Cyclic MDS Codes and Expander Graphs

Netanel Raviv, Itzhak Tamo, Rashish Tandon, Alexandros G. Dimakis

arXiv:1707.03858v3cs.ITstat.ML

TL;DR

Stragglers make synchronous distributed gradient computation unreliable, while exact gradient coding requires storage overhead d ≥ s + 1. The paper develops cyclic-MDS codes for exact recovery and expander-graph codes for approximate recovery, obtaining graceful error behavior and near-full-gradient generalization with simpler decoding.

  • Problem

    Exact gradient recovery requires storage overhead d ≥ s + 1, motivating approximate computation to reduce this barrier.

  • Method

    The paper uses cyclic MDS codes for deterministic exact gradient coding and normalized adjacency matrices of expander graphs for approximate coding.

  • Results

    Approximate coding has ℓ2 error that decreases with fewer stragglers, and expander graphs provide an error term smaller than the general regular-graph bound for any s.

  • Takeaways & Limitations

    Approximate gradient coding achieves generalization error only slightly worse than full-gradient coding, while linear decoding requires O(n) time instead of O(n3) for optimal decoding.

Abstract

from arXiv · show

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the $\ell_2$ error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that normalized adjacency matrices of expander graphs yield excellent approximate gradient codes, which enable significantly less computation compared to exact gradient coding, and guarantee faster convergence than trivial solutions under standard assumptions. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.

I. INTRODUCTION

The paper addresses stragglers in synchronous distributed gradient descent with exact and approximate gradient-coding schemes. It uses cyclic MDS codes for exact recovery and expander graphs for approximate recovery with graceful error degradation.

  • Gradient coding: Gradient coding assigns data parts redundantly to workers, which linearly combine partial gradients so the master can recover the full gradient despite s failed machines.The storage overhead d measures redundant computation or the number of data parts assigned to each worker.
  • Motivation: Synchronous distributed learning can be substantially delayed by unpredictable stragglers, motivating coding-theoretic and graph-theoretic mitigation.Amazon EC2 stragglers may run up to ×5 slower than typical workers, especially on cheaper virtual machines.
  • Limitations of exact coding: Existing exact gradient coding requires d ≥ s + 1 and generally assumes that s is known when constructing the system.The paper treats this requirement as a barrier for exact computation.
  • Contributions: The paper introduces cyclic-MDS constructions for exact gradients and compares them favorably with existing solutions in parameter applicability and algorithmic complexity.The construction uses classical coding-theoretic tools and is deterministic.
  • Contributions: Approximate gradient coding lets one trade exact recovery for an ℓ2 error that decreases as the number of stragglers decreases, without incorporating s into system construction.The resulting system supports any s < n, with quality deteriorating gracefully as s increases.
  • Framework: Workers send coded partial gradients based on matrix B, while the master combines responses from the non-stragglers using a vector a(K) to obtain an exact or approximate gradient.The support condition supp(a(K)) ⊆ K restricts decoding to responding workers.

IV. MATHEMATICAL NOTIONS

The paper reviews linear-code properties used for exact constructions and spectral properties of regular graphs used for approximate constructions. The key notions are MDS and cyclic codes, graph eigenvalues, and expanders.

  • Coding theory: Linear [n, κ] codes are κ-dimensional subspaces of F^n, with minimum distance defined by the smallest Hamming distance between distinct codewords.For linear codes, minimum distance equals the minimum Hamming weight of a nonzero codeword.
  • Coding theory: MDS codes attain the Singleton bound δ ≤ n − κ + 1 with equality.This makes their distance optimal for the given length and dimension.
  • Coding theory: A cyclic code remains unchanged under cyclic shifts of every codeword.The coordinate transformation maps (c1, c2, …, cn) to (cn, c1, …, c_{n−1}).
  • Coding theory: The paper uses duality and MDS properties, including that the dual of an [n, κ] MDS code is an [n, n − κ] MDS code.It also uses the existence of codewords with prescribed supports and the MDS property of reverse codes.
  • Code families: Reed–Solomon codes are evaluation codes and are widely known to be MDS, while BCH codes represent coefficient vectors constrained by polynomial roots.BCH codes are cyclic when their defining roots are roots of unity of order n.
  • Expander graphs: For a d-regular graph, the adjacency matrix has largest eigenvalue d, and expanders are constant-degree graphs whose remaining eigenvalues are small relative to d.Random regular graphs are used experimentally because they produce good expanders with high probability.

V. EXACT GRADIENT CODING FROM CYCLIC MDS CODES

The exact construction forms a matrix from cyclic shifts of a sparse codeword in a cyclic [n, n − s] MDS code. Its resulting decoder satisfies exact recovery, with optimal storage overhead and explicit complexity guarantees.

  • Construction: Starting from a cyclic [n, n − s] MDS code containing 1, the construction selects a codeword supported on {1, …, s + 1} and uses all cyclic shifts as matrix columns.Cyclicity ensures that every shifted codeword remains in the code.
  • Matrix properties: Every row of the resulting matrix B has Hamming weight s + 1, while every set of n − s rows is linearly independent.The column span of B is the original code, and its rows belong to the reverse code.
  • Decoding: Because every n − s rows form a basis and 1 belongs to the reverse code, a decoder a(K) supported on any surviving set K can satisfy a(K) · B = 1.This provides the coefficient vector needed to reconstruct the full gradient from any n − s responses.
  • Guarantee: The constructed pair (a, B) satisfies the Exact Computation condition.Thus the master can recover the exact gradient for every sufficiently large responding set specified by the condition.
  • Complexity: For any n and s, explicit complex-valued constructions achieve optimal d = s + 1 with encoding complexity O(s(n − s)) and decoding complexity O(s log^2 s + n log n).For n ≠ s mod 2, explicit real-valued constructions also achieve optimal d = s + 1.

A. Cyclic-MDS Codes Over the Complex Numbers

The paper constructs cyclic MDS codes over complex and real fields for gradient coding, using roots of unity, Vandermonde or BCH descriptions, and cyclic shifts. These codes support the paper’s exact-gradient construction with algorithms whose complexity improves over prior work in stated parameter ranges.

  • Complex construction: The complex construction evaluates degree-bounded polynomials at the n complex roots of unity using a Vandermonde generator matrix.The resulting code is an [n, n −s] MDS code containing the all-ones vector.
  • Complex construction: The complex code is cyclic because scaling the polynomial argument cyclically shifts its evaluations on the roots of unity.This establishes that the code can be used in the gradient-coding construction based on cyclic shifts.
  • Complex construction: Given n −s non-stragglers, the encoding vector can be computed in O(s log^2 s + n log n) operations after O(s^2 + s(n −s)) preprocessing.The paper states this is asymptotically smaller than corresponding algorithms in [7] and whenever s = o(n).
  • Construction trade-offs: Using complex rather than real coefficients may potentially double bandwidth, while the real construction applies only when n ≠ s mod 2.The paper gives a manipulation that resolves the complex-bandwidth issue and notes that the next scheme uses fewer multiplications.
  • Real construction: Real-valued cyclic MDS codes are constructed as BCH codes when n ≠ s mod 2, using root sets selected according to the parity of n and s.The codes C1 and C2 are shown to be cyclic [n, n −s] MDS codes containing the all-ones vector.
  • Real construction: The real-code MDS proof combines the BCH bound, dimension lower bounds, and the Singleton bound to obtain minimum distance s + 1 and dimension n −s.The root sets’ conjugation closure ensures the defining polynomials have real coefficients, while the roots-of-unity power sum verifies containment of the all-ones vector.

VI. APPROXIMATE GRADIENT CODING FROM EXPANDER GRAPHS

The paper replaces exact gradient recovery with an approximate scheme based on normalized adjacency matrices of regular graphs. Expander parameters control the approximation error and storage overhead, and the scheme can outperform trivial straggler-ignoring aggregation.

  • Motivation: Exact gradient recovery requires storage overhead d ≥s + 1, motivating approximate computation when that overhead is undesirable.The paper frames approximate recovery as consistent with stochastic-gradient methods, which already use approximate gradients.
  • Baseline: The trivial scheme uses B as the identity and averages the partial gradients from the non-stragglers after rescaling by n/|K|.This provides a baseline approximation scheme for comparison.
  • Expander construction: The proposed scheme sets B to a normalized adjacency matrix of a connected regular graph and chooses a simple master-side function a.The graph is constructed before data dispersal, and its degree determines the storage overhead.
  • Guarantees: The approximation error depends on the graph parameters, while storage overhead equals the regular graph’s degree d.For the scheme analyzed through the graph spectrum, the error bound is controlled by λ/d.
  • Trade-off: Constant-degree expanders preserve low storage overhead but prevent λ/d from tending to zero as n grows.Achieving a smaller improvement factor requires allowing the degree, and therefore the storage overhead, to increase.
  • Guarantees: The expander scheme improves over the trivial scheme by a multiplicative factor λ/d, which is below one for every non-bipartite graph.The paper separately discusses how bipartite graphs can be used to obtain different guarantees.
  • Examples: For n = 500 and d = 8 Margulis graphs, the paper reports an improvement factor based on λ/d, while Ramanujan graphs provide factors bounded by 2/√(d−1).The paper notes that Ramanujan graphs are harder to construct and gives examples with approximate factors 0.534 and 0.816.

A. Bipartite expanders.

The paper analyzes bipartite expander constructions through singular values, showing that the approximation error is bounded by the second singular value. Bipartite graphs can match or fail to improve on trivial schemes depending on their structure.

  • Limitations and modified constructions: Bipartite graphs have λ = d, so the general approximation scheme can lose its advantage over the trivial scheme and provide no gain.The paper instead notes that bipartite graphs on 2n nodes can be used in a modified fashion.
  • Bipartite expander analysis: The singular values of the biadjacency matrix connect directly to the eigenvalues of the graph’s adjacency matrix.The construction uses this spectral connection to evaluate expansion quality through σ2.
  • Bipartite expander analysis: For a connected d-regular bipartite graph, the approximation error satisfies d2(a(K)B, 1) ≤ σ2 for every non-straggler set K of size n − s.The bound follows from the singular-value decomposition of the bipartite graph’s biadjacency matrix.
  • Explicit constructions: Bipartite Ramanujan graphs provide explicit constructions with σ2 ≤ 2√p.The paper gives examples including n = 1092, d = 6, and σ2/d ≈ 0.745, and n = 60, d = 14, with σ2/d ≤ 2.

B. Lower bound.

The paper proves a lower bound on the approximation error achievable by any approximate computation scheme. Combined with the expander construction, this establishes asymptotic optimality up to constants for Ramanujan graphs.

  • Lower-bound result: A lower bound on every Approximate Computation scheme establishes asymptotic optimality up to constants when the proposed scheme uses Ramanujan graphs.The argument applies to arbitrary schemes, not only the paper’s construction.
  • Combinatorial argument: For a bipartite graph with worker degree at most d, every r ≤ ⌊n/d⌋ admits a set Qr whose neighborhood has size at most d|Qr|.This combinatorial lemma supplies the small-neighborhood set used in the lower-bound construction.
  • Combinatorial argument: When d < s < n, a row-sparse matrix has a set K of size n − s that supports the lower-bound construction.The proof associates the matrix with a bipartite graph and applies the neighborhood lemma.
  • Comparison with the lower bound: For the Ramanujan-based scheme, the error satisfies ϵ(s) ≤ 2√(s/d) / √(1 − s/n), tending to 2√(s/d) as s/n → 0.This matches the lower bound up to constants in the small-straggler-fraction regime.

C. A few remarks about convergence

The approximate gradient algorithm is analyzed under Bernoulli server responses and standard smoothness assumptions. Its unbiasedness supports convergence, while tighter deviation bounds can yield faster convergence than the trivial scheme.

  • Unbiasedness and convergence: If each server responds by the deadline with probability q, the expander scheme’s expected update equals the true gradient up to a constant factor.The expectation calculation gives Ez = (1 − (1 − q)^n) · 1.
  • Unbiasedness and convergence: The approximate algorithm converges because its gradient update has expectation proportional to the true gradient, with the learning rate adjusted accordingly.The same convergence reasoning applies to the trivial algorithm.
  • Comparison with the trivial scheme: The paper’s improved ℓ2-deviation bounds over the trivial algorithm provide better convergence bounds and are likely to yield faster convergence in many cases.This conclusion is stated within the paper’s standard convergence analysis.
  • Smoothness assumptions: Under β-smoothness and a bounded mean-squared gradient-deviation assumption, the convergence theorem applies on a constrained domain X.The theorem assumes Ev(w) = c∇LS(w) and E∥∇LS(w) − v(w)∥2^2 ≤ σ^2.

VII. EXPERIMENTAL RESULTS

This section presents experimental results for the paper’s proposed approximate gradient coding scheme, including ℓ2-error recovery results using normalized adjacency matrices of random d-regular graphs.

  • The experiments evaluate the proposed approximate gradient coding scheme.
  • A theorem cited in this section is presented as a special case of a more general result from.
  • Fig. 2 reports ℓ2-error for recovery of 1 using normalized adjacency matrices of random d-regular graphs.

A. ℓ2-Error

The approximate coding schemes use expander-graph matrices with linear and optimal decoders, and recovery worsens with more stragglers but improves with higher graph degree.

  • ℓ2-Error: The evaluation uses normalized adjacency matrices of random d-regular graphs and compares linear decoding with optimal least-squares decoding.The surviving workers are sampled as n−s rows of the graph matrix.
  • ℓ2-Error: As the number of stragglers increases, recovery gets worse for a fixed degree d.
  • ℓ2-Error: As the degree d increases, recovery error gets better for a fixed number of stragglers s.
  • ℓ2-Error: The optimal decoder achieves lower ℓ2-error than the linear decoder on average.Both decoders also outperform the theoretical upper bound on average in the reported cases.

B. Generalization Error

Approximate gradient coding is evaluated against exact gradient coding and a trivial scheme on EC2. Its generalization error is only slightly worse than exact coding and substantially better than the trivial approach, while linear decoding is much cheaper.

  • Generalization Error: The experiments compare approximate gradient coding with exact Gradient Coding and a trivial scheme using only the first n−s gradients.
  • Generalization Error: The evaluation measures validation-set AUC for logistic regression on the Amazon Employee dataset using gradient descent.The setup uses 26,200 training samples and a model dimension of 241,915.
  • Generalization Error: The EC2 experiments use t2.micro workers and a c3.8xlarge master, with results reported for n = 30 and n = 50.
  • Generalization Error: AGC uses the optimal decoder, while AGCL is the full proposed scheme using the linear decoder.
  • Generalization Error: AGC and AGCL are only slightly worse than exact Gradient Coding and substantially better than the trivial scheme.AGCL can be faster because its linear decoder requires O(n) time versus O(n^3) for the optimal decoder.
  • Generalization Error: For n = 30, Gradient Coding has ×6 computational overhead compared with ×3 for the proposed approach.This setting uses d = 3 and s = 5.
  • Generalization Error: For n = 50, Gradient Coding has ×11 computational overhead compared with ×5 for the proposed approach.This setting uses d = 5 and s = 10.

APPENDIX B

The appendix develops cyclic-code constructions and decoding algorithms, establishes their correctness, and gives complexity and bandwidth results for the proposed schemes.

  • APPENDIX B: The construction in Subsection V-B forms a code from codewords with s mutual roots and computes its matrix through a BCH generator polynomial.
  • APPENDIX B: Computing the construction matrix has complexity O(min{s log^2 s, n log n}), improving over whenever s = o(n).
  • APPENDIX B: Algorithm 3 outperforms when s = o(log^2 n) and when s = o(n^2/3).
  • APPENDIX B: Algorithm 3 outputs a decoding vector supported on the non-stragglers and satisfying a(K)B = 1.
  • APPENDIX B: Its complexity is O(γs+s(n−s)), with a simple O(s^3) option for generalized Vandermonde inversion.
  • APPENDIX C BANDWIDTH REDUCTION IN SUBSECTION V-A: The bandwidth-reduction construction combines pairs of real gradient coordinates into complex coordinates before transmission.The real and imaginary parts are later used to recover the real update.
  • APPENDIX C BANDWIDTH REDUCTION IN SUBSECTION V-A: The modified scheme preserves correctness for every set of n−s non-stragglers and attains optimal bandwidth using p′ complex numbers, or 2p′ real numbers.
  • APPENDIX C BANDWIDTH REDUCTION IN SUBSECTION V-A: The bandwidth-reduction variant changes worker computation from dp multiplications over R to approximately 2dp, while the original scheme requires dp multiplications.

APPENDIX D

The appendix analyzes approximate-gradient error under a convention for complete straggling and notes that sharper error analyses could improve the resulting bound.

  • APPENDIX D: When all servers are stragglers, the algorithm outputs the zero vector as the gradient approximation.
  • APPENDIX D: The analysis compares the trivial algorithm's error with a random-variable-based bound under the stated straggler convention.
  • APPENDIX D: A more sophisticated approach to bounding the error is not ruled out and would always produce a better bound for E[R].
Loading 1707.03858v3…