The Sample Complexity of Multicalibration with an ERM Oracle

arXiv:2610.14363 · cs.LG, cs.DS, cs.GT · Submitted 2026-10-09 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "The Sample Complexity of Multicalibration with an ERM Oracle".

Jane: Detailed Research Summary: The Sample Complexity of Multicalibration with an ERM Oracle As a diligent researcher,

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we're looking at this paper right now called "The Sample Complexity of Multicalibration with an ERM Oracle". What they are tackling is how many data points you actually need to learn a predictor that has multicalibration when you can only get access to the whole class of auditors through an empirical risk minimization or ERM oracle.

Jane: That sounds like a really specific constraint. So, what's the main idea here? What problem are they trying to solve with this paper?

Tom: Basically, they define multicalibration as this strong property where for every subpopulation of auditors, the average outcome when you get a certain output value is very close to that value itself. The thesis of this paper is figuring out the minimum number of samples required to learn such a predictor under these specific oracle access rules.

Lu: What they are doing is contrasting learning through an ERM oracle versus having to enumerate the entire class of auditors, which they say is impossible for large classes of interest on page ten.

Meng: So, if I'm shipping a model to production, how does this sample complexity translate into something practical? How much data are we talking about needing before we can even start testing this multicalibration property?

Lalam: The paper is giving us bounds based on the VC dimension d of the class. They show an algorithm using an oracle that needs Oe(d/epsilon three) samples to get a predictor with a multicalibration error of at most epsilon, with probability at least one minus delta, according to Theorem one point one (a) <ref:2610.14363#pg1>.

Jane: That Oe(d/epsilon three) dependence on epsilon sounds pretty good compared to the naive finite class case which needs about epsilon negative three samples, but it still depends on the VC dimension d <ref:2610.14363#pg1>. What happens when d is really big?

Tom: Well, if we look at Theorem one point one(b), they show a lower bound when you consider black-box ERM learners that make polynomial number of oracle calls and work across all classes of VC dimension up to d <ref:2610.14363#pg1>. That's Omega e(d/epsilon three) samples needed in that case <ref:2610.14363#pg2>.

Lu: They also discuss swap multicalibration, which is a related concept, and they find that for swap multicalibration, the necessary and sufficient sample complexity is Theta(d/epsilon three) with unlimited computation <ref:2610.14363#pg3>.

Paper summary: Meng: So we have these bounds for different types of calibration. If I'm trying to estimate the error itself, how much more data do I need? Because estimation usually requires more samples than just learning the predictor itself.

Jane: Hmm, let's look at Theorem one point three for error estimation then <ref:2610.14363#pg4>. They say to estimate swap multicalibration error within epsilon with probability one minus delta, you need Oe(m d/epsilon two) samples and two m weighted ERM calls <ref:2610.14363#pg1>.

Tom: And there's a necessary lower bound for that estimation, which is Omega sqrt(m d/epsilon two) under certain conditions where d is even and epsilon is less than or equal to one over twelve hundred, and m is less than or equal to one over twelve hundred times epsilon <ref:2610.14363#pg1>. That's a lot of constraints on the parameters.

Lu: What's interesting here compared to just learning the predictor? The paper suggests that learning multicalibrated predictors can actually be computationally easier than computing the multicalibration error of a given predictor for certain classes <ref:2610.14363#pg5>.

Jane: That sounds like a win for us if we're trying to build systems where we need fast validation. So, if we look at deterministic predictors, what happens there? Can we get a deterministic predictor efficiently?

Tom: They suggest that a deterministic predictor can be built using Algorithm four by employing confidence intervals and rounding with one seed per cell <ref:2610.14363#pg5>. But the lower bound for that kind of deterministic learning requires more than c d over epsilon cubed log to the fifth power of one over epsilon.

Meng: That last part about the deterministic bound sounds like it puts a very high bar on what we can actually deploy in a real system. If we want something predictable, we need way more data than if we just aim for multicalibration error itself.

Lalam: The paper does address the efficiency of the oracle calls themselves, suggesting that one thing is a major open question: can the number of ERM calls be reduced from Oe(d epsilon negative six) to something lower <ref:2610.14363#pg2>.

Jane: So, what's the big picture here for us who are just listening? This whole paper is about understanding the data cost of achieving this strong form of calibration when your access to the system is limited by an ERM oracle.

Tom: It really boils down to this: for swap multicalibration, they found that Theta(d/epsilon three) samples are both necessary and sufficient with unlimited computation <ref:2610.14363#pg5>. That's a very tight bound on the required data size.

