20年首次突破！序贯校准误差降到0.6629次方
Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$
📖 AI 总结
本文研究二元结果的序贯概率预测中的校准问题，即预测概率是否与经验结果频率相符。Foster和Vohra提出的期望累积ℓ₁校准误差O(T^{2/3})上界曾主导该领域二十余年，此后Dagan等人虽将指数2/3降低，但未给出具体常数。作者针对“带复用的符号保持博弈”提出一种新的两阶段递归标记策略，得到形如O(n^α t^β)的界，适用于任意空间与时间参数选择；同时改进Dagan等人的归约方法，将所需符号保持博弈实例数降至O(log T)。结合两项改进并选取显式可行参数，作者首次给出低于2/3的显式指数界O(T^{0.662942288})。该结果使序贯校准的收敛速率首次获得明确可计算的改进，对在线学习与博弈论交叉领域具有理论意义。
🔑 关键词速览
| 序贯校准 | 在序贯预测中，要求预测概率与长期结果频率一致的性质。 |
| ℓ1-校准误差 | 衡量预测概率与经验频率之间绝对差异的累积指标。 |
| 符号保持博弈 | 一种用于分析校准问题的博弈论模型，涉及保持符号的决策。 |
| 两阶段递归标记策略 | 本文提出的新策略，通过递归标记实现符号保持，用于改进校准界。 |
| 归约 | 将一个问题转化为另一个问题的技术，这里指将符号保持上界转化为校准上界。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