# Stochastic Zeroth-order Optimization in High Dimensions

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2017.

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

- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [InstructZero: Efficient Instruction Optimization for Black-Box Large Language Models](https://mlsanity.com/paper/2306.03082/) (2023)
- [Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuning](https://mlsanity.com/paper/2402.15751/) (2024)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Zero-Shot Knowledge Distillation from a Decision-Based Black-Box Model](https://mlsanity.com/paper/2106.03310/) (2021)
- [Gradient-Free Textual Inversion](https://mlsanity.com/paper/2304.05818/) (2023)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods](https://mlsanity.com/paper/2102.03389/) (2021)
- [ComPO: Preference Alignment via Comparison Oracles](https://mlsanity.com/paper/2505.05465/) (2025)
- [Efficient Federated Prompt Tuning for Black-box Large Pre-trained Models](https://mlsanity.com/paper/2310.03123/) (2023)
- [Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/2405.16805/) (2024)
- [On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedback](https://mlsanity.com/paper/2210.05584/) (2022)
- [ZooPFL: Exploring Black-box Foundation Models for Personalized Federated Learning](https://mlsanity.com/paper/2310.05143/) (2023)
- [Simultaneous Computation and Memory Efficient Zeroth-Order Optimizer for Fine-Tuning Large Language Models](https://mlsanity.com/paper/2410.09823/) (2024)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [Stochastic Zeroth Order Gradient and Hessian Estimators: Variance Reduction and Refined Bias Bounds](https://mlsanity.com/paper/2205.14737/) (2022)
- [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)
- [Boosting Offline Optimizers with Surrogate Sensitivity](https://mlsanity.com/paper/2503.04181/) (2025)
- [Problem Dependent View on Structured Thresholding Bandit Problems](https://mlsanity.com/paper/2106.10166/) (2021)
- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)
- [SGD with Coordinate Sampling: Theory and Practice](https://mlsanity.com/paper/2105.11818/) (2021)
- [Covariance-Adaptive Sequential Black-box Optimization for Diffusion Targeted Generation](https://mlsanity.com/paper/2406.00812/) (2024)
- [ZOQO: Zero-Order Quantized Optimization](https://mlsanity.com/paper/2501.06736/) (2025)
- [Dynamic Pricing with Adversarially-Censored Demands](https://mlsanity.com/paper/2502.06168/) (2025)
- [The Multi-Query Paradox in Zeroth-Order Optimization](https://mlsanity.com/paper/2509.15552/) (2025)

## Abstract (arXiv)

We consider the problem of optimizing a high-dimensional convex function using stochastic zeroth-order queries. Under sparsity assumptions on the gradients or function values, we present two algorithms: a successive component/feature selection algorithm and a noisy mirror descent algorithm using Lasso gradient estimates, and show that both algorithms have convergence rates that de- pend only logarithmically on the ambient dimension of the problem. Empirical results confirm our theoretical findings and show that the algorithms we design outperform classical zeroth-order optimization methods in the high-dimensional setting.