arXiv:2505.17365cs.LGcs.DS2025-05中稿 · ICML

提出更高效方法,直接实现在线l1多校准的最优收敛速度。

Improved and Oracle-Efficient Online $\ell_1$-Multicalibration

  • 将l1多校准转化为线性-乘积在线优化问题
  • 获得T^{-1/3}和T^{-1/4}的改进收敛率
  • 支持无限群体且计算高效,适合大规模公平预测

我们研究在线多校准框架,旨在对抗环境下确保多个群体的预测校准性,持续T轮。尽管在线校准通常在l1范数下分析,但以往方法通过其他范数(如l2、l∞)间接获得保证并转换至l1,导致性能损失。本文提出直接方法,首次实现l1多校准的改进与高效率:分别为T^{-1/3}和T^{-1/4}(带对数因子)。核心洞察是将在线l1多校准归约为具有乘积奖励的在线学习问题,称作在线线性-乘积优化(OLPO)。为达到T^{-1/3}速率,我们线性化OLPO并设计无遗憾算法;但当群体族H较大或无限时计算成本高。为此,我们提出第二种方法,仅需多项式次数调用离线多校准评估预言机,实现预言机高效的在线l1多校准,速率达T^{-1/4}。该框架还扩展至某些无限群体族(如上下文空间上的所有线性函数),利用l1多校准误差关于群体族H的1-Lipschitz性质。

原文摘要 · Abstract (English)

We study \emph{online multicalibration}, a framework for ensuring calibrated predictions across multiple groups in adversarial settings, across $T$ rounds. Although online calibration is typically studied in the $\ell_1$ norm, prior approaches to online multicalibration have taken the indirect approach of obtaining rates in other norms (such as $\ell_2$ and $\ell_{\infty}$) and then transferred these guarantees to $\ell_1$ at additional loss. In contrast, we propose a direct method that achieves improved and oracle-efficient rates of $\widetilde{\mathcal{O}}(T^{-1/3})$ and $\widetilde{\mathcal{O}}(T^{-1/4})$ respectively, for online $\ell_1$-multicalibration. Our key insight is a novel reduction of online \(\ell_1\)-multicalibration to an online learning problem with product-based rewards, which we refer to as \emph{online linear-product optimization} ($\mathtt{OLPO}$). To obtain the improved rate of $\widetilde{\mathcal{O}}(T^{-1/3})$, we introduce a linearization of $\mathtt{OLPO}$ and design a no-regret algorithm for this linearized problem. Although this method guarantees the desired sublinear rate (nearly matching the best rate for online calibration), it is computationally expensive when the group family \(\mathcal{H}\) is large or infinite, since it enumerates all possible groups. To address scalability, we propose a second approach to $\mathtt{OLPO}$ that makes only a polynomial number of calls to an offline optimization (\emph{multicalibration evaluation}) oracle, resulting in \emph{oracle-efficient} online \(\ell_1\)-multicalibration with a rate of $\widetilde{\mathcal{O}}(T^{-1/4})$. Our framework also extends to certain infinite families of groups (e.g., all linear functions on the context space) by exploiting a $1$-Lipschitz property of the \(\ell_1\)-multicalibration error with respect to \(\mathcal{H}\).

在线学习多校准公平性优化

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