PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Coded Deep Neural Network Training Strategy Based on Generalized PolyDot Codes for Matrix Multiplication

Sanghamitra Dutta, Ziqian Bai, Haewon Jeong, Tze Meng Low, Pulkit Grover

arXiv:1811.10751v1cs.ITcs.DCcs.LGmath.IT

TL;DR

To train DNNs across soft-error-prone nodes, the paper introduces Generalized PolyDot codes and a decentralized coded-training strategy. It reports unbounded worst-case error-tolerance gains over replication and MDS strategies, alongside a probability-one real-number error-correction result.

  • Problem

    Coded DNN training under soft-errors must handle costly per-iteration weight encoding, nonlinear operations, and decentralized execution without a reliable master.

    Source: §I · p. 3

  • Method

    The paper introduces Generalized PolyDot codes using garbage alignment and applies them in a decentralized coded DNN training strategy.

    Source: §I · p. 2

  • Results

    The strategy is reported to provide unbounded worst-case error-tolerance gains over replication and MDS baselines, while real-number (P,Q) MDS decoding corrects P−Q−1 errors with probability 1.

    Source: A. Adversarial and Probabilistic Error… · p. 13, §VIII · p. 21

  • Takeaways & Limitations

    The unified strategy advances coded matrix multiplication and can be adapted to applications such as autoencoders.

    Source: §XI · p. 28

    The probabilistic error analysis assumes a continuous noise distribution, a simplification the authors acknowledge can yield optimistic conclusions.

    Source: B. Error Models for the coded DNN… · p. 16

Abstract

from arXiv · show

This paper has two contributions. First, we propose a novel coded matrix multiplication technique called Generalized PolyDot codes that advances on existing methods for coded matrix multiplication under storage and communication constraints. This technique uses "garbage alignment," i.e., aligning computations in coded computing that are not a part of the desired output. Generalized PolyDot codes bridge between Polynomial codes and MatDot codes, trading off between recovery threshold and communication costs. Second, we demonstrate that Generalized PolyDot can be used for training large Deep Neural Networks (DNNs) on unreliable nodes prone to soft-errors. This requires us to address three additional challenges: (i) prohibitively large overhead of coding the weight matrices in each layer of the DNN at each iteration; (ii) nonlinear operations during training, which are incompatible with linear coding; and (iii) not assuming presence of an error-free master node, requiring us to architect a fully decentralized implementation without any "single point of failure." We allow all primary DNN training steps, namely, matrix multiplication, nonlinear activation, Hadamard product, and update steps as well as the encoding/decoding to be error-prone. We consider the case of mini-batch size $B=1$, as well as $B>1$, leveraging coded matrix-vector products, and matrix-matrix products respectively. The problem of DNN training under soft-errors also motivates an interesting, probabilistic error model under which a real number $(P,Q)$ MDS code is shown to correct $P-Q-1$ errors with probability $1$ as compared to $\lfloor \frac{P-Q}{2} \rfloor$ for the more conventional, adversarial error model. We also demonstrate that our proposed strategy can provide unbounded gains in error tolerance over a competing replication strategy and a preliminary MDS-code-based strategy for both these error models.

I. INTRODUCTION

The introduction presents Generalized PolyDot codes for storage-constrained matrix multiplication and a decentralized strategy for DNN training under soft-errors, addressing coding overhead, nonlinear operations, and the absence of a reliable master node. Its error-resilience overhead assumption concerns negligible added costs in error-free iterations; costs incurred when errors occur are not compared.

I. INTRODUCTION

  • Under the probabilistic error model, a real-number (P, Q) MDS code corrects P − Q − 1 errors with probability 1, versus ⌊(P − Q)/2⌋ under the adversarial model.The paper presents this as a novel real-number error-correction result for MDS codes.Source: §I · p. 2
  • Generalized PolyDot codes use garbage alignment to reduce polynomial-interpolation unknowns and improve the recovery threshold by a factor of 2 over PolyDot codes.They interpolate between Polynomial and MatDot codes, trading off recovery threshold and communication costs; concurrent work achieves the same threshold through a different route.Source: §I · p. 2, A. Why are Generalized PolyDot codes a… · p. 4
  • The DNN strategy keeps weight matrices encoded across updates, encoding smaller NB-element matrices per iteration instead of re-encoding each N²-element weight matrix.For B = 1, this means encoding vectors rather than matrices; the strategy also reports negligible per-iteration coding overhead when P^4 = o(N).Source: §I · p. 3, B. Problem 2 (Coded DNN) · p. 7

