论文标题
通过截短的贝叶斯算法，精确的遗憾损失范围
Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm
论文作者
论文摘要
我们研究了在对数损失下，与一定类的专家相比，在对数损失下，顺序一般的在线回归（也称为顺序概率分配）。我们专注于获得紧密的，经常匹配的，下限和上限，以定义为连续的minimax遗憾，这些遗憾被定义为一类专家造成的多余损失。在证明了一般的上限之后，我们考虑了一些从Lipschitz类到有限的Hessian类的特定专家类别，并以可证明的最佳常数得出匹配的下限和上限。我们的界限可用于广泛的数据维度值和回合的数量。为了获得下限，我们使用信息理论（例如Shtarkov Sum）中的工具，对于上限，我们求助于专家类别的新“平滑截断覆盖”。这使我们可以通过应用简单且新颖的截断贝叶斯算法来找到建设性的证据。我们的证明比现有的证据要简单得多，但提供了更紧密（通常是最佳）范围。
We study the sequential general online regression, known also as the sequential probability assignments, under logarithmic loss when compared against a broad class of experts. We focus on obtaining tight, often matching, lower and upper bounds for the sequential minimax regret that are defined as the excess loss it incurs over a class of experts. After proving a general upper bound, we consider some specific classes of experts from Lipschitz class to bounded Hessian class and derive matching lower and upper bounds with provably optimal constants. Our bounds work for a wide range of values of the data dimension and the number of rounds. To derive lower bounds, we use tools from information theory (e.g., Shtarkov sum) and for upper bounds, we resort to new "smooth truncated covering" of the class of experts. This allows us to find constructive proofs by applying a simple and novel truncated Bayesian algorithm. Our proofs are substantially simpler than the existing ones and yet provide tighter (and often optimal) bounds.
