Efficient Lipschitzian Global Optimization of Hölder Continuous Multivariate Functions

Abstract

This study presents an effective global optimization technique designed for multivariate functions that are Hölder continuous. Unlike traditional methods that construct lower bounding proxy functions, this algorithm employs a predetermined query creation rule that makes it computationally superior. The algorithm's performance is assessed using the average or cumulative regret, which also implies a bound for the simple regret and reflects the overall effectiveness of the approach. The results show that with appropriate parameters the algorithm attains an average regret bound of $O(T^{-\frac{\alpha }{n}})$ for optimizing a Hölder continuous target function with Hölder exponent $\alpha$ in an $n$-dimensional space within a given time horizon $T$. We demonstrate that this bound is minimax optimal.

this work draws from arXiv:2206.02383