Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions
This work addresses the challenge of non-convex optimization in high-dimensional spaces, offering a computationally superior method for researchers and practitioners in optimization and machine learning.
The authors tackled the problem of global optimization for multivariate Lipschitz continuous functions by proposing an efficient algorithm that achieves a minimax optimal average regret bound of O(L√n T^{-1/n}), where n is the dimension and T is the time horizon.
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.