# SGD with Coordinate Sampling: Theory and Practice

arXiv: https://arxiv.org/abs/2105.11818 · HTML: https://mlsanity.com/paper/2105.11818/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 68 references that are in the map.
- First posted on arXiv 25 May 2021.

## Builds on (most cited first, 30 of 30)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order](https://mlsanity.com/paper/1606.00498/) (2016)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching](https://mlsanity.com/paper/1805.02632/) (2018)
- [Importance Sampling Policy Evaluation with an Estimated Behavior Policy](https://mlsanity.com/paper/1806.01347/) (2018)
- [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013)
- [Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling](https://mlsanity.com/paper/1512.09103/) (2015)
- [On the Complexity Analysis of Randomized Block-Coordinate Descent Methods](https://mlsanity.com/paper/1305.4723/) (2013)
- [Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems](https://mlsanity.com/paper/1305.1922/) (2013)
- [On Optimal Probabilities in Stochastic Coordinate Descent Methods](https://mlsanity.com/paper/1310.3438/) (2013)
- [Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity](https://mlsanity.com/paper/1412.8060/) (2014)
- [Asymptotic optimality of adaptive importance sampling](https://mlsanity.com/paper/1806.00989/) (2018)
- [Optimal mini-batch and step sizes for SAGA](https://mlsanity.com/paper/1902.00071/) (2019)
- [Stochastic Dual Coordinate Ascent with Adaptive Probabilities](https://mlsanity.com/paper/1502.08053/) (2015)
- [Faster Coordinate Descent via Adaptive Importance Sampling](https://mlsanity.com/paper/1703.02518/) (2017)
- [Fast Distributed Coordinate Descent for Non-Strongly Convex Losses](https://mlsanity.com/paper/1405.5300/) (2014)

## Built on by (most cited first, 4 of 4)

- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024)
- [On the SAGA algorithm with decreasing step](https://mlsanity.com/paper/2410.03760/) (2024)
- [A stochastic gradient descent algorithm with random search directions](https://mlsanity.com/paper/2503.19942/) (2025)

## Abstract (arXiv)

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.