标题： Piyavskii--Shubert算法及其变种在全局优化中的累积遗憾分析 显示英文标题

标题： Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization

摘要： 我们研究全局优化问题，其中分析了Piyavskii--Shubert算法及其变体的性能。 对于任何给定的时间持续时间$T$，而不是广泛研究的简单遗憾（这是到$T$为止的最佳估计与全局最小值之间的损失差），我们研究到时间$T$的累积遗憾。 对于$L$-Lipschitz连续函数，我们证明累积遗憾是$O(L\log T)$。 对于$H$-Lipschitz光滑函数，我们证明累积遗憾是$O(H)$。 我们分析地扩展了对具有Holder连续导数的函数的结果，这些函数分别涵盖了Lipschitz连续和Lipschitz光滑函数。 我们进一步表明，Piyavskii-Shubert算法的一个更简单的变体在Lipschitz连续或Lipschitz光滑函数的情况下表现与传统变体一样好。 我们将结果进一步扩展到更广泛的函数类，并表明，我们的算法有效确定其查询；并且在目标函数极值上的广义凸性或甚至凹性正则条件下，实现了几乎最小最大最优（考虑对数因子）的累积遗憾，这涵盖了许多先前的正则性。 我们进一步通过研究Piyavskii-Shubert变体在未知正则性、噪声评估和多变量域场景下的性能来扩展研究。 显示英文摘要

摘要： 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.