A. Why are Generalized PolyDot codes a natural choice for coded DNN training?

  • A shared m × n partition of each weight matrix, with mn = K, supports both forward multiplication WX and backward multiplication ΔᵀW under the storage constraint.This lets the encoding interpolate between MatDot and Polynomial codes for both multiplications, targeting a good recovery threshold and error tolerance.Source: A. Why are Generalized PolyDot codes a… · pp. 3–4, Figure 2 · p. 4

A. Problem 1 (Coded Matrix Multiplication).

  • For storage-constrained matrix multiplication, the goal is to minimize the recovery threshold while trading it off against communication costs.The formulation computes S = WX across P nodes that store fixed fractions 1/K and 1/K′ of W and X; MatDot and Polynomial codes are special cases of the proposed general strategy.Source: A. Problem 1 (Coded Matrix… · p. 5

B. Problem 2 (Coded DNN).

  • The DNN strategy targets maximum error tolerance while keeping per-node computation and communication overhead negligible relative to local matrix operations.It uses a decentralized system with no reliable master and permits errors in encoding, decoding, matrix multiplication, activation, Hadamard products, and updates; it improves error tolerance over replication and preliminary MDS-based training under both error models.Source: §I · p. 3, B. Problem 2 (Coded DNN) · p. 7
  • Error detection and encoding run each iteration so their overhead remains negligible in error-free iterations; costs in iterations with detected errors are not compared.Error-iteration costs may include regenerating erroneous nodes or reverting to the last checkpoint.Source: B. Problem 2 (Coded DNN) · p. 7

III. MOTIVATING EXAMPLE FOR CODED MATRIX MULTIPLICATION

Polynomial-based coded multiplication encodes matrix blocks in polynomials so worker evaluations can be interpolated to recover the product. The motivating example shows how aligning unwanted coefficients reduces the number of evaluations needed for recovery.

III. MOTIVATING EXAMPLE FOR CODED MATRIX MULTIPLICATION

  • Polynomial-based coding chooses matrix-block polynomials whose product exposes output submatrices as coefficients recoverable by interpolation.Each processing node evaluates both polynomials and computes their product; the recovery threshold is one plus the product polynomial’s degree.Source: §III · p. 8
  • In Polynomial codes with K = 4, a degree-15 product polynomial requires 16 unique evaluations to recover its coefficients.Those coefficients include the submatrices of the result.Source: §III · p. 8
  • In MatDot codes, the coefficient of v^3 yields the product, so a degree-6 polynomial requires 7 unique evaluations.The other coefficients are called garbage.Source: §III · pp. 8–9
  • The example’s PolyDot encoding assigns increasing powers of v across W’s column blocks and decreasing powers across X’s row blocks.The motivating example splits both matrices horizontally and vertically into four submatrices.Source: §III · p. 9, Figure 4 · p. 10
  • Garbage alignment reduces the example’s recovery threshold from 12 to 9 by combining unwanted coefficients after substitution.The useful coefficients still identify the output blocks, while the substituted polynomial has degree 8.Source: §III · p. 10

IV. GENERALIZED POLYDOT CODES FOR CODED MATRIX MULTIPLICATION

Generalized PolyDot codes use garbage alignment to trade recovery threshold against communication cost for coded matrix multiplication. Their constructions cover matrix-vector and matrix-matrix products, with thresholds determined by the chosen partitioning parameters.

Matrix-vector multiplication

  • For matrix-vector multiplication, the recovery threshold is mn + n −1, allowing tolerance of at most P −mn −n + 1 erasures.The decoder recovers the desired sub-vectors as coefficients of the encoded product polynomial.Source: §IV · pp. 10–11

Matrix-matrix multiplication

  • For matrix-matrix multiplication, the recovery threshold is mnd + n −1, allowing tolerance of at most P −mnd −n + 1 erasures.The construction uses mn = K and nd = K′, with each node storing sub-matrices of W and X.Source: §IV · p. 11

Garbage alignment

  • Substitutions u = vn and w = vmn align unwanted polynomial terms while preserving the desired matrix-product coefficients.This converts the encoded product into a single-variable polynomial whose evaluations can be interpolated.Source: §IV · p. 12

Decoding under erasures

  • Under erasures, decoding waits for mnd + n −1 worker outputs and uses polynomial interpolation to recover the product.The master gathers these outputs from workers.Source: §IV · p. 12

Tradeoff between communication cost and recovery threshold

  • For fixed K = K′ = 36, Generalized PolyDot codes bridge Polynomial codes’ minimum N1B communication cost and threshold 1296 with MatDot codes’ lowest threshold, 71.Varying m, n, and d improves the tradeoff using garbage alignment; master-to-worker communication is excluded because it is the same across strategies.Source: Figure 5 · p. 12, §IV · p. 13

V. MODELLING ASSUMPTIONS FOR CODED DNNS WITH A RESULT ON REAL NUMBER ERROR CORRECTION

The section models soft-errors in coded DNN settings and proves a probabilistic error-correction result for real-number MDS codes. Under its probabilistic model, the decoder corrects up to P −Q −1 errors with probability 1, but the proposed decoding relies on an NP-hard sparse reconstruction problem.

Error models

  • The probabilistic model allows adversarially chosen error locations, but assumes the error values at those locations are iid Gaussian and independent of the symbol vector.The contrasting adversarial model limits errors to ⌊(P−Q)/2⌋ without assumptions on their locations or values.Source: A. Adversarial and Probabilistic Error… · p. 13

Real-number error correction

  • A real-number (P, Q) MDS decoder detects errors with probability 1 and corrects up to P −Q −1 errors with probability 1 under the probabilistic error model.With more errors, it declares decoding failure with probability 1.Source: A. Adversarial and Probabilistic Error… · p. 13

Decoding algorithm

  • The decoder detects errors using Hz and estimates the error vector by minimizing its number of nonzero entries subject to He = Hz.It returns the estimate only when its support is at most P −Q −1; otherwise it declares decoding failure.Source: A. Adversarial and Probabilistic Error… · p. 14

Practical limitation

  • The proposed decoder requires sparse reconstruction for undetermined systems, an NP-hard problem that may require relaxation or approximate algorithms in practice.The paper mentions L1-norm relaxation and polynomial-time sparse reconstruction methods as possible practical alternatives.Source: A. Adversarial and Probabilistic Error… · p. 15

B. Error Models for the coded DNN problem.

The section defines a model-parallel DNN setting with error-prone nodes and distinguishes adversarial from probabilistic soft-error models. It sets error-tolerance and communication goals, then reviews replication and MDS-code strategies for comparison.

B. Error Models for the coded DNN problem.

  • The model-parallel setting distributes each layer across P error-prone nodes, and the two error models differ in when errors may occur, their assumptions, and how they are handled.Error Model 1 bounds errors in O1, O2, and O3 while assuming other operations are error-free; Error Model 2 allows unbounded errors in primary operations and assumes additive iid Gaussian noise.Source: B. Error Models for the coded DNN… · pp. 15–16

C. Error Tolerance Goals for the coded DNN Strategy.

  • The goal is to maximize the numbers of erroneous outputs that can be detected and corrected after O1 and O2, under either error model.The achievable tolerances depend on P and strategy parameters; the section notes that errors from other steps may also be corrected at these points.Source: C. Error Tolerance Goals for the coded… · p. 16

D. Communication Complexity.

  • Communication cost for a message of N items between two nodes is modeled as α + βN, while broadcast and All-Gather use collective protocols with costs that depend on P.The stated costs are α log P + βN for broadcast and α log P + 2βPN for All-Gather.Source: D. Communication Complexity · pp. 16–17

VI. APPLYING EXISTING STRATEGIES TO THE CODED DNN PROBLEM

  • Replication creates P/(mn) copies of an mn-node block-partitioned system and compares outputs among replicas to detect and correct errors.Under Error Model 1, the strategy tolerates floor((P−mn)/(2mn)) errors; under Error Model 2, it tolerates P/mn−2 when mn divides P.Source: §VI · p. 17
  • The MDS strategy block-partitions W and uses separate systematic MDS codes across its row and column dimensions, activating the corresponding coded nodes for O1 and O2.Its architecture uses Pf nodes for O1 and Pb nodes for O2, with mn nodes common to both steps.Source: §VI · pp. 17–18
  • Under Error Model 1, the MDS strategy requires tf ≥ t1 + t3 and tb ≥ t2 + t3 to correct all errors in the worst case; under Error Model 2, excess errors can be detected but not corrected.The figure depicts W divided into 2×2 blocks and encoded with row- and column-wise systematic MDS codes.Source: §VI · p. 18, Figure 7 · p. 18

VII. OUR PROPOSED CODED DNN TRAINING STRATEGY FOR MINI-BATCH B = 1

The proposed B = 1 strategy encodes each weight matrix once, then uses coded vector operations for feedforward and backpropagation. Nodes decode outputs and update their coded weights while retaining the encoded structure.

VII. OUR PROPOSED CODED DNN TRAINING STRATEGY FOR MINI-BATCH B = 1

  • The weight matrix is encoded only before the first iteration; subsequent iterations encode and decode vectors instead of repeatedly encoding W.The same initial encoding supports coded post- and pre-multiplication of W by x and δT at each layer.Source: §VII · p. 18
  • In feedforward, nodes encode x, multiply their coded vector by their coded weight submatrix, and exchange outputs so each node can decode s = Wx.After decoding, each node applies the nonlinear function element-wise to produce the next layer's input.Source: §VII · p. 19
  • When errors are within tolerance, nodes can decode vectors and identify erroneous nodes, then regenerate their encoded weight submatrices from correct nodes.Regeneration can be performed element-wise while respecting each node's storage constraint.Source: §VII · p. 19
  • Under Error Model 2, excess errors that prevent decoding are detected with probability 1, after which the DNN is restored from the last checkpoint.Nodes also compare pre-decided decoded-vector values to detect decoding disagreements; this verification step is assumed error-free because of its low complexity.Source: §VII · pp. 19–20
  • Backpropagation similarly encodes δT, multiplies it by coded weight submatrices, and decodes the coefficients that form cT.The decoded cT vectors are reconstructed from outputs exchanged across nodes.Source: §VII · p. 20
  • Each node updates its coded weight submatrix using x and δ, preserving the coded structure with negligible additional overhead.The update is performed locally after both vectors are available at each node.Source: §VII · p. 20

VIII. RESULTS ON PERFORMANCE OF OUR PROPOSED STRATEGY

Generalized PolyDot offers the best reported feedforward/backpropagation error-tolerance tradeoff and improves worst-case error tolerances over replication and MDS strategies by a factor that can diverge while overhead remains negligible. The paper extends the strategy to mini-batches, with negligible additional overhead under a stated node-count condition.

VIII. RESULTS ON PERFORMANCE OF OUR PROPOSED STRATEGY

  • Generalized PolyDot’s worst-case error tolerances exceed those of MDS and replication by a factor that can diverge to infinity, with communication and computation overhead remaining negligible.The comparison is stated for both error models.Source: §VIII · p. 21
  • With P = 180 and K = 36, Generalized PolyDot achieves the best (tf, tb) tradeoff as m and n vary under both error models.The figure compares Error Model 1 on the left and Error Model 2 on the right; choosing v = um interchanges the tolerances but gives the same curve.Source: Figure 8 · p. 22
  • As K, N, and P grow, CGP’s total per-layer, per-iteration complexity relative to matrix-vector products and updates tends to zero if P^4 = o(N).The total includes encoding, decoding, communication, nonlinear activation, and Hadamard products.Source: §VIII · p. 22
  • Even under pessimistic communication and computation bounds, CGP’s additional overhead is negligible in scaling relative to steps O1, O2, and O3.The communication analysis uses an efficient All-Gather protocol; further cost reduction is left for future work.Source: §VIII · pp. 22–23

IX. EXTENSION TO MINI-BATCH SIZE B > 1: CODED MATRIX-MATRIX MULTIPLICATION

  • For mini-batch size B > 1, the strategy extends to coded matrix-matrix multiplication, with each node storing a 1/K fraction of each layer’s weight matrix.The stated design assumes B = o(N/K), so the input and intermediate matrices take smaller scaling-order storage than that weight fraction.Source: §IX · p. 23
  • For mini-batches, additional overheads remain negligible relative to matrix-matrix products and updates when P^4 = o(N), whether or not B = o(N/K).The upper bound on B is required for the stated storage constraint, not for the complexity comparison.Source: §IX · p. 23

A. Modification to Existing Strategies.

The paper adapts replication and MDS-coded strategies to mini-batches, then applies Generalized PolyDot codes to the feedforward, backpropagation, and update stages. Decoding recovers the desired matrix products at each node, and the update preserves the coded weight matrix.

A. Modification to Existing Strategies.

  • Replication adapts by splitting X into n blocks and ∆T into m blocks, while retaining additional costs smaller in scaling than per-node O1, O2, and O3 complexity.The weight matrix is block-partitioned and stored with Pmn replicas.Source: A. Modification to Existing Strategies · p. 23
  • The MDS strategy similarly divides X and ∆T into n and m parts, with added computation and communication still smaller in scaling than per-node O1, O2, and O3 complexity.Source: A. Modification to Existing Strategies · pp. 23–24

B. Our Proposed coded DNN Training Strategy for mini-batch size B > 1.

  • In feedforward, Generalized PolyDot encodes W and X so the desired WX blocks are polynomial coefficients recoverable from node evaluations; each node then applies activation to the decoded S.The method substitutes variables to obtain a single-variable polynomial and interpolates its coefficients from P evaluations, some of which may be erroneous.Source: B. Our Proposed coded DNN Training… · p. 24
  • In backpropagation, decoding the polynomial evaluations recovers CT = ∆T W at every node, which then computes the next-layer error using CT ◦ g(XT).The desired CT blocks correspond to coefficients in the polynomial formed from the encoded ∆T and W.Source: B. Our Proposed coded DNN Training… · p. 25
  • The update encodes columns of X and rows of ∆T, updates each coded weight polynomial, and preserves the coded nature of W.The update can also be extended to include regularization.Source: B. Our Proposed coded DNN Training… · pp. 25–26

C. Comparison with existing strategies.

The comparison section reports that Generalized PolyDot’s additional per-layer overhead is asymptotically negligible under a stated scaling condition. The paper also extends the coded DNN strategy to sparse autoencoders and summarizes its broader contributions.

C. Comparison with existing strategies.

  • When P^4=o(N), the ratio of CGP’s total per-layer, per-iteration complexity to the complexity-intensive steps tends to zero as K, N, and P grow.The authors also describe the additional overheads as negligible relative to steps O1, O2, and O3.Source: C. Comparison with existing strategies · p. 26

X. CODED AUTOENCODER

  • Sparse autoencoders with multiple hidden layers are treated as stacked single-hidden-layer autoencoders, so the coded extension analyzes one hidden layer.The paper presents this as an example of extending its coded DNN technique to another architecture.Source: §X · p. 27

XI. DISCUSSION AND CONCLUSIONS

  • Generalized PolyDot codes use garbage alignment to improve recovery thresholds, and the paper’s coded DNN strategy advances error tolerance over existing techniques.The conclusion also identifies sparse autoencoders as an application of the unified strategy.Source: §XI · p. 28
  • The authors suggest that error-resilient neural-network training could interest HPC, neuroscience, and neuromorphic computing, while its efficiency and energy implications remain possibilities.The conclusion frames these broader implications as potential rather than established outcomes.Source: §XI · p. 28

APPENDIX A DNN BACKGROUND

This background describes DNN training as iterative optimization of layer weights using feedforward computation, backpropagation, and updates. It introduces SGD as a way to compute updates from individual data points rather than the full dataset.

DNN structure

  • A DNN has one weight matrix per layer, and each layer applies its weights to the previous layer’s output before an elementwise nonlinear activation produces the next output.The final layer’s output is compared with the true label to evaluate the prediction.Source: Appendix A · pp. 31–32

Training objective and SGD

  • Training seeks weight matrices that minimize empirical loss; SGD updates weights using the gradient for one data point instead of accessing the full dataset at every iteration.The training iteration comprises feedforward, backpropagation, and update stages.Source: Appendix A · pp. 31–32

Backpropagation and updates

  • Backpropagation recursively computes layer errors from the succeeding layer, which are then used to update each layer’s weights.The text presents the backpropagated error vector as the quantity linking successive layers.Source: Appendix A · p. 33

A. Algorithmic Steps for DNN Training (B = 1).

For batch size one, DNN training alternates feedforward, backpropagation, and weight updates; the paper extends these operations to mini-batches and describes regularized updates. The described coding work assumes vanilla SGD.

A. Algorithmic Steps for DNN Training (B = 1).

  • For B=1, each layer performs a feedforward matrix-vector product, a backpropagation matrix-vector product, and a weight update, with activation and Hadamard-product steps between them.The update uses the learning rate, and L2 regularization adds weight decay.Source: A. Algorithmic Steps for DNN Training… · p. 34

B. Extension to mini-batch SGD with batch size B > 1.

C. Regularization.

  • With weight-decay regularization, each iteration shrinks weights by the factor (1−ηλ), and the paper assumes the same λ across layers for simplicity.The authors note that different layers could desirably use different λ values.Source: C. Regularization · p. 36

D. Training Autoencoders.

The paper adapts coded DNN training to sparse autoencoders by incorporating their sparsity term into the training procedure. It focuses on a one-hidden-layer autoencoder and also identifies related proof and error-model discussion in the appendix.

D. Training Autoencoders.

  • Sparse autoencoders add a loss term to encourage sparse hidden-layer outputs, even when the hidden layer has more neurons than the input or output layers.The paper focuses on a one-hidden-layer autoencoder because deeper autoencoders are treated as stacked single-hidden-layer units.Source: D. Training Autoencoders · p. 36
  • For mini-batch training, the sparsity term uses activation sparsity averaged over the batch and changes the update for W1, while the W2 update remains unchanged.The feedforward stage follows the previously described procedure.Source: D. Training Autoencoders · p. 37

APPENDIX B PROOF OF THEOREM 3 AND A DISCUSSION ON ERROR MODELS AND DECODING TECHNIQUES

  • Appendix B provides a proof of Theorem 3 and discusses the error models and decoding techniques.Source: Appendix B · p. 38

A. Notations and Definitions.

This section defines the real-number MDS channel model and notation for its codewords, errors, and probability calculations.

A. Notations and Definitions.

  • The channel input q is a Q × 1 real-valued symbol vector, and the codeword is corrupted by an additive error vector e on locations A.G is the generator matrix of the (P, Q) real-number MDS code.Source: A. Notations and Definitions · p. 38
  • The random symbol vector Q and error vector E are independent; conditioned on error locations A, active error entries are iid Gaussian.Entries outside A are zero.Source: A. Notations and Definitions · pp. 38–39
  • The notation defines sample spaces and integration over vector components, event probabilities and densities, matrix null spaces, and vector counts of nonzero elements.The count is denoted by ||·||0.Source: A. Notations and Definitions · p. 39

B. Formal Proof of Theorem 3.

Under the probabilistic error model, Theorem 3 characterizes when an MDS decoder detects, corrects, or rejects errors. Its proof uses a parity-check decoder and shows that ambiguous alternatives occur only on measure-zero sets.

B. Formal Proof of Theorem 3.

  • A (P, Q) MDS decoder detects errors with probability 1, corrects at most P −Q−1 errors with probability 1, and declares failure above that limit with probability 1.These claims hold under the probabilistic error model.Source: B. Formal Proof of Theorem 3 · p. 39
  • The decoder checks Hz, seeks a minimum-nonzero solution to He = Hz, and returns it only when its support is at most P −Q−1.Otherwise it declares decoding failure; if Hz = 0, it reports no errors.Source: B. Formal Proof of Theorem 3 · p. 39
  • The proof rules out incorrect decoding almost surely because competing error vectors require Gaussian error entries to lie in measure-zero subspaces.The argument examines candidate supports and shows the relevant sets have measure zero.Source: B. Formal Proof of Theorem 3 · pp. 40–42

C. Comparison with Adversarial Error Model.

For adversarial errors, a real-number (P, Q) MDS code corrects at most ⌊(P−Q)/2⌋ errors in the worst case. The section relates this bound to polynomial interpolation and parity-check decoding.

C. Comparison with Adversarial Error Model.

APPENDIX C PROOFS OF THEOREMS 4 AND 6

The proofs reduce coded matrix-product decoding to polynomial interpolation from node evaluations that may contain errors. They derive error tolerances for alternative Generalized PolyDot substitutions and compare them with replication and MDS-based strategies.

APPENDIX C PROOFS OF THEOREMS 4 AND 6

  • The interpolation problem concerns only selected coefficients of the two-variable product polynomials, which can be recovered from evaluations at P nodes despite erroneous values.The required coefficients are those of u^i v^(n−1) or u^(m−1) v^j.Source: Appendix C · p. 44
  • For CGP(K, N, P) with u = vn, feedforward tolerates ⌊(P−mn−n+1)/2⌋ errors under Error Model 1 and P−mn−n under Error Model 2.The substitution aligns some polynomial coefficients while preserving the coefficients of interest.Source: Appendix C · p. 44
  • The MDS-based strategy uses separate feedforward and backpropagation node counts, with mn nodes shared between the stages.The total node count is P = Pf + Pb −mn.Source: Appendix C · p. 44
  • Under Error Model 2, replication can detect and correct P/(mn)−2 errors when an output occurs at least twice.The argument relies on continuous error distributions, which make two outputs having exactly the same error probability zero.Source: Appendix C · p. 45
  • For feedforward, coefficient interpolation is equivalent to decoding a (P, mnd1+n−1) MDS code, correcting floor((P−mnd1−n+1)/2) errors under Error Model 1 and P−mnd1−n under Error Model 2.For backpropagation, the limits are floor((P−mnd2−mn+n)/2) errors under Error Model 1 and P−mnd2−mn+n−1 errors under Error Model 2.Source: Appendix C · p. 45
  • For feedforward, the polynomial degree mnd1+mn−m−1 gives mnd1+mn−m unique coefficients, permitting ⌊(P−mnd1−mn+m)/2⌋ errors under Error Model 1 and P−mnd1−mn+m−1 under Error Model 2.For backpropagation, the limits are ⌊(P−mnd2−n+1)/2⌋ errors under Error Model 1 and P−mnd2−n errors under Error Model 2.Source: Appendix C · p. 45

APPENDIX D COMPLEXITY ANALYSIS AND PROOFS OF THEOREM 5 AND THEOREM 7

The appendix analyzes per-node computation and communication for decentralized DNN training with mini-batches B=1 and B>1. Under P^4=o(N), the additional steps have negligible overhead as K, N, and P scale, while matrix products and updates dominate computation.

APPENDIX D COMPLEXITY ANALYSIS AND PROOFS OF THEOREM 5 AND THEOREM 7

  • Communication costs assume bounded simultaneous multicast: sending N values to P nodes costs α log2 P + βN, while all-gathering P distinct N-value sets costs α log2 P + βNP.The appendix also notes that reducing communication cost with improved implementation strategies remains under examination.Source: Appendix D · p. 46
  • For B=1, matrix-vector products and updates are the critical computational steps, while additional encoding and decoding overhead is negligible under the stated scaling condition.The proof uses P^4=o(N) to establish that the additional steps are negligible relative to the matrix-vector products and updates.Source: Appendix D · p. 47
  • For B>1, each node computes matrix-matrix products in feedforward and backpropagation, and the update performs B consecutive rank-1 updates to its stored encoded sub-matrix.The per-node product complexity is Θ(N^2B/K) in both stages, with K=mn.Source: Appendix D · pp. 47–48
  • Decoding is the most dominant among the complexities of the other steps apart from matrix-matrix products (steps O1 and O2) and the update (step O3); its pessimistic upper bound can be reduced by an appropriate decoding algorithm.Source: Appendix D · p. 48
  • Under P^4=o(N), the ratio of additional-step complexity to matrix-matrix product complexity tends to 0 for both feedforward and backpropagation as K, N, and P scale.The appendix concludes that matrix-matrix products and updates are the most computationally intensive steps; encoding and decoding add negligible overhead.Source: Appendix D · pp. 48–49

Related papers

Loading 1811.10751v1…