Optimal Deterministic Multicalibration and Omniprediction Georgy Noarov University of Pennsylvania
Aaron Roth University of Pennsylvania
arXiv:2606.20557v1 [cs.LG] 18 Jun 2026
June 19, 2026
Abstract A model is multicalibrated on a collection of group weights G if it is calibrated—i.e. unbiased even conditional on its prediction—not just overall, but also after reweighting contexts by each g ∈ G. It is a useful property for many downstream applications and is a basic desideratum of trustworthy machine learning. Before this work, all algorithms known to attain the minimaxe −3 ) sample complexity rate for ε-multicalibration output randomized predictors, optimal O(ε while deterministic predictors were known only with substantially worse sample complexity. Whether randomization is necessary for optimal sample complexity in multicalibration was explicitly asked by Collina et al. [2026c] and implicitly in several prior works. We resolve this open problem by giving a minimax-optimal multicalibration algorithm that outputs a deterministic predictor. We then generalize the algorithm to produce deterministic predictors that satisfy outcome indistinguishability with respect to finite or finitely covered collections of tests. As an application, this also gives deterministic omnipredictors and panpredictors with optimal sample complexity, resolving open problems posed by Okoroafor et al. [2025] and Balakrishnan et al. [2026].
Contents 1 Introduction 1.1 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Additional Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 2 3 7
2 Setting and calibration definitions 2.1 Distributions, atoms, and conditional means . . . . . . . . . . . . . . . . . . . . . . 2.2 Grid predictors and ECE multicalibration . . . . . . . . . . . . . . . . . . . . . . .
9 9 9
3 Learning a randomized predictor from valid interval hints
10
4 Learning the interval hints from repeated contexts
13
5 Building the finite list of rounding cells
14
6 Rounding the randomized predictor
16
7 Putting the deterministic learner together
19
8 Outcome indistinguishability and omniprediction 22 8.1 Finite OI test families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 8.2 Omniprediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 A Deferred online-to-batch proofs
33
B Factored implementation and query representation
34
C Concentration for learned interval hints
35
D Deferred proof for finite OI tests
37
E Deterministic panprediction from OI tests
38
F Removing training randomness
40
1
Introduction
Calibration and multicalibration. A predictor is calibrated if, conditional on the value it predicts, that value equals the expected outcome [Dawid, 1982]. The standard quantitative measure of miscalibration is the expected calibration error (ECE) which sums the magnitude of the prediction-conditional bias across all predicted values. Multicalibration [Hebert-Johnson et al., 2018] strengthens calibration by requiring it to hold not just marginally but simultaneously after reweighting by every group function in a collection G. The ECE multicalibration error is then the maximum, over groups g ∈ G, of the group-weighted ECE (Definition 2.2). Since its introduction, multicalibration and closely related notions have found a wide range of applications— from learning predictors that are simultaneously optimal for many loss functions [Gopalan et al., 2022, 2023a, Noarov et al., 2025, Roth and Shi, 2024], to strengthening complexity-theoretic constructions [Dwork and Tankala, 2025, Casacuberta et al., 2024], to low-complexity algorithms for agreement and information aggregation [Collina et al., 2025, 2026a, Kearns et al., 2026]—which motivates a sharp understanding of what it costs to achieve. Omniprediction. A closely connected goal is omniprediction [Gopalan et al., 2022]: learning a single predictor that can be simultaneously and cheaply post-processed to optimize a wide variety of downstream loss functions in a way that is competitive with some benchmark class of models— avoiding the need to train a separate predictor for each loss function. Multicalibration is one route towards omniprediction: Gopalan et al. [2022] show that a predictor with ε-ECE multicalibration error with respect to an appropriately defined class of groups is also an ε-omnipredictor. Recent work gives more direct routes through outcome indistinguishability (OI)1 [Gopalan et al., 2023a, Garg et al., 2024, Okoroafor can be obtained via online √ et al., 2025]: indeed, omniprediction √ e T ), equivalently average error O(1/ e algorithms with regret O( T ) [Garg et al., 2024, Okoroafor et al., 2025, Gibbs and Tibshirani, 2026], which is impossible for (multi)calibration [Qiao and Valiant, 2021, Dagan et al., 2025, Collina et al., 2026b,c], and so the two problems are distinct. Randomized versus deterministic predictors. In the batch setting, a learner sees n i.i.d. samples from an unknown distribution P over context–outcome pairs and must output a predictor whose population multicalibration error with respect to G is at most ε. Collina et al. [2026c] e −3 ) (in the regime established the minimax optimal sample complexity of ε-multicalibration as Θ(ε in which |G| lies anywhere between polylog(1/ε) and poly(1/ε)). Their lower bound holds for all algorithms, randomized or not, but their upper bound follows from online-to-batch reductions that output randomized predictors [Gupta et al., 2022, Noarov et al., 2025, Ghuge et al., 2025]. Gupta et al. [2022], who gave the first sample-complexity upper bounds for multicalibration via online-to-batch reductions, already noted that the best known bounds were achieved by randomized predictors. Haghtalab et al. [2023] emphasized the same point, and Collina et al. [2026c] explicitly asked whether the minimax sample complexity of multicalibration can be achieved by a learner whose output predictor is deterministic. For the closely related problem of multi-distribution learning [Peng, 2024, Zhang et al., 2024], randomized predictors can be statistically easier to learn than deterministic predictors, and recent work shows that derandomization can also be 1
The original paper of Dwork et al. [2021] defines a hierarchy of outcome-indistinguishability notions and tests, depending on the access given to distinguishers. Throughout this paper, outcome indistinguishability refers to their “one-sample sample-access” notion, in which a test sees a context, the prediction on that context, and one outcome drawn either from Nature or from the predictor-induced outcome model.
1
computationally hard in the fully general setting [Larsen et al., 2024]. Is multicalibration another setting where randomization gives a statistical advantage? The question is important because prediction-time randomness complicates auditing, reproducibility, and downstream decision-making. It also sits uneasily with multicalibration as a notion of “trustworthiness”: two identical individuals can receive different predictions from a randomized predictor solely because it flips different coins. The same issue arises for omniprediction. The sample-optimal omnipredictors of Okoroafor et al. [2025] are obtained by online-to-batch reductions and output randomized predictors, leading them to ask explicitly whether these omnipredictors can be derandomized, or whether randomness is necessary for sample-optimal omniprediction. Similarly, Balakrishnan et al. [2026] ask the same question for panprediction (a group conditional notion of omniprediction) for which the same seeming sample complexity gap between deterministic and randomized predictors arises. Quantitatively, the best prior deterministic rates were substantially worse than the randomized ones. Translating the deterministic multicalibration guarantee of Haghtalab et al. [2023, Theoe −6 ), while the optimal rem 4.2] to ECE multicalibration gives a sample complexity of about O(ε −3 e randomized rate is O(ε ) [Collina et al., 2026c]. For omniprediction, Okoroafor et al. [2025] obtain 2 ) rates for broad bounded-variation loss classes, where d is the relevant e sample-optimal O(d/ε complexity of the loss-derived auditor class, but their construction outputs randomized predictors. Earlier deterministic constructions had much worse dependence on ε—for example, the rate recalled by Okoroafor et al. [2025, Theorem C.1] for Gopalan et al. [2023a] scales as O(d/ε4 + ε−10 log(1/ε)). Gibbs and Tibshirani [2026] give a direct, deterministic, and sample-optimal result for the special case of proper losses—but their construction uses specific structural properties of proper losses and does not extend to the general case. We resolve all of these questions and show that prediction-time randomization is not necessary for sample-optimal multicalibration, omniprediction, or panprediction, or more generally for outcome indistinguishability: deterministic predictors can attain the minimax optimal sample complexity for each.
1.1
Our results
Throughout, when stating simplified rates, we assume that the group/constraint/benchmark e hides family has polynomially bounded cardinality: |G| ≤ ε−κ for a fixed constant κ, and O(·) polylogarithmic factors in 1/ε and |G|. In the body we allow the learner to use randomness during training, while its output is always a fixed deterministic function. Appendix F shows that this remaining training randomness can also be removed, with only logarithmic changes in the sample bounds. 1. Optimal Deterministic Multicalibration (Theorem 7.1). We give an algorithm that outputs a deterministic predictor h with ECE multicalibration error at most ε using 1/ε + log |G| e n=O ε2 e −3 ), matching the minimax optimal rate [Collina et al., 2026c]. We also samples. This is O(ε show how to implement the learning algorithm in polynomial time. 2. Optimal Deterministic Outcome Indistinguishability (Theorem 8.2). We then generalize our result to any finite family A of bounded outcome-indistinguishability tests a : X × [0, 1] → 2
[−1, 1]. The algorithm uses e O
log |A| ε2
samples and outputs a deterministic predictor h satisfying max |E[a(X, h(X))(h(X) − Y )]| ≤ ε. a∈A
These rates are optimal, since the tight bounds we give for multicalibration and omniprediction are special cases. 3. Optimal Deterministic Omniprediction (Theorem 8.7 and Corollaries 8.9–8.11). Applying the OI theorem to the tests that certify omniprediction gives deterministic versions of the sample-optimal randomized offline omnipredictors of Okoroafor et al. [2025]. Here is the concrete specialization. For a loss class L and benchmark class H, omniprediction reduces to threshold-calibration tests together with multiaccuracy tests for the loss-derived class ∆L ◦ H = {x 7→ ℓ(f (x), 1) − ℓ(f (x), 0) : ℓ ∈ L, f ∈ H}. If this class is represented to accuracy O(ε) by a finite auditor class C—for example, by a finite cover or finite approximate basis—then the sample complexity is log |C| + log(1/ε) e O ε2 matching the randomized offline rate up to logarithmic factors. In particular, if this loss-derived e class has pseudo-dimension p, then deterministic omnipredictors use O((p + log(1/ε))/ε2 ) samples. In Appendix E we extend this result to panprediction.
1.2
Technical overview
To understand our algorithm in the special case of multicalibration it is useful to first consider a simple/naive approach to derandomization that does not work. Given a randomized predictor obtaining low multicalibration error, perhaps we could just “fix its randomness up front” to make it deterministic. Put aside representation concerns for now (how do we “fix the randomness” of continuously many prediction values?) Indeed if the underlying distribution on contexts was continuous (or at least put only tiny probability on any context x) then this would succeed.2 If in a large sample we never see the same context twice, then there is no observable difference between flipping coins at test time vs. pre-flipping them at training time. Thus the only conceptual obstacle to derandomization is distributions that have non-trivial atoms — i.e. place large mass on particular contexts x. To understand the issue, which arises already for marginal calibration before imposing any group structure, consider the following minimal example. 2
In atomless finite-action settings, this intuition goes back to the purification theorem of Dvoretzky et al. [1951], which eliminates randomization in games while preserving finitely many expected payoffs. Our setting allows atoms in the feature distribution where exact purification can fail; the machinery we develop is designed to handle this obstruction.
3
A two-point obstruction. Consider a distribution over two contexts x1 and x2 , both of which have probability 1/2. Suppose x1 is always paired with label y = 0 and x2 is always paired with label y = 1. Consider the randomized predictor that on input x1 outputs prediction ỹ = 1/3 with probability 2/3 and otherwise outputs prediction ỹ = 2/3, and that on input x2 outputs prediction ỹ = 2/3 with probability 2/3 and otherwise outputs prediction ỹ = 1/3. This predictor has ECE zero: the expected bias of the prediction conditional on predicting ỹ = 1/3 is 1 2 1 1 · · (1/3 − 0) + · · (1/3 − 1) = 0, 2 3 2 3 and the analogous bias conditional on predicting ỹ = 2/3 is also zero. But any rounding that assigns each context a prediction from the support of its randomized prediction distribution produces a predictor h with h(xi ) ∈ {1/3, 2/3}. Any such predictor has ECE at least 1/6. The randomized predictor is calibrated because conditioning on each prediction value gives exactly the right mixture of the two contexts, and this mixture is destroyed by deterministic rounding. Thus any rounding-based derandomization must explicitly account for atoms. A first attempt: handle large atoms separately. If the distribution has no atoms, or if all atoms have very small mass, then fixing the predictor’s randomness up front works: an atom x of mass px contributes variance on the scale of p2x to the realized multicalibration error. As all px tend to 0, the multicalibration error is unaffected by fixing the randomness. At the other extreme, if an atom has sufficiently large mass that it appears many times in the training data, we can estimate its conditional label mean directly. This would solve the two-context example above, because each of x1 and x2 accounts for roughly half of the sample. These two observations suggest a hybrid algorithm: fix the randomness of a randomized multicalibrated predictor on “light”/infrequent contexts, and separately estimate the conditional label mean of each sufficiently frequent “heavy” context. Unfortunately the numbers do not work out. Let L denote the log of the number of signed calibration tests—informally, the exponent in the union bound used to control multicalibration error after fixing the randomness of a randomized predictor. L is on the order of the cardinality of the predictor’s domain, so L ≈ 1/ε up to logarithmic factors. Suppose an atom is declared to be “heavy” if it has mass more than τ , and is otherwise declared to be “light”. For any fixed signed calibration test,Pthe variance proxy for the rounding noise from the light atoms by a P 2is bounded P 2 constant times x px . Since every light atom has mass px ≤ τ , this satisfies √x px ≤ τ x px ≤ τ . Simultaneous concentration over the L signed calibration tests then asks for Lτ ≲ ε by a union bound, and so the threshold for “light” atoms that guarantees that they do not contribute more than ε additional multicalibration error is roughly τlight ≈
ε2 , L
which is about ε3 . On the other hand, directly estimating the conditional label mean of an atom to constant multiples of ε requires about ε−2 occurrences of that atom. If we have N samples, an atom of mass px appears about N px times, so direct estimation is only guaranteed when N px ≳ ε−2 ,
or equivalently
px ≳ τheavy (N ) :=
1 . N ε2
For a hard threshold τ to handle every atom, we would need τheavy (N ) ≲ τ ≲ τlight , which requires N≳ 4
L . ε4
Thus the hard split approach works only at a sample size much larger than the target rate N ≈ L/ε2 . At that target rate, τheavy (N ) is about 1/L, which is about ε, leaving a large range of atom masses between ε3 and ε that are too large for rounding but too small for conditional mean estimation. Figure 1 illustrates this mismatch and the confidence-interval approach that avoids it. Hard split versus adaptive intervals Hard Split
Rounding OK
Gap: Neither Rule Applies
Mean Estimation OK
Our Approach
Rare Points: Wide Intervals
Intermediate Length Intervals
Frequent Points: Narrow Intervals larger
smaller τlight ≈ ε3
τheavy (N ) ≈ε atom mass px
Figure 1: The obstruction to a hard split. The gap region contains atom masses that are too large for blind rounding but too small for accurate conditional-mean estimation at the target sample size. Confidence intervals interpolate between these two regimes.
Our solution. Our solution avoids the hard split by instead smoothly incorporating however much statistical information we have about the conditional label mean of a point x as a “hint” when producing the randomized predictor that we ultimately round—rather than either relying on the information we have as sufficient or else ignoring it entirely. From the training sample we record how many times each context x appears, and build a confidence interval for its conditional label mean whose width depends on this count Nx : frequent contexts receive narrow intervals, while rare contexts receive the trivial interval [0, 1]. To use these confidence intervals, we develop a new online learning primitive: an online multicalibration algorithm that receives with each context x a valid interval hint, consisting of an interval Ix containing the conditional label mean and a set of allowed grid values near Ix . The algorithm guarantees multicalibration error at the optimal rate against any adversary, provided the hints are valid, and it only makes predictions using the allowed grid values. We then use an online-to-batch reduction using this online learning algorithm paired with confidence intervals computed from a sample of the data. This results in a randomized predictor, but one with context conditional prediction variance that scales inversely with the mass of each point (since frequently seen contexts are endowed with narrower confidence intervals which constrain the support of the randomized predictor). The variance from fixing the randomness of this predictor therefore scales smoothly with the mass of each context, rather than depending on a brittle heavy/light threshold. Finally, we use the data to partition the context space into finitely many rounding cells and use one sampler seed per cell, giving us a finite derandomization even for continuous context spaces. We now map our results in more detail. Multicalibration upper bound. The learner splits its sample into three independent parts: a confidence sample S0 used to learn confidence intervals for the conditional mean around each context, an online-learning sample S1 used in the online-to-batch reduction, and a partition sample S2 used to define the cells used for deterministic rounding. The upper-bound proof has four ingredients. 5
(1) Online-to-batch reduction with interval hints (Section 3). Consider an online adversarial learning setting in which, after the adversary reveals context x, the learner also receives a valid interval hint: an interval Ix containing the conditional mean µ(x) and allowed grid values near that interval. A minimax and exponential-weights argument gives an online learning algorithm (Lemma 3.2) that obtains multicalibration against any such adversary at the optimal rate, while predicting only allowed grid values. With valid interval hints in the batch setting, a standard martingale online-to-batch reduction for multicalibration [Gupta et al., 2022] then produces a randomized batch predictor with small ECE multicalibration error whose support at each context is restricted to those allowed grid values. (2) Building the intervals (Section 4). The confidence sample S0 is used to compute the confidence intervals Ix . Atoms seen repeatedly get narrow empirical confidence intervals; unseen and infrequently seen contexts get the trivial interval [0, 1]. (3) Making the rounding finite (Section 5). The final step will fix one sampler seed for each rounding cell. The contexts observed in S0 already give finitely many singleton cells. The remaining issue is the unobserved region, which may be infinite. We need to partition it into a finite number of “rounding cells” whose sum of squared masses is small (so that they will not substantially harm multicalibration error even when rounded with a common seed in the next step). In one dimension, the natural version of this idea is to draw a fresh sample of points, sort them, and use the gaps between consecutive sample points as cells; an exchangeability argument then shows that two fresh points are unlikely to land in the same gap. We use the same rank-based idea for general contexts by imposing a lexicographic order, sorting the partition sample S2 in that order, and taking the cells induced by adjacent sampled contexts. (4) Rounding the Predictor (Section 6). Using one sampler seed per rounding cell turns the randomized predictor produced by the online-to-batch reduction on S1 into a deterministic function. The rounding itself is simple: each rounding cell gets one shared random draw from the randomized predictor, and every context in that cell is rounded using that shared draw. The proof is driven by a general finite-test rounding proposition: if the learned intervals make the weighted interval radii small on observed atoms and the partition P mass-squared 2 makes C PX (C) small on the unobserved region, then one sampler seed per cell preserves every test in any finite family. This is why the same derandomization step applies both to multicalibration and to outcome indistinguishability. Figure 2 summarizes how the three sample parts combine into the deterministic predictor. Our online multicalibration algorithm is most naturally described as an exponential-weights subroutine over an exponentially large space, with one weight per sign pattern over possible prediction values. In this form it would take exponential time. We show, however, that the exponential-weights distribution factors across prediction values, so the algorithm can be implemented implicitly in polynomial time (Theorem 7.1). Outcome indistinguishability and omniprediction. The scalar multicalibration proof uses the special form of ECE multicalibration only through the finite family of signed OI tests that it induces. This lets us state a more general theorem: fix any finite family A of bounded OI tests a(x, v), and ask that |E[a(X, h(X))(h(X) − Y )]|
6
S0
intervals Ix constrains support
i.i.d. sample S
S1
randomized Q (online-to-batch)
S2
lexicographic cells Π
round
deterministic predictor h
rounding-cell seed
Figure 2: The learner splits its sample into three independent parts. The confidence sample S0 produces valid interval hints Ix and their allowed grid values; the online-learning sample S1 produces a randomized predictor Q supported on those allowed values (Theorem 3.1); the partition sample S2 produces a finite family of lexicographic rounding cells Π (Section 5). Drawing one independent sampler seed per rounding cell turns Q into the deterministic predictor h (Lemma 6.2). be small for every a ∈ A. Our deterministic learner for this finite-test OI problem uses log |A| e O ε2 samples to make all these correlations at most ε. Omniprediction fits this template because the outcome-indistinguishability characterizations [Gopalan et al., 2023a, Okoroafor et al., 2025] reduce it to threshold-calibration tests together with multiaccuracy tests for a loss-derived auditor class. Instantiating our theorem with these tests yields sample-optimal omniprediction with a deterministic predictor.
1.3
Additional Related Work
Uniform convergence for fixed predictor classes. A related but distinct line of work [Shabat et al., 2020, Rosenberg et al., 2022] studies uniform convergence of multicalibration error over a fixed predictor class. Models found via ERM over a fixed model class can be deterministic, but these results only control the gap between empirical and population multicalibration error uniformly over a class of candidate predictors—they do not by themselves imply that the class contains any low-error predictor, whereas our results study the sample complexity of producing a predictor with small population multicalibration error. Multicalibration upper and lower bounds. Noarov et al. [2025], Collina et al. [2026b] establish the optimal rate for multicalibration in the online adversarial setting, and Collina et al. [2026c] establish the optimal sample complexity in the batch setting (the setting we study here). The upper bound in Collina et al. [2026c] is randomized, and they ask whether the minimax optimal sample complexity is obtainable via a deterministic predictor. We resolve this question. Before this work, the strongest deterministic guarantees had worse dependence on the target ECE error. Haghtalab et al. [2023] give deterministic algorithms for bucketed multicalibration; translating their bucketed L∞ guarantee to ECE requires roughly 1/ε buckets and bucket bias e −6 ). Older deterministic constructions, such about ε2 , leading to a sample complexity of about O(ε as the original multicalibration algorithm of Hebert-Johnson et al. [2018], give still weaker ECE rates after the same translation. 7
Multi-distribution learning and derandomization. A closely related derandomization question has been studied for agnostic multi-distribution learning. Larsen et al. [2024] show that, in the fully general multi-distribution setting, converting randomized multi-distribution predictors into deterministic ones can be computationally hard even when ERM over the benchmark class is efficient. They also give a positive black-box derandomization under a label-consistency condition, where all distributions share the same conditional label law given the context. Our setting is complementary: multicalibration, outcome indistinguishability, and omniprediction impose many residual tests or group reweightings, but all are evaluated under a single joint distribution and hence a single conditional mean function µ(x). Thus the obstruction exploited in their hardness result is absent, while the central challenge is statistical and distributional: controlling the effect of fixing the prediction-time randomness, especially on atoms. Omniprediction and outcome indistinguishability. Omniprediction was introduced by Gopalan et al. [2022] as a way to learn a single predictor whose loss-specific postprocessings compete with a benchmark class across many losses. Their original construction proceeds through multicalibration. Subsequent work developed a more direct outcome-indistinguishability viewpoint (see Dwork et al. [2021]): Gopalan et al. [2023a] introduced Loss OI and showed how to decompose it into calibration plus multiaccuracy for a loss-derived class, while Gopalan et al. [2023b] characterized swap variants of omniprediction through swap multicalibration. Garg et al. [2024] studied oracleefficient online multicalibration and omniprediction. Hu et al. [2022] study the sample complexity of outcome indistinguishability, giving metricentropy characterizations in the distribution-specific setting and fat-shattering characterizations in the distribution-free setting. Their distinguishers are “no-access” distinguishers: they see the context and outcome, but not the prediction value. Equivalently, their tests are context-only residual tests, which coincide with multiaccuracy. Our finite-test OI theorem includes this case, but is aimed at the more general prediction-dependent tests needed for calibration and omniprediction. Hu and Peale [2023] study a complementary setting, characterizing distribution-free realizable multiaccuracy and multicalibration by a mutual fat-shattering dimension of the source and distinguisher classes. Their results exploit realizable structure in the conditional label mean, whereas our results are agnostic in the label distribution and focus on derandomizing optimal-rate multicalibration and OI guarantees. Okoroafor et al. [2025] gave near-sample-optimal online and offline algorithms for omniprediction, e −2 ) times the relevant auditor-class complexity. Their offline with sample complexity scaling as O(ε constructions output randomized predictors through online-to-batch style conversions, and they ask whether these randomized omnipredictors can be derandomized without losing sample optimality. We resolve this question affirmatively. The deterministic landscape before our work was mixed. The Loss-OI construction of Gopalan et al. [2023a] outputs deterministic predictors, but its general sample complexity has substantially worse ε-dependence; Okoroafor et al. [2025, Theorem C.1] record the bound as O(d/ε4 + ε−10 log(1/ε)) for the relevant complexity parameter d. Thus it did not match the 2 ) rate achieved by randomized online-to-batch methods. The proper-loss setting e optimal O(d/ε is an important exception: Gibbs and Tibshirani [2026] give a direct algorithm outputting a deterministic predictor with the optimal proper-loss omniprediction rate. Their result exploits the special structure of proper losses, whereas our OI theorem gives a derandomization route for the broader finite-test and finitely covered loss-derived auditor classes used in Okoroafor et al. [2025]. Panprediction. Balakrishnan et al. [2026] introduce panprediction, which generalizes om8
niprediction by requiring guarantees simultaneously across downstream losses and subgroups. They reduce panprediction to step calibration and obtain deterministic and randomized panpredictors e −3 ) and O(ε e −2 ) sample complexity rates, respectively, and ask whether the gap is inherat O(ε ent. After their reduction, the relevant objectives are again OI tests, now indexed by prediction thresholds, comparator thresholds, and groups. The OI extension we give in Section 8 therefore applies, resolving their question of whether optimal panprediction bounds can be obtained with deterministic predictors; Appendix E gives the formal statement.
2
Setting and calibration definitions
2.1
Distributions, atoms, and conditional means
Fix a finite dimension d < ∞ and a context space X ⊆ [0, 1]d . We consider distributions P over pairs (X, Y ) ∈ X × [0, 1]. Let PX denote the marginal distribution of X, and let µ(x) = E[Y | X = x] denote the conditional label mean. For x ∈ X , write px = PX ({x}). Let At(PX ) = {x ∈ X : px > P0} denote the set of atoms. This set is at most countable for every probability measure, and x∈At(PX ) px ≤ 1. Indeed, for each j ≥ 1 there are at most 2j atoms with mass at least 2−j , and At(PX ) is the union of these finite sets. Points with px = 0 never affect population calibration quantities individually, but the learning procedure still defines predictions on them. A group is a nonnegative weight function on contexts. A group family is a finite nonempty set G ⊆ [0, 1]X of such functions. All logarithms are natural. We suppress universal numerical constants, but all choices below can be made by taking a single sufficiently large universal constant C.
2.2
Grid predictors and ECE multicalibration
Fix a finite grid Λ ⊆ [0, 1]. A randomized grid predictor assigns to each context a distribution over grid values: Q : X → ∆(Λ), where Qx (v) denotes the probability assigned to v ∈ Λ. A deterministic predictor is a function h : X → Λ, identified with the point-mass randomized predictor Qx = δh(x) . Definition 2.1 (Calibration bias at a prediction value). For a randomized grid predictor Q, a group g ∈ G, and a grid value v ∈ Λ, define BP (Q; g, v) = E g(X)QX (v)(v − Y ) . This is the calibration bias contributed by group g among predictions that place mass on value v. Since QX (v) and v are functions of X, BP (Q; g, v) = E g(X)QX (v)(v − µ(X)) . For a deterministic predictor h, this becomes BP (h; g, v) = E g(X)1{h(X) = v}(v − Y ) . Definition 2.2 (ECE multicalibration error). The ECE multicalibration error of Q with respect to G is X MCP (Q; G) = max |BP (Q; g, v)|. g∈G
v∈Λ
It is sometimes convenient to think about multicalibration error in its dual “signed” form: 9
Lemma 2.3 (Signed form of ECE multicalibration). For every randomized grid predictor Q, " # X MCP (Q; G) = max max E g(X) σ(v)QX (v)(v − Y ) . g∈G σ∈{±1}Λ
v∈Λ
For deterministic h, this specializes to: MCP (h; G) = max max E [g(X)σ(h(X))(h(X) − Y )] . g∈G σ∈{±1}Λ
The identity is the elementary fact that
3
P
v |bv | is the largest signed sum
P
v σ(v)bv .
Learning a randomized predictor from valid interval hints
We first prove the randomized learning guarantee that the derandomization argument builds on. In this section the learner is handed context-dependent interval hints: intervals Ux together with allowed grid sets Λx . This is exactly the information that the confidence sample S0 will later supply (Section 4): the learner does not know µ(x), but on the coverage event it has an interval Ux containing µ(x) and a grid set Λx that approximates every value in Ux . The theorem says that valid interval hints are enough to learn a randomized batch predictor with small ECE multicalibration error whose support stays near Ux . The algorithm behind the theorem is an online multicalibration algorithm, run through the standard multicalibration online-to-batch reduction [Gupta et al., 2022]. An interval-hint system for a finite grid Λ assigns to each context x a nonempty closed interval Ux = [ax , bx ] ⊆ [0, 1] and a nonempty set Λx ⊆ Λ of allowed grid values. Call an interval-hint system γ-valid for P if, for every x, µ(x) ∈ Ux
and
∀m ∈ Ux ∃a ∈ Λx with |a − m| ≤ γ.
In the final algorithm the hint system is random because it is learned from the confidence sample S0 . We apply the theorem conditionally on the high-probability event that the learned hints are γ-valid. Theorem 3.1 (Learning from valid interval hints). There is a universal constant Con such that the following holds. Let G be a finite nonempty group family, let γ ∈ (0, 1), let δ ∈ (0, 1), and let Λ ⊆ [0, 1] be a γ-net of [0, 1] with |Λ| ≤ Cgrid /γ for a universal constant Cgrid . Suppose the learner is given a γ-valid interval-hint system (Ux , Λx )x∈X on this grid. Then there is a learning algorithm which, given T i.i.d. samples from P and the interval-hint system, outputs a randomized grid predictor Q satisfying supp(Qx ) ⊆ Λx for every x, and, with probability at least 1 − δ, r MCP (Q; G) ≤ Con
γ+
1/γ + log |G| + log(1/δ) T
! .
We next spell out the one-step action rule used by the online algorithm. After the past history has fixed the current exponential-weights distribution, each context x and grid value v receives a coefficient c(v). This coefficient is the current aggregate signed “weight” for predicting v at x. The learner wants a distribution q over the allowed grid values Λx whose signed payoff is small for 10
every mean value that could be consistent with the interval hint Ux = [ax , bx ] (but not necessarily with mean values outside of the interval hint). For a fixed q, the payoff is affine in the unknown mean m ∈ Ux , so the worst case over the interval occurs at one of the two endpoints. Thus the one-step prediction distribution can be computed by the following finite linear program. For a context x and coefficients c : Λ → [−1, 1], let LPx (c) denote the deterministic tie-broken solution q ∈ ∆(Λ) of minimize P λ subject to v∈Λ q(v) = 1, q(v) = 0
q(v) ≥ 0
(v ∈ Λ),
(v ∈ / Λx ),
(1)
−1 ≤ λ ≤ 1, P q(v)c(v)(v − ax ) ≤ λ, Pv∈Λ v∈Λ q(v)c(v)(v − bx ) ≤ λ.
The constraints q(v) = 0 for v ∈ / Λx enforce the interval hint’s allowed grid set, and λ upper-bounds the two endpoint payoffs. The interval-hint subroutine has two equivalent implementations. Algorithm 1 is the direct exponential-weights version used in the proof. Algorithm 2 computes the same one-step objectives without enumerating {±1}Λ ; Appendix B gives the short factorization argument. Algorithm 1. Enumerating tests
Algorithm 2. Factored implementation p 1. Set η = (log(|G|2|Λ| ) + log(3/δ))/T .
Λ 1. Set p T = G × {±1} , M = |T |, and η = (log M + log(3/δ))/T .
0 2. Initialize Sg,v = 0 for all g ∈ G and v ∈ Λ.
2. Initialize π1 uniformly on T .
3. For t = 1, . . . , T :
3. For t = 1, . . . , T :
(a) Set
(a) For every query context x and grid value v ∈ Λ, set X ct (x, v) = πt (r)g(x)σ(v).
Y
πt (g) ∝
t−1 2 cosh(ηSg,v ).
v∈Λ
(b) For every query context x and v ∈ Λ, set X t−1 ct (x, v) = πt (g)g(x) tanh(ηSg,v ).
r=(g,σ)∈T
(b) Define qt (x) = LPx (ct (x, ·)) for every x.
g∈G
(c) On the realized sample (Xt , Yt ), set X ztr = g(Xt ) qt (Xt )(v)σ(v)(v − Yt )
(c) Define qt (x) = LPx (ct (x, ·)) for every x. (d) On (Xt , Yt ), update
v∈Λ
t t−1 Sg,v = Sg,v + g(Xt )qt (Xt )(v)(v − Yt ),
for each r = (g, σ).
with qt (Xt )(v) = 0 for v ∈ / ΛXt .
(d) Update πt+1 (r) ∝ πt (r) exp(ηztr ). P 4. Output Qx = T1 Tt=1 qt (x).
t−1 T 4. Store the states {SP g,v }t=1 and output the implicit 1 predictor Qx = T t qt (x).
Lemma 3.2 (Online learning with interval hints). Fix a finite group family G, a finite grid Λ with K = |Λ|, interval hints Ux , allowed grid sets Λx , a covering radius γ, and δ ∈ (0, 1). Let T = G × {±1}Λ ,
M = |T | = |G|2K .
Consider any possibly adaptive sequence of rounds with the following structure. Before round t, the past history is fixed; then a context Xt is revealed, the learner chooses qt (Xt ) ∈ ∆(ΛXt ), and then 11
a label Yt ∈ [0, 1] is drawn with conditional mean mt = E[Yt | X1 , Y1 , . . . , Xt−1 , Yt−1 , Xt ] ∈ UXt . Assume that, on every realized context, ΛXt γ-covers UXt . When Algorithm 1 is run, qt (x) is supported on Λx for every t, x, and with probability at least 1 − δ/3, r T X 1X log M + log(3/δ) g(Xt ) qt (Xt )(v)σ(v)(v − Yt ) ≤ γ + C max . T r=(g,σ)∈T T t=1
v∈Λ
Proof. The analysis follows a standard reduction from multiobjective optimization to no regret learning (as in e.g. Lee et al. [2022], Noarov et al. [2025]) in this case instantiated with exponential weights. The difference is that the minimax step restricts the learner’s strategy space to the subset of grid points captured by the interval hints. This constructively restricts the support of the learner’s distribution, and does not change the value of the game (and hence the convergence analysis of the algorithm) so long as the interval hints are valid. Appendix A gives the details. The next lemma is the online-to-batch conversion. Running the online procedure on i.i.d. samples from a fixed distribution and averaging its iterates gives a randomized batch predictor with comparable population multicalibration error. Lemma 3.3 (Martingale online-to-batch conversion). Fix a finite group family G, a finite grid Λ, and δ ∈ (0, 1). Let T = G × {±1}Λ , M = |T |. Let (Xt , Yt )Tt=1 be i.i.d. samples from P . Suppose that, before observing (Xt , Yt ), an online procedure chooses a grid predictor qt : X → ∆(Λ) as a function of the previous samples. Define T
1X Qx (v) = qt (x)(v), T
v ∈ Λ.
t=1
For each signed calibration test r = (g, σ) ∈ T , let X ztr = g(Xt ) qt (Xt )(v)σ(v)(v − Yt ) v∈Λ
and
"
#
Ar (S) = E(X,Y )∼P g(X)
X
σ(v)QX (v)(v − Y ) .
v∈Λ
Then, with probability at least 1 − δ/3, T
1X r zt ≤ C max Ar (S) − r∈T T t=1
r
log M + log(3/δ) . T
Proof. For a fixed signed test, the population residual of the averaged predictor differs from its online empirical average by a martingale difference sequence: at time t, the predictor qt is fixed before the fresh sample (Xt , Yt ) is drawn. Azuma–Hoeffding controls this difference for one signed test, and a union bound controls all signed tests at once. Appendix A records the details. The pieces combine to prove Theorem 3.1: Lemma 3.2 controls the empirical signed residuals of the online iterates, Lemma 3.3 transfers this control to the population residuals of the averaged predictor Q, and Lemma 2.3 converts signed residual control into ECE multicalibration. Appendix A spells out the constants and the support guarantee. 12
4
Learning the interval hints from repeated contexts
This section constructs, from the confidence sample S0 , the interval-hint system (Ix , Λx ) used by Theorem 3.1. The idea is simple: contexts seen repeatedly get empirical confidence intervals, while contexts seen zero or one times receive the full interval [0, 1]. The key point will be that an atom x with a confidence interval of width rx will eventually contribute to the rounding variance on the order of rx2 p2x , which we show is controlled—because wide intervals correspond to infrequent contexts and vice versa. Fix an internal accuracy parameter α ∈ (0, 1/10). Let γ = Θ(α), let Λ be a γ-net of [0, 1] containing 0 and 1, and write K = |Λ| = O(1/γ) = O(1/α). Set L = K + log(|G| + 1) + 100, and let J = Θ(log(L/α)) be the logarithmic confidence parameter. The confidence sample has size n0 = C0
LJ α2
for a sufficiently large universal constant C0 . Appendix C records one concrete choice of constants and grid. Let O0 = {Xi : i ≤ n0 } be the finite P set of contexts observed in S0 . For x ∈ O0 , let −1 Nx = #{i ≤ n0 : Xi = x} and µ bx = Nx i:Xi =x Yi . Set ( r rx = min 1,
J Nx
) Ix = [b µx − r x , µ bx + rx ] ∩ [0, 1].
,
For x ∈ / O0 , set Nx = 0, rx = 1, and Ix = [0, 1]. For every x ∈ X , define the allowed grid set Λx = {v ∈ Λ : dist(v, Ix ) ≤ γ}. Together, (Ix , Λx ) form the learned interval-hint system that will be passed to the learning algorithm of Theorem 3.1. Proposition 4.1 records the two facts needed later: the hints are valid, and the atom-weighted radius budget is small. Proposition 4.1 (Learned interval hints). There are events Ecov and Erad , depending only on S0 , with probabilities at least 0.99 and 0.90, respectively, such that: (i) on Ecov , the learned interval-hint system (Ix , Λx )x∈X is γ-valid for P ; (ii) on Erad , X
p2x rx2 ≤ C1
x∈At(PX )
α2 L
for a universal constant C1 . Consequently, with probability at least 0.89, both conclusions hold. Proof. We sketch the proof here; the full concentration details are deferred to Appendix C. With probability one, no non-atom appears twice in S0 . Thus every context with Nx ≥ 2 is an atom, and Hoeffding’s inequality controls |b µx − µ(x)| for each such context. A union bound over the at most n0 repeated contexts gives the coverage event Ecov . Contexts with Nx = 0 or Nx = 1 receive the full interval [0, 1], and the γ-net property of Λ gives the allowed grid value near every point of Ix .
13
For the radius bound, fix an atom x of mass p and write Nx ∼ Bin(n0 , p). The elementary binomial estimate J E[p2 rx2 ] ≤ C p n0 captures the desired tradeoff: either the atom is rare, in which case the factor p2 is already small, or it is frequent, in which case Nx is typically of order n0 p and rx2 is of order J/(n0 p). Summing over atoms gives X J α2 E p2x rx2 ≤ C ≤C , n0 L x∈At(PX )
and Markov’s inequality gives Erad .
5
Building the finite list of rounding cells
The final rounding step in Section 6 will use one independent seed per “rounding cell”, so we need a finite list of such cells. The partition sample builds such a list on the part of the space not already observed in S0 . The goal is to cut this unobserved region into cells whose summed squared masses are small; this is the term that will control the part of the rounding error not already controlled by the confidence intervals on observed atoms. Use the lexicographic order inherited from [0, 1]d : for distinct x, z ∈ X , write x ≺ z if, at the first coordinate where they differ, x has the smaller coordinate. Let the partition sample be S2 = (W1 , . . . , Wm ), an independent sample of contexts from PX , where m = C0
L . α2
Sort the distinct values appearing in S2 : w(1) ≺ w(2) ≺ · · · ≺ w(r) . Let U0 = X \ O0 be the region unobserved in S0 . Define Πunobs to be the finite family of rounding cells induced by these comparisons, intersected with U0 : U0 ∩ {x : x ≺ w(1) }, U0 ∩ {w(j) }
(1 ≤ j ≤ r),
U0 ∩ {x : w(j) ≺ x ≺ w(j+1) }
(1 ≤ j < r),
U0 ∩ {x : w(r) ≺ x}. The full rounding-cell family is Π = {x} : x ∈ O0 ∪ Πunobs . The goal is to show that this partition of the unobserved space does not result in any cell of high mass. The next lemma shows via exchangeability that two distinct draws from the distribution are unlikely to lie in the same cell. Lemma 5.1. Let A, B, W1 , . . . , Wm be i.i.d. draws from PX . Then P (A ̸= B and no Wi lies in the closed lexicographic interval between A and B) ≤ 14
2 . m+2
Proof. Condition on the multiset of the m + 2 sampled contexts, and sort its distinct values in lexicographic order. Call an ordered pair of sampled labels isolated if the two labels have distinct contexts and no other sampled context lies in the closed lexicographic interval between them. Such a pair can only come from two adjacent distinct context values in the sorted list, and both of those values must appear with multiplicity one. Hence there are at most 2(m + 1) isolated ordered pairs. By exchangeability, conditional on the multiset, the ordered pair of labels corresponding to (A, B) is uniformly distributed over the (m + 2)(m + 1) ordered pairs of distinct sampled labels. Therefore the conditional probability that (A, B) is isolated is at most 2(m + 1) 2 = . (m + 2)(m + 1) m+2 Averaging over the multiset proves the lemma. Finally this lets us control the sum of squared masses of the partition of the unseen context space, which is what we will need to control the rounding error. Lemma 5.2 (The partition sample controls squared cell masses). There is an event Epart with probability at least 0.95 over (S0 , S2 ) such that X
PX (C)2 ≤ C2
C∈Πunobs
α2 L
for a universal constant C2 . Proof. Fix S0 and let ν(A) = PX (A ∩ U0 ). Conditional on S0 , X X PX (C)2 = ν(C)2 C∈Πunobs
C∈Πunobs
is the ν × ν mass of pairs that fall in the same unobserved cell. The contribution from pairs in which the two draws are exactly the same atom is X p2x . x∈At(PX )∩U0
For distinct x ≺ x′ , the two points can fall in the same cell only if no partition-sample cutpoint lies in the closed lexicographic interval [x, x′ ]≺ = {z ∈ X : x ⪯ z ⪯ x′ }. Since ν ≤ PX , the off-diagonal contribution is at most the probability of the following event: draw independent A, B, W1 , . . . , Wm ∼ PX , have A = ̸ B, and have no Wi in the closed lexicographic interval between A and B. By Lemma 5.1, this probability is at most 2/(m + 2). Therefore X X 2 ES2 PX (C)2 S0 ≤ p2x + . (2) m+2 C∈Πunobs
x∈At(PX )∩U0
Now average over S0 . An atom x of mass px lies in U0 exactly when it is not observed in S0 , so X X ES0 p2x = p2x (1 − px )n0 . x∈At(PX )∩U0
x∈At(PX )
15
For p ∈ [0, 1], p(1 − p)n0 ≤ catom /(n0 + 1) for a universal constant catom ; hence p2x (1 − px )n0 ≤ Summing over atoms and using ES0 ,S2
catom px . n0 + 1
P
x px ≤ 1 gives
X
PX (C)2 ≤
C∈Πunobs
catom 2 α2 + ≤ cpart n0 m+2 L
for a universal constant cpart . Choosing C2 large enough and applying Markov’s inequality gives the event Epart with probability at least 0.95. Remark 5.3 (The third split is optional). We use a separate partition sample S2 to keep the proof bookkeeping clean: S0 is used to learn the interval hints, S1 is used to learn the randomized predictor, and S2 defines the rounding cells. But the third sample S2 is not necessary. One can instead sort the distinct contexts appearing in the confidence sample S0 and use them as the lexicographic cutpoints for the unobserved region. The same exchangeability argument applies. Thus the third split can be removed at the cost of coupling the interval and partition bookkeeping.
6
Rounding the randomized predictor
The lemma below rounds the randomized predictor constructed in Section 4. The rounding is by shared inverse-CDF seeds: each cell C ∈ Π receives one independent uniform seed UC , and every context x ∈ C is assigned the grid value obtained by applying the inverse-CDF sampler for Qx to that same seed. One independent sampler seed per rounding cell preserves all signed calibration tests when the observed-atom radius term and the unobserved cell-mass term are small. The previous two sections establish exactly these bounds: Proposition 4.1 controls the mass-squared weighted interval radii on observed atoms, and Lemma 5.2 controls the summed squared masses of unobserved cells. A small optimization improves the run-time using the structure of the online to batch predictors P we produce. If Qx = T −1 Tt=1 qt (x), then drawing from Qx is the same as first drawing τ ∼ Unif({1, . . . , T }) and then drawing from qτ (x). Thus a cell sampler seed can be stored as a pair (τC , UC ); on query x ∈ C, the evaluator reconstructs only qτC (x) and samples from it using UC . Proposition 6.1 (One-seed rounding for finite test families). Fix the interval-hint system (Ix , Λx )x∈X constructed from S0 and the rounding partition Π constructed from S0 and S2 , and suppose S0 lies in the coverage event Ecov from Proposition 4.1. Let Q be any randomized grid predictor satisfying supp(Qx ) ⊆ Λx for every x. Let A ⊆ [−1, 1]X ×[0,1] be a finite nonempty family of tests, and define X X VΠ = p2x rx2 + PX (C)2 . C∈Πunobs
x∈O0 ∩At(PX )
For each rounding cell C ∈ Π, draw an independent seed UC ∼ Unif[0, 1]. Enumerate Λ = {v1 , . . . , vK } and set X X Fx (u) = vj when Qx (vi ) < u ≤ Qx (vi ), i<j
16
i≤j
with the endpoint convention Fx (0) = v1 . For x ∈ C ∈ Π, define h(x) = Fx (UC ). Then for every δ ∈ (0, 1), with probability at least 1 − δ over the cell seeds, " # ! r X 2|A| VΠ log max E a(X, h(X))(h(X) − Y ) − E QX (v)a(X, v)(v − Y ) ≤ Crnd +γ a∈A δ v∈Λ
for a universal constant Crnd . Proof. Write Ix = [ax , bx ] and define clipx (v) = min{max{v, ax }, bx } for v ∈ Λx . By the definition of Λx , |v − clipx (v)| ≤ γ whenever v ∈ Λx . If x ∈ / O0 , then Ix = [0, 1], Λx = Λ, and clipx (v) = v. Values of clipx (v) for v ∈ / Λx are irrelevant because Qx (v) = 0. Fix a test a ∈ A. Since both predictors are functions of X, replacing Y by µ(X) does not change either expectation. Split v − µ(x) into the clipped part and the grid-rounding part: v − µ(x) = clipx (v) − µ(x) + v − clipx (v) . For a rounding cell C, let ! Z X 0 Za,C = a(x, Fx (UC ))(clipx (Fx (UC )) − µ(x)) − Qx (v)a(x, v)(clipx (v) − µ(x)) dPX (x). C
v∈Λ
0 ] = 0. For fixed x, Fx (UC ) has distribution Qx , so E[Za,C
0 The variables {Za,C : C ∈ Π} are
independent because the cell seeds are independent. We bound their ranges cell by cell. If C = {x} is an observed singleton with px > 0, then x is an atom. On the coverage event, both clipx (v) and µ(x) lie in Ix for every v ∈ supp(Qx ), so |a(x, v)(clipx (v) − µ(x))| ≤ 2rx . 0 Thus Za,{x} has range length at most 4px rx ; if px = 0, the range length is zero. If C ∈ Πunobs , 0 then Ix = [0, 1] on C and clipx (v) = v, so the clipped payoff is bounded by one and Za,C has range length at most 2PX (C). P 0 , Hoeffding’s inequality therefore gives, for Za0 = C Za,C ct2 0 P |Za | > t ≤ 2 exp − VΠ
with the interpretation that the probability is zero when VΠ = 0 and t > 0. Taking r 2|A| t = C VΠ log δ and union bounding over a ∈ A controls the clipped part simultaneously for all tests. The grid-rounding part is deterministic. For every a ∈ A, ! Z X a(x, h(x))(h(x) − clipx (h(x))) − Qx (v)a(x, v)(v − clipx (v)) dPX (x) ≤ 2γ, v∈Λ
because both h(x) and every v with Qx (v) > 0 lie in Λx . Combining the clipped and grid-rounding bounds and absorbing constants proves the proposition. The proof used only that the cell seeds are independent, that for each fixed x the rounded value has marginal distribution Qx , and that rounded values lie in Λx . Therefore the same guarantee applies to the equivalent mixture sampler described above. 17
Lemma 6.2 (One seed per rounding cell preserves calibration). Fix S0 lying in the events Ecov ∩ Erad from Proposition 4.1. Fix S2 lying in the partition event Epart of Lemma 5.2. Let Q be any randomized grid predictor such that supp(Qx ) ⊆ Λx for every x, and assume that the allowed-grid radius satisfies γ ≤ α/2. For each rounding cell C ∈ Π, draw an independent seed UC ∼ Unif[0, 1]. Enumerate Λ = {v1 , . . . , vK } and define the inverse-CDF sampler X X Fx (u) = vj when Qx (vi ) < u ≤ Qx (vi ), i<j
i≤j
with the endpoint convention Fx (0) = v1 . For x ∈ C ∈ Π, set h(x) = Fx (UC ). P Equivalently, if Qx = T −1 t qt (x), one may draw for each cell an independent pair (τC , UC ) with τC uniform on {1, . . . , T } and UC uniform on [0, 1], and set h(x) by applying the inverse-CDF sampler for qτC (x) to UC . Then, with probability at least 0.99 over the cell seeds, the deterministic grid predictor h : X → Λ satisfies MCP (h; G) ≤ MCP (Q; G) + C3 α. Consequently, there exists a deterministic choice of the cell seeds with the same guarantee. Proof. Apply Proposition 6.1 to the finite test family AMC = {(x, v) 7→ g(x)σ(v) : g ∈ G, σ ∈ {±1}Λ }. Its size is M = |G|2K , and by the definition of L we have log M ≤ L. On the radius and partition events, X X α2 VΠ = p2x rx2 + PX (C)2 ≤ C . L C∈Πunobs
x∈O0 ∩At(PX )
Indeed, the observed-atom sum is dominated by the full atomic sum in Proposition 4.1, while the unobserved-cell sum is controlled by Lemma 5.2. Since L ≥ 100, Proposition 6.1 with δ = 0.01 gives, with probability at least 0.99 over the cell seeds, a deterministic predictor h satisfying, for all g ∈ G and σ ∈ {±1}Λ , " # X E [g(X)σ(h(X))(h(X) − Y )] − E g(X) σ(v)QX (v)(v − Y ) ≤ C ′ α, v∈Λ
where we used γ ≤ α/2 and log(200M ) ≤ CL. Finally, apply Lemma 2.3. For any g, X |BP (h; g, v)| = max E[g(X)σ(h(X))(h(X) − Y )] v∈Λ
σ
"
#
≤ max E g(X)
X
σ
σ(v)QX (v)(v − Y ) + C ′ α
v
≤ MCP (Q; G) + C ′ α. Taking the maximum over g proves the lemma after increasing C3 if necessary. 18
7
Putting the deterministic learner together
We now give the full learning procedure. Its output predictor is deterministic, although the training procedure uses randomness to choose the final cell sampler seeds. Appendix F shows how to remove these final training coins by enumerating limited-independent seed choices and selecting one on a validation sample. At a high level, the learner uses the confidence sample S0 to build intervals, the online-learning sample S1 to learn a randomized predictor constrained to those intervals, and the partition sample S2 to create finitely many rounding cells. It then chooses one sampler seed per rounding cell and uses those seeds to turn the randomized predictor into a deterministic function. Algorithm 3. Learn, average, and round with one sampler seed per rounding cell 1. Input: accuracy ε ∈ (0, 1/10), group family G, and an i.i.d. sample S from P . 2. Set the internal accuracy α = cε for a sufficiently small universal constant c > 0. Set γ = α/64, build the grid Λ, define K, L, J, n0 as in Section 4, and set T = C0
L , α2
m = C0
L . α2
3. Split S into three independent parts: the confidence sample S0 , the online-learning sample S1 , and the partition sample S2 , with |S0 | = n0 = C0
LJ , α2
|S1 | = T,
|S2 | = m.
bx , confidence 4. Using the confidence sample S0 , compute the counts Nx , empirical means µ intervals Ix , and allowed grid sets Λx = {v ∈ Λ : dist(v, Ix ) ≤ γ}. These define the learned interval-hint system. 5. Run Algorithm 1, or its factored implementation Algorithm 2, on the online-learning sample S1 with the learned interval-hint system (Ix , Λx )x∈X and group family G. Let Q be the resulting randomized grid predictor. 6. Sort the distinct contexts in the partition sample S2 lexicographically and form the finite rounding-cell family Π from Section 5. 7. Round Q to a deterministic predictor h as in Lemma 6.2. For the query-efficient implementation, draw for each rounding cell C ∈ Π an independent pair (τC , UC ) with τC uniform on {1, . . . , T } and UC uniform on [0, 1]; for x ∈ C, reconstruct qτC (x) and set h(x) by applying its inverse-CDF sampler to UC . 8. Output: the deterministic grid predictor h : X → Λ.
19
Theorem 7.1 (Deterministic predictors with randomized-rate sample complexity). There is a universal constant C such that the following holds. For every distribution P on X × [0, 1], every finite nonempty group family G ⊆ [0, 1]X , and every ε ∈ (0, 1/10), Algorithm 3, with a sufficiently small universal choice α = cε, uses n≤C
(1/ε + log(|G| + 1)) log((1/ε + log(|G| + 2))/ε) ε2
samples and outputs a deterministic predictor h : X → Λ satisfying MCP (h; G) ≤ ε with probability at least 2/3 over the sample and the training randomness. In particular, if |G| ≤ ε−κ for any fixed κ > 0, then e −3 ). n = O(ε Moreover, Algorithm 3 has an implicit representation with the same statistical guarantee, training time polynomial in n0 , T , m, |G|, K, and d, and per-query evaluation time polynomial in |G|, K, d, log T , and log m. In the polynomial group regime |G| ≤ ε−κ , this running time is polynomial in 1/ε and d. The polynomial implementation claim follows from the factored exponential-weights representation and finite query reconstruction in Appendix B. Proof. Let Ecov and Erad be the events from Proposition 4.1, and set E0 = Ecov ∩ Erad . By that proposition, after adjusting constants, P(E0 ) ≥ 0.85. Let Epart be the partition event of Lemma 5.2. Since P(Epart ) ≥ 0.95, a union bound gives P(E0 ∩ Epart ) ≥ 0.80. Condition on the confidence and partition samples S0 , S2 such that E0 ∩ Epart holds. Set Ux = Ix . Proposition 4.1 gives µ(x) ∈ Ux for every x, and Λx γ-covers Ux for every x. Thus, on the event we have conditioned on, the learned interval-hint system is γ-valid. Apply Theorem 3.1 with failure probability 0.05. Since 1/γ + log |G| + O(1) ≤ CL and
L , α2 taking C0 sufficiently large gives, with conditional probability at least 0.95 over the online-learning sample S1 and the online procedure, r ! L MCP (Q; G) ≤ Con γ + ≤ C4 α. (3) T T = C0
The predictor Q is supported on Λx for every x.
20
The algorithm sets γ = α/64, so the hypothesis γ ≤ α/2 in Lemma 6.2 holds. On the event (3), that lemma gives, with probability at least 0.99 over the rounding seeds, a deterministic predictor h with MCP (h; G) ≤ MCP (Q; G) + C3 α ≤ (C3 + C4 )α. Choose the universal constant c small enough that (C3 + C4 )α ≤ ε. The final rounding succeeds with probability at least 0.99 by Lemma 6.2. Therefore the total success probability is at least 0.80 · 0.95 · 0.99 > 2/3. Finally, K = O(1/α) = O(1/ε), and
L = O(1/ε + log(|G| + 1)),
1/ε + log(|G| + 2) J = O log . ε
Thus n = n0 + T + m = O
LJ α2
≤C
(1/ε + log(|G| + 1)) log((1/ε + log(|G| + 2))/ε) . ε2
e e −3 ). If |G| ≤ ε−κ for fixed κ, then L = O(1/ε), and hence n = O(ε It remains to justify the implementation and query-time claims in the theorem. During training, the confidence-interval data from S0 is computed by scanning the n0 confidence-sample points and maintaining the observed-context table. The partition data from S2 is computed by sorting the m partition-sample contexts lexicographically and assigning one sampler seed (τC , UC ) to each rounding cell induced by the sorted cutpoints. Appendix B shows that each exponential-weights t−1 rather than by |G|2K weights over signed calibration state is represented by the |G|K numbers Sg,v tests, that each online round solves one linear program with at most K + 1 variables, and that each update costs polynomial time in |G|K. Thus training is polynomial in n0 , T , m, |G|, K, and d. For query evaluation, the implicit evaluator locates the query’s rounding cell using O(d log m) lexicographic comparisons, retrieves its stored index τC , and reconstructs only qτC (x) from the corresponding online state. It then applies the inverse-CDF sampler for qτC (x) using the stored uniform seed UC . Therefore each query is polynomial in |G|, K, d, log T , and log m, with no need to reconstruct all T online predictions. In the polynomial group regime, the bounds on n0 , T , m, and K above are polynomial in 1/ε, including the logarithmic factors. We stated our main theorem for finite classes, but it easily extends to infinite classes that have finite covers. Corollary 7.2 (Infinite group classes from covers). Let G ⊆ [0, 1]X be any nonempty group class, and interpret MCP (h; G) with the supremum over g ∈ G. For a marginal distribution PX , let N1 (ρ, G, PX ) denote the least cardinality of an L1 (PX ) ρ-cover of G. There are universal constants C, c > 0 such that the following holds. Fix any distribution P on X × [0, 1] with marginal PX , and let ε ∈ (0, 1/10). If N = N1 (cε, G, PX ) < ∞ and such a cover is supplied to the learner, then there is an algorithm using n≤C
(1/ε + log(N + 1)) log((1/ε + log(N + 2))/ε) ε2
21
samples that outputs a deterministic predictor h : X → Λ satisfying MCP (h; G) ≤ ε with probability at least 2/3 over the sample and the training randomness. Proof. Let G0 be the supplied L1 (PX ) cover at radius cε, and run Theorem 7.1 on the finite family G0 with target accuracy ε/2. With probability at least 2/3, the resulting deterministic predictor h satisfies MCP (h; G0 ) ≤ ε/2. Now fix any g ∈ G and choose g0 ∈ G0 with E|g(X) − g0 (X)| ≤ cε. By the signed form in Lemma 2.3, for every sign pattern σ ∈ {±1}Λ , |E [(g − g0 )(X)σ(h(X))(h(X) − Y )]| ≤ E|g(X) − g0 (X)| ≤ cε, since h, Y ∈ [0, 1]. Thus the signed calibration error for g is at most the signed calibration error for g0 plus cε. Taking the supremum over g and choosing c small enough gives MCP (h; G) ≤ ε. The sample bound is the bound in Theorem 7.1, with constants adjusted for the target accuracy ε/2. Remark 7.3 (Pseudo-dimension classes). If G ⊆ [0, 1]X has pseudo-dimension p, standard covering estimates for bounded real-valued classes [Haussler, 1992] imply that, for every marginal PX and every ρ > 0, Cp C N1 (ρ, G, PX ) ≤ ρ for a universal constant C. Thus, when such a cover is available, Corollary 7.2 gives deterministic ECE multicalibration with sample complexity e ε−3 + p . O ε2 If the marginal distribution is not known, one can build the cover from an additional context-only 2 ) by the usual empirical-cover argument, in the same way as in Corollary 8.10. e sample of size O(p/ε e −3 + p/ε2 ). This keeps the total sample complexity at O(ε
8
Outcome indistinguishability and omniprediction
The scalar theorem was stated for ECE multicalibration, but was specialized to multicalibration only through the finite family of signed OI tests (x, v) 7→ g(x)σ(v). In this section we isolate the more general principle. Suppose we are given any finite collection of bounded OI tests A ⊆ [−1, 1]X ×[0,1] . The goal is to find a deterministic predictor whose residual h(X) − Y has small correlation with every test evaluated at the context and the prediction. The theorem below says that the same interval-hint learning idea and one-seed rounding construction give a deterministic predictor satisfying these constraints at the nearly optimal rate.
8.1
Finite OI test families
Fix a finite grid Λ ⊆ [0, 1]. For a randomized grid predictor Q : X → ∆(Λ) and a finite test family A, define the OI error as: " # X OIErrP (Q; A) = max E QX (v)a(X, v)(v − Y ) . a∈A
v∈Λ
22
For a deterministic predictor h : X → Λ, this specializes to OIErrP (h; A) = max |E [a(X, h(X))(h(X) − Y )]| . a∈A
The lemma below is the finite-test analogue of Theorem 3.1. Its proof uses the same interval-hint online-to-batch mechanism as Section 3: taking A = {(x, v) 7→ g(x)σ(v) : g ∈ G, σ ∈ {±1}Λ } recovers the signed-test guarantee underlying Theorem 3.1, with Lemma 2.3 converting that guarantee to ECE multicalibration. Concretely, the learner in the lemma is the finite-test variant of Algorithm 1, with the signed calibration class replaced by A± = {a, −a : a ∈ A}. At round t it maintains an exponential-weights distribution πt over A± , forms the mixture X ct (x, v) = πt (a)a(x, v), a∈A±
predicts with qt (x) = LPx (ct (x, ·)), updates the weights using the realized residuals X zta = qt (Xt )(v)a(Xt , v)(v − Yt ), v∈Λ
and outputs the averaged predictor Qx = T −1
P
t qt (x).
Lemma 8.1 (Finite-test learning from valid interval hints). There is a universal constant Coi such that the following holds. Let A ⊆ [−1, 1]X ×[0,1] be a finite nonempty family of tests, let Λ ⊆ [0, 1] be a finite grid, let δ ∈ (0, 1), and suppose the learner is given a γ-valid interval-hint system (Ux , Λx )x∈X for P . Then there is a learning algorithm which, given T i.i.d. samples from P and the interval-hint system, outputs a randomized grid predictor Q satisfying supp(Qx ) ⊆ Λx
for every x,
and, with probability at least 1 − δ, r OIErrP (Q; A) ≤ Coi
γ+
log(2|A|) + log(1/δ) T
! .
Proof. This is the same interval-hint online-to-batch proof as Lemmas 3.2 and 3.3, with the finite test family A and its negatives replacing the signed calibration tests. The endpoint LP is run against the current exponential-weights mixture of tests, the valid interval hint gives a one-step γ minimax bound, and the martingale online-to-batch step turns the online residual guarantees into population OI guarantees for the averaged predictor. Appendix D gives the full argument. Theorem 8.2 (Deterministic outcome indistinguishability for finite test families). There is a universal constant C such that the following holds. Let A ⊆ [−1, 1]X ×[0,1] be a finite nonempty test family. For every distribution P on X × [0, 1] and every ε ∈ (0, 1/10), there is an algorithm using n≤C
LA log(100LA /ε) , ε2
LA = log(2|A| + 2) + 100, 23
samples that outputs a deterministic grid predictor h : X → Λ satisfying OIErrP (h; A) ≤ ε with probability at least 2/3 over the sample and the training randomness. In particular, if e −2 ). |A| ≤ ε−κ for any fixed κ > 0, then n = O(ε Proof. The algorithm is the same three-way sample split as Algorithm 3. Set an internal accuracy α = cε for a sufficiently small universal constant c, set γ = α/64, and take the same uniform γ-net grid Λ. The only change is that the quantity called L in Sections 4–6 is replaced by L = LA = log(2|A| + 2) + 100, and J = 100 log(100L/α). Use LJ L L , T = C0 2 , m = C0 2 . 2 α α α The confidence sample S0 builds intervals Ix and allowed grid sets Λx exactly as in Section 4; the partition sample S2 builds the rounding cells exactly as in Section 5. Proposition 4.1 and Lemma 5.2 are unchanged with this value of L: with probability at least 0.80, the learned interval hints are valid, the atom radius bound is at most Cα2 /L, and the unobserved cell-mass sum is at most Cα2 /L. Condition on these events. The learned interval-hint system is γ-valid, so Lemma 8.1 with failure probability 0.05 produces a randomized grid predictor Q supported on Λx such that r ! L OIErrP (Q; A) ≤ C γ + ≤ C ′ α. T n0 = C0
Finally round Q using one independent seed per rounding cell, as in Proposition 6.1. On the same radius and partition events, 2 X X α VΠ = p2x rx2 + PX (C)2 ≤ C L x∈O0 ∩At(PX )
C∈Πunobs
and log(200|A|) ≤ CL. Proposition 6.1 with δ = 0.01 therefore gives, with probability at least 0.99 over the cell seeds, a deterministic grid predictor h satisfying OIErrP (h; A) ≤ OIErrP (Q; A) + Cα ≤ C ′′ α. Choosing c small enough gives the target error ε, and the success probabilities combine exactly as in Theorem 7.1. The stated sample bound follows from the definitions of n0 , T, m, L, and J.
8.2
Omniprediction
We now specialize Theorem 8.2 to omniprediction. In this subsection outcomes are binary, Y ∈ {0, 1}. For a loss ℓ : [0, 1] × {0, 1} → [0, 1] and a value p ∈ [0, 1], call any minimizer of (1 − p)ℓ(a, 0) + pℓ(a, 1) over a ∈ [0, 1] a Bayes act for ℓ at p. We assume throughout that, for each loss considered below, we have fixed one such Bayes act at every p, and write this choice as kℓ (p) ∈ argmin EZ∼Bernoulli(p) [ℓ(a, Z)], a∈[0,1]
using the chosen act when there are multiple minimizers. We also write ∆ℓ(u) = ℓ(u, 1) − ℓ(u, 0). 24
Definition 8.3 (Gopalan et al. [2022]). A deterministic predictor h : X → [0, 1] is an (L, H, ε)omnipredictor if E[ℓ(kℓ (h(X)), Y )] ≤ inf E[ℓ(f (X), Y )] + ε f ∈H
for every ℓ ∈ L.
Given a loss class L and a hypothesis class H ⊆ [0, 1]X , let ∆L ◦ H = {x 7→ ∆ℓ(f (x)) : ℓ ∈ L, f ∈ H}. We assume below that all functions in the auditor classes are bounded in [−1, 1]; other bounded ranges can be handled by rescaling. The route from OI tests to omniprediction follows the Loss OI reduction of Gopalan et al. [2023a], in the threshold-calibration and multiaccuracy formulation of Okoroafor et al. [2025, Section 3]. It has three ingredients. Threshold tests in the prediction value give threshold calibration; context-only auditor tests give multiaccuracy for the loss-derived class ∆L ◦ H; and the omniprediction argument of Gopalan et al. [2023a], Okoroafor et al. [2025] combines threshold calibration and multiaccuracy. We spell out these implications in our notation below. For θ ∈ [0, 1], let Tθ (v) = 1{v ≤ θ}. When predictions are supported on a finite grid Λ, only |Λ| + 1 different threshold functions can appear on Λ. Let ΘΛ contain one representative for each distinct restriction of Tθ to Λ. For a randomized grid predictor Q : X → ∆(Λ), define threshold calibration and multiaccuracy errors by " # X QX (v)1{v ≤ θ}(v − Y ) TCalP (Q; ΘΛ ) = max E θ∈ΘΛ
and
v∈Λ
"
#
MAP (Q; C) = max E c(X) c∈C
X
QX (v)(v − Y )
.
v∈Λ
For deterministic h, we again identify h with the point-mass predictor QX = δh(X) . We next record the elementary monotonicity fact that converts the finite threshold tests into the errors used by the omniprediction reduction. This is the population version of the Bayes-act/proper-loss observation used by Okoroafor et al. [2025, Theorem 3.1]: after Bayes-act postprocessing, an arbitrary loss induces a threshold-calibration residual. Lemma 8.4 (Threshold calibration controls Bayes-act residuals). Let ℓ : [0, 1] × {0, 1} → [0, 1] be a bounded loss with a fixed Bayes-act choice kℓ , and set sℓ (v) = ∆ℓ(kℓ (v)). If Q is supported on a finite grid Λ, ΘΛ contains one representative for every threshold sublevel-set pattern on Λ, and V ∼ QX conditionally on X, then |E[(Y − V )sℓ (V )]| ≤ 3 TCalP (Q; ΘΛ ). Proof. We first show that sℓ is nonincreasing. Fix 0 ≤ a < b ≤ 1 and set d0 = ℓ(kℓ (b), 0) − ℓ(kℓ (a), 0),
d1 = ℓ(kℓ (b), 1) − ℓ(kℓ (a), 1). 25
For q ∈ [0, 1], define the affine function F (q) = (1 − q)d0 + qd1 = EZ∼Bernoulli(q) [ℓ(kℓ (b), Z) − ℓ(kℓ (a), Z)]. Since kℓ (a) is a Bayes act at mean a, we have F (a) ≥ 0. Since kℓ (b) is a Bayes act at mean b, we have F (b) ≤ 0. Because F is affine and a < b, its slope is nonpositive: d1 − d0 =
F (b) − F (a) ≤ 0. b−a
But d1 − d0 = ℓ(kℓ (b), 1) − ℓ(kℓ (b), 0) − ℓ(kℓ (a), 1) − ℓ(kℓ (a), 0) = sℓ (b) − sℓ (a). Thus sℓ is nonincreasing. Also sℓ (v) ∈ [−1, 1] because ℓ is [0, 1]-valued. Write the grid as Λ = {v1 < · · · < vK }. Let b0 = sℓ (vK ) and, for i < K, let bi = sℓ (vi ) − sℓ (vi+1 ) ≥ 0. Then for every vj ∈ Λ, sℓ (vj ) = b0 +
K−1 X
bi 1{vj ≤ vi },
i=1
and |b0 | +
K−1 X
bi ≤ 3.
i=1
The constant term is the threshold 1{v ≤ 1}. Therefore, by the definition of TCalP (Q; ΘΛ ), each term in this decomposition has residual correlation at most TCalP (Q; ΘΛ ) in absolute value. Since " # X E[(Y − V )sℓ (V )] = −E QX (v)sℓ (v)(v − Y ) , v∈Λ
the coefficient bound gives the claim. Definition 8.5 (Finite auditor representation). Fix a marginal distribution PX and a class D ⊆ [−1, 1]X . A finite auditor class C ⊆ [−1, 1]X (λ, ρ)-represents D under PX if every c⋆ ∈ D admits an approximation " # X X ⋆ E c (X) − βi ci (X) ≤ ρ, ci ∈ C, |βi | ≤ λ i
i
where the expectation is over X ∼ PX . If the same inequality holds with supx in place of the expectation, then the representation is uniform and holds under every distribution. This representation packages the finite approximate bases and spanned classes used by Okoroafor et al. [2025, Definitions 4.3–4.4] into the population finite-auditor form needed by our OI theorem. Thus MAP (Q; C) ≤ β implies multiaccuracy with respect to all of D at error at most λβ + ρ, since the residual term is bounded by one. This is the same linearity observation as in Okoroafor et al. [2025, Lemmas 4.11 and 4.14]. The next lemma is the Loss OI omniprediction reduction of Gopalan et al. [2023a], adapted to the threshold-calibration formulation of Okoroafor et al. [2025, Lemma 3.2], randomized grid predictors, and the finite-auditor representation above. We give the proof for completeness. 26
Lemma 8.6 (Omniprediction from threshold calibration and multiaccuracy). Let P be a distribution on X × {0, 1} with marginal PX , let Q be supported on a finite grid Λ, and let ΘΛ contain one representative for every threshold sublevel-set pattern on Λ. Suppose C (λ, ρ)-represents ∆L ◦ H under PX . If Q satisfies TCalP (Q; ΘΛ ) ≤ β
and
MAP (Q; C) ≤ β,
then Q is an (L, H, O((1 + λ)β + ρ))-omnipredictor, where for randomized Q the loss is interpreted as EX,Y EV ∼QX [ℓ(kℓ (V ), Y )]. In particular, the same conclusion holds for deterministic predictors. Proof. Let V ∼ QX , conditionally independently given X, and let Z ∼ Bernoulli(V ), conditionally independently given (X, V ). Fix a loss ℓ ∈ L and a benchmark f ∈ H. By the definition of the Bayes act, E[ℓ(kℓ (V ), Z) | X, V ] ≤ E[ℓ(f (X), Z) | X, V ], and hence the same inequality holds after averaging. It remains to compare the predictor-induced label Z with the true label Y on the two sides. For the postprocessed predictor, |E[ℓ(kℓ (V ), Y ) − ℓ(kℓ (V ), Z)]| = |E[(Y − V )∆ℓ(kℓ (V ))]| . Lemma 8.4 bounds this quantity by 3 TCalP (Q; ΘΛ ) = O(β). For the benchmark side, |E[ℓ(f (X), Y ) − ℓ(f (X), Z)]| = |E[(Y − V )∆ℓ(f (X))]| . The function x 7→ ∆ℓ(f (x)) lies P in ∆L ◦ H. By the representation assumption, it is within L1 (PX ) P error ρ of a linear combination i βi ci with ci ∈ C and i |βi | ≤ λ. Since |Y − V | ≤ 1, this gives |E[(Y − V )∆ℓ(f (X))]| ≤ λ MAP (Q; C) + ρ ≤ λβ + ρ. Combining these two comparisons with the ideal inequality under Z, and then taking the infimum over f ∈ H and the supremum over ℓ ∈ L, proves the lemma. Theorem 8.7 (Deterministic omniprediction from finite auditors). Let L be a class of losses ℓ : [0, 1] × {0, 1} → [0, 1] satisfying the Bayes-act convention above, let H ⊆ [0, 1]X , and let C ⊆ [−1, 1]X be a finite auditor class. There are universal constants C, c > 0 such that the following holds. For every ε ∈ (0, 1/10) and every distribution P on X × {0, 1}, with marginal PX , if C (λ, ρ)-represents ∆L ◦ H under PX with ρ ≤ cε, then there is an algorithm using (1 + λ)2 Lomni log(100(1 + λ)Lomni /ε) 1+λ + 2 + 100, n≤C , Lomni = log |C| + ε2 ε samples and outputs a deterministic grid predictor h : X → Λ that is an (L, H, ε)-omnipredictor with probability at least 2/3. In particular, for constant λ and |C| ≥ 2, this is e log |C| + log(1/ε) . n=O ε2 27
Proof. Set the OI-test accuracy
ε 1+λ for a sufficiently small universal constant c0 . Use the construction from Theorem 8.2 at accuracy α: first build its uniform grid Λ, and then define the threshold representatives ΘΛ for this grid. Run the construction with the test family α = c0
Aomni = {(x, v) 7→ c(x) : c ∈ C} ∪ {(x, v) 7→ 1{v ≤ θ} : θ ∈ ΘΛ }. Since |Λ| = O(1/α) = O((1 + λ)/ε), we have |Aomni | ≤ |C| + O
1+λ ε
.
The resulting deterministic predictor h satisfies MAP (h; C) ≤ α, and TCalP (h; ΘΛ ) ≤ α. The representation assumption gives multiaccuracy with respect to ∆L ◦ H at error at most λα + ρ. Lemma 8.6 therefore implies that h is an (L, H, O((1 + λ)α + ρ))-omnipredictor. The choices of c0 and c make this error at most ε. The sample bound follows from Theorem 8.2 with target accuracy α and the bound above on |Aomni |. Corollary 8.8 (Finite-class deterministic omniprediction). If L and H are finite, then log |L| + log |H| + log(1/ε) e n=O ε2 samples suffice for a deterministic (L, H, ε)-omnipredictor, with constant success probability. Proof. Take C = ∆L ◦ H, so λ = 1, ρ = 0, and |C| ≤ |L||H|. Corollary 8.9 (Deterministic omniprediction from covers). Let D = ∆L ◦ H ⊆ [−1, 1]X . For a marginal distribution PX , let N1 (ρ, D, PX ) denote the least cardinality of an L1 (PX ) ρ-cover of D. There are universal constants C, c > 0 such that the following holds. Fix any distribution P on X × {0, 1} with marginal PX , and let ε ∈ (0, 1/10). If N = N1 (cε, D, PX ) < ∞ and such a cover is supplied to the learner, then there is an algorithm using Lcov log(100Lcov /ε) 1 n≤C , Lcov = log N + + 2 + 100, ε2 ε samples that outputs a deterministic (L, H, ε)-omnipredictor with probability at least 2/3. The same conclusion holds distribution-free whenever D has a uniform cε-cover of cardinality N . Proof. Let C be the supplied L1 (PX ) cover. Then C (1, cε)-represents D under PX in the sense of Definition 8.5. The result follows from Theorem 8.7. 28
Corollary 8.10 (Pseudo-dimension auditor classes). Let D = ∆L ◦ H ⊆ [−1, 1]X have pseudodimension p. Then there is an algorithm that for every distribution P on X × {0, 1} and every 2 ) to construct a finite auditor cover e ε ∈ (0, 1/10) uses a fourth, context-only sample of size O(p/ε and uses, in total, p + log(1/ε) e n=O ε2 samples and outputs a deterministic (L, H, ε)-omnipredictor with probability at least 2/3. Proof. Standard covering estimates for bounded real-valued classes of pseudo-dimension p [Haussler, 1992] imply that for every marginal PX and every ρ > 0, Cp C N1 (ρ, D, PX ) ≤ ρ for a universal constant C. Applying Corollary 8.9 with ρ = cε gives the above rate when such a cover is available. To obtain the stated sample complexity without knowing PX , draw an independent context 2 ), or equivalently set aside this many labeled examples and ignore e sample of size m = O(p/ε their labels. Uniform convergence for the pairwise absolute-difference class {|d − d′ | : d, d′ ∈ D} implies that, with high constant probability, empirical L1 distances on this sample approximate their population L1 (PX ) values to accuracy O(ε) uniformly over d, d′ ∈ D. On this event, any empirical c′ ε-cover is a population cε-cover after adjusting constants. Haussler’s covering bound also controls the size of such an empirical cover by (C/ε)Cp . Run the finite-test learner on this cover and take constants large enough for the two success events; the cover-building sample and the learner’s sample together remain within the claimed rate, and the overall success probability is at least 2/3. Corollary 8.11 (Derandomizing finite-basis offline omniprediction). For every ε ∈ (0, 1/10) and every distribution P on X × {0, 1} with marginal PX , let Cε be any finite auditor class that (λ, ρ)-represents ∆L ◦ H under PX in the sense of Definition 8.5, with ρ ≤ cε for the universal constant in Theorem 8.7. Then the corresponding finite-basis offline omniprediction guarantee can be realized by a deterministic grid-valued predictor using (1 + λ)2 (log |Cε | + log(1/ε)) e O ε2 samples, with constant success probability. In particular, instantiating Cε with the finite approximate bases, spanned classes, or covers used in the offline constructions of Okoroafor et al. [2025, Definitions 4.3–4.4 and Section 6] gives deterministic offline omnipredictors at the same (nearly) optimal statistical rate of Okoroafor et al. [2025]. Proof. Apply Theorem 8.7 to C = Cε . The theorem uses only the finite OI tests induced by Cε and the O(1/ε) threshold representatives on the prediction grid, so the sample bound follows from |Aomni | ≤ |Cε | + O((1 + λ)/ε). The final statement is obtained by taking Cε to be the finite basis or cover supplied by the offline omniprediction theorem being instantiated. e For example, whenever such a finite auditor class has log |Cε | = O(d), constant coefficient norm, and approximation error ρ = O(ε) for the relevant loss/hypothesis family, Corollary 8.11 gives a deterministic omnipredictor with sample complexity e d + log(1/ε) , O ε2 29
matching the randomized offline rate up to logarithmic factors. The new ingredient here is only the derandomization: the finite-cover or basis construction is inherited from the omniprediction theorem being instantiated.
Acknowledgements We thank Jiuyao Lu for helpful comments — in particular suggesting a simpler test time implementation, and noting that the sample on which confidence intervals are computed can also be used to compute split points, removing the need for a third split.
References Sivaraman Balakrishnan, Nika Haghtalab, Daniel Hsu, Brian Lee, and Eric Zhao. Panprediction: Optimal predictions for any downstream task and loss. In Twenty-Ninth International Conference on Artificial Intelligence and Statistics, 2026. URL https://arxiv.org/abs/2510.27638. Sı́lvia Casacuberta, Cynthia Dwork, and Salil Vadhan. Complexity-theoretic implications of multicalibration. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1071–1082, 2024. Natalie Collina, Surbhi Goel, Varun Gupta, and Aaron Roth. Tractable agreement protocols. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1532–1543, 2025. Natalie Collina, Ira Globus-Harris, Surbhi Goel, Varun Gupta, Aaron Roth, and Mirah Shi. Collaborative prediction: Tractable information aggregation via agreement. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2026a. Natalie Collina, Jiuyao Lu, Georgy Noarov, and Aaron Roth. Optimal lower bounds for online multicalibration. arXiv preprint arXiv:2601.05245, 2026b. Natalie Collina, Jiuyao Lu, Georgy Noarov, and Aaron Roth. The sample complexity of multicalibration. arXiv preprint arXiv:2604.21923, 2026c. doi: 10.48550/arXiv.2604.21923. URL https://arxiv.org/abs/2604.21923. Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich, Robert Kleinberg, and Princewill Okoroafor. Breaking the T 2/3 barrier for sequential calibration. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2007–2018. ACM, 2025. doi: 10.1145/3717823.3718178. A Philip Dawid. The well-calibrated bayesian. Journal of the American Statistical Association, 77 (379):605–610, 1982. A. Dvoretzky, A. Wald, and J. Wolfowitz. Elimination of randomization in certain statistical decision procedures and zero-sum two-person games. The Annals of Mathematical Statistics, 22(1):1–21, 1951. doi: 10.1214/aoms/1177729689. URL https://doi.org/10.1214/aoms/1177729689. Cynthia Dwork and Pranay Tankala. Supersimulators. arXiv preprint arXiv:2509.17994, 2025.
30
Cynthia Dwork, Michael P Kim, Omer Reingold, Guy N Rothblum, and Gal Yona. Outcome indistinguishability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1095–1108, 2021. Sumegha Garg, Christopher Jung, Omer Reingold, and Aaron Roth. Oracle efficient online multicalibration and omniprediction. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2725–2792. Society for Industrial and Applied Mathematics, 2024. Rohan Ghuge, Vidya Muthukumar, and Sahil Singla. Improved and oracle-efficient online ℓ1 multicalibration. In Proceedings of the 42nd International Conference on Machine Learning, pages 19437–19457. PMLR, 2025. Isaac Gibbs and Ryan J. Tibshirani. Sample-efficient omniprediction for proper losses. In Proceedings of Thirty Ninth Conference on Learning Theory. PMLR, 2026. Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 79:1–79:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. Parikshit Gopalan, Lunjia Hu, Michael P Kim, Omer Reingold, and Udi Wieder. Loss minimization through the lens of outcome indistinguishability. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), 2023a. Parikshit Gopalan, Michael Kim, and Omer Reingold. Swap agnostic learning, or characterizing omniprediction via multicalibration. In Advances in Neural Information Processing Systems, volume 36, pages 39936–39956, 2023b. Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth. Online multivalid learning: Means, moments, and prediction intervals. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 82:1–82:24. Schloss Dagstuhl – LeibnizZentrum für Informatik, 2022. Nika Haghtalab, Michael I. Jordan, and Eric Zhao. A unifying perspective on multi-calibration: Game dynamics for multi-objective learning. In Advances in Neural Information Processing Systems, volume 36, pages 72464–72506, 2023. David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78–150, 1992. doi: 10.1016/ 0890-5401(92)90010-D. Ursula Hebert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In Proceedings of the 35th International Conference on Machine Learning, pages 1939–1948. PMLR, 2018. Lunjia Hu and Charlotte Peale. Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 72:1–72:30, Dagstuhl, Germany, 2023. Schloss Dagstuhl – LeibnizZentrum für Informatik. ISBN 978-3-95977-263-1. doi: 10.4230/LIPIcs.ITCS.2023.72. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.72. 31
Lunjia Hu, Charlotte Peale, and Omer Reingold. Metric entropy duality and the sample complexity of Outcome Indistinguishability. In Sanjoy Dasgupta and Nika Haghtalab, editors, Proceedings of The 33rd International Conference on Algorithmic Learning Theory, volume 167 of Proceedings of Machine Learning Research, pages 515–552. PMLR, 29 Mar–01 Apr 2022. URL https: //proceedings.mlr.press/v167/hu22a.html. Michael Kearns, Aaron Roth, and Emily Ryu. Networked information aggregation via machine learning. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4799–4845. SIAM, 2026. Kasper Green Larsen, Omar Montasser, and Nikita Zhivotovskiy. Derandomizing multi-distribution learning. In Advances in Neural Information Processing Systems 37 (NeurIPS 2024), 2024. doi: 10.52202/079017-2989. URL https://arxiv.org/abs/2409.17567. Daniel Lee, Georgy Noarov, Mallesh Pai, and Aaron Roth. Online minimax multiobjective optimization: Multicalibeating and other applications. Advances in Neural Information Processing Systems, 35:29051–29063, 2022. Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. High-dimensional prediction for sequential decision making. In Proceedings of the 42nd International Conference on Machine Learning, pages 46762–46783. PMLR, 2025. Princewill Okoroafor, Robert Kleinberg, and Michael P. Kim. Near-optimal algorithms for omniprediction. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1595–1609, 2025. Binghui Peng. The sample complexity of multi-distribution learning. In The Thirty Seventh Annual Conference on Learning Theory, pages 4185–4204. PMLR, 2024. Mingda Qiao and Gregory Valiant. Stronger calibration lower bounds via sidestepping. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 456–466. ACM, 2021. doi: 10.1145/3406325.3451050. Harrison Rosenberg, Robi Bhattacharjee, Kassem Fawaz, and Somesh Jha. An exploration of multicalibration uniform convergence bounds. arXiv preprint arXiv:2202.04530, 2022. Aaron Roth and Mirah Shi. Forecasting for swap regret for all downstream agents. In Proceedings of the 25th ACM Conference on Economics and Computation, pages 466–488, 2024. Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff–Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223–250, 1995. doi: 10.1137/S089548019223872X. URL https://doi.org/10.1137/S089548019223872X. Eliran Shabat, Lee Cohen, and Yishay Mansour. Sample complexity of uniform convergence for multicalibration. In Advances in Neural Information Processing Systems, volume 33, pages 13331–13340, 2020. Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171–176, 1958. doi: 10.2140/pjm.1958.8.171. URL https://msp.org/pjm/1958/8-1/pjm-v8-n1-p14-s.pdf. Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S Du, and Jason D Lee. Optimal multi-distribution learning. In The Thirty Seventh Annual Conference on Learning Theory, pages 5220–5223. PMLR, 2024. 32
A
Deferred online-to-batch proofs
Proof of Lemma 3.2. Let T = G × {±1}Λ ,
M = |T | = |G|2K .
Set A = log M + log(3/δ). If T < A, the conclusion is trivial after increasing the universal constant, since each signed payoff lies in [−1, 1]. Assume T ≥ A. For a signed calibration test r = (g, σ) ∈ T , write X ϕr (x, v, m) = g(x)σ(v)(v − m), ϕr (x, q, m) = q(v)ϕr (x, v, m). v∈Λx
We first record the one-step minimax fact. Fix a context x for which Λx γ-covers Ux and fix π ∈ ∆(T ). There exists q ∈ ∆(Λx ) such that X sup π(r)ϕr (x, q, m) ≤ γ. (4) m∈Ux r∈T
Indeed, for each fixed m ∈ Ux , choose a ∈ Λx with |a − m| ≤ γ. Then X X π(r)ϕr (x, a, m) ≤ |a − m| π(r) ≤ γ. r∈T
r∈T
P Thus supm inf q r π(r)ϕr (x, q, m) ≤ γ, and Sion’s minimax theorem Sion [1958] gives (4). The endpoint LP computes such a q, because the payoff is affine in m. Run p Algorithm 1, and write πt for its weight distribution before round t. The algorithm uses η = A/T ≤ 1. By the minimax fact and validity of the realized hint, qt (Xt ) satisfies (4). For r = (g, σ), let X ztr = g(Xt ) qt (Xt )(v)σ(v)(v − Yt ). v∈Λ
Then ztr ∈ [−1, 1]. Let Wt =
r r πt (r)zt . Since the conditional mean mt lies in UXt ,
P
E[Wt | X1 , Y1 , . . . , Xt−1 , Yt−1 , Xt ] ≤ γ. Azuma–Hoeffding gives, with probability at least 1 − δ/3, T X
Wt ≤ γT + C
p T log(3/δ).
t=1
The exponential-weights regret bound for gains in [−1, 1] gives, simultaneously for every r ∈ T , T X
ztr ≤
t=1
T X
Wt +
t=1
log M + CηT. η
Combining the two bounds and the choice of η proves r T 1X r log M + log(3/δ) max zt ≤ γ + C r∈T T T t=1
with probability at least 1 − δ/3. 33
Proof of Lemma 3.3. By the definition of Q, " # T X 1X Ar (S) = E(X,Y )∼P g(X) qt (X)(v)σ(v)(v − Y ) . T t=1
v∈Λ
For each fixed signed calibration test, define " # X r Dt = E(X,Y )∼P g(X) qt (X)(v)σ(v)(v − Y ) − ztr . v∈Λ
Since qt is determined before the fresh draw (Xt , Yt ), (Dtr )Tt=1 is a martingale difference sequence with |Dtr | ≤ 2. Azuma–Hoeffding and a union bound over T give the claimed uniform bound. Proof of Theorem 3.1. Set K = |Λ| and T = G × {±1}Λ ,
M = |T | = |G|2K .
Run Algorithm 1 on the i.i.d. sample. Since the interval-hint system is γ-valid, Lemma 3.2 gives r T log M + log(3/δ) 1X r zt ≤ γ + C max r∈T T T t=1
with probability at least 1 − δ/3. Define the batch predictor by averaging the online rules: T
Qx (v) =
1X qt (x)(v). T t=1
Since qt (x)(v) = 0 when v ∈ / Λx , supp(Qx ) ⊆ Λx for every x. Lemma 3.3 converts the empirical bound into the same population bound, up to another r log M + log(3/δ) C T term. On the intersection of these events, which has probability at least 1 − δ, every signed calibration test has population score at most ! r K + log |G| + log(1/δ) C γ+ . T Because T contains both signs of every σ, Lemma 2.3 turns this signed-test bound into MCP (Q; G). Finally, in Theorem 3.1 we have K = |Λ| ≤ Cgrid /γ, giving the stated bound after adjusting the universal constant.
B
Factored implementation and query representation
Here we justify Algorithm 2. Let t−1 Sg,v =
X
g(Xs )qs (Xs )(v)(v − Ys )
s<t
34
be the cumulative calibration bias for group g and grid value v before round t. The direct exponential-weights distribution assigns signed calibration test (g, σ) weight proportional to ! X t−1 exp η σ(v)Sg,v . v∈Λ
For each fixed group, ! X σ∈{±1}Λ
exp η
X
t−1 σ(v)Sg,v
v∈Λ
=
Y
t−1 2 cosh(ηSg,v ).
v∈Λ
Thus the marginal weight of group g is t−1 v∈Λ 2 cosh(ηSg,v ) Q t−1 , g ′ ∈G v∈Λ 2 cosh(ηSg ′ ,v )
Q
πt (g) = P and, conditional on g,
t−1 E[σ(v) | g] = tanh(ηSg,v ).
Therefore the weighted one-step objective can be computed from the coefficients X t−1 ct (x, v) = πt (g)g(x) tanh(ηSg,v ), g∈G
which are exactly the coefficients used in Algorithm 2. The same endpoint LP (1) then computes the next distribution qt (x). During training, the learner solves this LP only at the realized context Xt and updates t t−1 Sg,v = Sg,v + g(Xt )qt (Xt )(v)(v − Yt ),
g ∈ G, v ∈ Λ.
This uses |G|K stored numbers rather than |G|2K signed-test weights. The batch randomized predictor T
1X qt (x) Qx = T t=1
need not be materialized on all of X . The learner stores the online states, the confidence-interval table from S0 , the sorted distinct contexts from S2 , and one sampler seed (τC , UC ) for each rounding cell. On query x, it finds the singleton, gap, or cutpoint cell containing x, recomputes only qτC (x) from the stored state at time τC , and returns the inverse-CDF value for qτC (x) at the seed UC . Since τC is uniform on {1, . . . , T }, this has the same marginal law as sampling from Qx , but it avoids reconstructing all T distributions at query time.
C
Concentration for learned interval hints
For the concrete constants used in the main proof, take α 1 i γ= , Ngrid = , Λ= : i = 0, 1, . . . , Ngrid . 64 γ Ngrid 35
Then Λ contains 0 and 1, is a γ-net of [0, 1], and has size K = |Λ| = Ngrid + 1 ≤ We use
192 . α
L = K + log(|G| + 1) + 100,
J = 100 log
100L α
,
n0 = C0
LJ . α2
Proof of Proposition 4.1. First note that, with probability one, no non-atom appears twice in S0 . Indeed, for each pair i < j, P Xi = Xj ∈ / At(PX ) = E [1{Xi ∈ / At(PX )}PX ({Xi })] = 0, and there are only finitely many pairs. We include this full-probability event in Ecov . Condition on any multiset of contexts with this no-repeated-non-atom property. If Nx ≥ 2, then x is an atom, and the labels with context x are independent [0, 1]-valued variables with mean µ(x). Hoeffding’s inequality gives ! r J P |b µx − µ(x)| > X1 , . . . , Xn0 ≤ 2e−2J . Nx There are at most n0 contexts with Nx ≥ 2. Since J is a sufficiently large multiple of log(100L/α) and n0 ≤ CLJ/α2 , the union bound gives failure probability at most 0.01. This defines Ecov . On Ecov , if Nx ≥ 2 then µ(x) ∈ Ix . If Nx = 0, then Ix = [0, 1] by definition. If Nx = 1, then rx = 1 because J ≥ 1, and µ bx ∈ [0, 1], so again Ix = [0, 1]. Thus µ(x) ∈ Ix for every x. If m ∈ Ix , then the γ-net property gives a ∈ Λ with |a − m| ≤ γ. By definition of Λx , this a belongs to Λx . Therefore the learned interval-hint system is γ-valid. It remains to prove the radius event. It suffices to show X α2 ES0 p2x rx2 ≤ C , L x∈At(PX )
because Markov’s inequality then gives an event Erad of probability at least 0.90 on which this same sum is at most C1 α2 /L, after increasing the universal constant C1 . All summands are nonnegative, so we may sum one-point expectation bounds over the countable atom set. Fix an atom x with mass p = px and let N = Nx ∼ Bin(n0 , p). Define ( 1, N = 0, p r(N ) = min{1, J/N }, N ≥ 1. We first show E[p2 r(N )2 ] ≤ C
J p. n0
(5)
Let λ = n0 p. If λ ≤ 2J, then p2 ≤ (2J/n0 )p, and (5) follows because r(N )2 ≤ 1. If λ > 2J, then E[r(N )2 ] ≤ P(N < λ/2) +
2J . λ
By a Chernoff bound, P(N < λ/2) ≤ e−λ/8 . Since λe−λ/8 is uniformly bounded for λ > 0, p2 e−λ/8 =
p −λ/8 p λe ≤C . n0 n0 36
Also p2 (2J/λ) = 2Jp/n0 . Thus (5) holds in all cases. Summing (5) over the atoms gives X
E
p2x rx2 ≤ C
x∈At(PX )
J α2 ≤C , n0 L
using n0 = C0 LJ/α2 . Markov’s inequality gives Erad , and the final probability statement follows by the union bound.
D
Deferred proof for finite OI tests
Proof of Lemma 8.1. Let T = A± = {a, −a : a ∈ A},
M = |T | ≤ 2|A|.
Run exponential weights over T . At round t, after the past history has fixed the distribution πt ∈ ∆(T ), set X ct (x, v) = πt (a)a(x, v), v ∈ Λ, a∈T
and choose qt (x) = LPx (ct (x, ·)). The one-step minimax step is identical to the one in Lemma 3.2. Fix a context x where the hint is valid and a distribution π ∈ ∆(T ). For every m ∈ Ux , choose vm ∈ Λx with |vm − m| ≤ γ. Since every test is bounded by one, X π(a)a(x, vm )(vm − m) ≤ γ. a∈T
Sion’s minimax theorem Sion [1958] gives an action q ∈ ∆(Λx ) whose expected payoff is at most γ for every mean value in Ux , and the endpoint LP computes such an action. For a ∈ T , write X zta = qt (Xt )(v)a(Xt , v)(v − Yt ) ∈ [−1, 1]. v∈Λ
Let Wt =
a a∈T πt (a)zt . Since µ(Xt ) ∈ UXt and qt (Xt ) satisfies the one-step minimax bound,
P
E[Wt | X1 , Y1 , . . . , Xt−1 , Yt−1 , Xt ] ≤ γ. Azuma–Hoeffding gives, with probability at least 1 − δ/4, T X
Wt ≤ γT + C
p T log(1/δ).
t=1
The standard exponential-weights regret bound gives, simultaneously for every a ∈ T , T X
zta ≤
t=1
T X
Wt + C
p T log M .
t=1
Thus, with probability at least 1 − δ/2, T
1X a max zt ≤ γ + C a∈T T
r
t=1
37
log M + log(1/δ) . T
P Define the averaged batch predictor Qx (v) = T −1 t qt (x)(v). For each a ∈ T , the difference between " # T X 1X a zt E QX (v)a(X, v)(v − Y ) and T t=1
v∈Λ
is an average of martingale differences bounded by 2. Azuma–Hoeffding and a union bound over T control all these differences by r log M + log(1/δ) C T with probability at least 1 − δ/2. On the intersection of the two events, the population residual is bounded by the claimed quantity for every signed test in T . Since T contains both signs of each test in A, this is exactly OIErrP (Q; A). Finally, M ≤ 2|A| and supp(Qx ) ⊆ Λx because each online action has this support.
E
Deterministic panprediction from OI tests
We use the notation of Balakrishnan et al. [2026]. Outcomes are binary, Y ∈ {0, 1}. A group is a binary function g : X → {0, 1}, and Pg = P[g(X) = 1]. As in Section 8, fix a Bayes-act choice for each loss. For a loss ℓ : [0, 1] × {0, 1} → [−1, 1], write kℓ (p) ∈ argmin EZ∼Bernoulli(p) [ℓ(a, Z)] a∈[0,1]
using the chosen act when there are multiple minimizers. A deterministic predictor p : X → [0, 1] is an (L, G, H, ε)-panpredictor if, for every ℓ ∈ L and every g ∈ G with Pg > 0, ε E[ℓ(kℓ (p(X)), Y ) | g(X) = 1] ≤ inf E[ℓ(f (X), Y ) | g(X) = 1] + p . f ∈H Pg As in Balakrishnan et al. [2026], we consider losses of bounded variation in the first argument, normalized so that their threshold-basis approximation has universal constants. Definition E.1 (Step calibration). Let G be a group family and let H ⊆ [0, 1]X . A deterministic predictor p : X → [0, 1] is (G, H, η)-step calibrated if, for every g ∈ G, f ∈ H, and v, w ∈ [0, 1], η |E[(Y − p(X))1{p(X) ≤ v, f (X) ≤ w} | g(X) = 1]| ≤ p . Pg Lemma E.2 (Step calibration implies panprediction). For bounded-variation losses, every deterministic (G, H, η)-step calibrated predictor is an (L, G, H, Cη)-panpredictor, for a universal constant C. Proof. This is the deterministic reduction of Balakrishnan et al. [2026, Theorem 3.3]. We recall the short argument. Applied pointwise with q = p(X), the postprocessing kℓ (q) is optimal under a Bernoulli label with mean q, so for every comparator f , EZ∼Bernoulli(p(X)) [ℓ(kℓ (p(X)), Z)] ≤ EZ∼Bernoulli(p(X)) [ℓ(f (X), Z)] 38
pointwise in X. It remains to compare these predictor-induced label expectations to the true label expectation, group by group. Writing ∆ℓ(a) = ℓ(a, 1) − ℓ(a, 0), the two discrepancies are E[(Y − p(X))∆ℓ(kℓ (p(X))) | g(X) = 1] and E[(Y − p(X))∆ℓ(f (X)) | g(X) = 1]. The first discrepancy is controlled by the monotonicity argument of Lemma 8.4, applied under the conditional distribution given g(X) = 1. After rescaling the loss to [0, 1], that argument shows that u 7→ ∆ℓ(kℓ (u)) is a monotone function of u whose range is bounded by a universal constant, and hence has a threshold-basis representation with universal coefficient norm. Definition E.1 controls those threshold terms by using thresholds of p and setting the comparator threshold to 1. The second discrepancy is different: it involves ∆ℓ(f (X)), not the Bayes-act map. Here we use the bounded-variation normalization directly, which gives a threshold-basis representation with universal coefficient norm for the action-loss difference u 7→ ∆ℓ(u). Definition E.1 controls these terms by setting p the prediction threshold to 1 and using thresholds of f . Thus each discrepancy is at most O(η/ Pg ), and substituting these two comparisons into the ideal predictor-induced inequality gives the claimed panprediction guarantee. Theorem E.3 (Deterministic finite-class panprediction). Let L be a class of bounded-variation losses, let G be a finite family of binary groups, and let H ⊆ ΓX be a finite nonempty class of predictors taking values in a finite grid Γ ⊆ [0, 1]. Fix a distribution P on X × {0, 1} and suppose pmin = min Pg > 0. g∈G
Assume the values Pg are supplied to the learner. There is a universal constant C such that, for every ε ∈ (0, 1/10), there is an algorithm using √ Lpan log(100Lpan /(ε pmin )) n≤C ε2 pmin samples that outputs a deterministic predictor p : X → [0, 1] which is an (L, G, H, ε)-panpredictor with probability at least 2/3, where C Lpan = log 2|G||H|(|Γ| + 1) √ + 1 + 2 + 100. ε pmin In particular, if pmin is constant and |Γ|, |G|, and |H| are polynomially bounded in 1/ε, then e −2 ). n = O(ε √ Proof. Let τ = c0 ε pmin for a sufficiently small universal constant c0 . Run the finite-test OI learner of Theorem 8.2 with target accuracy τ . Let Λ be the prediction grid used by that learner, and let ΘΛ and ΘΓ contain one representative threshold for each distinct sublevel-set pattern on Λ and Γ, respectively. Thus |ΘΛ | ≤ |Λ| + 1 = O(1/τ ), 39
|ΘΓ | ≤ |Γ| + 1.
Use the OI test family r pmin g(x)1{z ≤ ϑ}1{f (x) ≤ ω} : g ∈ G, f ∈ H, ϑ ∈ ΘΛ , ω ∈ ΘΓ . Apan = (x, z) 7→ Pg p p The factor pmin /Pg converts a uniform OI error into the group-conditional 1/ Pg tolerance in Definition E.1, while keeping every test bounded by one. Theorem 8.2 therefore gives, with probability at least 2/3, a deterministic grid predictor p : X → Λ satisfying r pmin g(X)1{p(X) ≤ ϑ}1{f (X) ≤ ω}(p(X) − Y ) ≤ τ E Pg simultaneously for all choices of g, f, ϑ, ω above. Since p is Λ-valued and every f ∈ H is Γ-valued, the same inequality holds for arbitrary thresholds v, w ∈ [0, 1] after replacing them by their representatives. Rearranging and dividing by Pg yields |E[(Y − p(X))1{p(X) ≤ v, f (X) ≤ w} | g(X) = 1]| ≤ √
τ
c ε p = p0 . pmin Pg Pg
Thus p is (G, H, c0 ε)-step calibrated. Lemma E.2 implies that p is an (L, G, H, Cc0 ε)-panpredictor, and choosing c0 small enough gives the stated error. Finally, C |Apan | ≤ |G||H|(|Γ| + 1)(|Λ| + 1) ≤ |G||H|(|Γ| + 1) √ +1 , ε pmin and substituting this bound into Theorem 8.2 with target accuracy τ gives the stated sample complexity. Remark E.4 (Finitely covered classes). The finite-class assumption can be replaced by a finitecover assumption in the same way as in Corollary 8.9. The relevant class is the normalized threshold-conjunction class r pmin x 7→ g(x)1{f (x) ≤ w} : g ∈ G, f ∈ H, w ∈ [0, 1] . Pg Here pmin = ming∈G Pg , as in Theorem E.3. If a finite L1 (PX ) cover of this class at radius √ O(ε pmin ) is supplied, the same proof gives the corresponding logarithmic dependence on the cover size. For VC group classes and finite-pseudo-dimension benchmark classes, such covers can be built from an independent context sample by the usual empirical-cover argument, at the same e −2 p−1 ) scale. O(ε min
F
Removing training randomness
The algorithms in the body of the paper output prediction-time deterministic predictors, but they are presented with one source of training randomness: the final cell sampler seeds used for rounding. This randomness can also be removed. We state the argument for finite OI test families, since multicalibration is obtained by taking the signed calibration tests and the omniprediction applications use finite OI tests after the cover or basis reduction. The derandomization below is information-theoretic; it is not meant to preserve computational efficiency. 40
The idea is simple. Rather than picking the rounding-cell seeds randomly, we enumerate a smaller explicit family of candidate seed assignments, evaluate the resulting predictors on a holdout set, and then pick the best one. The idea on its own fails if we enumerate all fully independent seed assignments: the candidate family would be far too large for uniform convergence on a holdout set of the target size. The fix is to use seeds that are not truly independent, but only k-wise independent. Taking k on the order of log |A| (and the desired failure-probability parameter) is sufficient for the same rounding concentration argument, without exceeding our target sample complexity. Fix the setup of Proposition 6.1. Let Π be the finite family of rounding cells, let M = |Π|, and enumerate Λ = {v1 , . . . , vK }. For each x, let X X Fx (u) = vj when Qx (vi ) < u ≤ Qx (vi ), i<j
i≤j
with the endpoint convention Fx (0) = v1 . Lemma F.1 (Limited-independent cell rounding). There is a universal constant C such that the following holds. Let β, η ∈ (0, 1), and let q be a prime with q ≥ max{M, 4K/η}. Assign distinct identifiers ι(C) ∈ Fq to the cells C ∈ Π. Let k be an even integer with k ≥ C log
2|A| . β
For each polynomial p ∈ Fq [z] of degree less than k, define a deterministic predictor p(ι(C)) + 1/2 hp (x) = Fx for x ∈ C, q where the field element p(ι(C)) is identified with its representative in {0, . . . , q − 1}. Then at least a 1 − β fraction of these polynomials satisfy max E a(X, hp (X))(hp (X) − Y ) a∈A
"
# X
−E
QX (v)a(X, v)(v − Y )
v∈Λ
s ≤C
! 2|A| VΠ log +γ+η . β
Proof. Choose p uniformly from the q k polynomials of degree less than k. For any k distinct cells, the values p(ι(C)) are independent and uniform in Fq , so the induced cell seeds are k-wise independent and each is uniform on {(j + 1/2)/q : j = 0, . . . , q − 1}. Using midpoints avoids putting mass on the artificial endpoint u = 0 in the inverse-CDF convention. First compare this discrete seed to a continuous uniform seed. If J is uniform on {0, . . . , q − 1} e x is the distribution of Fx ((J + 1/2)/q), then for every function ψ : Λ → [−1, 1], and Q X v∈Λ
e x (v)ψ(v) − Q
X
Qx (v)ψ(v) ≤
v∈Λ
41
η 2K ≤ . q 2
(6)
Indeed, the probability of each inverse-CDF interval is approximated by the fraction of midpoints it contains, and the sum of the absolute errors over the K intervals is at most 2K/q. Write Ix = [ax , bx ] and define clipx (v) = min{max{v, ax }, bx }, as in Proposition 6.1. Fix a test a ∈ A and define the clipped payoff ψa,x (v) = a(x, v)(clipx (v) − µ(x)). For a cell C, set
q−1 X j + 1/2 p(ι(C)) + 1/2 1 ψa,x Fx dPX (x). Za,C = − ψa,x Fx q q q C Z
j=0
The variables {Za,C }C∈Π are mean zero and k-wise independent. Their ranges are bounded exactly as in the proof of Proposition 6.1: if C = {x} is an observed singleton, then |Za,C | ≤ 4px rx when px > 0 and Za,C = 0 when px = 0, while if C ∈ Πunobs then |Za,C | ≤ 2PX (C). Hence X ∥Za,C ∥2∞ ≤ C0 VΠ C∈Π
for a universal constant C0 . We use the standard Chernoff–Hoeffding moment bound for bounded k-wise independent P sums [Schmidt et al., 1995]: if ZC are mean-zero, k-wise independent, |ZC | ≤ bC , and B 2 = C b2C , then for even k, ! X √ P ZC > C1 B k ≤ exp(−k). C
For the simple form used here, this follows directly from the usual kth-moment proof for independent bounded sums, since the kth moment depends only on joint distributions of at most k coordinates. Applying this with B 2 ≤ C0 VΠ and our choice of k gives, for the fixed test a, s X 2|A| Za,C ≤ C2 VΠ log β C
except with probability at most β/|A|. A union bound controls all tests simultaneously. It remains to add back the two deterministic approximation terms. Equation (6), applied pointwise and integrated over x, contributes at most η/2 to the clipped payoff. The unclipped grid-rounding part contributes at most 2γ, exactly as in Proposition 6.1: the midpoint convention ensures hp (x) ∈ supp(Qx ) ⊆ Λx , and all grid values in Λx lie within distance γ of Ix . Absorbing constants proves the lemma. Lemma F.2 (Validation over a finite candidate list). Let H be any finite collection of deterministic predictors h : X → Λ, and let Sval be an independent validation sample of size Nval ≥ C
log(2|A||H|/δ) . η2
For h ∈ H, define the empirical OI error \ S (h; A) = max OIErr val a∈A
1 Nval
X (Xi ,Yi )∈Sval
42
a(Xi , h(Xi ))(h(Xi ) − Yi ) .
With probability at least 1 − δ over Sval , every h ∈ H satisfies \ S (h; A) − OIErrP (h; A) ≤ η. OIErr val Consequently, if some h⋆ ∈ H has OIErrP (h⋆ ; A) ≤ ρ, then any empirical minimizer b h has OIErrP (b h; A) ≤ ρ + 2η. Proof. For fixed h and a, the summands are in [−1, 1]. Hoeffding’s inequality and a union bound over A × H give the uniform deviation event. On this event, an empirical minimizer b h satisfies \ S (b \ S (h⋆ ; A) + η ≤ ρ + 2η. OIErrP (b h; A) ≤ OIErr h; A) + η ≤ OIErr val val
Theorem F.3 (Deterministic training for finite OI tests). There is a universal constant C such that the following holds. Let A ⊆ [−1, 1]X ×[0,1] be a finite nonempty test family, let LA = log(2|A| + 2) + 100, and let ε ∈ (0, 1/10). There is a deterministic learning algorithm which uses n≤C
LA log(CLA /ε) ε2
i.i.d. samples from P , outputs a deterministic grid predictor h : X → Λ satisfying OIErrP (h; A) ≤ ε with probability at least 2/3 over the sample. The same conclusion therefore applies to the finite-test multicalibration and omniprediction instantiations used in the body, with the same sample bounds e notation. up to the logarithmic factors already hidden in the O(·) Proof. Run the construction from Theorem 8.2 at internal accuracy α = cε, but do not draw the final independent rounding seeds. Instead, reserve an independent validation sample Sval ; all earlier samples are used exactly as in Theorem 8.2 to construct the interval hints, the rounding cells, and the randomized grid predictor Q. From the proof of Theorem 8.2, with probability at least 0.75 over these non-validation samples, the following three conclusions hold simultaneously: OIErrP (Q; A) ≤ C1 α,
supp(Qx ) ⊆ Λx
for every x,
VΠ ≤ C1
α2 . LA
Condition on this event. Let M = |Π| and choose a prime K q ≤ C2 M + + 10 with q ≥ max{M, 4K/α}, α which exists by Bertrand’s postulate after increasing C2 . The number of cells is at most the number of observed singletons plus the number of unobserved cells, so M ≤ n0 + m + 1; together with K = O(1/α) and the sample sizes in Theorem 8.2, this gives log q ≤ C log(CLA /α). Let k 43
be the smallest even integer at least C3 LA , and let H be the set of predictors hp obtained from all degree-(k − 1) polynomials over Fq as in Lemma F.1. Then |H| = q k ,
log |H| ≤ C4 LA log(C4 LA /α).
Lemma F.1, applied with β = 1/4 and η = α, implies that at least one h⋆ ∈ H satisfies s 2 α OIErrP (h⋆ ; A) ≤ OIErrP (Q; A) + C5 log(8|A|) + γ + α ≤ C6 α. LA \ S (h; A) over h ∈ H. Now use the validation sample to choose an empirical minimizer of OIErr val By Lemma F.2, a validation sample of size Nval ≥ C7
LA log(C7 LA /α) α2
is enough to ensure, with probability at least 0.95 over Sval , that the selected predictor b h satisfies OIErrP (b h; A) ≤ C6 α + 2α. Choosing the universal constant c in α = cε small enough makes this at most ε. The total success probability is at least 0.75 · 0.95 > 2/3. The base construction and validation sample sizes are both bounded by LA log(CLA /ε) C ε2 after adjusting the universal constant C. The algorithm is deterministic because the polynomial list is enumerated in a fixed order, the validation minimizer is tie-broken deterministically, and all LP tie-breaking in the earlier construction was fixed deterministically.
44