# Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity

DevFeed: [Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity](<https://devfeed.tech/articles/calibrated-multiaccuracy-deterministic-and-randomized-sample-complexity-114786.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.03305>)

Author: Jiuyao Lu, Georgy Noarov, Aaron Roth

Published: 2026-11-03T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [Calibrated uncertainty](<https://devfeed.tech/topics/calibrated-uncertainty.md>)

Tags: [complexity](<https://devfeed.tech/tags/complexity.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [math-st](<https://devfeed.tech/tags/math-st.md>), [sample](<https://devfeed.tech/tags/sample.md>), [stat-th](<https://devfeed.tech/tags/stat-th.md>)

## AI overview

Calibrated multiaccuracy has randomized sample complexity \(\widetilde\Theta(\log|G|/\varepsilon^2+1/\varepsilon^{5/2})\), improving on the stated multicalibration rate in relevant regimes. For deterministic predictors, the tight rate is \(\widetilde\Theta(\log|G|/\varepsilon^2+ (\log|G|)^{1/3}/\varepsilon^{8/3})\) when \(\log|G|=\Omega(\log(1/\varepsilon))\). The deterministic rate is polynomially larger when \(\log|G|\le\varepsilon^{-1+\kappa}\) for fixed \(0<\kappa<1\), establishing a separation between predictor types. At \(\log|G|\asymp\varepsilon^{-1}\), both calibrated multiaccuracy rates coincide with the multicalibration minimax rate. Matching bounds show the cube-root dependence on \(\log|G|\) is intrinsic.

## Source excerpt

arXiv:2611.03305v1 Announce Type: new Abstract: 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.