mlsanityData to 14 Oct 2026

SGD with Coordinate Sampling: Theory and Practice

arXiv 2105.11818 ↗First posted 25 May 2021stat.ML cs.LGcited by 4

Not on the map. Why?

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.

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

30 of 68 references.

References · 30

  1. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  4. 2018The Convergence of Sparsified Gradient Methodscited by 229
  5. 2019SGD: General Analysis and Improved Ratescited by 207
  6. 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 201
  7. 2016Stochastic Optimization for Large-scale Optimal Transportcited by 189
  8. 2020A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learningcited by 162
  9. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  10. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
  11. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  12. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 95
18 more
  1. 2014Stochastic Optimization with Importance Samplingcited by 91
  2. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 63
  3. 2016A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Ordercited by 44
  4. 2016Stochastic Heavy Ballcited by 42
  5. 2015Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selectioncited by 39
  6. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  7. 2018Importance Sampling Policy Evaluation with an Estimated Behavior Policycited by 34
  8. 2013Accelerated, Parallel and Proximal Coordinate Descentcited by 25
  9. 2015Even Faster Accelerated Coordinate Descent Using Non-Uniform Samplingcited by 23
  10. 2013On the Complexity Analysis of Randomized Block-Coordinate Descent Methodscited by 21
  11. 2013Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systemscited by 14
  12. 2013On Optimal Probabilities in Stochastic Coordinate Descent Methodscited by 14
  13. 2014Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexitycited by 14
  14. 2018Asymptotic optimality of adaptive importance samplingcited by 9
  15. 2019Optimal mini-batch and step sizes for SAGAcited by 9
  16. 2015Stochastic Dual Coordinate Ascent with Adaptive Probabilitiescited by 5
  17. 2017Faster Coordinate Descent via Adaptive Importance Samplingcited by 5
  18. 2014Fast Distributed Coordinate Descent for Non-Strongly Convex Lossescited by 4

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2; 2025: 1.

4 papers.

  1. 2023A Guide Through the Zoo of Biased SGDcited by 40
  2. 2024Non-asymptotic Analysis of Biased Adaptive Stochastic Approximationcited by 5
  3. 2024On the SAGA algorithm with decreasing stepcited by 1
  4. 2025A stochastic gradient descent algorithm with random search directionscited by 0