# Zeroth-order Optimization with Weak Dimension Dependency

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

## Key facts

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

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

- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [Zeroth-Order Fine-Tuning of LLMs in Random Subspaces](https://mlsanity.com/paper/2410.08989/) (2024)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [Online Pseudo-Zeroth-Order Training of Neuromorphic Spiking Neural Networks](https://mlsanity.com/paper/2407.12516/) (2024)
- [Towards Fast LLM Fine-tuning through Zeroth-Order Optimization with Projected Gradient-Aligned Perturbations](https://mlsanity.com/paper/2510.18228/) (2025)
- [CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity](https://mlsanity.com/paper/2309.13307/) (2023)
- [Efficient Personalization of Quantized Diffusion Model without Backpropagation](https://mlsanity.com/paper/2503.14868/) (2025)
- [On the Inherent Privacy of Zeroth Order Projected Gradient Descent](https://mlsanity.com/paper/2507.05610/) (2025)
- [ConMeZO: Adaptive Descent-Direction Sampling for Gradient-Free Finetuning of Large Language Models](https://mlsanity.com/paper/2511.02757/) (2025)
- [Stochastic Dimension Zeroth-Order Estimator: Stable and Memory-Efficient Training of PINNs](https://mlsanity.com/paper/2603.24002/) (2026)
- [From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stability](https://mlsanity.com/paper/2604.25372/) (2026)

## Abstract (arXiv)

Zeroth-order optimization is a fundamental research topic that has been a focus of various learning tasks, such as black-box adversarial attacks, bandits, and reinforcement learning. However, in theory, most complexity results assert a linear dependency on the dimension of optimization variable, which implies paralyzations of zeroth-order algorithms for high-dimensional problems and cannot explain their effectiveness in practice. In this paper, we present a novel zeroth-order optimization theory characterized by complexities that exhibit weak dependencies on dimensionality. The key contribution lies in the introduction of a new factor, denoted as EDα=supx∈ ℝdsumi=1dσiα(nabla2 f(x)) (α>0, σi(·) is the i-th singular value in non-increasing order), which effectively functions as a measure of dimensionality. The algorithms we propose demonstrate significantly reduced complexities when measured in terms of the factor EDα. Specifically, we first study a well-known zeroth-order algorithm from Nesterov and Spokoiny (2017) on quadratic objectives and show a complexity of Oleft(fracED1σdlog(1/ε)right) for the strongly convex setting. Furthermore, we introduce novel algorithms that leverages the Heavy-ball mechanism. Our proposed algorithm exhibits a complexity of Oleft(fracED1/2√σd·logfracLμ·log(1/ε)right). We further expand the scope of the method to encompass generic smooth optimization problems under an additional Hessian-smooth condition. The resultant algorithms demonstrate remarkable complexities which improve by an order in d under appropriate conditions. Our analysis lays the foundation for zeroth-order optimization methods for smooth functions within high-dimensional settings.