TY - GEN
T1 - Optimal distributed online prediction
AU - Dekel, Ofer
AU - Gilad-Bachrach, Ran
AU - Shamir, Ohad
AU - Xiao, Lin
PY - 2011
Y1 - 2011
N2 - Online prediction methods are typically studied as serial algorithms running on a single processor. In this paper, we present the distributed mini-batch (DMB) framework, a method of converting a serial gradient-based online algorithm into a distributed algorithm, and prove an asymptotically optimal regret bound for smooth convex loss functions and stochastic examples. Our analysis explicitly takes into account communication latencies between computing nodes in a network. We also present robust variants, which are resilient to failures and node heterogeneity in an asynchronous distributed environment. Our method can also be used for distributed stochastic optimization, attaining an asymptotically linear speedup. Finally, we empirically demonstrate the merits of our approach on large-scale online prediction problems.
AB - Online prediction methods are typically studied as serial algorithms running on a single processor. In this paper, we present the distributed mini-batch (DMB) framework, a method of converting a serial gradient-based online algorithm into a distributed algorithm, and prove an asymptotically optimal regret bound for smooth convex loss functions and stochastic examples. Our analysis explicitly takes into account communication latencies between computing nodes in a network. We also present robust variants, which are resilient to failures and node heterogeneity in an asynchronous distributed environment. Our method can also be used for distributed stochastic optimization, attaining an asymptotically linear speedup. Finally, we empirically demonstrate the merits of our approach on large-scale online prediction problems.
UR - http://www.scopus.com/inward/record.url?scp=80053446822&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:80053446822
SN - 9781450306195
T3 - Proceedings of the 28th International Conference on Machine Learning, ICML 2011
SP - 713
EP - 720
BT - Proceedings of the 28th International Conference on Machine Learning, ICML 2011
Y2 - 28 June 2011 through 2 July 2011
ER -