arXiv:2607.28856cs.LG2026-07被引 2

提出高效方法实现对正确损失函数的交换无关学习,提升预测后处理能力。

Fast Rates for Swap-Agnostic Learning of Proper Losses

  • 将交换无关学习转化为二阶多校准问题,利用伯恩斯坦方差修正优化
  • 在有限假设类上实现近最优风险率,离线为 $\widetilde{O}((\log |H|/m)^{2/3})$
  • 适用于多种损失函数族,特别对凸光滑损失有更强性能保障

交换无关学习通过允许比较器在学习者预测的每个取值层级选择不同假设,增强了经典广义学习。该基准捕捉了依赖预测结果的后处理行为,但传统上需为每个预测值求解独立的广义学习问题。本文证明,对于正确损失,这些层级比较可联合控制。主要成果是:针对任意固定正确损失,提出一种离线交换无关学习算法;在 $m$ 个独立同分布样本下,额外风险为 $\widetilde{O}((\log |H|/m)^{2/3})$;在线情形下,交换遗憾为 $\widetilde{O}(T^{1/3}("log |H|)^{2/3})$。同时给出可同时适应整个损失族的算法:对所有取值于 $[-1,1]$ 的正确损失,获得 $\widetilde{O}(\sqrt{T\log |H|})$(在线)和 $\widetilde{O}(\sqrt{\log |H|/m})$(离线)的速率;对凸、1-利普希茨正确损失,进一步提升至 $\widetilde{O}(T^{1/3}("log |H|)^{2/3})$(在线)和 $\widetilde{O}((\log |H|/m)^{2/3})$(离线)。这些界在对数因子内紧致,并优于洛等人(2025)所暗示的 $\widetilde{O}(T^{2/3}("log |H|)^{1/3})$ 界。核心技术贡献是通过带伯恩斯坦风格方差修正的布莱克韦尔可接近性,将交换无关学习归约为二阶多校准。

原文摘要 · Abstract (English)

Swap-agnostic learning strengthens classical agnostic learning by allowing the comparator to select a different hypothesis on each level set of the learner's predictions. This benchmark captures prediction-dependent postprocessing, but appears to require solving a separate agnostic-learning problem for every possible prediction value. We show that, for proper losses, these prediction-level comparisons can instead be controlled jointly. Our main result is an offline swap-agnostic learner for any fixed proper loss. For a finite hypothesis class $H$ and any fixed smooth proper loss, the excess risk from $m$ i.i.d. samples is $\widetilde{O}((\log |H|/m)^{2/3})$, with a corresponding online swap-regret bound of $\widetilde{O}(T^{1/3}(\log |H|)^{2/3})$. We also give algorithms whose predictions are simultaneously swap-agnostic for entire families of losses. For all proper losses bounded in $[-1,1]$, we obtain online and offline rates of $\widetilde{O}(\sqrt{T\log |H|})$ and $\widetilde{O}(\sqrt{\log |H|/m})$, respectively. For convex, $1$-Lipschitz proper losses, these rates improve to $\widetilde{O}(T^{1/3}(\log |H|)^{2/3})$ online and $\widetilde{O}((\log |H|/m)^{2/3})$ offline. These bounds are tight up to logarithmic factors and improve upon the $\widetilde{O}(T^{2/3}(\log |H|)^{1/3})$ rate implied by the swap-omniprediction guarantee of Luo et al. (2025). Our main technical contribution is a reduction from swap-agnostic learning to a second-order form of multicalibration, obtained via Blackwell approachability with a Bernstein-style variance correction.

学习理论在线学习正确损失

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。