Efficient Swap Multicalibration of Elicitable Properties

Lunjia Hu, Haipeng Luo, Spandan Senapati, Vatsal Sharan
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3314-3348, 2026.

Abstract

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 $\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 adversarial (online) setting, Noarov and Roth (2023) proposed an inefficient algorithm that achieves $\tilde{\mathcal{O}}(\sqrt{T})$ $\ell_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 Gopalan et al. (2023b). Subsequently, we propose an oracle-efficient algorithm which when given access to an online agnostic learner, achieves $\tilde{\mathcal{O}}(T^{\frac{1}{r+1}})$ $\ell_r$-swap multicalibration error with high probability ($r \ge 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 $\tilde{\mathcal{O}}(T^{\frac{1}{3}})$ $\ell_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 $\tilde{\mathcal{O}}(\sqrt{T})$ $\ell_2$-mean multicalibration error by answering it in a strongly affirmative sense.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-hu26b, title = {Efficient Swap Multicalibration of Elicitable Properties}, author = {Hu, Lunjia and Luo, Haipeng and Senapati, Spandan and Sharan, Vatsal}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {3314--3348}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/hu26b/hu26b.pdf}, url = {https://proceedings.mlr.press/v336/hu26b.html}, abstract = {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 $\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 adversarial (online) setting, Noarov and Roth (2023) proposed an inefficient algorithm that achieves $\tilde{\mathcal{O}}(\sqrt{T})$ $\ell_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 Gopalan et al. (2023b). Subsequently, we propose an oracle-efficient algorithm which when given access to an online agnostic learner, achieves $\tilde{\mathcal{O}}(T^{\frac{1}{r+1}})$ $\ell_r$-swap multicalibration error with high probability ($r \ge 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 $\tilde{\mathcal{O}}(T^{\frac{1}{3}})$ $\ell_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 $\tilde{\mathcal{O}}(\sqrt{T})$ $\ell_2$-mean multicalibration error by answering it in a strongly affirmative sense.} }
Endnote
%0 Conference Paper %T Efficient Swap Multicalibration of Elicitable Properties %A Lunjia Hu %A Haipeng Luo %A Spandan Senapati %A Vatsal Sharan %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-hu26b %I PMLR %P 3314--3348 %U https://proceedings.mlr.press/v336/hu26b.html %V 336 %X 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 $\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 adversarial (online) setting, Noarov and Roth (2023) proposed an inefficient algorithm that achieves $\tilde{\mathcal{O}}(\sqrt{T})$ $\ell_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 Gopalan et al. (2023b). Subsequently, we propose an oracle-efficient algorithm which when given access to an online agnostic learner, achieves $\tilde{\mathcal{O}}(T^{\frac{1}{r+1}})$ $\ell_r$-swap multicalibration error with high probability ($r \ge 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 $\tilde{\mathcal{O}}(T^{\frac{1}{3}})$ $\ell_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 $\tilde{\mathcal{O}}(\sqrt{T})$ $\ell_2$-mean multicalibration error by answering it in a strongly affirmative sense.
APA
Hu, L., Luo, H., Senapati, S. & Sharan, V.. (2026). Efficient Swap Multicalibration of Elicitable Properties. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:3314-3348 Available from https://proceedings.mlr.press/v336/hu26b.html.

Related Material