The Sample Complexity of Multicalibration with an ERM Oracle

arXiv:2610.14363v1 Announce Type: new Abstract: A predictor is multicalibrated with respect to a class of subpopulations (formally, of functions on the inputs, called auditors) if, for every subpopulation in the class and every value the predictor outputs, the average outcome among the members of that subpopulation who receive that value is close to the value itself. For finite classes, about arepsilon^{-3} samples are necessary and sufficient to learn a predictor with multicalibration error arepsilon, but the algorithms that attain this rate enumerate the class, which is impossible for the large classes of interest. We ask how many samples suffice when the learner accesses the class only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses ilde{O}(d/arepsilon^{3}) samples and polynomially many ERM calls, where d is the VC dimension of the class. Its dependence on arepsilon is optimal for all learners. When d is at least about 1/arepsilon, every learner that can only access the class through polynomially many ERM calls needs ilde{Omega}(d/arepsilon^{3}) samples. Learners with unlimited computation need only ilde{O}(arepsilon^{-3}+darepsilon^{-2}) samples, so the extra factor 1/arepsilon on the dimension term is the price of oracle efficiency. For swap multicalibration, which allows a different function from the class for each predicted value, ilde{Theta}(d/arepsilon^{3}) samples are necessary and sufficient. For estimating the error of a given predictor, the ordinary notion is the harder one: the swap error can be estimated with an ERM oracle, whereas the ordinary error is NP-hard to approximate even for classes with linear-time ERM. Consequently, there are classes for which it is computationally easier to learn a multicalibrated predictor than to compute the multicalibration error of a given predictor.

Source: arXiv cs.LG | 2026-10-14

Related