# Certified Multi-Fidelity Zeroth-Order Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 77 references that are in the map.
- First posted on arXiv 2 Aug 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Survey of multifidelity methods in uncertainty propagation, inference, and optimization](https://mlsanity.com/paper/1806.10761/) (2018)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [A General Framework for Multi-fidelity Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1811.00755/) (2018)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Global optimization of Lipschitz functions](https://mlsanity.com/paper/1703.02628/) (2017)
- [Multi-fidelity Gaussian Process Bandit Optimisation](https://mlsanity.com/paper/1603.06288/) (2016)
- [A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption](https://mlsanity.com/paper/1810.00997/) (2018)
- [The Multi-fidelity Multi-armed Bandit](https://mlsanity.com/paper/1610.09726/) (2016)
- [Best Arm Identification in Generalized Linear Bandits](https://mlsanity.com/paper/1905.08224/) (2019)
- [Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization](https://mlsanity.com/paper/2002.02390/) (2020)
- [Noisy Blackbox Optimization with Multi-Fidelity Queries: A Tree Search Approach](https://mlsanity.com/paper/1810.10482/) (2018)
- [Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates](https://mlsanity.com/paper/2102.01977/) (2021)
- [Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-Fidelity Feedback](https://mlsanity.com/paper/2110.07232/) (2021)

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

- [Variational Quantum Optimization with Continuous Bandits](https://mlsanity.com/paper/2502.04021/) (2025)
- [Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search](https://mlsanity.com/paper/2505.00162/) (2025)
- [Instance-dependent Stochastic Lipschitz bandit](https://mlsanity.com/paper/2605.29748/) (2026)

## Abstract (arXiv)

We consider the problem of multi-fidelity zeroth-order optimization, where one can evaluate a function f at various approximation levels (of varying costs), and the goal is to optimize f with the cheapest evaluations possible. In this paper, we study certified algorithms, which are additionally required to output a data-driven upper bound on the optimization error. We first formalize the problem in terms of a min-max game between an algorithm and an evaluation environment. We then propose a certified variant of the MFDOO algorithm and derive a bound on its cost complexity for any Lipschitz function f. We also prove an f-dependent lower bound showing that this algorithm has a near-optimal cost complexity. As a direct example, we close the paper by addressing the special case of noisy (stochastic) evaluations, which corresponds to eps-best arm identification in Lipschitz bandits with continuously many arms.