Batched Stochastic Gradient Descent with Weighted Sampling
From MaRDI portal
Abstract: We analyze a batched variant of Stochastic Gradient Descent (SGD) with weighted sampling distribution for smooth and non-smooth objective functions. We show that by distributing the batches computationally, a significant speedup in the convergence rate is provably possible compared to either batched sampling or weighted sampling alone. We propose several computationally efficient schemes to approximate the optimal weights, and compute proposed sampling distributions explicitly for the least squares and hinge loss problems. We show both analytically and experimentally that substantial gains can be obtained.
Recommendations
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Adaptive sampling for incremental optimization using stochastic gradient descent
- A stochastic multiple gradient descent algorithm
- Non-asymptotic guarantees for sampling by stochastic gradient descent
- Weighted SGD for \(\ell_p\) regression with randomized preconditioning
- Weighted SGD for _p regression with randomized preconditioning
- A stochastic version of Stein variational gradient descent for efficient sampling
- scientific article; zbMATH DE number 6860839
- Combining resampling and reweighting for faithful stochastic optimization
- Distributed stochastic variance reduced gradient methods by sampling extra data with replacement
Cites work
- scientific article; zbMATH DE number 1256751 (Why is no real title available?)
- scientific article; zbMATH DE number 6982318 (Why is no real title available?)
- A Stochastic Approximation Method
- A proximal stochastic gradient method with progressive variance reduction
- A randomized Kaczmarz algorithm with exponential convergence
- Decoding by Linear Programming
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Introductory lectures on convex optimization. A basic course.
- Large-scale machine learning with stochastic gradient descent
- Minimizing finite sums with the stochastic average gradient
- On optimal probabilities in stochastic coordinate descent methods
- Optimal distributed online prediction using mini-batches
- Pegasos: primal estimated sub-gradient solver for SVM
- Randomized Kaczmarz solver for noisy linear systems
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- Regularization tools version 4.0 for matlab 7.3
- Robust Stochastic Approximation Approach to Stochastic Programming
- Sample size selection in optimization methods for machine learning
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- Two-subspace projection method for coherent overdetermined systems
- Weighted SGD for \(\ell_p\) regression with randomized preconditioning
Cited in
(12)- A block-randomized stochastic method with importance sampling for CP tensor decomposition
- Randomized Kaczmarz with averaging
- Iterative singular tube hard thresholding algorithms for tensor recovery
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
- scientific article; zbMATH DE number 7370623 (Why is no real title available?)
- Stochastic greedy algorithms for multiple measurement vectors
- Randomized Kaczmarz algorithm with averaging and block projection
- A selective review on statistical methods for massive data computation: distributed computing, subsampling, and minibatch techniques
- Optimized convergence of stochastic gradient descent by weighted averaging
- On the fast convergence of minibatch heavy ball momentum
- A multivariate adaptive gradient algorithm with reduced tuning efforts
- Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification
This page was built for publication: Batched Stochastic Gradient Descent with Weighted Sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4609808)
