Efficient Swap Multicalibration of Elicitable Properties

摘要

Multicalibration (Hébert-Johnson et al., 2018) is an algorithmic fairness perspective which 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 Noarov and Roth (2023) 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 adversarial (online) setting, Noarov and Roth (2023) proposed an inefficient algorithm that achieves 𝒪̃(√(T)) ℓ_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 Gopalan et al. (2023b). Subsequently, we propose an oracle-efficient algorithm which when given access to an online agnostic learner, achieves 𝒪̃(T^1/r+1) ℓ_r-swap multicalibration error with high probability (r ≥ 2) 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) ℓ_2-swap multicalibration error, which significantly improves on the previously established bounds for the problem (Noarov and Roth, 2023; Ghuge et al., 2025; Luo et al., 2025a), and completely resolves an open question raised in Garg et al. (2024) on the possibility of an oracle-efficient algorithm that achieves 𝒪̃(√(T)) ℓ_2-mean multicalibration error by answering it in a strongly affirmative sense.