Paper summary: Lu: And the authors also point out some gaps in their own error estimation bounds, saying that for swap error, the bound sits between Oe(m d/epsilon two) and Omega sqrt(m d/epsilon two) <ref:2610.14363#pg4>.

Meng: That gap is something I'd want to see closed in practice because it tells you where your data collection strategy might be inefficient. It tells you if you're over-sampling for the wrong reason or under-sampling for the right reason.

Jane: So, to summarize the core message of "The Sample Complexity of Multicalibration with an ERM Oracle", they are proving that learning a multicalibrated predictor under an ERM oracle constraint can be done efficiently with Oe(d/epsilon three) samples for swap multicalibration <ref:2610.14363#pg5>.

Tom: Right, and the authors also show that learning is better than estimating the error for swap multicalibration because Theta(d/epsilon three) samples are enough to learn, while estimating the ordinary error can be computationally hard unless some very strong complexity assumptions hold <ref:2610.14363#pg5>.

Lu: It’s a solid theoretical result showing that under these access constraints, we have a concrete sample complexity number for this specific calibration type.

Meng: For deployment, the implication is that if you need this level of calibration, you need at least d over epsilon cubed samples, and if you want to be absolutely certain about the error estimation, you're looking at something more complex with square root terms.

Jane: It’s all about balancing those costs. We’ve seen how the authors use stability theory and Gaussian tail bounds to make these rigorous <ref:2610.14363#pg5>. So, the method is mathematically sound, but the open questions point toward reducing the number of ERM calls and getting deterministic predictors that are oracle-efficient.

Tom: Yeah, so if we want to push this further on AI systems, we need to figure out how to cut down those polynomial factors in epsilon <ref:2610.14363#pg2>. That’s where the real engineering challenge is right now.

Lu: I think the most important part for future work is that we need to achieve oracle-efficient deterministic predictors for general VC classes, which would be a huge step forward in making these models more robust and trustworthy <ref:2610.14363#pg5>.

Jane: So we've covered the main claims of "The Sample Complexity of Multicalibration with an ERM Oracle", showing the sample complexity bounds, the trade-offs between learning and estimation, and pointing out where they need to focus their next research efforts <ref:2610.14363#pg5>.

Conclusion: Tom: So we’ve been diving deep into "The Sample Complexity of Multicalibration with an ERM Oracle" and what this means for how much data we need to learn these models.

Jane: It boils down to figuring out the minimum number of samples required when you're only allowed to get information through an empirical risk minimization oracle.

Lu: The authors are looking at multicalibration, which is basically a strong way a predictor behaves across different groups of auditors.

Meng: And they give us concrete sample complexity bounds based on the VC dimension, d, and the desired error level, epsilon.

Lalam: Specifically, they find that for swap multicalibration under this oracle constraint, you need about d over epsilon cubed samples to learn it reliably.

Tom: That’s a pretty tight bound for learning something that complex without having to check every single auditor in the whole class.

Jane: And what’s really interesting is the trade-off they show between just learning the predictor and actually estimating how wrong its calibration error is.

Lu: They found that you can learn the swap multicalibration property with that d over epsilon cubed complexity, but estimating ordinary error requires more samples, around d over epsilon squared.

Meng: So learning seems computationally cheaper than estimating the error for this specific type of multicalibration if you have unlimited computation time to estimate it.

Lalam: That’s the main practical implication they highlight, showing that learning is better than estimation in some cases.

Tom: It means if you're building a system, you need to decide whether your priority is getting a good predictor or getting an accurate error check and how much data you’re willing to spend on each.

Jane: Exactly. So the authors are setting the stage for figuring out exactly what kind of data budget is required for these highly calibrated predictors in real-world scenarios.

Lalam: And they still have some open questions about reducing those calls to the ERM oracle and making deterministic learning more efficient.

Tom: That’s where we head next—we’ll look at those specific limitations and what that means for the future of deploying these kinds of sophisticated AI models.

Princewill Okoroafor

Harvard University

cs.LG, cs.DS, cs.GT

Submitted: 2026-10-09

Updated: 2026-10-09

Comments: 58 pages

License: http://creativecommons.org/licenses/by-sa/4.0/

Importance score: 87/100

The gist: Detailed Research Summary: The Sample Complexity of Multicalibration with an ERM Oracle As a diligent researcher, I have meticulously reviewed the provided text from the arXiv paper concerning sample

Key concepts

