Slow Learners are Fast
arXiv (Cornell University)Published 3 November 2009Open access
John Langford, Alexander J. Smola, Martin Zinkevich
Citations202
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper proves that online learning with delayed updates converges well, thereby facilitating parallel online learning.
Abstract
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.
Keywords
Computer ScienceDecision Sciences
Dryad
2,460 Citations2007Michael Isard, Mihai Budiu +3 more
The Dryad execution engine handles all the difficult problems of creating a large distributed, concurrent application: scheduling the use of computers and their CPUs, recovering from communication or computer failures, and transporting data between vertices.
The MIT Press eBooksMap-Reduce for Machine Learning on Multicore
1,253 Citations2007Cheng-Tao Chu, Sang Kyun Kim +5 more
This work shows that algorithms that fit the Statistical Query model can be written in a certain "summation form," which allows them to be easily parallelized on multicore computers and shows basically linear speedup with an increasing number of processors.
Feature hashing for large scale multitask learning
937 Citations2009Kilian Q. Weinberger, Anirban Dasgupta +3 more
This paper provides exponential tail bounds for feature hashing and shows that the interaction between random subspaces is negligible with high probability, and demonstrates the feasibility of this approach with experimental results for a new use case --- multitask learning.
Machine LearningLogarithmic regret algorithms for online convex optimization
874 Citations2007Elad Hazan, Amit Agarwal +1 more
Several algorithms achieving logarithmic regret are proposed, which besides being more general are also much more efficient to implement, and give rise to an efficient algorithm based on the Newton method for optimization, a new tool in the field.
Maximum margin planning
630 Citations2006Nathan Ratliff, J. Andrew Bagnell +1 more
This work learns mappings from features to cost so an optimal policy in an MDP with these cost mimics the expert's behavior, and demonstrates a simple, provably efficient approach to structured maximum margin learning, based on the subgradient method, that leverages existing fast algorithms for inference.
ScienceScreen Savers of the World Unite!
573 Citations2000Michael R. Shirts, Vijay S. Pande
Unused CPU time on desktop computers could be put to good use, if distributed computing succeeds in capturing people's imagination and raising biological and other scientific computation to fundamentally new predictive levels.
ANU Open Research (Australian National University)COFI RANK - Maximum margin matrix factorization for collaborative ranking
360 Citations2007Markus Weimer, Alexandros Karatzoglou +2 more
A method which uses Maximum Margin Matrix Factorization and optimizes ranking instead of rating is presented and gives very good ranking scores and scales well on collaborative filtering tasks.
Large Scale Online Learning
337 Citations2003Léon Bottou, Y. Le Cun
It is argued that suitably designed online learning algorithms asymptotically outperform any batch learning algorithm in situations where training data is abundant and computing resources are comparatively scarce.
Journal of Machine Learning ResearchBundle Methods for Regularized Risk Minimization
235 Citations2010Choon Hui Teo, S.V.N. Vishwanthan +2 more
The theory and implementation of a scalable and modular convex solver which solves all these estimation problems, which can be parallelized on a cluster of workstations, allows for data-locality, and can deal with regularizers such as L1 and L2 penalties is described.
Neural Information Processing SystemsAdaptive Online Gradient Descent
188 Citations2007Elad Hazan, Alexander Rakhlin +1 more
An algorithm is provided, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates between √T and log T and shows strong optimality of the algorithm.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)(Online) Subgradient Methods for Structured Prediction
140 Citations2018Nathan Ratliff, J. Andrew Bagnell +1 more
This work proposes using simple subgradient-based techniques for optimizing a regularized risk formulation of structured learning problems in both online and batch settings, and analyzes the theoretical convergence, generalization, and robustness properties of the resulting techniques.
Proximal regularization for online and batch learning
46 Citations2009Joshua Shulman, Quoc V. Le +1 more
P proximal regularization is employed, in which the original learning problem is solved via a sequence of modified optimization tasks whose objectives are chosen to have greater curvature than the original problem.