Slow Learners are Fast

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.

Extended version of conference paper - NIPS 2009

Cited by in corpus (67)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Optimal Distributed Online Prediction using Mini-Batches
• Asynchronous Federated Optimization
• A Reliable Effective Terascale Linear Learning System
• Federated Collaborative Filtering for Privacy-Preserving Personalized Recommendation System
• Distributed Delayed Stochastic Optimization
• Deep learning with Elastic Averaging SGD
• Delay and Cooperation in Nonstochastic Bandits
• CYCLADES: Conflict-free Asynchronous Machine Learning
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• Online Learning under Delayed Feedback
• Programming with Personalized PageRank: A Locally Groundable First-Order Probabilistic Logic
• CHAOS: A Parallelization Scheme for Training Convolutional Neural Networks on Intel Xeon Phi
• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Learning Scalable Deep Kernels with Recurrent Structure
• Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates
• Federated Residual Learning
• Communication trade-offs for synchronized distributed SGD with large step size
• Efficient Parallel Translating Embedding For Knowledge Graphs
• AdaDelay: Delay Adaptive Distributed Stochastic Convex Optimization
• Distributed linear regression by averaging
• ICE: Enabling Non-Experts to Build Models Interactively for Large-Scale Lopsided Problems
• Primitives for Dynamic Big Model Parallelism
• Parallel Markov Chain Monte Carlo for Non-Gaussian Posterior Distributions
• parallelMCMCcombine: An R Package for Bayesian Methods for Big Data and Analytics
• Bandit Online Learning with Unknown Delays
• Delay-Tolerant Constrained OCO with Application to Network Resource Allocation
• GradiVeQ: Vector Quantization for Bandwidth-Efficient Gradient Aggregation in Distributed CNN Training
• A Data and Model-Parallel, Distributed and Scalable Framework for Training of Deep Networks in Apache Spark
• Amortized Analysis on Asynchronous Gradient Descent
• Petuum: A New Platform for Distributed Machine Learning on Big Data
• Structure Regularization for Structured Prediction: Theories and Experiments
• Distributed Stochastic Optimization of the Regularized Risk
• Variance Reduction for Distributed Stochastic Gradient Descent
• Probabilistic Synchronous Parallel
• Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
• A Discussion on Parallelization Schemes for Stochastic Vector Quantization Algorithms
• DS-MLR: Exploiting Double Separability for Scaling up Distributed Multinomial Logistic Regression
• Para-active learning
• Decoupled Asynchronous Proximal Stochastic Gradient Descent with Variance Reduction
• Online Learning with Local Permutations and Delayed Feedback
• Speculative Approximations for Terascale Analytics
• Distributed Autonomous Online Learning: Regrets and Intrinsic Privacy-Preserving Properties
• Parallel Stochastic Gradient Descent with Sound Combiners
• Stochastic Bandits with Delayed Composite Anonymous Feedback
• Data-Distributed Weighted Majority and Online Mirror Descent
• Accelerated Parallel Optimization Methods for Large Scale Machine Learning
• Parallel Coordinate Descent Newton Method for Efficient ${\ell }_1$-Regularized Minimization
• Differential Equations for Modeling Asynchronous Algorithms
• Convergence of distributed asynchronous learning vector quantization algorithms
• The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
• Asynchronous Distributed Optimization with Redundancy in Cost Functions
• A Survey on Large-scale Machine Learning
• The Scalability for Parallel Machine Learning Training Algorithm: Dataset Matters
• Online Strongly Convex Optimization with Unknown Delays
• Adversarial Delays in Online Strongly-Convex Optimization
• Distributed stochastic optimization for deep learning (thesis)
• Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learning
• Long-Term Online Smoothing Prediction Using Expert Advice
• Near Data Acceleration with Concurrent Host Access
• Fully Asynchronous Stochastic Coordinate Descent: A Tight Lower Bound on the Parallelism Achieving Linear Speedup
• On the Performance and Convergence of Distributed Stream Processing via Approximate Fault Tolerance
• Parallel Markov Chain Monte Carlo for Bayesian Hierarchical Models with Big Data, in Two Stages
• Asymptotic properties of parallel Bayesian kernel density estimators
• Partitioning Large Scale Deep Belief Networks Using Dropout
• Consensus-Based Modelling using Distributed Feature Construction
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory