动态调整预测网格，让在线多校准算法自动适应不同难易程度的数据。
Instance-Adaptive Online Multicalibration
- 根据数据复杂度自适应细化预测分组网格，实现动态优化。
- 最坏情况下误差为 $ ilde{O}(T^{2/3})$，随机场景下可降至 $ ilde{O}( oot ext{2} rown{T})$。
- 适合处理非平稳、分段平稳等复杂实际场景，对群体公平性建模有帮助。
我们研究了在线多校准在最坏情况之外的表现。提出一种单一高效算法，通过自适应地精炼二叉网格来动态平衡良性与最坏情况序列。其误差由细化树的叶子数控制。分析表明，该算法在最坏情况下恢复了已知的 $ ilde{O}(T^{2/3})$ 最优率，同时能自动适应更简单的情形：在边际随机设定下达到 $ ilde{O}( oot ext{2} rown{T})$ 的速率，对于具有 $J$ 个片段的分段平稳均值，速率为 $ ilde{O}( oot ext{2} rown{JT})$。更一般地，速率依赖于可预测均值过程相对于群体族的阈值复杂度测度，且该依赖关系在对数因子内是紧的。
原文摘要 · Abstract (English)
We study online multicalibration beyond the worst-case. We give a single, efficient algorithm which dynamically interpolates between benign and worst-case sequences by adaptively refining a dyadic grid of prediction values. Its error is controlled by the number of leaves in the refinement tree. Our analysis recovers the known $\widetilde O(T^{2/3})$ worst-case-optimal rate for online multicalibration, while simultaneously automatically adapting to easier instances: in the marginal stochastic setting it obtains a rate of $\widetilde O(\sqrt T)$, and for piecewise-stationary means with $J$ segments its rate is $\widetilde O(\sqrt{JT})$. More generally, the rate depends on a threshold-complexity measure of the predictable mean process relative to the group family. We show that this dependence is tight up to logarithmic factors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。