  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.

Machine Learning;Optimization and Control