Expected Worst Case Regret via Stochastic Sequential Covering
Expected Worst Case Regret via Stochastic Sequential Covering
复制标题
通过随机顺序覆盖预期的最坏情况遗憾
DOI：
10.48550/arxiv.2209.04417
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Wojtek Szpankowski
中科院分区：
文献类型：
--
作者：
Changlong Wu;Mohsen Heidari;A. Grama;Wojtek Szpankowski
研究了一般损失函数下随机生成特征的序贯预测和在线极小极大后悔问题。我们引入了一个概念，预期最坏情况下的极大极小遗憾，概括和包括以前已知的极大极小遗憾。对于这种极大极小遗憾，我们通过随机全局序列覆盖的新概念建立了严格的上界。我们证明了，对于VC维$\mathsf{VC}$和$i.i.d.$的假设类，生成的长度为$T$的特征，随机全局序列覆盖的基数可以通过$e^{O（\mathsf{VC} \cdot\log^2 T）}$以高概率（whp）上界。然后，我们通过引入一个新的称为Star-Littlestone维数的复杂性度量来改进这个界，并证明具有Star-Littlestone维数$\mathsf{SL}$的类允许一个随机全局序列覆盖，其阶为$e^{O（\mathsf{SL} \cdot \log T）}$。我们进一步建立上界的真实的值类有限脂肪粉碎数。最后，通过应用信息论工具的固定设计极大极小遗憾，我们提供了预期的最坏情况极大极小遗憾的下限。我们证明了我们的方法的有效性，通过建立严格的界限预期最坏情况下的极大极小的对数损失和一般的混合损失的遗憾。
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.
具有分类特征值的 Logistic 回归的精确 Minimax Regret
DOI：
--
发表时间：
2021
期刊：
2021
影响因子：
--
作者：
Jacquet, P.
通讯作者：
Jacquet, P.
在线和差异化私人学习的平滑分析
DOI：
--
发表时间：
2020
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Haghtalab, Nika;Roughgarden, Tim;Shetty, Abhishek
通讯作者：
Shetty, Abhishek