Data Encoding for Byzantine-Resilient Distributed Optimization Article Swipe

MAKE IMPACT

Deepesh Data , Linqi Song , Suhas Diggavi · YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.1109/tit.2020.3035868

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.

Type

preprint

Language

en

Landing Page

https://doi.org/10.1109/tit.2020.3035868

OA Status

green

Cited By

6

References

86

Related Works

20

OpenAlex ID

https://openalex.org/W2954114036

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W2954114036

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.1109/tit.2020.3035868

Digital Object Identifier

Title

Data Encoding for Byzantine-Resilient Distributed Optimization

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2020

Year of publication

Publication date

2020-11-04

Full publication date if available

Authors

Deepesh Data, Linqi Song, Suhas Diggavi

List of authors in order

Landing page

https://doi.org/10.1109/tit.2020.3035868

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1907.02664

Direct OA link when available

Concepts

Overhead (engineering), Computer science, Encoding (memory), Node (physics), Decoding methods, Gradient descent, Algorithm, Scheme (mathematics), Theoretical computer science, Mathematics, Artificial neural network, Machine learning, Engineering, Mathematical analysis, Artificial intelligence, Structural engineering, Operating system

Top concepts (fields/topics) attached by OpenAlex

Cited by

6

Total citation count in OpenAlex

Citations by year (recent)

2023: 1, 2021: 3, 2020: 1, 2019: 1

Per-year citation counts (last 5 years)

References (count)

86

Number of works referenced by this work

Related works (count)

20

Other works algorithmically related by OpenAlex

Full payload