# Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 52 references that are in the map.
- First posted on arXiv 6 Jun 2022.

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

- [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)
- [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)

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

- [Efficient Lipschitzian Global Optimization of H"older Continuous Multivariate Functions](https://mlsanity.com/paper/2303.14293/) (2023)
- [A Note On Nonlinear Regression Under L2 Loss](https://mlsanity.com/paper/2303.17745/) (2023)

## Abstract (arXiv)

In this work, we propose an efficient minimax optimal global optimization algorithm for multivariate Lipschitz continuous functions. To evaluate the performance of our approach, we utilize the average regret instead of the traditional simple regret, which, as we show, is not suitable for use in the multivariate non-convex optimization because of the inherent hardness of the problem itself. Since we study the average regret of the algorithm, our results directly imply a bound for the simple regret as well. Instead of constructing lower bounding proxy functions, our method utilizes a predetermined query creation rule, which makes it computationally superior to the Piyavskii-Shubert variants. We show that our algorithm achieves an average regret bound of O(L√nT^-frac1n) for the optimization of an n-dimensional L-Lipschitz continuous objective in a time horizon T, which we show to be minimax optimal.