# Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2020.

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

- [Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm](https://mlsanity.com/paper/2306.02159/) (2023)
- [A gradient estimator via L1-randomization for online zero-order optimization with two point feedback](https://mlsanity.com/paper/2205.13910/) (2022)
- [Black-Box Generalization: Stability of Zeroth-Order Learning](https://mlsanity.com/paper/2202.06880/) (2022)
- [Estimating the minimizer and the minimum value of a regression function under passive design](https://mlsanity.com/paper/2211.16457/) (2022)
- [Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity](https://mlsanity.com/paper/2406.19617/) (2024)
- [Non-stationary Bandit Convex Optimization: A Comprehensive Study](https://mlsanity.com/paper/2506.02980/) (2025)
- [Active Bipartite Ranking with Smooth Posterior Distributions](https://mlsanity.com/paper/2602.24263/) (2026)
- [The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimization](https://mlsanity.com/paper/2607.18652/) (2026)
- [Stochastic Direct Search Method for Blind Resource Allocation](https://mlsanity.com/paper/2210.05222/) (2022)
- [A conversion theorem and minimax optimality for continuum contextual bandits](https://mlsanity.com/paper/2406.05714/) (2024)
- [How to Boost Any Loss Function](https://mlsanity.com/paper/2407.02279/) (2024)
- [Optimal estimators of cross-partial derivatives and surrogates of functions](https://mlsanity.com/paper/2407.11035/) (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)
- [Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension](https://mlsanity.com/paper/2607.12938/) (2026)

## Abstract (arXiv)

We study the problem of zero-order optimization of a strongly convex function. The goal is to find the minimizer of the function by a sequential exploration of its values, under measurement noise. We study the impact of higher order smoothness properties of the function on the optimization error and on the cumulative regret. To solve this problem we consider a randomized approximation of the projected gradient descent algorithm. The gradient is estimated by a randomized procedure involving two function evaluations and a smoothing kernel. We derive upper bounds for this algorithm both in the constrained and unconstrained settings and prove minimax lower bounds for any sequential search method. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters. Based on this algorithm, we also propose an estimator of the minimum value of the function achieving almost sharp oracle behavior. We compare our results with the state-of-the-art, highlighting a number of key improvements.