提出高效算法实现可诱导属性的交换多校准，显著提升公平预测精度。
Efficient Swap Multicalibration of Elicitable Properties
- 将多校准扩展至任意有界假设类，引入更强的交换多校准概念
- 在高概率下实现 $T^{1/(r+1)}$ 的 $oldsymbol{oldsymbol{ ext{ℓ}_r}}$ 交换多校准误差（$r \≥ 2$）
- 对 $r=2$ 时达 $T^{1/3}$ 误差，解决开放问题并优于已有方法
多校准 [HJKRR18] 是一种算法公平性视角，要求预测值在自身和群体子集条件下保持准确。[NR23] 建立了任意属性 $Γ$（如均值或中位数）的多校准与属性诱导之间的联系：当且仅当 $Γ$ 可被诱导时，其可被多校准。在线设置下，[NR23] 提出一个低效算法，在 $T$ 轮交互后实现 $\sqrt{T}$ $\ell_2$-多校准误差，针对群组成员函数假设类与可诱导属性 $Γ$。本文将多校准从群组成员函数推广至任意有界假设类，引入更强的交换多校准（swap multicalibration），并提出一个预言机高效的算法。该算法利用在线鲁棒学习器，对具有有界序列 Rademacher 复杂度的假设类和可诱导属性 $Γ$，以高概率实现 $T^{1/(r+1)}$ $\ell_r$-交换多校准误差（$r \geq 2$）。当 $r=2$ 时，误差为 $T^{1/3}$，显著优于先前结果 [NR23, GMS25, LSS25a]，并完全正面回答了 [GJRR24] 关于是否存在能实现 $\sqrt{T}$ $\ell_2$-均值多校准的预言机高效算法这一开放问题。
原文摘要 · Abstract (English)
Multicalibration [HJKRR18] is an algorithmic fairness perspective that demands that the predictions of a predictor are correct conditional on themselves and membership in a collection of potentially overlapping subgroups of a population. The work of [NR23] established a surprising connection between multicalibration for an arbitrary property $Γ$ (e.g., mean or median) and property elicitation: a property $Γ$ can be multicalibrated if and only if it is elicitable, where elicitability is the notion that the true property value of a distribution can be obtained by solving a regression problem over the distribution. In the online setting, [NR23] proposed an inefficient algorithm that achieves $\sqrt T$ $\ell_2$-multicalibration error for a hypothesis class of group membership functions and an elicitable property $Γ$, after $T$ rounds of interaction between a forecaster and adversary. In this paper, we generalize multicalibration for an elicitable property $Γ$ from group membership functions to arbitrary bounded hypothesis classes and introduce a stronger notion -- swap multicalibration, following [GKR23]. Subsequently, we propose an oracle-efficient algorithm which, when given access to an online agnostic learner, achieves $T^{1/(r+1)}$ $\ell_r$-swap multicalibration error with high probability (for $r\ge2$) for a hypothesis class with bounded sequential Rademacher complexity and an elicitable property $Γ$. For the special case of $r=2$, this implies an oracle-efficient algorithm that achieves $T^{1/3}$ $\ell_2$-swap multicalibration error, which significantly improves on the previously established bounds for the problem [NR23, GMS25, LSS25a], and completely resolves an open question raised in [GJRR24] on the possibility of an oracle-efficient algorithm that achieves $\sqrt{T}$ $\ell_2$-mean multicalibration error by answering it in a strongly affirmative sense.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。