mlsanityData to 14 Oct 2026

A stochastic gradient descent algorithm with random search directions

arXiv 2503.19942 ↗First posted 25 Mar 2025stat.ML cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

Stochastic coordinate descent algorithms are efficient methods in which each iterate is obtained by fixing most coordinates at their values from the current iteration, and approximately minimizing the objective with respect to the remaining coordinates. However, this approach is usually restricted to canonical basis vectors of ℝd. In this paper, we develop a new class of stochastic gradient descent algorithms with random search directions which uses the directional derivative of the gradient estimate following more general random vectors. We establish the almost sure convergence of these algorithms with decreasing step. We further investigate their central limit theorem and pay particular attention to analyze the impact of the search distributions on the asymptotic covariance matrix. We also provide non-asymptotic mathbbLp rates of convergence.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 21 of its 38 references that are in the map. First posted on arXiv 25 Mar 2025.

Builds on

21 of 38 references.

References · 21

  1. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  2. 2023Fine-Tuning Language Models with Just Forward Passescited by 345
  3. 2015Coordinate Descent Algorithmscited by 219
  4. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
  5. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  6. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 67
  7. 2015Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selectioncited by 39
  8. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  9. 2013Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regressioncited by 32
  10. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  11. 2015Even Faster Accelerated Coordinate Descent Using Non-Uniform Samplingcited by 23
  12. 2013On Optimal Probabilities in Stochastic Coordinate Descent Methodscited by 14
9 more
  1. 2017Asynchronous Coordinate Descent under More Realistic Assumptionscited by 14
  2. 2021Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methodscited by 14
  3. 2019Stochastic Subspace Descentcited by 10
  4. 2019Exponential Convergence for Distributed Smooth Optimization Under the Restricted Secant Inequality Conditioncited by 6
  5. 2014Semi-Stochastic Coordinate Descentcited by 5
  6. 2022Gradient Descent Is Optimal Under Lower Restricted Secant Inequality And Upper Error Boundcited by 5
  7. 2021SGD with Coordinate Sampling: Theory and Practicecited by 4
  8. 2023Analyzing and Improving Greedy 2-Coordinate Updates for Equality-Constrained Optimization via Steepest Descent in the 1-Normcited by 2
  9. 2024On the SAGA algorithm with decreasing stepcited by 1

Built on by

Not cited yet.