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

Jun 18, 2026

Optimal Deterministic Multicalibration and Omniprediction

A model is multicalibrated on a collection of group weights GG if it is calibrated -- i.e. unbiased even conditional on its prediction -- not just overall, but also after reweighting contexts by each g∈Gg \in G. It is a useful property for many downstream applications and is a basic desideratum of trustworthy machine learning. Before this work, all predictors known to attain the minimax-optimal O~(ε−3)\widetilde O(\varepsilon^{-3}) sample complexity rate for ε\varepsilon-multicalibration were randomized, while deterministic predictors were known only with substantially worse sample complexity. Whether randomization is necessary for optimal sample complexity in multicalibration was explicitly asked by [CLNR26] and implicitly in several prior works. We resolve this open problem by giving a minimax-optimal multicalibration algorithm that outputs a deterministic predictor. We then generalize the algorithm to produce optimal deterministic predictors that satisfy outcome indistinguishability (OI) with respect to finite or finitely covered collections of tests. As an application, this also gives deterministic omnipredictors and panpredictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].
Apr 23, 2026

The Sample Complexity of Multicalibration

We study the minimax sample complexity of multicalibration in the batch setting. A learner observes nn i.i.d. samples from an unknown distribution and must output a (possibly randomized) predictor whose population multicalibration error, measured by Expected Calibration Error (ECE), is at most ε\varepsilon with respect to a given family of groups. For every fixed κ>0κ> 0, in the regime ∣G∣≤ε−κ|G|\le \varepsilon^{-κ}, we prove that Θ~(ε−3)\widetildeΘ(\varepsilon^{-3}) samples are necessary and sufficient, up to polylogarithmic factors. The lower bound holds even for randomized predictors, and the upper bound is realized by a randomized predictor obtained via an online-to-batch reduction. This separates the sample complexity of multicalibration from that of marginal calibration, which scales as Θ~(ε−2)\widetildeΘ(\varepsilon^{-2}), and shows that mean-ECE multicalibration is as difficult in the batch setting as it is in the online setting, in contrast to marginal calibration which is strictly more difficult in the online setting. In contrast we observe that for κ=0κ= 0, the sample complexity of multicalibration remains Θ~(ε−2)\widetildeΘ(\varepsilon^{-2}) exhibiting a sharp threshold phenomenon. More generally, we establish matching upper and lower bounds, up to polylogarithmic factors, for a weighted LpL_p multicalibration metric for all 1≤p≤21 \le p \le 2, with optimal exponent 3/p3/p. We also extend the lower-bound template to a regular class of elicitable properties, and combine it with the online upper bounds of Hu et al. (2025) to obtain matching bounds for calibrating properties including expectiles and bounded-density quantiles.
Aug 4, 2026

Sample Complexity of Multicalibration for Multilevel Properties

Calibration requires a predictor to be unbiased after conditioning on its own predictions. Multicalibration asks for this guarantee simultaneously across a collection of groups. Many prediction tasks ask for several related features of the same conditional outcome distribution: variance is defined relative to the mean, skewness relative to both mean and variance, and conditional value at risk relative to a quantile. We study multicalibration for a sequence of kk properties in which each property is identifiable once the preceding properties are fixed. This framework includes Bayes pairs but does not require the properties to arise from a single loss. For every fixed k≥2k\ge2, we establish matching upper and lower sample-complexity bounds up to logarithmic factors under regularity conditions. Even with only polylogarithmically many binary groups, achieving multicalibration error ε\varepsilon requires Ω~(ε−(k+2))\widetildeΩ(\varepsilon^{-(k+2)}) samples. Conversely, for any finite group family G\mathcal G, we give a randomized learner using O(ε−(k+2)+ε−2log⁡∣G∣)O(\varepsilon^{-(k+2)}+\varepsilon^{-2}\log|\mathcal G|) samples. Thus the sample complexity is Θ~(ε−(k+2))\widetildeΘ(\varepsilon^{-(k+2)}) for polynomial-size group families. We instantiate the theory for three canonical examples.