论文标题
弃权在线预测的快速费率
Fast Rates for Online Prediction with Abstention
论文作者
论文摘要
在设置单个$ \ {0，1 \} $的顺序预测中，带有专家建议的序列，我们表明，通过支付小于$ \ frac 12 $（例如，$ 0.49 $）的费用来允许学习者放弃预测，就可以实现与时间hive hive hive hive hive hive hive hive hive hive $ t $ t $ t $ t $ t $。我们确切地描述了对弃权成本$ c $的依赖性和专家$ n $的数量，通过提供订单$ \ frac {\ log n} {1-2c} $的上限和下限，这与最佳的$ \ sqrt {t \ log n} $相反，这是与Absstain无用的最佳速度。我们还讨论了我们的模型的各种扩展，包括一个环境，弃权成本的顺序可以随着时间的推移任意变化，在某些自然假设上，我们在弃权成本的某些自然假设下，表现出遗憾的界限。
In the setting of sequential prediction of individual $\{0, 1\}$-sequences with expert advice, we show that by allowing the learner to abstain from the prediction by paying a cost marginally smaller than $\frac 12$ (say, $0.49$), it is possible to achieve expected regret bounds that are independent of the time horizon $T$. We exactly characterize the dependence on the abstention cost $c$ and the number of experts $N$ by providing matching upper and lower bounds of order $\frac{\log N}{1-2c}$, which is to be contrasted with the best possible rate of $\sqrt{T\log N}$ that is available without the option to abstain. We also discuss various extensions of our model, including a setting where the sequence of abstention costs can change arbitrarily over time, where we show regret bounds interpolating between the slow and the fast rates mentioned above, under some natural assumptions on the sequence of abstention costs.
