Data Encoding for Byzantine-Resilient Distributed Optimization

By Deepesh Data, Linqi Song, Suhas N. Diggavi. 2019

40 citations recorded by the source corpus.

We study distributed optimization in the presence of Byzantine adversaries, where both data and computation are distributed among <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> worker machines, <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> 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 <italic>generalized linear models</italic>. In this work, we primarily focus on two iterative algorithms: <italic>Proximal Gradient Descent</italic> (PGD) and <italic>Coordinate Descent</italic> (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. At the core of our solutions to both these algorithms is a method for Byzantine-resilient matrix-vector (MV) multiplication; and for that, we propose a method based on data encoding and error correction over real numbers to combat adversarial attacks. We can tolerate up to <inline-formula> <tex-math notation="LaTeX">$t\leq \lfloor \frac {m-1}{2}\rfloor $ </tex-math></inline-formula> 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 <italic>sparse</italic> 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 <inline-formula> <tex-math notation="LaTeX">$t\leq \frac {m}{3}$ </tex-math></inline-formula>, our scheme incurs only a <italic>constant</italic> 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 connects MV multiplication with CD and designs a specific encoding matrix for MV multiplication whose structure we can leverage to make CD secure against adversarial attacks. Our encoding scheme extends <italic>efficiently</italic> to <italic>(i)</italic> the data streaming model, in which data samples come in an online fashion and are encoded as they arrive, and <italic>(ii)</italic> making <italic>stochastic gradient descent</italic> (SGD) Byzantine-resilient. In the end, we give experimental results to show the efficacy of our proposed schemes.

Subfields: Artificial Intelligence, Statistics and Probability, Optimization & Training, ML Systems & Hardware

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Enhancing Privacy via Hierarchical Federated Learning (2020, methodology): “To detect and mitigate such attacks, several methods can be considered, such as anomaly detectors [21], median-based aggregation [32], trimmed mean [32], and redundancy-based encoding [6].”
Learning from History for Byzantine Robust Optimization (2020, background): “There have also been attempts to use recent breakthroughs in robust high-dimensional aggregators (Diakonikolas et al., 2018; Su & Xu, 2018; El-Mhamdi & Guerraoui, 2019; Data et al., 2019; Data & Diggavi, 2020).”
Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data (2020, unknown): “, 2018; 2019) or by explicitly introducing redundancy in the system via coding-theoretic solutions (Chen et al., 2018; Data et al., 2021; Rajput et al., 2019); however, these approaches fall short of in the FL setting.”
Data Encoding Methods for Byzantine-Resilient Distributed Optimization (2019, methodology): “Due to space constraints, we give omitted details including an extension of our encoding procedure to the data streaming model and details of our numerical experiments in the full version [10].”