# Gradientless Descent: High-Dimensional Zeroth-Order Optimization

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

## Key facts

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

## Built on by (most cited first, 30 of 43)

- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Towards Learning Universal Hyperparameter Optimizers with Transformers](https://mlsanity.com/paper/2205.13320/) (2022)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [evosax: JAX-based Evolution Strategies](https://mlsanity.com/paper/2212.04180/) (2022)
- [Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles](https://mlsanity.com/paper/2303.03751/) (2023)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms](https://mlsanity.com/paper/2107.10110/) (2021)
- [ZARTS: On Zero-order Optimization for Neural Architecture Search](https://mlsanity.com/paper/2110.04743/) (2021)
- [Zero-th Order Algorithm for Softmax Attention Optimization](https://mlsanity.com/paper/2307.08352/) (2023)
- [Synergizing Foundation Models and Federated Learning: A Survey](https://mlsanity.com/paper/2406.12844/) (2024)
- [Permutation Search of Tensor Network Structures via Local Sampling](https://mlsanity.com/paper/2206.06597/) (2022)
- [ComPO: Preference Alignment via Comparison Oracles](https://mlsanity.com/paper/2505.05465/) (2025)
- [MACE: An Efficient Model-Agnostic Framework for Counterfactual Explanation](https://mlsanity.com/paper/2205.15540/) (2022)
- [Alternating Local Enumeration (TnALE): Solving Tensor Network Structure Search with Fewer Evaluations](https://mlsanity.com/paper/2304.12875/) (2023)
- [Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/2405.16805/) (2024)
- [A Method to Reveal Speaker Identity in Distributed ASR Training, and How to Counter It](https://mlsanity.com/paper/2104.07815/) (2021)
- [Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm](https://mlsanity.com/paper/2102.05198/) (2021)
- [Global optimization using random embeddings](https://mlsanity.com/paper/2107.12102/) (2021)
- [EvoFed: Leveraging Evolutionary Strategies for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2311.07485/) (2023)
- [DittoGym: Learning to Control Soft Shape-Shifting Robots](https://mlsanity.com/paper/2401.13231/) (2024)
- [On the Second-order Convergence Properties of Random Search Methods](https://mlsanity.com/paper/2110.13265/) (2021)
- [Evaluating Resilience of Encrypted Traffic Classification Against Adversarial Evasion Attacks](https://mlsanity.com/paper/2105.14564/) (2021)
- [Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity](https://mlsanity.com/paper/2210.05279/) (2022)
- [FedCF: Fair Federated Conformal Prediction](https://mlsanity.com/paper/2509.22907/) (2025)
- [OPT-GAN: A Broad-Spectrum Global Optimizer for Black-box Problems by Learning Distribution](https://mlsanity.com/paper/2102.03888/) (2021)
- [Lazy Queries Can Reduce Variance in Zeroth-order Optimization](https://mlsanity.com/paper/2206.07126/) (2022)
- [Zero-Order One-Point Estimate with Distributed Stochastic Gradient-Tracking Technique](https://mlsanity.com/paper/2210.05618/) (2022)
- [Forward Learning for Gradient-based Black-box Saliency Map Generation](https://mlsanity.com/paper/2403.15603/) (2024)
- [Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function](https://mlsanity.com/paper/2410.05942/) (2024)
- [Stochastic Optimization with Random Search](https://mlsanity.com/paper/2510.15610/) (2025)

## Abstract (arXiv)

Zeroth-order optimization is the process of minimizing an objective f(x), given oracle access to evaluations at adaptively chosen inputs x. In this paper, we present two simple yet powerful GradientLess Descent (GLD) algorithms that do not rely on an underlying gradient estimate and are numerically stable. We analyze our algorithm from a novel geometric perspective and present a novel analysis that shows convergence within an ε-ball of the optimum in O(kQlog(n)log(R/ε)) evaluations, for any monotone transform of a smooth and strongly convex objective with latent dimension k < n, where the input dimension is n, R is the diameter of the input space and Q is the condition number. Our rates are the first of its kind to be both 1) poly-logarithmically dependent on dimensionality and 2) invariant under monotone transformations. We further leverage our geometric perspective to show that our analysis is optimal. Both monotone invariance and its ability to utilize a low latent dimensionality are key to the empirical success of our algorithms, as demonstrated on BBOB and MuJoCo benchmarks.