Optimal distributed online prediction using mini-batches
From MaRDI portal
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.
Recommendations
Cited in
(51)- Consensus-based modeling using distributed feature construction with ILP
- Stochastic variance-reduced prox-linear algorithms for nonconvex composite optimization
- Stochastic gradient descent for semilinear elliptic equations with uncertainties
- Distributed optimization and statistical learning for large-scale penalized expectile regression
- Multi-round smoothed composite quantile regression for distributed data
- Vaidya's method for convex stochastic optimization problems in small dimension
- A modular analysis of adaptive (non-)convex optimization: optimism, composite objectives, variance reduction, and variational bounds
- Accelerating deep neural network training with inconsistent stochastic gradient descent
- On the convergence analysis of asynchronous SGD for solving consistent linear systems
- Communication-efficient sparse composite quantile regression for distributed data
- On the parallelization upper bound for asynchronous stochastic gradients descent in non-convex optimization
- Efficient online and batch learning using forward backward splitting
- Revisiting EXTRA for Smooth Distributed Optimization
- Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication
- Distributed prediction from vertically partitioned data
- Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification
- scientific article; zbMATH DE number 6982986 (Why is no real title available?)
- A sparsity preserving stochastic gradient methods for sparse regression
- Batched Stochastic Gradient Descent with Weighted Sampling
- Utilizing second order information in minibatch stochastic variance reduced proximal iterations
- Distributed learning with regularized least squares
- Optimal rates for multi-pass stochastic gradient methods
- Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
- Linear coupling: an ultimate unification of gradient and mirror descent
- Random gradient extrapolation for distributed and stochastic optimization
- Graph-dependent implicit regularisation for distributed stochastic subgradient descent
- Multilevel composite stochastic optimization via nested variance reduction
- Online learning of a weighted selective naive Bayes classifier with non-convex optimization
- scientific article; zbMATH DE number 7626728 (Why is no real title available?)
- Quantile-based iterative methods for corrupted systems of linear equations
- Complexity Analysis of stochastic gradient methods for PDE-constrained optimal Control Problems with uncertain parameters
- The error-feedback framework: SGD with delayed gradients
- Distributed learning for random vector functional-link networks
- Stochastic distributed learning with gradient quantization and double-variance reduction
- Unifying mirror descent and dual averaging
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs
- scientific article; zbMATH DE number 7740914 (Why is no real title available?)
- Online Estimation for Functional Data
- Scaling up stochastic gradient descent for non-convex optimisation
- scientific article; zbMATH DE number 7800967 (Why is no real title available?)
- Stochastic online optimization for cyber-physical and robotic systems
- Permutation mask: a combined gradient sparsification for federated learning
- Adaptive distributed kernel ridge regression: a feasible distributed learning scheme for data silos
- Optimal Subsampling for Data Streams with Measurement Constrained Categorical Responses
- Minibatch and local SGD: algorithmic stability and linear speedup in generalization
- Efficient projection-free online convex optimization using stochastic gradients
- A tight convergence analysis for stochastic gradient descent with delayed updates
- Stochastic nonconvex optimization with large minibatches
- Sample size selection in optimization methods for machine learning
- Feature-aware regularization for sparse online learning
This page was built for publication: Optimal distributed online prediction using mini-batches
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405113)
