# A stochastic subspace approach to gradient-free optimization in high dimensions

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2020.

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

- [Zeroth-Order Fine-Tuning of LLMs in Random Subspaces](https://mlsanity.com/paper/2410.08989/) (2024)
- [On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms](https://mlsanity.com/paper/2107.10110/) (2021)
- [Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations](https://mlsanity.com/paper/2510.19975/) (2025)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method](https://mlsanity.com/paper/2505.12378/) (2025)
- [Random Gradient-Free Optimization in Infinite Dimensional Spaces](https://mlsanity.com/paper/2512.20566/) (2025)
- [Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2601.20399/) (2026)
- [Optimal low-rank stochastic gradient estimation for LLM training](https://mlsanity.com/paper/2603.20632/) (2026)
- [Subspace Langevin Monte Carlo](https://mlsanity.com/paper/2412.13928/) (2024)
- [Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search](https://mlsanity.com/paper/2505.00162/) (2025)
- [Trust-Region Methods with Low-Fidelity Objective Models](https://mlsanity.com/paper/2511.00434/) (2025)
- [Stochastic Dimension Zeroth-Order Estimator: Stable and Memory-Efficient Training of PINNs](https://mlsanity.com/paper/2603.24002/) (2026)
- [Randomized Subspace Nesterov Accelerated Gradient](https://mlsanity.com/paper/2605.00740/) (2026)
- [MpSub: A Momentum p-Dimensional Subspace Trust-Region Method for Derivative-Free Fine-Tuning of Large Language Models](https://mlsanity.com/paper/2609.07666/) (2026)
- [ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization](https://mlsanity.com/paper/2609.27199/) (2026)

## Abstract (arXiv)

We present a stochastic descent algorithm for unconstrained optimization that is 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 algorithm maps the gradient onto a low-dimensional random subspace of dimension ℓ at each iteration, similar to coordinate descent but without restricting directional derivatives to be along the axes. Without requiring a full gradient, this mapping can be performed by computing ℓ directional derivatives (e.g., via forward-mode automatic differentiation). We give proofs for convergence in expectation under various convexity assumptions as well as probabilistic convergence results under strong-convexity. Our method extends the well-known Gaussian smoothing technique to descent in subspaces of dimension greater than one, opening the doors to new analysis of Gaussian smoothing when more than one directional derivative is used at each iteration. We also provide a finite-dimensional variant of a special case of the Johnson-Lindenstrauss lemma. Experimentally, we show that our method compares favorably to coordinate descent, Gaussian smoothing, gradient descent and BFGS (when gradients are calculated via forward-mode automatic differentiation) on problems from the machine learning and shape optimization literature.