Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization
This work provides theoretical guarantees for global optimization algorithms, which is important for researchers and practitioners in optimization and machine learning, though it appears incremental as it builds on existing algorithms with new regret analyses.
The paper tackles the problem of global optimization by analyzing the cumulative regret of the Piyavskii-Shubert algorithm and its variants, showing that for L-Lipschitz continuous functions, the cumulative regret is O(L log T), and for H-Lipschitz smooth functions, it is O(H), with extensions to broader function classes achieving nearly minimax optimal regret.
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 is the difference of the losses between the best estimate up to $T$ and the global minimum), we study the cumulative regret up to time $T$. For $L$-Lipschitz continuous functions, we show that the cumulative regret is $O(L\log T)$. For $H$-Lipschitz smooth functions, we show that the cumulative regret is $O(H)$. We analytically extend our results for functions with Holder continuous derivatives, which cover both the Lipschitz continuous and the Lipschitz smooth functions, individually. We further show that a simpler variant of the Piyavskii-Shubert algorithm performs just as well as the traditional variants for the Lipschitz continuous or the Lipschitz smooth functions. We further extend our results to broader classes of functions, and show that, our algorithm efficiently determines its queries; and achieves nearly minimax optimal (up to log factors) cumulative regret, for general convex or even concave regularity conditions on the extrema of the objective (which encompasses many preceding regularities). We consider further extensions by investigating the performance of the Piyavskii-Shubert variants in the scenarios with unknown regularity, noisy evaluation and multivariate domain.