Optimal Distributed Online Prediction using Mini-Batches

Abstract

Online prediction methods are typically presented as serial algorithms running on a single processor. However, in the age of web-scale prediction problems, it is increasingly common to encounter situations where a single processor cannot keep up with the high rate at which inputs arrive. In this work, we present the \emph{distributed mini-batch} algorithm, a method of converting many serial gradient-based online prediction algorithms into distributed algorithms. We prove a regret bound for this method that is asymptotically optimal for smooth convex loss functions and stochastic inputs. Moreover, our analysis explicitly takes into account communication latencies between nodes in the distributed environment. We show how our method can be used to solve the closely-related distributed stochastic optimization problem, achieving an asymptotically linear speed-up over multiple processors. Finally, we demonstrate the merits of our approach on a web-scale online prediction problem.

Final version of paper to appear in Journal of Machine Learning Research (JMLR)

References in corpus (3)

• Slow Learners are Fast
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• A Stochastic View of Optimal Regret through Minimax Duality

Cited by in corpus (167)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Federated Optimization in Heterogeneous Networks
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• A Reliable Effective Terascale Linear Learning System
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Stochastic Variance Reduction for Nonconvex Optimization
• Don't Use Large Mini-Batches, Use Local SGD
• Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis
• Local SGD Converges Fast and Communicates Little
• A Field Guide to Federated Optimization
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Online Learning: A Comprehensive Survey
• Communication Complexity of Distributed Convex Learning and Optimization
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Kernel Least Mean Square with Adaptive Kernel Size
• Distributed Delayed Stochastic Optimization
• Variance Reduced Local SGD with Lower Communication Complexity
• FedSplit: An algorithmic framework for fast federated optimization
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Distributed learning with regularized least squares
• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
• Communication optimization strategies for distributed deep neural network training: A survey
• Federated Learning for Healthcare Informatics
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares
• Better Theory for SGD in the Nonconvex World
• Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
• Monotonic Calibrated Interpolated Look-Up Tables
• Optimality guarantees for distributed statistical estimation
• Straggler-aware Distributed Learning: Communication Computation Latency Trade-off
• Communication-efficient sparse regression: a one-shot approach
• Is Local SGD Better than Minibatch SGD?
• Efficient Distributed Learning with Sparsity
• Asynchronous stochastic convex optimization
• Distributed Exploration in Multi-Armed Bandits
• Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD
• Distributed Mini-Batch SDCA
• Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Decentralized Deep Learning with Arbitrary Communication Compression
• Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server
• Online Learning of Dynamic Parameters in Social Networks
• Consensus Control for Decentralized Deep Learning
• ActiveClean: Interactive Data Cleaning While Learning Convex Loss Models
• Hemingway: Modeling Distributed Optimization Algorithms
• Federated Accelerated Stochastic Gradient Descent
• Gradient Diversity: a Key Ingredient for Scalable Distributed Learning
• Federated Residual Learning
• Asynchronous Online Federated Learning for Edge Devices with Non-IID Data
• Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling
• Communication trade-offs for synchronized distributed SGD with large step size
• Online and Stochastic Gradient Methods for Non-decomposable Loss Functions
• Differentially Private Federated Learning for Resource-Constrained Internet of Things
• Median Selection Subset Aggregation for Parallel Inference
• The Complexity of Making the Gradient Small in Stochastic Convex Optimization
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
• Communication-efficient Distributed Sparse Linear Discriminant Analysis
• Layer-wise Adaptive Gradient Sparsification for Distributed Deep Learning with Convergence Guarantees
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• Orchestrating the Development Lifecycle of Machine Learning-Based IoT Applications: A Taxonomy and Survey
• Exploiting Unlabeled Data in Smart Cities using Federated Learning
• Stochastic Nonconvex Optimization with Large Minibatches
• Federated Optimization of Smooth Loss Functions
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization
• Gradient-only line searches: An Alternative to Probabilistic Line Searches
• Stochastic Optimization from Distributed, Streaming Data in Rate-limited Networks
• Applications of Federated Learning in Smart Cities: Recent Advances, Taxonomy, and Open Challenges
• Communication-Efficient Decentralized Learning with Sparsification and Adaptive Peer Selection
• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Federated Composite Optimization
• MixedGrad: An O(1/T) Convergence Rate Algorithm for Stochastic Smooth Optimization
• Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent
• Byzantine Resilient Non-Convex SVRG with Distributed Batch Gradient Computations
• Accelerated Large Batch Optimization of BERT Pretraining in 54 minutes
• Federated Learning for Commercial Image Sources
• O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
• Playing to distraction: towards a robust training of CNN classifiers through visual explanation techniques
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• Revisiting EXTRA for Smooth Distributed Optimization
• Stochastic Gradient Descent for Semilinear Elliptic Equations with Uncertainties
• A Distributed Hierarchical SGD Algorithm with Sparse Global Reduction
• RingFed: Reducing Communication Costs in Federated Learning on Non-IID Data
• Hierarchical Weight Averaging for Deep Neural Networks
• Advances in Asynchronous Parallel and Distributed Optimization
• On Data Dependence in Distributed Stochastic Optimization
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize
• Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data
• A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning
• Async-RED: A Provably Convergent Asynchronous Block Parallel Stochastic Method using Deep Denoising Priors
• Efficient Communications in Training Large Scale Neural Networks
• (Bandit) Convex Optimization with Biased Noisy Gradient Oracles
• Differentially Private Distributed Computation via Public-Private Communication Networks
• Stochastic Distributed Optimization for Machine Learning from Decentralized Features
• Para-active learning
• Optimal Mini-Batch Size Selection for Fast Gradient Descent
• Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets
• A Stochastic Newton Algorithm for Distributed Convex Optimization
• Speculative Approximations for Terascale Analytics
• D-SPIDER-SFO: A Decentralized Optimization Algorithm with Faster Convergence Rate for Nonconvex Problems
• Distributed Machine Learning for Wireless Communication Networks: Techniques, Architectures, and Applications
• Data-Distributed Weighted Majority and Online Mirror Descent
• Opportunistic Emulation of Computationally Expensive Simulations via Deep Learning
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• Stochastic Composite Least-Squares Regression with convergence rate O(1/n)
• Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
• Anytime Stochastic Gradient Descent: A Time to Hear from all the Workers
• Efficient Projection-Free Online Methods with Stochastic Recursive Gradient
• Multi-Level Composite Stochastic Optimization via Nested Variance Reduction
• Effective Parallelisation for Machine Learning
• Model Aggregation via Good-Enough Model Spaces
• A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate
• The Minimax Complexity of Distributed Optimization
• Adaptive Periodic Averaging: A Practical Approach to Reducing Communication in Distributed Learning
• Decentralized Differentially Private Without-Replacement Stochastic Gradient Descent
• Bootstrap Model Aggregation for Distributed Statistical Learning
• Accelerated Sparsified SGD with Error Feedback
• The Scalability for Parallel Machine Learning Training Algorithm: Dataset Matters
• Mass-spring-damper Networks for Distributed Optimization in Non-Euclidean Spaces
• Robust Estimation of Covariance Matrices: Adversarial Contamination and Beyond
• Data Analytics for Fog Computing by Distributed Online Learning with Asynchronous Update
• On the Convergence of Quantized Parallel Restarted SGD for Central Server Free Distributed Training
• Asynchronous Distributed Optimization with Stochastic Delays
• Probabilistic Federated Learning of Neural Networks Incorporated with Global Posterior Information
• Blockchain Assisted Federated Learning over Wireless Channels: Dynamic Resource Allocation and Client Scheduling
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression
• Estimating Fund-Raising Performance for Start-up Projects from a Market Graph Perspective
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• Distributed Sparse SGD with Majority Voting
• DaSGD: Squeezing SGD Parallelization Performance in Distributed Training Using Delayed Averaging
• Distributed stochastic optimization for deep learning (thesis)
• Graph Balancing for Distributed Subgradient Methods over Directed Graphs
• Scalable Approximate Inference and Some Applications
• On the Convergence of Memory-Based Distributed SGD
• Near Optimal Adaptive Shortest Path Routing with Stochastic Links States under Adversarial Attack
• Machine Learning on Volatile Instances
• Meta-Regularization: An Approach to Adaptive Choice of the Learning Rate in Gradient Descent
• Accelerating Distributed Online Meta-Learning via Multi-Agent Collaboration under Limited Communication
• Adaptive Communication Bounds for Distributed Online Learning
• Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?
• Communication-Efficient Distributed Online Learning with Kernels
• The Gradient Convergence Bound of Federated Multi-Agent Reinforcement Learning with Efficient Communication
• Deep learning-based quality filtering of mechanically exfoliated 2D crystals
• Random gradient extrapolation for distributed and stochastic optimization
• Online Optimization for Large-Scale Max-Norm Regularization
• Online Estimation for Functional Data
• Trade-offs of Local SGD at Scale: An Empirical Study
• Data Dependent Convergence for Distributed Stochastic Optimization
• Consensus-Based Modelling using Distributed Feature Construction
• Coordinated Online Learning With Applications to Learning User Preferences
• Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays
• Escaping Saddle Points with Compressed SGD
• Stochastic dual averaging methods using variance reduction techniques for regularized empirical risk minimization problems
• Exploring Effects of Random Walk Based Minibatch Selection Policy on Knowledge Graph Completion
• Training few-shot classification via the perspective of minibatch and pretraining
• A polynomial expansion line search for large-scale unconstrained minimization of smooth L2-regularized loss functions, with implementation in Apache Spark