Data Encoding for Byzantine-Resilient Distributed Optimization

Deepesh Data, Linqi Song, Suhas Diggavi

In the world of large-scale machine learning, we often distribute data and computation across dozens or hundreds of worker machines. But what happens when some of those machines go rogue? Whether due to hardware failure, software bugs, or active malicious intent, "Byzantine" workers can send corrupted updates to a master node, potentially derailing the entire training process.

This paper, "Data Encoding for Byzantine-Resilient Distributed Optimization," presents a robust framework to protect distributed optimization—specifically Proximal Gradient Descent (PGD) and Coordinate Descent (CD)—against such adversarial attacks using clever data encoding and real-number error correction.

TL;DR

The authors propose a sparse data encoding scheme that makes distributed optimization information-theoretically optimal in its fault tolerance, handling up to $t < m/2$ corrupt worker nodes. It is the first work to provide a Byzantine-resilient solution for Coordinate Descent (model-parallelism) and offers a constant-overhead trade-off for practical corruption levels.

What Problem Does This Paper Address?

Distributed optimization typically follows a master-worker architecture. The master node maintains the model parameters and asks workers to compute gradients on their local data. In a Byzantine setting, an adversary can compromise a subset of these workers. Unlike simple "stragglers" (nodes that are just slow), Byzantine nodes can collaborate and send perfectly crafted, incorrect values to the master to steer the model toward a sub-optimal solution or prevent convergence entirely.

While previous research has tackled Byzantine-resilient Gradient Descent (GD), most solutions rely on statistical assumptions about the data or specific attack patterns. Furthermore, Coordinate Descent (CD)—a popular choice for high-dimensional problems like Lasso or SVMs where data is partitioned by features (model-parallelism)—had remained largely unprotected. The challenge with CD is that updates are coordinate-specific, making it harder to apply standard redundancy techniques without massive overhead.

Methods

The core of the authors' solution is a two-round approach based on Matrix-Vector (MV) multiplication and real-error correction.

  1. Sparse Data Encoding: Before training begins, the data matrix $X$ is encoded using a specially designed sparse matrix $S$. This encoded data is distributed among $m$ workers. The sparsity is crucial; it ensures that the storage and computational overhead remain low.
  2. Two-Round Gradient Computation: For PGD, the master node computes the gradient in two rounds of MV multiplication. In each round, workers return their results. The master treats the received (and potentially corrupted) vectors as a "sparse reconstruction" problem—a concept borrowed from compressed sensing.
  3. Error Locating: The master uses a "parity-check" style matrix $F$ to identify which workers are lying. By taking a random linear combination of the received error vectors, the master can identify the set of corrupt indices with probability one.
  4. Coordinate Descent (CD) Adaptation: This is the paper's standout contribution. The authors designed an encoding matrix with a specific regular structure of non-zero entries. This structure allows the master to update only a subset of coordinates (as required by CD) while still being able to decode the results and maintain an "invariant" where the encoded parameters map perfectly back to the original parameter space.
  5. Extensions: The scheme is extended to Stochastic Gradient Descent (SGD) using a one-round approach (recovering the data point itself) and to streaming data, where new samples can be encoded and added to the workers on the fly with minimal cost.

Datasets

The authors evaluated their methods using synthetic datasets for linear regression tasks:

  • Moderate Scale: $n = 10,000$ samples, $d = 250$ features, $m = 15$ workers.
  • Large Scale: $n = 20,000$ samples, $d = 22,000$ features, $m = 15$ workers.

They chose synthetic data because their method provides exact recovery of gradients/updates. Therefore, the convergence behavior is identical to a standard non-adversarial setup, and the primary metrics of interest are computational efficiency and time-per-iteration under attack.

Key Insights and Ideas

  • Optimal Fault Tolerance: The method hits the information-theoretic limit, tolerating up to $t \leq \lfloor\frac{m-1}{2}\rfloor$ corruptions. If more than half the workers are lying, no deterministic algorithm can guarantee the correct result.
  • The Power of Sparsity: By using a sparse encoding matrix, the authors avoid the quadratic decoding complexity of off-the-shelf "real-error correction" codes. For a corruption threshold of $t \leq m/3$, the resource overhead (storage, communication, and computation) is just a constant factor.
  • Bridging MV and CD: The "aha moment" is the realization that Coordinate Descent can be viewed through the lens of MV multiplication if the encoding matrix is structured correctly. This allows the master to decode updates even when only a few coordinates are changed in parallel across workers.

Key Results

  • Computational Efficiency: In the large-scale experiment ($d=22,000$), running Coordinate Descent on 10% of the coordinates (CD 0.1d) resulted in a 95% reduction in worker computation time per iteration compared to full Gradient Descent, even under Byzantine attack.
  • Master Node Performance: The decoding time at the master node scales linearly with the number of workers and the data dimensions, making it orders of magnitude faster than the worker computation.
  • Deterministic Guarantees: Unlike many robust aggregation methods (like geometric median), this approach recovers the exact gradient, meaning there is no "approximation error" introduced by the defense mechanism.

Limitations and Future Work

  • Generalized Linear Models: The current framework is specifically tailored for GLMs (like linear/logistic regression, Lasso, SVMs) where the objective function depends on the data through inner products. Extending this to deep neural networks with non-linear layers remains a challenge.
  • Master Node as a Central Point: While the master's work is efficient, it remains a central point of failure. The authors mention that decentralized architectures (no hierarchy) have been explored by others, and adapting these encoding schemes to a fully decentralized setting could be a promising future direction.
  • Pre-processing Cost: While the encoding is a one-time cost, it is still $O(nd \cdot t)$. For extremely massive datasets, this initial setup time might be significant, though the authors' streaming extension helps mitigate this for growing datasets.

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 Diggavi},
  title = {{Data Encoding for Byzantine-Resilient Distributed Optimization}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  doi = {10.1109/tit.2020.3035868},
}
Figure