用平方根熵分析概率预测的最小最大遗憾，揭示其几何本质。
On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy
- 引入平方根熵刻画无侧信息时的预测遗憾上界。
- 有侧信息时，上下界匹配，误差仅差对数因子。
- 适合研究统计学习理论与信息论交叉问题的研究者。
我们研究在对数损失下的序列概率分配问题，包括有和无侧信息的情形。目标是通过覆盖数和敏感尺度维度等几何量来分析最小最大遗憾。我们发现，无侧信息情形（等价于Shtarkov和）的最小最大遗憾可被序列平方根熵上界控制，该熵与Hellinger距离密切相关。对于带侧信息的序列概率分配问题，我们基于此熵建立了上下界。下界与上界在Donsker条件下（按我们定义的熵）匹配，仅相差对数因子。
原文摘要 · Abstract (English)
We study the problem of sequential probability assignment under logarithmic loss, both with and without side information. Our objective is to analyze the minimax regret -- a notion extensively studied in the literature -- in terms of geometric quantities, such as covering numbers and scale-sensitive dimensions. We show that the minimax regret for the case of no side information (equivalently, the Shtarkov sum) can be upper bounded in terms of sequential square-root entropy, a notion closely related to Hellinger distance. For the problem of sequential probability assignment with side information, we develop both upper and lower bounds based on the aforementioned entropy. The lower bound matches the upper bound, up to log factors, for classes in the Donsker regime (according to our definition of entropy).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。