Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Cumulative 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-optimizationLow Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions
In this work, we propose a computationally efficient algorithm for the problem of global optimization in univariate loss functions. For the performance evaluation, we study the cumulative regret of the algorithm instead …
global-optimizationEfficient 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 t…
global-optimizationDerivative-Free Global Optimization Algorithms: Bayesian Method and Lipschitzian Approaches
In this paper, we will provide an introduction to the derivative-free optimization algorithms which can be potentially applied to train deep learning models. Existing deep learning model training is mostly based on the b…
Deep Learningglobal-optimizationDerivative-Free Global Optimization Algorithms: Population based Methods and Random Search Approaches
In this paper, we will provide an introduction to the derivative-free optimization algorithms which can be potentially applied to train deep learning models. Existing deep learning model training is mostly based on the b…
Deep Learningglobal-optimization