Robust Distributed Online Prediction
By Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, Lin Xiao. 2010
5 citations recorded by the source corpus.
The standard model of online prediction deals with serial processing of inputs by a single processor. However, in large-scale online prediction problems, where inputs arrive at a high rate, an increasingly common necessity is to distribute the computation across several processors. A non-trivial challenge is to design distributed algorithms for online prediction, which maintain good regret guarantees. In \cite{DMB}, we presented the DMB algorithm, which is a generic framework to convert any serial gradient-based online prediction algorithm into a distributed algorithm. Moreover, its regret guarantee is asymptotically optimal for smooth convex loss functions and stochastic inputs. On the flip side, it is fragile to many types of failures that are common in distributed environments. In this companion paper, we present variants of the DMB algorithm, which are resilient to many types of network failures, and tolerant to varying performance of the computing nodes.
Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research
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
- Ji Liu
- Tong Zhang
- Ohad Shamir
- Xiangru Lian
- Sebastian U. Stich
- John C. Duchi
- Peter Richtárik
- Martin Jaggi
In Computational Mechanics
- Ji Liu
- Xiangru Lian
- Sebastian U. Stich
- Peter Richtárik
- Lin Xiao
- Ohad Shamir
- Tong Zhang
- Jakub Konecný
In Management Science and Operations Research
- John C. Duchi
- Ohad Shamir
- Alekh Agarwal
- Lin Xiao
- Ofer Dekel
- Ji Liu
- Ran Gilad-Bachrach
- Francis R. Bach
Citations in the corpus
- Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, background): “In their follow up work [Dekel et al., 2010], they showed that a variant of their approach is asymptotically robust to asynchrony, as long as most processors remain synchronized for most of time.”
- Distributed delayed stochastic optimization (2011, background): “The rate holds so long as most processors remain synchronized for most of the time [6].”
- Optimal Distributed Online Prediction (2011, methodology): “Due to limitation of space, proofs can be found in Dekel et al. (2010a) and Dekel et al. (2010b).”