论文标题
预期的最坏情况是通过随机顺序覆盖
Expected Worst Case Regret via Stochastic Sequential Covering
论文作者
论文摘要
我们研究了在一般损失函数下随机生成的特征的顺序预测和在线minimax遗憾的问题。我们介绍了一个预期的最坏情况下的概念minimax遗憾的是，概括并涵盖了先前已知的minimax遗憾。对于这样的极小遗憾的是，我们通过随机全局顺序覆盖的新颖概念建立了紧密的上限。我们表明，对于Vc-Dimension $ \ Mathsf {Vc} $和$ I.I.D. $生成的长度$ T $的特征的假设类别，随机全局顺序覆盖的基数可以在上限上具有高概率（WHP），$ e^{然后，我们通过引入一种称为Star-Littlestone维度的新复杂度度量来改善这一束缚，并表明具有Star-Littlestone dimension $ \ Mathsf {Slsf {Slsf {Sl} $的类，接纳了$ e^{O（\ Mathsf {slssf {sl}} \ cdot \ log t）的随机全局顺序覆盖。我们进一步建立了具有有限脂肪的数字的真实有价值类的上限。最后，通过应用固定设计minimax遗憾的信息理论工具，我们为预期的最坏情况下的最小值遗憾提供了下限。我们通过对预期的最坏情况下的最小情况遗憾的对数损失和一般可混合损失的遗憾来证明我们的方法的有效性。
We study the problem of sequential prediction and online minimax regret with stochastically generated features under a general loss function. We introduce a notion of expected worst case minimax regret that generalizes and encompasses prior known minimax regrets. For such minimax regrets we establish tight upper bounds via a novel concept of stochastic global sequential covering. We show that for a hypothesis class of VC-dimension $\mathsf{VC}$ and $i.i.d.$ generated features of length $T$, the cardinality of the stochastic global sequential covering can be upper bounded with high probability (whp) by $e^{O(\mathsf{VC} \cdot \log^2 T)}$. We then improve this bound by introducing a new complexity measure called the Star-Littlestone dimension, and show that classes with Star-Littlestone dimension $\mathsf{SL}$ admit a stochastic global sequential covering of order $e^{O(\mathsf{SL} \cdot \log T)}$. We further establish upper bounds for real valued classes with finite fat-shattering numbers. Finally, by applying information-theoretic tools of the fixed design minimax regrets, we provide lower bounds for the expected worst case minimax regret. We demonstrate the effectiveness of our approach by establishing tight bounds on the expected worst case minimax regrets for logarithmic loss and general mixable losses.
