# Zeroth order optimization with orthogonal random directions

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2021.

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

- [Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures](https://mlsanity.com/paper/2410.07698/) (2024)
- [Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalization](https://mlsanity.com/paper/2602.17155/) (2026)
- [Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations](https://mlsanity.com/paper/2510.19975/) (2025)
- [Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order](https://mlsanity.com/paper/2506.04430/) (2025)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [MaZO: Masked Zeroth-Order Optimization for Multi-Task Fine-Tuning of Large Language Models](https://mlsanity.com/paper/2502.11513/) (2025)
- [An Efficient Subspace Algorithm for Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2509.05213/) (2025)
- [Forward Learning for Gradient-based Black-box Saliency Map Generation](https://mlsanity.com/paper/2403.15603/) (2024)
- [Subspace-based Approximate Hessian Method for Zeroth-Order Optimization](https://mlsanity.com/paper/2507.06125/) (2025)
- [Towards Fast LLM Fine-tuning through Zeroth-Order Optimization with Projected Gradient-Aligned Perturbations](https://mlsanity.com/paper/2510.18228/) (2025)
- [On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization](https://mlsanity.com/paper/2510.19953/) (2025)
- [Convergence Rates of Stochastic Zeroth-order Gradient Descent for L ojasiewicz Functions](https://mlsanity.com/paper/2210.16997/) (2022)
- [A New Formulation for Zeroth-Order Optimization of Adversarial EXEmples in Malware Detection](https://mlsanity.com/paper/2405.14519/) (2024)
- [Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization](https://mlsanity.com/paper/2408.12209/) (2024)
- [Optimal low-rank stochastic gradient estimation for LLM training](https://mlsanity.com/paper/2603.20632/) (2026)
- [Position: Zeroth-Order Optimization in Deep Learning Is Underexplored, Not Underpowered](https://mlsanity.com/paper/2605.15622/) (2026)
- [Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search](https://mlsanity.com/paper/2505.00162/) (2025)
- [A Structured Tour of Optimization with Finite Differences](https://mlsanity.com/paper/2505.19720/) (2025)
- [Dimensional Peeking for Low-Variance Gradients in Zeroth-Order Discrete Optimization via Simulation](https://mlsanity.com/paper/2602.00075/) (2026)
- [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)

## Abstract (arXiv)

We propose and analyze a randomized zeroth-order approach based on approximating the exact gradient byfinite differences computed in a set of orthogonal random directions that changes with each iteration. A number ofpreviously proposed methods are recovered as special cases including spherical smoothing, coordinate descent, as wellas discretized gradient descent. Our main contribution is proving convergence guarantees as well as convergence ratesunder different parameter choices and assumptions. In particular, we consider convex objectives, but also possiblynon-convex objectives satisfying the Polyak-Lojasiewicz (PL) condition. Theoretical results are complemented andillustrated by numerical experiments.