# Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 55 references that are in the map.
- First posted on arXiv 24 Aug 2021.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Global optimization of Lipschitz functions](https://mlsanity.com/paper/1703.02628/) (2017)
- [A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption](https://mlsanity.com/paper/1810.00997/) (2018)
- [Sequential Outlier Detection based on Incremental Decision Trees](https://mlsanity.com/paper/1803.03674/) (2018)
- [Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization](https://mlsanity.com/paper/2002.02390/) (2020)
- [Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates](https://mlsanity.com/paper/2102.01977/) (2021)

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

- [Generalized Huber Loss for Robust Learning and its Efficient Minimization for a Robust Statistics](https://mlsanity.com/paper/2108.12627/) (2021)
- [Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions](https://mlsanity.com/paper/2201.07164/) (2022)
- [A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization](https://mlsanity.com/paper/2203.05618/) (2022)
- [Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions](https://mlsanity.com/paper/2206.02383/) (2022)
- [Blind Source Separation for Mixture of Sinusoids with Near-Linear Computational Complexity](https://mlsanity.com/paper/2203.14324/) (2022)
- [Robust, Nonparametric, Efficient Decomposition of Spectral Peaks under Distortion and Interference](https://mlsanity.com/paper/2204.08411/) (2022)
- [An Auto-Regressive Formulation for Smoothing and Moving Mean with Exponentially Tapered Windows](https://mlsanity.com/paper/2206.14749/) (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)

## Abstract (arXiv)

We study the problem of global optimization, where we analyze the performance of the Piyavskii--Shubert algorithm and its variants. For any given time duration T, instead of the extensively studied simple regret (which is the difference of the losses between the best estimate up to T and the global minimum), we study the cumulative regret up to time T. For L-Lipschitz continuous functions, we show that the cumulative regret is O(Llog T). For H-Lipschitz smooth functions, we show that the cumulative regret is O(H). We analytically extend our results for functions with Holder continuous derivatives, which cover both the Lipschitz continuous and the Lipschitz smooth functions, individually. We further show that a simpler variant of the Piyavskii-Shubert algorithm performs just as well as the traditional variants for the Lipschitz continuous or the Lipschitz smooth functions. We further extend our results to broader classes of functions, and show that, our algorithm efficiently determines its queries; and achieves nearly minimax optimal (up to log factors) cumulative regret, for general convex or even concave regularity conditions on the extrema of the objective (which encompasses many preceding regularities). We consider further extensions by investigating the performance of the Piyavskii-Shubert variants in the scenarios with unknown regularity, noisy evaluation and multivariate domain.