The Sample Complexity of Multicalibration with an ERM Oracle
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 $\varepsilon^{-3}$ samples are necessary and sufficient to learn a predictor with multicalibration error $\varepsilon$, 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 $\tilde{O}(d/\varepsilon^{3})$ samples and polynomially many ERM calls, where $d$ is the VC dimension of the class. Its dependence on $\varepsilon$ is optimal for all learners. When $d$ is at least about $1/\varepsilon$, every learner that can only access the class through polynomially many ERM calls needs $\tildeΩ(d/\varepsilon^{3})$ samples. Learners with unlimited computation need only $\tilde{O}(\varepsilon^{-3}+d\varepsilon^{-2})$ samples, so the extra factor $1/\varepsilon$ 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, $\tildeΘ(d/\varepsilon^{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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper resolves key open questions regarding the sample complexity of multicalibration under oracle efficiency constraints, providing tight upper and lower bounds that define the theoretical limits of fair learning algorithms. It introduces novel techniques combining Hadamard tests with hybrid online learning to achieve optimal rates, and demonstrates the computational hardness of auditing multicalibration error, offering profound insights into the trade-offs between statistical efficiency and computational feasibility in fairness-aware machine learning.
Methodology
The paper presents a rigorous theoretical framework for understanding the sample complexity of multicalibration when the learner is restricted to using an Empirical Risk Minimization (ERM) oracle. The core methodological contribution is the development of an algorithm that achieves the optimal $\tilde{O}(d/\varepsilon^3)$ sample complexity for ordinary multicalibration, where $d$ is the VC dimension. This is achieved by replacing the exponential number of sign patterns required in previous enumeration-based approaches with a polynomial number of "signed tests" derived from Hadamard matrices. The authors cleverly combine this with a high-probability regret bound for Gaussian Follow-the-Perturbed-Leader (FTPL) in a hybrid online learning setting (random inputs, adversarial feedback). The paper also provides matching lower bounds, proving that this sample complexity is optimal for any learner making polynomially many ERM calls, thereby establishing a clear separation between oracle-efficient learning and enumeration-based learning. The extension to swap multicalibration and the analysis of error estimation (showing NP-hardness for ordinary error estimation) are also technically sound and well-supported.
Results & evaluation
As a pure theory paper, there are no empirical experiments. The "evaluation" consists of rigorous mathematical proofs of upper and lower bounds on sample complexity. The results are definitive within the theoretical model defined (VC dimension, ERM oracle access, distribution-free setting).
Reproducibility
The paper is fully reproducible in the sense that the algorithms are described in sufficient detail for implementation, and the theoretical guarantees are proven. The algorithms rely on standard oracles (ERM) which are well-defined. The deterministic predictor construction requires a computable total order on the input space, which is a standard assumption in such contexts.
Limitations
The results are theoretical and do not provide empirical validation on real-world datasets. The lower bounds rely on the assumption that the learner accesses the class only through polynomially many ERM calls; if a learner had unlimited computational power to enumerate the class (if finite), better rates are possible, but this is often infeasible for large classes. The NP-hardness result for error estimation applies to the worst-case scenario for specific classes, which may not reflect typical practical instances.
Broader impact
This paper significantly advances the understanding of the computational and statistical limits of fair machine learning. By establishing the optimal sample complexity for oracle-efficient multicalibration, it provides a benchmark for future algorithmic developments. The separation between learning and error estimation has important implications for the auditability of ML models, suggesting that verifying a model's fairness may be computationally harder than training a fair model. This insight is crucial for regulatory frameworks and practical deployment of fair AI systems. The paper resolves key open questions regarding the sample complexity of multicalibration under oracle efficiency constraints, providing tight upper and lower bounds that define the theoretical limits of fair learning algorithms. It introduces novel techniques combining Hadamard tests with hybrid online learning to achieve optimal rates, and demonstrates the computational hardness of auditing multicalibration error, offering profound insights into the trade-offs between statistical efficiency and computational feasibility in fairness-aware machine learning.
Author of this paper? Send a correction.