Metraipolis › archive › dc_ea175a7c7a4e
Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity — arXiv:2611.03305
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03305
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:23:11.730Z
- SHA-256 of the archived text
a34dc83f4fe7ce3af92e3016118744a1fbf0963f9c4085e0cbcb49acd2e58455- Stable URL of this page
https://metraipolis.com/documento/dc_ea175a7c7a4e
How to cite
Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity — arXiv:2611.03305 — arXiv (en), https://arxiv.org/abs/2611.03305 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ea175a7c7a4e (Metraipolis archive dc_ea175a7c7a4e, sha256 a34dc83f4fe7ce3af92e3016118744a1fbf0963f9c4085e0cbcb49acd2e58455)
BibTeX
@misc{dcea175a7c7a4e,
title = {Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity — arXiv:2611.03305},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03305},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ea175a7c7a4e; sha256 a34dc83f4fe7ce3af92e3016118744a1fbf0963f9c4085e0cbcb49acd2e58455},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03305. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Calibrated multiaccuracy asks that a predictor be globally calibrated and multiaccurate with respect to a bounded test family $G$; that is, its residuals should be uncorrelated with every test $g(x)\in G$. This weakening of multicalibration suffices for many applications. Its sample complexity was not known to improve on that of full multicalibration, which is $\widetilde\Theta\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{3}}\right)$ when $|G|$ is at least a sufficiently large power of $\log(1/\varepsilon)$. We resolve the sample complexity of $\varepsilon$-calibrated multiaccuracy, showing that it scales as $$ \widetilde\Theta\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{5/2}}\right), $$ separating it from the complexity of multicalibration. The upper bound is obtained by an algorithm that outputs a randomized predictor. For deterministic predictors, we establish the tight rate $$ \widetilde\Theta\left( \frac{\log|G|}{\varepsilon^2} + \frac{(\log|G|)^{1/3}}{\varepsilon^{8/3}} \right) $$ whenever $\log|G|=\Omega(\log(1/\varepsilon))$. When $\log|G|\le\varepsilon^{-1+\kappa}$ for any fixed $\kappa\in(0,1)$, this rate is polynomially larger than the rate for randomized predictors. Thus, unlike for multicalibration, calibrated multiaccuracy exhibits a genuine sample-complexity separation between deterministic and randomized predictors. The matching upper and lower bounds show that the unusual cube-root dependence on $\log|G|$ is intrinsic. At $\log|G|\asymp\varepsilon^{-1}$, the minimax rates for randomized and deterministic calibrated multiaccuracy both coincide with the minimax rate for multicalibration.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Data Structures and Algorithms (cs.DS); Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2611.03305 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:02:37.692Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).