# Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization

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

## Key facts

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

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

- [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)
- [Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits](https://mlsanity.com/paper/2302.06025/) (2023)
- [Certified Multi-Fidelity Zeroth-Order Optimization](https://mlsanity.com/paper/2308.00978/) (2023)
- [Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions](https://mlsanity.com/paper/2206.02383/) (2022)
- [An Application of Online Learning to Spacecraft Memory Dump Optimization](https://mlsanity.com/paper/2202.06617/) (2022)
- [Online Learning in Supply-Chain Games](https://mlsanity.com/paper/2207.04054/) (2022)
- [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)
- [Proximal basin hopping: global optimization with guarantees](https://mlsanity.com/paper/2605.18364/) (2026)

## Abstract (arXiv)

We consider the problem of maximizing a non-concave Lipschitz multivariate function over a compact domain by sequentially querying its (possibly perturbed) values. We study a natural algorithm designed originally by Piyavskii and Shubert in 1972, for which we prove new bounds on the number of evaluations of the function needed to reach or certify a given optimization accuracy. Our analysis uses a bandit-optimization viewpoint and solves an open problem from Hansen et al. (1991) by bounding the number of evaluations to certify a given accuracy with a near-optimal sum of packing numbers.