Efficient Lipschitzian Global Optimization of Hölder Continuous Multivariate Functions
This provides an efficient solution for global optimization in high-dimensional spaces, though it is incremental as it builds on existing regret-based frameworks.
The paper tackles the problem of globally optimizing multivariate Hölder continuous functions by introducing an algorithm that uses a predetermined query creation rule, achieving a minimax optimal average regret bound of O(T^{-α/n}) for a given time horizon T.
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α{n}})$ for optimizing a Hölder continuous target function with Hölder exponent $α$ in an $n$-dimensional space within a given time horizon $T$. We demonstrate that this bound is minimax optimal.