基于调和权重的高维在线校准

arXiv:2610.07740v1 公告类型：交叉收录 摘要：我们研究任意凸集 $Y\subseteq\mathbb{R}^d$ 上的多维预测相对于任意误差范数 $\|\cdot\|_{L}$ 的在线校准问题。对于同时预测 $d$ 个二元结果的情形（$Y=[0,1]^d$），我们给出了首个对任意固定精度均能在关于 $d$ 的多项式轮数内实现 $\varepsilon$-校准的算法。该算法需要 $d^{O(1/\varepsilon)}$ 轮，将以往界限对维度的依赖改善了指数级。对于多类别预测（$Y=\Delta_d$），我们获得了相同的 $d^{O(1/\varepsilon)}$ 速率，改进了 Peng 和 Fishelson 等人的 $d^{\widetilde{O}(1/\varepsilon^2)}$ 界限。我们的算法很简单：在每一轮中，它输出一个以经过调和平滑的历史结果为支撑的调和加权分布。同一算法适用于所有预测集和范数。更一般地，该算法在 $\exp(O(\gamma(Y,L)/\varepsilon))$ 轮后实现 $\varepsilon$-校准，其中 $\gamma(Y,L)$ 是由一个矩阵差异度问题定义的几何参数。采用调和权重的动机在于，离散 Hilbert 变换矩阵能够同时对所有 $L$ 达到相差至多一个通用常数因子的最优差异度。这一最优性结果本身也可能具有独立的研究价值。