cs.LGNov 2, 2026

Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity

Authors: Jiuyao Lu, Georgy Noarov, Aaron Roth

Organizations: University of Pennsylvania · Institute for Advanced Study · Resolution

Abstract

Calibrated multiaccuracy asks that a predictor be globally calibrated and multiaccurate with respect to a bounded test family GG; that is, its residuals should be uncorrelated with every test g(x)∈Gg(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 Θ~(log⁡∣G∣ε2+1ε3)\widetildeΘ\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{3}}\right) when ∣G∣|G| is at least a sufficiently large power of log⁡(1/ε)\log(1/\varepsilon). We resolve the sample complexity of ε\varepsilon-calibrated multiaccuracy, showing that it scales as Θ~(log⁡∣G∣ε2+1ε5/2),\widetildeΘ\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 Θ~(log⁡∣G∣ε2+(log⁡∣G∣)1/3ε8/3)\widetildeΘ\left( \frac{\log|G|}{\varepsilon^2} + \frac{(\log|G|)^{1/3}}{\varepsilon^{8/3}} \right) whenever log⁡∣G∣=Ω(log⁡(1/ε))\log|G|=Ω(\log(1/\varepsilon)). When log⁡∣G∣≤ε−1+κ\log|G|\le\varepsilon^{-1+κ} for any fixed κ∈(0,1)κ\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∣\log|G| is intrinsic. At log⁡∣G∣≍ε−1\log|G|\asymp\varepsilon^{-1}, the minimax rates for randomized and deterministic calibrated multiaccuracy both coincide with the minimax rate for multicalibration.

Figures & tables

Explore similar work

CardsList
  1. Optimal Deterministic Multicalibration and Omniprediction

    Jun 18, 2026Georgy Noarov, Aaron RothMinimax EstimationModel Calibration

  2. The Sample Complexity of Multicalibration

    Apr 23, 2026Natalie Collina, Jiuyao Lu, Georgy Noarov +1Probability CalibrationSample Complexity

  3. Sample Complexity of Multicalibration for Multilevel Properties

    Aug 4, 2026Jiuyao Lu, Krishnakumar Balasubramanian, Aleksandr Podkopaev +1Sample ComplexityModel Calibration