Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity
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)∈ G. This weakening of multicalibration suffices for many applications. Its sample complexity was not known to improve on that of full multicalibration, which is Θ̃(log|G|/ε2 + 1/ε3) when |G| is at least a sufficiently large power of log(1/ε). We resolve the sample complexity of ε-calibrated multiaccuracy, showing that it scales as Θ̃(log|G|/ε2 + 1/ε5/2), 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 Θ̃( log|G|/ε2 + (log|G|)1/3/ε8/3 ) whenever log|G|=Ω(log(1/ε)). When log|G|≤ε−1+κ for any fixed κ∈(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ε−1, the minimax rates for randomized and deterministic calibrated multiaccuracy both coincide with the minimax rate for multicalibration.
Related
- An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
- High-resolution Calibrated Probabilistic Hourly Precipitation from a Deterministic Forecast
- Exponential Deterministic Query Complexity of Goldstein Stationarity
- Calibrated Predictive Distributions from Sample-Based Generators
- SCOPE Before You Sample: Conformal Scores Guide Posterior Exploration for Fast and Calibrated Bayesian Predictive Inference
BibTeX
@misc{lu2026calibrated,
title = {{Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity}},
author = {Jiuyao Lu and Georgy Noarov and Aaron Roth},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03305},
eprint = {2611.03305},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03305},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity
AU - Jiuyao Lu
AU - Georgy Noarov
AU - Aaron Roth
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03305
UR - https://arxiv.org/abs/2611.03305
AB - 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)∈ G. This weakening of multicalibration suffices for many applications. Its sample complexity was not known to improve on that of full multicalibration, which is Θ̃(log|G|/ε^2 + 1/ε^3) when |G| is at least a sufficiently large power of log(1/ε). We resolve the sample complexity of ε-calibrated multiaccuracy, showing that it scales as Θ̃(log|G|/ε^2 + 1/ε^5/2), 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 Θ̃( log|G|/ε^2 + (log|G|)^1/3/ε^8/3 ) whenever log|G|=Ω(log(1/ε)). When log|G|≤ε^−1+κ for any fixed κ∈(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ε^−1, the minimax rates for randomized and deterministic calibrated multiaccuracy both coincide with the minimax rate for multicalibration.
ER -