# Highly-Smooth Zero-th Order Online Optimization Vianney Perchet

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2016.

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

- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Derivative-Free Reinforcement Learning: A Review](https://mlsanity.com/paper/2102.05710/) (2021)
- [Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm](https://mlsanity.com/paper/2306.02159/) (2023)
- [Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning](https://mlsanity.com/paper/2207.10415/) (2022)
- [Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations](https://mlsanity.com/paper/2510.19975/) (2025)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [A gradient estimator via L1-randomization for online zero-order optimization with two point feedback](https://mlsanity.com/paper/2205.13910/) (2022)
- [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)
- [Zero-Order One-Point Estimate with Distributed Stochastic Gradient-Tracking Technique](https://mlsanity.com/paper/2210.05618/) (2022)
- [Local and adaptive mirror descents in extensive-form games](https://mlsanity.com/paper/2309.00656/) (2023)
- [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)
- [Optimal Stochastic Nonconvex Optimization with Bandit Feedback](https://mlsanity.com/paper/2103.16082/) (2021)
- [Estimating the minimizer and the minimum value of a regression function under passive design](https://mlsanity.com/paper/2211.16457/) (2022)
- [Hebbian learning inspired estimation of the linear regression parameters from queries](https://mlsanity.com/paper/2311.03483/) (2023)
- [Interacting Particle Systems for Fast Linear Quadratic RL](https://mlsanity.com/paper/2406.11057/) (2024)
- [A simple and improved algorithm for noisy, convex, zeroth-order optimisation](https://mlsanity.com/paper/2406.18672/) (2024)
- [Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity](https://mlsanity.com/paper/2406.19617/) (2024)
- [Stochastic Direct Search Method for Blind Resource Allocation](https://mlsanity.com/paper/2210.05222/) (2022)
- [Optimal estimators of cross-partial derivatives and surrogates of functions](https://mlsanity.com/paper/2407.11035/) (2024)
- [Gradient-free stochastic optimization for additive models](https://mlsanity.com/paper/2503.02131/) (2025)
- [Zeroth-Order Sharpness-Aware Learning with Exponential Tilting](https://mlsanity.com/paper/2510.16157/) (2025)

## Abstract (arXiv)

The minimization of convex functions which are only available through partial and noisy information is a key methodological problem in many disciplines. In this paper we consider convex optimization with noisy zero-th order information, that is noisy function evaluations at any desired point. We focus on problems with high degrees of smoothness, such as logistic regression. We show that as opposed to gradient-based algorithms, high-order smoothness may be used to improve estimation rates, with a precise dependence of our upper-bounds on the degree of smoothness. In particular, we show that for infinitely differentiable functions, we recover the same dependence on sample size as gradient-based algorithms, with an extra dimension-dependent factor. This is done for both convex and strongly-convex functions, with finite horizon and anytime algorithms. Finally, we also recover similar results in the online optimization setting.