Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions
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\sqrt{n}T^{-\frac{1}{n}})$ for the optimization of an $n$-dimensional $L$-Lipschitz continuous objective in a time horizon $T$, which we show to be minimax optimal.
Code (0)
등록된 구현이 없습니다.
Tasks
global-optimizationSimilar Papers 제목 키워드 기반
Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants
Optimizing expensive, non-convex, black-box Lipschitz continuous functions presents significant challenges, particularly when the Lipschitz constant of the underlying function is unknown. Such problems often demand numer…
global-optimizationCumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization
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…
global-optimizationEfficient Lipschitzian Global Optimization of Hölder Continuous Multivariate Functions
This study presents an effective global optimization technique designed for multivariate functions that are H\"older continuous. Unlike traditional methods that construct lower bounding proxy functions, this algorithm em…
global-optimizationAdaptive and Optimal Second-order Optimistic Methods for Minimax Optimization
We propose adaptive, line search-free second-order methods with optimal rate of convergence for solving convex-concave min-max problems. By means of an adaptive step size, our algorithms feature a simple update rule that…
Second-order methodsGlobal optimization of Lipschitz functions
The goal of the paper is to design sequential strategies which lead to efficient optimization of an unknown function under the only assumption that it has a finite Lipschitz constant. We first identify sufficient conditi…
global-optimizationHyperparameter Optimization