SGD with Coordinate Sampling: Theory and Practice
arXiv:2105.11818
Abstract
While classical forms of stochastic gradient descent algorithm treat the different coordinates in the same way, a framework allowing for adaptive (non uniform) coordinate sampling is developed to leverage structure in data. In a non-convex setting and including zeroth order gradient estimate, almost sure convergence as well as non-asymptotic bounds are established. Within the proposed framework, we develop an algorithm, MUSKETEER, based on a reinforcement strategy: after collecting information on the noisy gradients, it samples the most promising coordinate (all for one); then it moves along the one direction yielding an important decrease of the objective (one for all). Numerical experiments on both synthetic and real data examples confirm the effectiveness of MUSKETEER in large scale problems.
arXiv commentJournal of Machine Learning Research 2022
References in corpus (14)
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
- An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
- Stochastic Optimization for Large-scale Optimal Transport
- Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
- SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
- A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
- SGD: General Analysis and Improved Rates
- Stochastic Dual Coordinate Ascent with Adaptive Probabilities
- On Optimal Probabilities in Stochastic Coordinate Descent Methods
- Optimal mini-batch and step sizes for SAGA
- On the Convergence of SGD with Biased Gradients
- Faster Coordinate Descent via Adaptive Importance Sampling
- On the asymptotic rate of convergence of Stochastic Newton algorithms and their Weighted Averaged versions