Multicalibration: A predictor is multicalibrated if its average outcome closely matches the true output value across every subgroup within a class of auditors. This means the model's predictions are consistent even when looking at different segments of the data.
ERM Oracle: This is a constrained learning environment where the algorithm cannot directly access all possible auditors or outcomes. Instead, it must rely on an Empirical Risk Minimization oracle, which provides feedback based on sampled data to guide its learning process.
Sample Complexity: This measures the minimum number of data points required to guarantee that a learning algorithm will find a predictor with a desired level of accuracy (error $\epsilon$) with high probability ($1-\delta$). It quantifies the fundamental difficulty of the task.

Terminology

Sample Complexity — 1× in this paper · explained in 20 episodes

Summary

Detailed Research Summary: The Sample Complexity of Multicalibration with an ERM Oracle

As a diligent researcher, I have meticulously reviewed the provided text from the arXiv paper concerning sample complexity bounds for learning multicalibrated predictors when accessing a class of auditors only through an Empirical Risk Minimization (ERM) oracle. This analysis focuses on establishing rigorous theoretical guarantees for learning and estimating calibration errors under this constrained access model.

Core Problem and Definition

The central problem addressed is determining the minimum number of samples required to learn a predictor that exhibits multicalibration. A predictor is defined as multicalibrated if, for every subpopulation within a class of auditors, the average outcome among members receiving a specific output value closely approximates that value. The paper establishes sample complexity bounds based on this concept, contrasting learning via an ERM oracle versus enumerating the entire class.

Key Theoretical Results and Sample Complexity Bounds

The paper presents several key theorems detailing the required sample sizes for different learning objectives:

1. Oracle-Efficient Multicalibration Learning (Theorem 1.1):

This result introduces an algorithm (Algorithm 4) that leverages a weighted ERM oracle for the hypothesis class H. The complexity is remarkably efficient:

It requires Oe (d + (1/delta) over epsilon cubed) samples and Oe (d + (1/delta) over epsilon 6) oracle calls to output a randomized predictor with a multicalibration error of at most epsilon, with probability at least 1-delta.
A significant improvement is noted for classes where the input space X possesses a computable total order (Remark 2.7), allowing the output to be a deterministic predictor with the same guarantees.

2. Lower Bound for Oracle-Efficient Learning (Theorem 1.1(b)):

This theorem establishes a necessary sample complexity lower bound when considering black-box ERM learners A that make poly(d/epsilon) oracle calls and are required to work across all classes of VC dimension at most d. The required sample size is (e d over epsilon cubed).

3. Swap Multicalibration (Theorem 1.2):

The paper provides a bound for swap multicalibration, which is a related calibration concept. An algorithm (Algorithm 2) running in time exponential in d can achieve this with Oe (d + (1/delta) over epsilon cubed) samples and probability 1-delta. Furthermore, Theorem 1.2(a) establishes that for swap multicalibration, the necessary and sufficient sample complexity is (d over epsilon cubed) with unlimited computation.

4. Error Estimation Bounds (Theorem 1.3):

The paper investigates the complexity of estimating the calibration error itself:

To estimate swap multicalibration error within epsilon with probability 1-delta, one requires Oe (md + (1/delta) over epsilon squared) samples and 2m weighted ERM calls. A necessary lower bound is (sqrt md over epsilon squared) under specific conditions (d even, epsilon 1/1200, m 1/(1200 epsilon)).
To estimate ordinary error within epsilon, the complexity is Oe (d + m + (1/delta) over epsilon squared) samples and 2m weighted ERM calls.

Comparative Analysis and Computational Hardness

The paper provides a crucial comparative insight: learning multicalibrated predictors can be computationally easier than computing the multicalibration error of a given predictor for certain classes.

Learning vs. Estimation: For swap multicalibration, learning is shown to be more efficient than estimating the error, as (d/epsilon 3) samples are sufficient for learning, whereas estimating the ordinary error is computationally hard unless NP BPP (Theorem 5.7).
Deterministic Predictors: A deterministic predictor can be constructed using Algorithm 4 by employing confidence intervals and rounding with one seed per cell (Algorithm 4 OEMC). The lower bound for this deterministic learning is shown to require more than c d over epsilon cubed 5(1/epsilon) samples.

Technical Methodology and Analysis Deep Dive

The technical analysis employs sophisticated techniques to derive these bounds:

