提出高概率下可收敛的在线预测方法，突破传统期望误差限制。
Online Prediction of Stochastic Sequences with High Probability Regret Bounds
- 设计新算法实现高概率下的渐近收敛
- 在概率至少1-δ下达到T⁻¹/²δ⁻¹/²的误差率
- 证明无法在不加假设下改进δ的指数阶数
我们重新审视已知有限时间窗口T的随机序列通用预测问题。研究目标是能否推导出在高概率下成立的消失性后悔界，以补充现有文献中仅在期望意义下成立的界限。本文提出了具有类似期望界形式的高概率后悔界。对于可数字母表上的随机过程通用预测情形，该界在概率至少1-δ下达到收敛速率O(T⁻¹/²δ⁻¹/²)，优于先前已知的期望界O(T⁻¹/²)。此外，我们还给出一个不可能性结果，证明在不引入额外假设的情况下，无法改进同类型界中δ的指数阶数。
原文摘要 · Abstract (English)
We revisit the classical problem of universal prediction of stochastic sequences with a finite time horizon $T$ known to the learner. The question we investigate is whether it is possible to derive vanishing regret bounds that hold with high probability, complementing existing bounds from the literature that hold in expectation. We propose such high-probability bounds which have a very similar form as the prior expectation bounds. For the case of universal prediction of a stochastic process over a countable alphabet, our bound states a convergence rate of $\mathcal{O}(T^{-1/2} δ^{-1/2})$ with probability as least $1-δ$ compared to prior known in-expectation bounds of the order $\mathcal{O}(T^{-1/2})$. We also propose an impossibility result which proves that it is not possible to improve the exponent of $δ$ in a bound of the same form without making additional assumptions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。