Calibrated multiaccuracy sample complexity differs for random and deterministic predictors
Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity
Machine LearningData Structures and Algorithms
Summary
This paper studies how many examples are needed to train a predictor that is both accurate on average and well calibrated across different groups defined by tests in a set. The authors find that allowing the predictor to be randomized can reduce the number of samples needed compared to deterministic predictors. They precisely characterize the sample sizes for both types of predictors and show that the difference is intrinsic to the problem. This clarifies how calibration and accuracy requirements affect learning complexity differently for random and fixed prediction methods.
What this means in practice
- •For machine learning engineers: Determine the minimum data needed for training calibrated predictors with guarantees on accuracy and fairness using either fixed or randomized algorithms.
- •For statistical learning system designers: Assess whether to employ randomized or deterministic predictive models based on sample size limitations and calibration goals in complex testing scenarios.
A theory result. No direct application yet.
Authors
Jiuyao Lu, Georgy Noarov, Aaron Roth
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Θ\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Θ\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Θ\left( \frac{\log|G|}{\varepsilon^2} + \frac{(\log|G|)^{1/3}}{\varepsilon^{8/3}} \right) $$ whenever $\log|G|=Ω(\log(1/\varepsilon))$. When $\log|G|\le\varepsilon^{-1+κ}$ for any fixed $κ\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.