提出高效算法，实现近最优交换后悔值，突破此前理论瓶颈。
Near-optimal Swap Regret Minimization for Convex Losses
- 多尺度分箱机制同时使用不同粒度的区间进行随机预测
- 首次实现$ ilde{O}( oot{2}{T})$期望交换后悔，优于之前$O(T^{2/3})$
- 适用于中位数校准等场景，无需传统光滑性假设
我们提出一种随机在线算法，在单位区间上对任意自适应选择的李普希茨凸损失序列，可保证近似最优的$ ilde{O}( oot{2}{T})$期望交换后悔。该结果改进了先前$O(T^{2/3})$的最优界限，并回答了Fishelson等人[2025b]提出的开放问题。算法运行时间为多项式时间$ extsf{poly}(T)$。核心技术是将单位区间在多个粒度层级上离散化，同时使用所有层级进行随机预测，称为多尺度分箱，可能具有独立研究价值。作为直接推论，该结果给出了针对一般可诱导性质的校准误差最小化高效在线算法，不依赖以往所需的识别函数光滑性假设，首次为中位数校准提供了$ ilde{O}( oot{2}{T})$的误差保证。
原文摘要 · Abstract (English)
We give a randomized online algorithm that guarantees near-optimal $\widetilde O(\sqrt T)$ expected swap regret against any sequence of $T$ adaptively chosen Lipschitz convex losses on the unit interval. This improves the previous best bound of $\widetilde O(T^{2/3})$ and answers an open question of Fishelson et al. [2025b]. In addition, our algorithm is efficient: it runs in $\mathsf{poly}(T)$ time. A key technical idea we develop to obtain this result is to discretize the unit interval into bins at multiple scales of granularity and simultaneously use all scales to make randomized predictions, which we call multi-scale binning and may be of independent interest. A direct corollary of our result is an efficient online algorithm for minimizing the calibration error for general elicitable properties. This result does not require the Lipschitzness assumption of the identification function needed in prior work, making it applicable to median calibration, for which we achieve the first $\widetilde O(\sqrt T)$ calibration error guarantee.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。