Variants on Block Design Based Gradient Codes for Adversarial Stragglers

• URL: http://arxiv.org/abs/2105.05231v1
• Date: Tue, 11 May 2021 17:49:05 GMT
• Title: Variants on Block Design Based Gradient Codes for Adversarial Stragglers
• Authors: Animesh Sakorikar and Lele Wang
• Abstract summary: gradient coding provides robustness against slow or unresponsive machines, known as stragglers, in distributed machine learning applications. Recently, Kadhe et al. proposed a gradient code based on an incomplete block design, called balanced adversarial block design (BIBD), which is shown to outperform many existing gradient codes in worst-case adversarial straggling scenarios. In this paper, we aim to overcome such limitations and construct gradient codes which exist for a wide range of parameters while retaining the superior performance of BIBD gradient codes.
• Score: 3.5661843925286574
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gradient coding is a coding theoretic framework to provide robustness against slow or unresponsive machines, known as stragglers, in distributed machine learning applications. Recently, Kadhe et al. proposed a gradient code based on a combinatorial design, called balanced incomplete block design (BIBD), which is shown to outperform many existing gradient codes in worst-case adversarial straggling scenarios. However, parameters for which such BIBD constructions exist are very limited. In this paper, we aim to overcome such limitations and construct gradient codes which exist for a wide range of parameters while retaining the superior performance of BIBD gradient codes. Two such constructions are proposed, one based on a probabilistic construction that relax the stringent BIBD gradient code constraints, and the other based on taking the Kronecker product of existing gradient codes. Theoretical error bounds for worst-case adversarial straggling scenarios are derived. Simulations show that the proposed constructions can outperform existing gradient codes with similar redundancy per data piece.

Related papers

• Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
  Low-Density Parity-Check (LDPC) codes possess several advantages over other families of codes. The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
  arXiv  Detail & Related papers  (2024-06-09T12:08:56Z)
• Learning Linear Block Error Correction Codes [62.25533750469467]
  We propose for the first time a unified encoder-decoder training of binary linear block codes. We also propose a novel Transformer model in which the self-attention masking is performed in a differentiable fashion for the efficient backpropagation of the code gradient.
  arXiv  Detail & Related papers  (2024-05-07T06:47:12Z)
• Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation [55.8930142490617]
  We propose a decoder for QLDPC codes based on BP guided decimation (BPGD) BPGD significantly reduces the BP failure rate due to non-convergence.
  arXiv  Detail & Related papers  (2023-12-18T05:58:07Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  This paper aims to design a new gradient coding scheme for mitigating partial stragglers in distributed learning. We propose a gradient coordinate coding scheme with L coding parameters representing L possibly different diversities for the L coordinates, which generates most gradient coding schemes.
  arXiv  Detail & Related papers  (2022-06-06T09:25:40Z)
• Towards Extremely Fast Bilevel Optimization with Self-governed Convergence Guarantees [42.514612465664605]
  We propose a single-level formulation to uniformly understand existing explicit and implicit Gradient-based BLOs. A striking feature of our convergence result is that, compared to those original unaccelerated GBLO versions, the fast BAGDC admits a unified non-asymptotic convergence theory towards stationarity.
  arXiv  Detail & Related papers  (2022-05-20T09:46:10Z)
• Bias-Variance Tradeoffs in Single-Sample Binary Gradient Estimators [100.58924375509659]
  Straight-through (ST) estimator gained popularity due to its simplicity and efficiency. Several techniques were proposed to improve over ST while keeping the same low computational complexity. We conduct a theoretical analysis of Bias and Variance of these methods in order to understand tradeoffs and verify originally claimed properties.
  arXiv  Detail & Related papers  (2021-10-07T15:16:07Z)
• Fault-tolerant logical gates in holographic stabilizer codes are severely restricted [0.0]
  We evaluate the usefulness of holographic stabilizer codes for practical purposes by studying their allowed sets of fault-tolerantly implementable gates. We show that the set of stabilizerly implementable logical operations is contained in the Clifford group for sufficiently localized logical subsystems.
  arXiv  Detail & Related papers  (2021-03-24T18:00:05Z)
• Approximate Gradient Coding with Optimal Decoding [22.069731881164895]
  In distributed optimization problems, a technique called gradient coding has been used to mitigate the effect of straggling machines. Recent work has studied approximate gradient coding, which concerns coding schemes where the replication factor of the data is too low to recover the full gradient exactly. We introduce novel approximate gradient codes based on expander graphs, in which each machine receives exactly two blocks of data points.
  arXiv  Detail & Related papers  (2020-06-17T03:46:27Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)
• Communication-Efficient Gradient Coding for Straggler Mitigation in Distributed Learning [17.454251607446555]
  Distributed implementations of gradient-based methods, wherein a server distributes gradient computations across worker machines, need to overcome two limitations. Ye and Abbe [ICML 2018] proposed a coding-theoretic paradigm to characterize a fundamental trade-off between computation load per worker, communication overhead per worker, and straggler tolerance. We develop a communication-efficient gradient coding framework to overcome these drawbacks.
  arXiv  Detail & Related papers  (2020-05-14T17:57:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.