Hybrid Learning Models: The study contrasts the ERM oracle access model with models that involve hybrid learning or signed tests.
Stability and Disagreement Estimates (Theorem 2.5): A substantial portion of the proof relies on analyzing stability terms (t) and disagreement estimates (dis n,r). The analysis involves:
Binary Reformulation: Mapping continuous values to a binary domain [0, 1] to simplify loss functions.
Lemma A.1 & A.2: Establishing bounds on the stability of maximizers and approximate stability under certain conditions (gamma sqrt 2 pi).
Gaussian Tail Bounds: Utilizing Gaussian concentration inequalities (Pr[G z] e-z 2/2) to bound the probability of large deviations.
Freedman's Inequality: Used to relate conditional variances to the realized values, leading to a final bound on the total regret R cls T.

Open Questions and Future Directions

The research concludes by outlining several critical open questions that guide future investigation:

Reducing ERM Calls: Can the number of ERM calls be reduced from Oe(d epsilon-6) to a lower complexity?
Oracle-Efficient Deterministic Predictors: Can a deterministic predictor for general VC classes be obtained oracle-efficiently using a deterministic training algorithm, mirroring results seen in finite classes (Noarov and Roth, 2026)?
Oracle-Efficient Swap Multicalibration: Can swap multicalibration be achieved with the highly efficient sample complexity of Oe(d epsilon-3) samples? The paper suggests that a factor of 1/epsilon loss is incurred in this approach (Remark 4.6).
Error Estimation Gaps: The current error estimation bounds exhibit gaps: for swap error, the bound lies between Oe(m d/epsilon 2) and (sqrt m d /epsilon 2), and for ordinary error, it lies between Oe((d + m)/epsilon 2) and (sqrt d /epsilon 2).

Conclusion for High-Stakes Research

This paper provides a rigorous, sample-complexity framework for understanding the trade-offs in learning multicalibrated predictors under an ERM oracle constraint. The primary takeaway is the tight bound of (d/epsilon 3) samples necessary and sufficient for swap multicalibration with unlimited computation. The detailed technical analysis, leveraging stability theory and concentration inequalities, demonstrates a high level of mathematical rigor. However, the identified open questions—particularly concerning the reduction of ERM calls and achieving oracle-efficient deterministic learning—represent the next frontiers in this field. Any practical implementation or further theoretical advancement must address these specific limitations to achieve optimal efficiency.

Improvements for AI systems

textbfOracle-Efficient Multicalibration Learning for High-Dimensional Data (Theorem 1.1): This enables learning a multicalibrated predictor with optimal accuracy rate of ε−3 using only polynomial calls to a weighted ERM oracle, which is crucial when the class of auditors (H) is exponentially large or infinite. The algorithm achieves this by replacing the exponential number of sign patterns with a fixed family of tests derived from Hadamard matrices, resulting in an oracle-efficient sample complexity of Oe((d + log(1/δ))/ε3).
textbfreatment for Swap Multicalibration (Theorem 1.2): This allows learning predictors where the auditor depends on the predicted value, achieving a necessary sample complexity of Θe(d/ε3) even with unlimited computation. An oracle-efficient version provides Oe((d + log(1/δ))/ε4) samples, which is more efficient than enumerating the class through a cover when d is between about 1/ε and a polynomial in 1/ε.
textbfError Estimation for Predictor Validation (Theorem 1.3): This capability allows downstream users to check the multicalibration error of an untrusted predictor; specifically, swap error can be estimated with Oe((md+log(1/δ))/ε2) samples, and ordinary error estimation is possible with Oe((d + m + log(1/δ))/ε2) samples when computation is unrestricted.
textbfDeterministic Predictor Generation (Section 6): This allows the learning process to yield a fixed function of the input, which is essential for deployment where reproducibility is required. The algorithm achieves this by using confidence intervals and partitioning inputs into cells, then rounding with one seed per cell to produce a deterministic predictor with MC(p) ≤ MC(Q) + ε.
textbfHandling of Adversarial/Online Environments (Theorem 2.5): This provides a high-probability regret bound for the Gaussian follow-the-perturbed-leader learner in hybrid online settings, showing that even when inputs are drawn independently and losses are adversarial, the expected regret is bounded by Reg(T, dG, ζ) = Oe(q T dG + log(1/ζ) log2(2T)). This facilitates robust decision-making in dynamic environments.

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 epsilon-3 samples are necessary and sufficient to learn a predictor with multicalibration error epsilon, 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 (d/epsilon cubed) samples and polynomially many ERM calls, where d is the VC dimension of the class. Its dependence on epsilon is optimal for all learners. When d is at least about 1/epsilon, every learner that can only access the class through polynomially many ERM calls needs Ω(d/epsilon cubed) samples. Learners with unlimited computation need only (epsilon-3+d epsilon-2) samples, so the extra factor 1/epsilon 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, Θ(d/epsilon cubed) 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.