提出新算法，显著提升公平预测与损失最小化的在线与分布设置性能。
Improved Bounds for Swap Multicalibration and Swap Omniprediction
- 设计高效算法，实现 $T^{1/3}$ 的 $oldsymbol{ ext{swap multicalibration}}$ 误差。
- 首次达成 $T^{2/3}$ 误差，优于之前的 $T^{7/8}$ 上界。
- 适用于需要高精度公平学习的场景，如风险评估与推荐系统。
本文研究多校准（multicalibration）——一种多群体公平性概念，以及全能预测（omniprediction）——一种同时最小化损失的范式，涵盖分布设置与在线设置。近期工作提出开放问题：能否在有界线性函数下高效实现 $O(\ oot{2}\\text{)}$ 误差？本文以肯定回答：提出一种高效算法，在高概率与期望意义下实现 $O(T^{1/3})$ 的 $oldsymbol{ ext{swap multicalibration}}$ 误差。该结果进一步推动了 $oldsymbol{ ext{swap omniprediction}}$ 和 $oldsymbol{ ext{ℓ₁}}$-swap multicalibration 的优化，分别达到 $O(T^{2/3})$，优于此前 $O(T^{7/8})$ 的最佳上界。由此改进的在线结果，还带来了分布设置下的样本复杂度提升：对凸且 Lipschitz 函数类，学习 $oldsymbol{ ext{ε}}$-swap omnipredictor 的样本复杂度为 $O(\varepsilon^{-3})$；对平方损失，$oldsymbol{ ext{ε}}$-swap agnostic learner 为 $O(\varepsilon^{-2.5})$；对线性函数，$oldsymbol{ ext{ℓ₁, ℓ₂}}$-swap multicalibrated predictor 分别为 $O(\varepsilon^{-5})$、$O(\varepsilon^{-2.5})$，均显著优于已有最优结果。
原文摘要 · Abstract (English)
In this paper, we consider the related problems of multicalibration -- a multigroup fairness notion and omniprediction -- a simultaneous loss minimization paradigm, both in the distributional and online settings. The recent work of Garg et al. (2024) raised the open problem of whether it is possible to efficiently achieve $O(\sqrt{T})$ $\ell_{2}$-multicalibration error against bounded linear functions. In this paper, we answer this question in a strongly affirmative sense. We propose an efficient algorithm that achieves $O(T^{\frac{1}{3}})$ $\ell_{2}$-swap multicalibration error (both in high probability and expectation). On propagating this bound onward, we obtain significantly improved rates for $\ell_{1}$-swap multicalibration and swap omniprediction for a loss class of convex Lipschitz functions. In particular, we show that our algorithm achieves $O(T^{\frac{2}{3}})$ $\ell_{1}$-swap multicalibration and swap omniprediction errors, thereby improving upon the previous best-known bound of $O(T^{\frac{7}{8}})$. As a consequence of our improved online results, we further obtain several improved sample complexity rates in the distributional setting. In particular, we establish a $O(\varepsilon ^ {-3})$ sample complexity of efficiently learning an $\varepsilon$-swap omnipredictor for the class of convex and Lipschitz functions, $O(\varepsilon ^{-2.5})$ sample complexity of efficiently learning an $\varepsilon$-swap agnostic learner for the squared loss, and $O(\varepsilon ^ {-5}), O(\varepsilon ^ {-2.5})$ sample complexities of learning $\ell_{1}, \ell_{2}$-swap multicalibrated predictors against linear functions, all of which significantly improve on the previous best-known bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。