Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity
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 ; that is, its residuals should be uncorrelated with every test . This weakening of multicalibration suffices for many applications. Its sample complexity was not known to improve on that of full multicalibration, which is when is at least a sufficiently large power of . We resolve the sample complexity of -calibrated multiaccuracy, showing that it scales as 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 whenever . When for any fixed , 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 is intrinsic. At , the minimax rates for randomized and deterministic calibrated multiaccuracy both coincide with the minimax rate for multicalibration.
Figures & tables
Sample Complexity
Sample complexity studies how many data points, queries, or observations are needed to learn, estimate, test, or sample to a target accuracy.
See all 110 papers