Impact of Redundancy on Resilience in Distributed Optimization and Learning
Preprint
Abstract
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; \epsilon)$-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 $\epsilon$ represents a better approximation. We also introduce a measure named $(f, r; \epsilon)$-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; \mathcal{O}(\epsilon))$-resilience can indeed be achieved in practice, given that the local cost functions are sufficiently redundant.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Advances in Asynchronous Parallel and Distributed OptimizationProceedings of the IEEE, 2020
- A Survey of the Usages of Deep Learning for Natural Language ProcessingIEEE Transactions on Neural Networks and Learning Systems, 2020
- Speeding Up Distributed Machine Learning Using CodesIEEE Transactions on Information Theory, 2017
- An Asynchronous Mini-Batch Algorithm for Regularized Stochastic OptimizationIEEE Transactions on Automatic Control, 2016
- When Do Redundant Requests Reduce Latency?IEEE Transactions on Communications, 2015
- Newton-Raphson Consensus for Distributed Convex OptimizationIEEE Transactions on Automatic Control, 2015
- EXTRA: An Exact First-Order Algorithm for Decentralized Consensus OptimizationSIAM Journal on Optimization, 2015
- Parallel distributed computing using PythonAdvances in Water Resources, 2011
- Distributed Subgradient Methods for Multi-Agent OptimizationIEEE Transactions on Automatic Control, 2009
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998