# Stochastic Subspace Descent

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2019.

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

- [PV-Tuning: Beyond Straight-Through Estimation for Extreme LLM Compression](https://mlsanity.com/paper/2405.14852/) (2024)
- [Memory-Efficient LLM Training with Online Subspace Descent](https://mlsanity.com/paper/2408.12857/) (2024)
- [Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretraining](https://mlsanity.com/paper/2502.05790/) (2025)
- [Learning long range dependencies through time reversal symmetry breaking](https://mlsanity.com/paper/2506.05259/) (2025)
- [Global optimization using random embeddings](https://mlsanity.com/paper/2107.12102/) (2021)
- [Gradient Descent for Low-Rank Functions](https://mlsanity.com/paper/2206.08257/) (2022)
- [Cubic regularized subspace Newton for non-convex optimization](https://mlsanity.com/paper/2406.16666/) (2024)
- [A stochastic gradient descent algorithm with random search directions](https://mlsanity.com/paper/2503.19942/) (2025)
- [Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search](https://mlsanity.com/paper/2505.00162/) (2025)
- [Factor Augmented High-Dimensional SGD](https://mlsanity.com/paper/2605.19291/) (2026)

## Abstract (arXiv)

We present two stochastic descent algorithms that apply to unconstrained optimization and are particularly efficient when the objective function is slow to evaluate and gradients are not easily obtained, as in some PDE-constrained optimization and machine learning problems. The basic algorithm projects the gradient onto a random subspace at each iteration, similar to coordinate descent but without restricting directional derivatives to be along the axes. This algorithm is previously known but we provide new analysis. We also extend the popular SVRG method to this framework but without requiring that the objective function be written as a finite sum. We provide proofs of convergence for our methods under various convexity assumptions and show favorable results when compared to gradient descent and BFGS on non-convex problems from the machine learning and shape optimization literature. We also note that our analysis gives a proof that the iterates of SVRG and several other popular first-order stochastic methods, in their original formulation, converge almost surely to the optimum; to our knowledge, prior to this work the iterates of SVRG had only been known to converge in expectation.