2009

Slow Learners are Fast

Langford, John, Smola, Alexander, Zinkevich, Martin

Understand

Online learning algorithms have impressive convergence properties when it comes to risk minimization and convex games on very large problems.

However, they are inherently sequential in their design which prevents them from taking advantage of modern multi-core architectures.
In this paper we prove that online learning with delayed updates converges well, thereby facilitating parallel online learning.

Robust Statistics
P. J. Huber · 1981
Earlier work this paper cites.
Network information criterion — determining the number of hidden units for artificial neural network models
N. Murata, S. Yoshizawa, and S. Amari · 1994
Earlier work this paper cites.
Confidence level solutions for stochastic programming
Y. Nesterov and J.-P. Vial · 2000
Earlier work this paper cites.
Screen savers of the world unite!
M. Shirts and V.S. Pande · 2000
Earlier work this paper cites.
Online convex programming and generalised infinitesimal gradient ascent
M. Zinkevich · 2003
Earlier work this paper cites.
Large scale online learning
Léon Bottou and Yann LeCun · 2004
Earlier work this paper cites.
Online learning with delayed label feedback
C. Mesterharm · 2005
Earlier work this paper cites.
Maximum margin planning
N. Ratliff, J. Bagnell, and M. Zinkevich · 2006
Earlier work this paper cites.

Accelerated training conditional random fields with stochastic gradient methods
S. V. N. Vishwanathan, Nicol N. Schraudolph, Mark Schmidt, and Kevin Murphy · 2006
Cited alongside, same era.
The tradeoffs of large scale learning
L. Bottou and O. Bousquet · 2007
Cited alongside, same era.
Map-reduce for machine learning on multicore
C.T. Chu, S.K. Kim, Y. A. Lin, Y. Y. Yu, G. Bradski, A. Ng, and K. Olukotun · 2007
Cited alongside, same era.
TREC 2007 spam track overview
G. Cormack · 2007
Cited alongside, same era.
Parallel stochastic gradient descent, 2007
O. Delalleau and Y. Bengio · 2007
Cited alongside, same era.
Logarithmic regret algorithms for online convex optimization
Elad Hazan, Amit Agarwal, and Satyen Kale · 2007
Cited alongside, same era.
Dryad: distributed data-parallel programs from sequential building blocks
M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly · 2007
Cited alongside, same era.
Vowpal wabbit online learning project, 2007
J. Langford, L. Li, and A. Strehl · 2007
Cited alongside, same era.

(online) subgradient methods for structured prediction
N. Ratliff, J. Bagnell, and M. Zinkevich · 2007
Later among the works it cites.
Logarithmic regret algorithms for strongly convex repeated games
S. Shalev-Shwartz and Y. Singer · 2007
Later among the works it cites.
Pegasos: Primal estimated sub-gradient solver for SVM
Shai Shalev-Shwartz, Yoram Singer, and Nathan Srebro · 2007
Later among the works it cites.
Adaptive online gradient descent
Peter L. Bartlett, Elad Hazan, and Alexander Rakhlin · 2008
Later among the works it cites.
Cofi rank - maximum margin matrix factorization for collaborative ranking
M. Weimer, A. Karatzoglou, Q. Le, and A. Smola · 2008
Later among the works it cites.
Proximal regularization for online and batch learning
C.B. Do, Q.V. Le, and C.-S. Foo · 2009
Closest in time.
Bundle methods for regularized risk minimization
Choon Hui Teo, S. V. N. Vishwanthan, Alex J. Smola, and Quoc V. Le · 2009
Closest in time.
Feature hashing for large scale multitask learning
K. Weinberger, A. Dasgupta, J. Attenberg, J. Langford, and A.J. Smola · 2009
Closest in time.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…

Reading the bibliography…