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.