# Black-box optimization of noisy functions with unknown smoothness

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 16 references that are in the map.
- First posted on arXiv 4 May 2026.

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

- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Online Stochastic Optimization under Correlated Bandit Feedback](https://mlsanity.com/paper/1402.0562/) (2014)
- [Stochastic simultaneous optimistic optimization](https://mlsanity.com/paper/2604.24537/) (2026)
- [Adaptive-treed bandits](https://mlsanity.com/paper/1302.2489/) (2013)
- [Unimodal Bandits without Smoothness](https://mlsanity.com/paper/1406.7447/) (2014)

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

- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)
- [Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits](https://mlsanity.com/paper/2609.30017/) (2026)
- [Adaptive Partitioning Schemes for Optimistic Optimization](https://mlsanity.com/paper/2610.04039/) (2026)

## Abstract (arXiv)

We study the problem of black-box optimization of a function f of any dimension, given function evaluations perturbed by noise. The function is assumed to be locally smooth around one of its global optima, but this smoothness is unknown. Our contribution is an adaptive optimization algorithm, POO or parallel optimistic optimization, that is able to deal with this setting. POO performs almost as well as the best known algorithms requiring the knowledge of the smoothness. Furthermore, POO works for a larger class of functions than what was previously considered, especially for functions that are difficult to optimize, in a very precise sense. We provide a finite-time analysis of POO's performance, which shows that its error after n evaluations is at most a factor of sqrt(ln n) away from the error of the best known optimization algorithms using the knowledge of the smoothness.