# A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption

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

## Key facts

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

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

- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions](https://mlsanity.com/paper/2201.07164/) (2022)
- [Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization](https://mlsanity.com/paper/2108.10859/) (2021)
- [Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates](https://mlsanity.com/paper/2102.01977/) (2021)
- [Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization](https://mlsanity.com/paper/2106.09215/) (2021)
- [Federated X-Armed Bandit](https://mlsanity.com/paper/2205.15268/) (2022)
- [PyXAB -- A Python Library for X-Armed Bandit and Online Blackbox Optimization Algorithms](https://mlsanity.com/paper/2303.04030/) (2023)
- [Certified Multi-Fidelity Zeroth-Order Optimization](https://mlsanity.com/paper/2308.00978/) (2023)
- [Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants](https://mlsanity.com/paper/2502.04290/) (2025)
- [Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions](https://mlsanity.com/paper/2206.02383/) (2022)
- [Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions](https://mlsanity.com/paper/2402.15188/) (2024)
- [ECPv2: Fast, Efficient, and Scalable Global Optimization of Lipschitz Functions](https://mlsanity.com/paper/2511.16575/) (2025)
- [EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization](https://mlsanity.com/paper/2508.12479/) (2025)
- [Active Bipartite Ranking with Smooth Posterior Distributions](https://mlsanity.com/paper/2602.24263/) (2026)
- [Adaptive multi-fidelity optimization with fast learning rates](https://mlsanity.com/paper/2604.16239/) (2026)
- [Scale-free adaptive planning for deterministic dynamics & discounted rewards](https://mlsanity.com/paper/2604.18312/) (2026)
- [1D to nD: A Meta Algorithm for Multivariate Global Optimization via Univariate Optimizers](https://mlsanity.com/paper/2209.03246/) (2022)
- [Efficient Lipschitzian Global Optimization of H"older Continuous Multivariate Functions](https://mlsanity.com/paper/2303.14293/) (2023)
- [Personalized Federated X -armed Bandit](https://mlsanity.com/paper/2310.16323/) (2023)
- [Federated X-armed Bandit with Flexible Personalisation](https://mlsanity.com/paper/2409.07251/) (2024)
- [Bandits in Prod: Hyperparameter Optimization at Inference Time](https://mlsanity.com/paper/2609.01335/) (2026)
- [Adaptive Partitioning Schemes for Optimistic Optimization](https://mlsanity.com/paper/2610.04039/) (2026)

## Abstract (arXiv)

We study the problem of optimizing a function under a budgeted number of evaluations. We only assume that the function is locally smooth around one of its global optima. The difficulty of optimization is measured in terms of 1) the amount of noise b of the function evaluation and 2) the local smoothness, d, of the function. A smaller d results in smaller optimization error. We come with a new, simple, and parameter-free approach. First, for all values of b and d, this approach recovers at least the state-of-the-art regret guarantees. Second, our approach additionally obtains these results while being textitagnostic to the values of both b and d. This leads to the first algorithm that naturally adapts to an textitunknown range of noise b and leads to significant improvements in a moderate and low-noise regime. Third, our approach also obtains a remarkable improvement over the state-of-the-art SOO algorithm when the noise is very low which includes the case of optimization under deterministic feedback (b=0). There, under our minimal local smoothness assumption, this improvement is of exponential magnitude and holds for a class of functions that covers the vast majority of functions that practitioners optimize (d=0). We show that our algorithmic improvement is borne out in experiments as we empirically show faster convergence on common benchmarks.