# Impact of Redundancy on Resilience in Distributed Optimization and Learning

arXiv: https://arxiv.org/abs/2211.08622 · HTML: https://mlsanity.com/paper/2211.08622/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 59 references that are in the map.
- First posted on arXiv 16 Nov 2022.

## Builds on (most cited first, 27 of 27)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [DRACO: Byzantine-resilient Distributed Training via Redundant Gradients](https://mlsanity.com/paper/1803.09877/) (2018)
- [Advances in Asynchronous Parallel and Distributed Optimization](https://mlsanity.com/paper/2006.13838/) (2020)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [Approximate Byzantine Fault-Tolerance in Distributed Optimization](https://mlsanity.com/paper/2101.09337/) (2021)
- [Straggler Mitigation in Distributed Optimization Through Data Encoding](https://mlsanity.com/paper/1711.04969/) (2017)
- [Optimal Black-Box Reductions Between Optimization Objectives](https://mlsanity.com/paper/1603.05642/) (2016)
- [Improving Distributed Gradient Descent Using Reed-Solomon Codes](https://mlsanity.com/paper/1706.05436/) (2017)
- [Accelerated Mini-Batch Stochastic Dual Coordinate Ascent](https://mlsanity.com/paper/1305.2581/) (2013)
- [Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning](https://mlsanity.com/paper/1803.05397/) (2018)
- [When Do Redundant Requests Reduce Latency ?](https://mlsanity.com/paper/1311.2851/) (2013)
- [More Iterations per Second, Same Quality -- Why Asynchronous Algorithms may Drastically Outperform Traditional Ones](https://mlsanity.com/paper/1708.05136/) (2017)
- [Efficient Straggler Replication in Large-scale Parallel Computing](https://mlsanity.com/paper/1503.03128/) (2015)
- [A Survey on Fault-tolerance in Distributed Optimization and Machine Learning](https://mlsanity.com/paper/2106.08545/) (2021)
- [Byzantine Multi-Agent Optimization: Part I](https://mlsanity.com/paper/1506.04681/) (2015)
- [Newton-Raphson Consensus for Distributed Convex Optimization](https://mlsanity.com/paper/1511.01509/) (2015)
- [Byzantine Fault Tolerant Distributed Linear Regression](https://mlsanity.com/paper/1903.08752/) (2019)
- [Resilience in Collaborative Optimization: Redundant and Independent Cost Functions](https://mlsanity.com/paper/2003.09675/) (2020)

## Abstract (arXiv)

This report considers the problem of resilient distributed optimization and stochastic learning in a server-based architecture. The system comprises a server and multiple agents, where each agent has its own local cost function. The agents collaborate with the server to find a minimum of the aggregate of the local cost functions. In the context of stochastic learning, the local cost of an agent is the loss function computed over the data at that agent. In this report, we consider this problem in a system wherein some of the agents may be Byzantine faulty and some of the agents may be slow (also called stragglers). In this setting, we investigate the conditions under which it is possible to obtain an "approximate" solution to the above problem. In particular, we introduce the notion of (f, r; ε)-resilience to characterize how well the true solution is approximated in the presence of up to f Byzantine faulty agents, and up to r slow agents (or stragglers) -- smaller ε represents a better approximation. We also introduce a measure named (f, r; ε)-redundancy to characterize the redundancy in the cost functions of the agents. Greater redundancy allows for a better approximation when solving the problem of aggregate cost minimization. In this report, we constructively show (both theoretically and empirically) that (f, r; O(ε))-resilience can indeed be achieved in practice, given that the local cost functions are sufficiently redundant.