Data Encoding for Byzantine-Resilient Distributed Optimization

Deepesh Data, Linqi Song, Suhas N. Diggavi

Introduction

In large-scale distributed learning, a central master node coordinates multiple worker nodes to solve complex optimization problems. However, real-world deployments—ranging from federated learning to the Internet of Battlefield Things—are vulnerable to "Byzantine" workers. Unlike simple fail-stop errors or stragglers, Byzantine nodes can act maliciously, collaborating to send arbitrary or strategically incorrect values to the master to subvert the learning process.

This paper introduces a novel framework that utilizes sparse data encoding and real-number error correction to make distributed optimization—specifically Proximal Gradient Descent (PGD) and Coordinate Descent (CD)—resilient to such adversaries. The proposed method achieves the information-theoretically optimal corruption threshold while maintaining low, often constant, overhead in storage and computation.

The Problem: Beyond Statistical Defense

Existing defenses against Byzantine workers often rely on statistical assumptions, such as the data being independent and identically distributed (i.i.d.), or utilize robust aggregation techniques like geometric medians. While useful, these techniques can be computationally expensive and often provide only approximate results.

The authors seek a deterministic solution that works for any data distribution, provides exact gradients, and handles both data-parallel (PGD) and model-parallel (CD) architectures efficiently. The goal is to ensure that even if a significant fraction of the workers are malicious, the master node can still recover the exact computation results.

Methodology: MV Multiplication as a Primitive

The core insight of this work is that most first-order optimization methods for Generalized Linear Models (GLMs) rely fundamentally on Matrix-Vector (MV) multiplications. By securing the MV product, one secures the entire optimization algorithm. The authors propose a three-step process:

1. Sparse Data Encoding

Before computation begins, the master node encodes the data matrix $X$ using a specially designed sparse encoding matrix $S$. This encoded data is then distributed among $m$ workers. By using sparse encoding matrices, the authors ensure that the "encoded" version of a sparse data matrix remains relatively sparse, preventing the computational explosion typically associated with error-correcting codes.

2. Two-Round Gradient Computation

For PGD, the gradient computation is split into two distinct rounds of MV multiplication:

  • Round 1: Workers assist in computing $Xw$.
  • Round 2: Workers assist in computing $X^T f'(Xw)$.

3. Real-Error Correction

When workers return their results, the master treats any discrepancies as a "sparse noise" vector. Drawing from compressive sensing and sparse reconstruction theory—specifically using Vandermonde matrices and Reed-Solomon-style decoding over real numbers—the master identifies the corrupt workers.

Unlike standard compressed sensing where any entry can be noisy, Byzantine distributed computing exhibits a "block" error structure: if a worker is corrupt, their entire output vector is suspect. The authors leverage this structure to simplify decoding, reducing it to a sparse recovery problem on a vector of size $m$ (the number of workers), which is significantly smaller than the data dimensions.

Resilient Coordinate Descent (CD)

Coordinate Descent is often preferred for high-dimensional problems where full gradient descent is too costly, as workers update only a few coordinates of the model in parallel. This paper provides the first Byzantine-resilient version of CD. The authors designed a structured, sparse encoding matrix that ensures updates in the "encoded" parameter space map correctly and efficiently back to the original parameter space, maintaining the efficiency of the CD approach while adding robust protection.

Key Results and Performance

The proposed encoding scheme demonstrates several critical advantages:

  • Optimal Resilience: The system can tolerate up to $t < m/2$ corruptions, the theoretical limit for any such distributed system.
  • Constant Overhead: When corruptions are limited to $t \le m/3$, the overhead for storage, communication, and computation is a small constant factor (roughly $2\times$ to $3\times$) compared to a non-resilient system.
  • Linear Scaling: Decoding at the master node scales linearly with the data dimensions $O((n+d)m)$. This is significantly faster than traditional real-error correction methods that often scale quadratically.
  • Empirical Efficiency: In tests involving $22,000$ features, the resilient CD framework was significantly faster than full Gradient Descent while maintaining perfect resilience against up to 6 corrupt workers out of 15.

Conclusion

This work provides a robust, deterministic framework for securing distributed optimization against malicious actors. By transforming the problem into one of resilient Matrix-Vector multiplication and utilizing sparse encoding, the authors achieve optimal resilience with minimal overhead. While currently optimized for Generalized Linear Models (GLMs), future work may extend these encoding techniques to non-linear models, such as deep neural networks, or explore asynchronous versions to further mitigate the impact of slow or honest-but-lagging workers.

Summary updated

Abstract

We study distributed optimization in the presence of Byzantine adversaries, where both data and computation are distributed among $m$ worker machines, $t$ of which may be corrupt. The compromised nodes may collaboratively and arbitrarily deviate from their pre-specified programs, and a designated (master) node iteratively computes the model/parameter vector for generalized linear models. In this work, we primarily focus on two iterative algorithms: Proximal Gradient Descent (PGD) and Coordinate Descent (CD). Gradient descent (GD) is a special case of these algorithms. PGD is typically used in the data-parallel setting, where data is partitioned across different samples, whereas, CD is used in the model-parallelism setting, where data is partitioned across the parameter space. In this paper, we propose a method based on data encoding and error correction over real numbers to combat adversarial attacks. We can tolerate up to $t\leq \lfloor\frac{m-1}{2}\rfloor$ corrupt worker nodes, which is information-theoretically optimal. We give deterministic guarantees, and our method does not assume any probability distribution on the data. We develop a {\em sparse} encoding scheme which enables computationally efficient data encoding and decoding. We demonstrate a trade-off between the corruption threshold and the resource requirements (storage, computational, and communication complexity). As an example, for $t\leq\frac{m}{3}$, our scheme incurs only a {\em constant} overhead on these resources, over that required by the plain distributed PGD/CD algorithms which provide no adversarial protection. To the best of our knowledge, ours is the first paper that makes CD secure against adversarial attacks. Our encoding scheme extends efficiently to the data streaming model and for stochastic gradient descent (SGD). We also give experimental results to show the efficacy of our proposed schemes.
BibTeX
@article{data2019data,
  author = {Deepesh Data and Linqi Song and Suhas N. Diggavi},
  title = {{Data Encoding for Byzantine-Resilient Distributed Optimization}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  doi = {10.1109/tit.2020.3035868},
}
Figure