Efficient Swap Multicalibration of Elicitable Properties

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 Gamma (e.g., mean or median) and property elicitation: a property Gamma 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 √ T ℓ2-multicalibration error for a hypothesis class of group membership functions and an elicitable property Gamma, after T rounds of interaction between a forecaster and adversary. In this paper, we generalize multicalibration for an elicitable property Gamma 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 T1/(r+1) ℓr-swap multicalibration error with high probability (for r≥2) for a hypothesis class with bounded sequential Rademacher complexity and an elicitable property Gamma. For the special case of r=2, this implies an oracle-efficient algorithm that achieves T1/3 ℓ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 √T ℓ2-mean multicalibration error by answering it in a strongly affirmative sense.