# Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 3 Jun 2023.

## Builds on (most cited first, 13 of 13)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Highly-Smooth Zero-th Order Online Optimization Vianney Perchet](https://mlsanity.com/paper/1605.08165/) (2016)
- [Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits](https://mlsanity.com/paper/2006.07862/) (2020)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry](https://mlsanity.com/paper/1703.09477/) (2017)
- [Distributed Zero-Order Optimization under Adversarial Noise](https://mlsanity.com/paper/2102.01121/) (2021)
- [A gradient estimator via L1-randomization for online zero-order optimization with two point feedback](https://mlsanity.com/paper/2205.13910/) (2022)
- [Gradient projection and conditional gradient methods for constrained nonconvex minimization](https://mlsanity.com/paper/1906.11580/) (2019)

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

- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [KerZOO: Kernel Function Informed Zeroth-Order Optimization for Accurate and Accelerated LLM Fine-Tuning](https://mlsanity.com/paper/2505.18886/) (2025)
- [Accelerated zero-order SGD under high-order smoothness and overparameterized regime](https://mlsanity.com/paper/2411.13999/) (2024)
- [On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization](https://mlsanity.com/paper/2510.19953/) (2025)
- [The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimization](https://mlsanity.com/paper/2607.18652/) (2026)
- [A conversion theorem and minimax optimality for continuum contextual bandits](https://mlsanity.com/paper/2406.05714/) (2024)
- [Finite Sample Bounds for Non-Parametric Regression: Optimal Sample Efficiency and Space Complexity](https://mlsanity.com/paper/2412.14744/) (2024)
- [Gradient-free stochastic optimization for additive models](https://mlsanity.com/paper/2503.02131/) (2025)
- [High-probability zeroth-order online convex optimisation beyond Euclidean geometry](https://mlsanity.com/paper/2509.21484/) (2025)
- [Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity](https://mlsanity.com/paper/2601.01160/) (2026)
- [Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity](https://mlsanity.com/paper/2605.31346/) (2026)
- [Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension](https://mlsanity.com/paper/2607.12938/) (2026)

## Abstract (arXiv)

This work studies minimization problems with zero-order noisy oracle information under the assumption that the objective function is highly smooth and possibly satisfies additional properties. We consider two kinds of zero-order projected gradient descent algorithms, which differ in the form of the gradient estimator. The first algorithm uses a gradient estimator based on randomization over the ℓ2 sphere due to Bach and Perchet (2016). We present an improved analysis of this algorithm on the class of highly smooth and strongly convex functions studied in the prior work, and we derive rates of convergence for two more general classes of non-convex functions. Namely, we consider highly smooth functions satisfying the Polyak-Lojasiewicz condition and the class of highly smooth functions with no additional property. The second algorithm is based on randomization over the ℓ1 sphere, and it extends to the highly smooth setting the algorithm that was recently proposed for Lipschitz convex functions in Akhavan et al. (2022). We show that, in the case of noiseless oracle, this novel algorithm enjoys better bounds on bias and variance than the ℓ2 randomization and the commonly used Gaussian randomization algorithms, while in the noisy case both ℓ1 and ℓ2 algorithms benefit from similar improved theoretical guarantees. The improvements are achieved thanks to a new proof techniques based on Poincar'e type inequalities for uniform distributions on the ℓ1 or ℓ2 spheres. The results are established under weak (almost adversarial) assumptions on the noise. Moreover, we provide minimax lower bounds proving optimality or near optimality of the obtained upper bounds in several cases.