arXiv CSopen access

The Sample Complexity of Multicalibration

The Sample Complexity of Multicalibration Natalie Collina

Jiuyao Lu Georgy Noarov University of Pennsylvania

Aaron Roth

arXiv:2604.21923v1 [cs.LG] 23 Apr 2026

Abstract We study the minimax sample complexity of multicalibration in the batch setting. A learner observes n i.i.d. samples from an unknown distribution and must output a (possibly randomized) predictor whose population multicalibration error, measured by Expected Calibration Error (ECE), is at most ε with respect to a given family of groups. For every fixed κ > 0, in the regime e −3 ) samples are necessary and sufficient, up to polylogarithmic |G| ≤ ε−κ , we prove that Θ(ε factors. The lower bound holds even for randomized predictors, and the upper bound is realized by a randomized predictor obtained via an online-to-batch reduction. This separates the sample e −2 ), and complexity of multicalibration from that of marginal calibration, which scales as Θ(ε shows that mean-ECE multicalibration is as difficult in the batch setting as it is in the online setting, in contrast to marginal calibration which is strictly more difficult in the online setting. e −2 ) In contrast we observe that for κ = 0, the sample complexity of multicalibration remains Θ(ε exhibiting a sharp threshold phenomenon. More generally, we establish matching upper and lower bounds, up to polylogarithmic factors, for a weighted Lp multicalibration metric for all 1 ≤ p ≤ 2, with optimal exponent 3/p. We also extend the lower-bound template to a regular class of elicitable properties, and combine it with the online upper bounds of [HLSS25] to obtain matching bounds for calibrating properties including expectiles and bounded-density quantiles.

1

Contents 1

Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Lower Bound Proof Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Upper Bound Proof Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Additional Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Preliminaries 2.1 Mean multicalibration for finitely supported randomized predictors . . . . . . . . . . . . . . . . . . . 2.2 Learners and minimax sample complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Elicitable properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Lower Bounds 3.1 Coding theory primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 The hard instance: compressed groups and staircase distributions . . . . . . . . . . . . . . . . . . . . 3.2.1 Hard group family Gm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Hard distribution family . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Multicalibration implies exact decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Exact decoding has high sample complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Proof of Theorem 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Upper Bounds 4.1 Online-setting notation and constructing the averaged predictor . . . . . . . . . . . . . . . . . . . . . 4.2 The online-to-batch reduction for swap multicalibration . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Instantiating the batch swap multicalibration algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Sharper upper bound for mean ECE multicalibration . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Discussion and Open Problems A Regularity Verifications A.1 The mean property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Expectiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Quantiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B Details for the related-work rate conversions C Quantizing arbitrary randomized predictors

1 3 4 7 9 10 10 11 12 14 15 17 17 19 21 24 25 26 28 29 32 33 36 40 40 41 42 44 47

1

Introduction

Calibration and multicalibration. A predictor is calibrated if, conditional on the value it predicts, the predicted value equals the expected outcome [Daw82]. The standard quantitative measure of mis-calibration is the Expected Calibration Error (ECE), which sums the magnitude of the prediction-conditional bias across all prediction values: X E[v − Y | prediction = v] · P[prediction = v] . ECE = v

Multicalibration, introduced by [HJKRR18], strengthens calibration by requiring it to hold simultaneously on every subpopulation represented by a collection of group functions G. The Expected Multicalibration Error is the maximum, over groups, of the group-weighted ECE. 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 — omniprediction [GKR+ 22, GHK+ 23, OKK25] — to strengthening complexity-theoretic constructions [CDV24, DT25], to low complexity algorithms for distributed information aggregation [CGGR25, CGHG+ 26]. These applications motivate a thorough understanding of the statistical requirements for achieving multicalibration. Batch multicalibration. In the batch or statistical setting, a learner is given a finite family G of binary groups together with n i.i.d. samples from an unknown distribution P over context– outcome pairs (X, Y ), and must output a (possibly randomized) predictor Q whose population multicalibration error with respect to G is at most ε, with constant probability. The population multicalibration error is defined as follows (see Section 2 for the precise definitions). Given a finitely supported randomized predictor Q that, upon observing context X = x, draws its prediction from a distribution Qx supported on a finite set V (Q) ⊂ [0, 1], the signed bias on group g at prediction value v is BP (Q; v, g) = E[g(X) · QX ({v}) · (v − Y )]. The Expected Calibration Error on group g sums the absolute biases across prediction values, and the Expected Multicalibration Error takes the maximum over groups: X MCP (Q; G) := max |BP (Q; v, g)|. g∈G

v∈V (Q)

Multicalibration asks for substantially more than plain (marginal ) calibration. If one only asks for calibration with no group structure, then a constant predictor that always outputs an estimate of the marginal mean E[Y ] is calibrated, so the sample complexity is just Θ(ε−2 ), exactly as in mean estimation. In general, multicalibration can still permit substantial coarsening of the regression function. The real issue is to understand when a given group family rules out such coarsening and instead forces the learner to resolve a much finer estimate of E[Y | X] itself. Our lower bound gives a family with exactly this behavior. Prior work on sample complexity. Despite almost a decade of algorithmic work on multicalibration, the optimal sample complexity — as a function of the target error ε — has remained an open question. In all of the upper bounds discussed below, the group family G may be an arbitrary finite class whose size is polynomial in the sample size, and its contribution to the error guarantee is e notation. This makes the polynomial-budget regime only logarithmic and is absorbed into the O(·) 1

a natural target for a sharp minimax characterization. Different algorithms and error metrics have produced a wide range of exponents when translated to the common metric of mean ECE used in this paper (see Table 1 and Appendix B for the conversions). After conversion to ECE, the e −7 ). [GJN+ 22] gave original deterministic algorithm of [HJKRR18] gives sample complexity O(ε the first online multicalibration algorithms together with an online-to-batch reduction, yielding a e −4 ). [LNPR22] and [HJZ23] later developed game randomized predictor with sample complexity O(ε theoretic treatments of several multicalibration notions, and gave randomized algorithms with the e −4 ) sample complexity. Most recently, the online multicalibration algorithm of [NRRX25], same O(ε when combined with a suitable online-to-batch reduction (which we give in this paper), achieves e −3 ), which is the best known upper bound—see also [GMS25], who independently gave another O(ε algorithm with the same rate. On the lower-bound side, there has been less work. The trivial lower bound from mean estimation gives Ω(ε−2 ). To our knowledge, the only improvement is due to [GT25], who proved an Ω(ε−5/2 ) sample complexity lower bound for the weaker notion of calibrated multiaccuracy (c.f. [CGKR25]), and only for deterministic predictors. No lower bound beyond the trivial one was known to hold against randomized predictors, and so it was consistent with known results that randomized predictors might reduce the sample complexity down to ε−2 . Indeed, the best known upper bounds continue to be realized only via randomized predictors. Calibration has also been studied for statistics beyond means. Early work treated particular properties such as moments and quantiles [JLP+ 21, GJN+ 22, BGJ+ 22, JNRR23, DDZ23, GJRR24]. [NR23] introduced the general framework of property multicalibration for continuous scalar elicitable properties and gave online and batch algorithms under mild regularity conditions. Very recently, [HLSS25] obtained substantially sharper online upper bounds for a family of weighted Lp multicalibration metrics on elicitable properties: the case p = 1 is the ECE metric defined above, while larger values of p measure higher moments of the bucketwise calibration bias, weighted by the prediction mass of each bucket. Prior to our work, no non-trivial sample-complexity lower bounds were known for any non-mean property, or even for means against randomized predictors. Our contributions. We resolve the minimax sample-complexity of multicalibration up to polylogarithmic factors, by proving lower bounds using explicit polylogarithmically sized group families that therefore match the best known upper bounds throughout every polynomial-size budget regime |G| ≤ ε−κ with fixed κ > 0. Our results hold for the standard mean property, extend to Lp multicalibration metrics for 1 ≤ p ≤ 2, and further extend to a regular class of elicitable properties including expectiles and bounded-density quantiles. The lower bounds hold even for randomized predictors, and the upper bounds are realized by randomized predictors that result from online-tobatch reductions. Our minimax statements study the regime in which the group family may grow polynomially with 1/ε, i.e. |G| ≤ Mκ (ε) = ⌈ε−κ ⌉ for a fixed κ > 0. This is the natural scale on which to compare with the known upper bounds, whose dependence on the group family is only logarithmic in |G| and therefore contributes only polylogarithmic factors in 1/ε. Definition 6 formalizes the corresponding (κ) minimax sample-complexity problem. In the notation of Definition 6, we determine SCmean-ECE (ε) (κ) and SCLp (ε) up to polylogarithmic factors for every fixed κ > 0. For regular elicitable properties, we prove an abstract lower-bound template with the same polylogarithmic group-size dependence and combine it with matching upper bounds over the distribution classes covered by the online hypothesis in [HLSS25], yielding matching exponents for expectiles and bounded-density quantiles 2

Paper

Guarantee

Rate in ECE

Lower Bounds Batch lower bound for calibrated multiaccuracy / ECE in mean regression (for deterministic predictors) Batch lower bound for multicalibration in mean regression and for more general properties Upper Bounds Batch (G, α)-multicalibration with discarded mass and a minimum-group-mass assumption Online (α, n)-mean multicalibration on n buckets, plus online-to-batch Batch (G, ε, λ) bucketed multicalibration in L∞ Full multicalibration with interval basis, specialized back to mean ECE Weighted L2 -multicalibration from L2 -boosting Online bucketed mean multicalibration, followed by rounding and Proposition 39

[GT25] This paper

[HJKRR18] [GJN+ 22] [HJZ23] [GKSZ22] [GHHK+ 23] [NRRX25]

Randomized

Ω(ε−5/2 ) e −3 ) Ω(ε

✓

e −7 ) O(ε e −4 ) O(ε

✓

e −4 ) O(ε e −8 ) O(ε

✓

e −10 ) O(ε e −3 ) O(ε

✓

Table 1: Previously known and newly derived sample-complexity rates for (mean) multicalibration error as measured with ECE. For upper bounds, “Randomized” means the algorithm produces a probabilistic predictor. For lower bounds, “Randomized” means that the lower bound holds even for probabilistic predictors. Upper bounds hold for arbitrary group families whose cardinality can grow polynomially with the sample size; the calibration error bounds all grow logarithmically with the group family cardinality, which increases the sample complexity by only a polylog(1/ε) factor e notation. Some upper bounds from prior work were stated under different absorbed in the O(·) error metrics; see Appendix B for conversions. for every fixed κ > 0. To summarize, we ask: What is the minimax sample complexity of multicalibration? e −3 ) for the ECE metric, and Θ(ε e −3/p ) for the Lp metric. This in particular The answer we give: Θ(ε separates the sample complexity of multicalibration from the sample complexity of plain marginal e −2 ). Together with the tight online lower bound calibration, whose batch sample complexity is Θ(ε of [CLNR26], our result shows that the minimax exponents for mean-ECE multicalibration agree in the batch and adversarial online settings. This is in sharp contrast with ordinary marginal e −2 ), [QV21, DDF+ 25] showed that this rate cannot be calibration: while the batch rate is Θ(ε obtained in the online setting.

1.1

Our Results

We now state our results more precisely. 1. Lower bound for mean ECE multicalibration (special case of Theorem 14). For every sufficiently small ε, there exists a hard instance on a domain [m] with   1/ε m=Θ log(1/ε)

3

together with a family of only O(polylog(1/ε)) binary groups and a family of Bernoulli distributions, such that any possibly randomized learner achieving population multicalibration error ε with probability at least 2/3 requires e −3 ) n = Ω(ε samples. The hard instance is a one-dimensional Bernoulli regression with a monotone mean function on [m], showing that the optimal rate already arises on extremely simple instances. 2. Matching upper bound for mean ECE (Theorem 32). We record the straightforward online-to-batch conversion of the online multicalibration algorithm of [NRRX25] into a randomized batch predictor that achieves population multicalibration error ε using only e −3 log |G|) n = O(ε e −3 ) as the optimal sample samples. Together with the lower bound, this establishes Θ(ε complexity for mean ECE multicalibration, up to polylogarithmic factors, for every fixed polynomial group-size budget |G| ≤ ε−κ with κ > 0. 3. Lp multicalibration for 1 ≤ p ≤ 2 (Theorem 14 and Theorem 30). We extend both bounds to the Lp multicalibration metric (cf. [HLSS25]). For every fixed κ > 0, the optimal e −3/p ) for every p ∈ [1, 2]. The lower bound follows from a Hölder sample complexity is Θ(ε comparison relating Lp error back to ECE, applied to the same compressed hard family. The upper bound combines the online Lp algorithm in [HLSS25] with an online-to-batch reduction. 4. Regular elicitable properties (Theorem 14 and Theorem 30). We introduce a regular class of elicitable properties, encompassing means, expectiles, and bounded-density quantiles e −3/p ) for the among other examples. For this class, the same lower-bound template yields Ω(ε property-specific weighted Lp multicalibration metric. When combined with the online upperbound framework of [HLSS25], this gives matching batch exponents of 3/p for expectiles and bounded-density quantiles, up to polylogarithmic factors, for all p ∈ [1, 2] and all fixed κ > 0. We remark on the exponent κ that determines how quickly the group family is allowed to grow as a function of ε. The lower-bound construction uses only polylogarithmically many groups in the hard-instance parameter m; after choosing m as a function of ε, this becomes |G| = polylog(1/ε). e −3 ) for mean ECE and Ω(ε e −3/p ) for weighted Lp already As a result, the sharp lower bounds Ω(ε fit every polynomial budget |G| ≤ ε−κ with fixed κ > 0. At κ = 0 (corresponding to constant-size group families that do not grow with 1/ε), no separation is possible for binary groups: if |G| is fixed, then the group-membership patterns partition the domain into at most 2|G| cells, and predicting e |G| ε−2 ) = O(ε−2 ). The remaining the empirical mean on each cell gives sample complexity O(2 question is therefore the sharp joint dependence on ε and |G|, especially in the regime in which |G| grows with ϵ but only polylogarithmically.

1.2

Lower Bound Proof Overview

Our lower bounds are fully stated and proved in Section 3, with the general result (which applies to all regular properties and to Lp metrics) is recorded in Theorem 14. Here, we now give a proof overview in the language of our standard (L1 , mean) multicalibration sample complexity lower 4

bound, in order to elide technicalities associated with the general statement and proof; still, we will address the extension to other Lp norms and other distributional properties at the end of this proof sketch. (Since the complete proof in Section 3 proves the lower bound for general regular distributional properties, many of the intermediate lemmas which we reference here are proved in greater generality than we describe here.) The Hard Instance. To establish our Ω̃(ϵ−3 ) lower bound, we construct a sequence of hard instances parameterized by m = Θ̃(1/ϵ). For each m, the hard instance consists of: 1. A hard binary group family Gm (Definition 19); 2. A hard family of data distributions Hm (Definition 23). At a high level, we construct Hm as a parametric family (Pθ )θ∈Θm of distributions Pθ over X × Y, with the parameter space Θm satisfying two desiderata: being (1) very large, and (2) pairwise well-separated. These two properties are clearly in tension, but, borrowing from a coding theory perspective, it turns out that they are possible to satisfy at the same time: such a collection Θm can be taken to be any code satisfying a packing property. The construction of the individual joint distributions Pθ must be quite specific, and their conditional label distributions crucially satisfy a certain monotonicity property, which is formalized via what we call staircase maps tθ (θ ∈ Θm ). We will describe this in more detail shortly. Meanwhile, the hard group family Gm is constructed so as, at a high level, to: (1) be small: |Gm | = O(polylog(m)), and (2) give rise to a well-behaved (in the sense of boundedness/slow growth of the coefficients) approximate representation of all possible sign threshold functions on the domain [m]. The significance of this latter property will be described shortly, but we note that it is tightly interlinked with the already mentioned monotonicity property of staircase maps. Once again, we see that both of these properties are in direct tension — as one must represent the threshold function family by a well-behaved approximate basis much smaller than its cardinality — yet again, a coding theory and a discrepancy theory insight enables both of these properties to hold at once. Specifically, the groups in Gm will be constructed in a dyadic representation manner, which decomposes every prefix interval into a disjoint union of dyadic intervals at different scales and then represents each dyadic block by a short, nearly orthogonal sign vector obtained from a low-correlation code. (This group construction is inspired by [GOR+ 24], which studies omniprediction for regression and builds interval approximations from low-rank factorizations of the identity matrix via results based on Johnson-Lindenstrauss lemma; but differs in the technical details.) The existence of both types of codes, with the properties required for constructing Hm and Gm , follows in a simple way from an elementary probabilistic method-based lemma, allowing us to concisely present1 the few coding theory primitives that we need in Section 3.1. Proof structure. Now, we describe the steps that our lower bound proof goes through. At a high level, we start with any learner that, with high probability, enforces approximate Gm multicalibration on any joint distribution Pθ ∈ Hm . We then show, crucially relying on the properties of Gm and Hm , that such a multicalibrated learner must in fact be a good predictor on Hm . 1 We note that the results in that section are folklore (e.g. the packing argument is of Gilbert-Varshamov type), and our goal is to present them in a brief and unifying manner for the benefit of the reader, underscoring the remarkable point that our entire hard instance is constructed with the help of a single basic coding theory primitive.

5

Then, once again relying on the properties of the hard distribution family Hm , we show that a precise-enough predictor on this hard family is in fact an exact θ-decoder, i.e. must be able to exactly (without approximation error) determine the ground truth parameter θ ∈ Θm using its sample from Pθ . And finally, using that the parameter space Θm is very large, we show via an application of Fano’s inequality that an exact θ-decoder must have a high sample complexity, which evaluates to Ω(m3 ) = Ω̃(ϵ−3 ). Via the just-laid-out chain of equivalencies, this exact-decoding lower bound thus also serves as a multicalibration lower bound, just as we had set out to show. In what follows, we now describe each of the proof steps in more detail, referencing the relevant intermediate lemmas established in Section 3. Step 1: A Gm -multicalibrated predictor is a low-error predictor: In Proposition 26, we show that for any distribution Pθ as we construct it, a learner’s prediction error is bounded by its Gm -multicalibration error with an additional logarithmic factor: Learner’s prediction error ≤ O(log m) · (Learner’s Gm -multicalibration error). To understand the mechanics of this step, we must now discuss how each Pθ is constructed. For means, Pθ is the following joint distribution. Contexts are distributed uniformly over the finite domain [m], and the conditional distributions are chosen as Y |X = i ∼ Ber(tθ (i)) for all i ∈ [m]. Here, the key object is tθ , indexed by θ, which we call a staircase map. For the illustration of this map, see Figure 1. This map is crucially defined to (1) be monotonically increasing, and (2) “hide” the bits in its defining codeword θ across its domain. Now, recall that the group family Gm is defined to approximately represent all the m signed threshold functions on the domain [m]. The key point in proving this step’s assertion is to note that for the staircase tθ , due to its monotonicity, every sign pattern of v − tθ (i) (where v is any prediction) is always equivalent to one of the threshold functions in the domain [m]. Since our groups Gm approximate every such threshold sign with only polylog(m) signed test functions, we may thus convert the learner’s prediction error (which depends on the error patterns v − tθ (i)) into a decomposition in terms of the group functions in Gm — and thus (up to a loss in the boundedness parameter of the coefficients, which is only a log(m) factor) into the learner’s multicalibration error. To summarize, this is a delicate structural step: one must simultaneously approximate all thresholds while keeping the group family small enough to obtain the desired minimax lower bound. Step 2: A low-error predictor is an exact θ-decoder: Having demonstrated that small-error multicalibration forces small prediction error, we now carry this line of reasoning forward, and show that once a small-enough prediction error is achieved, it becomes possible for the learner to exactly determine the ground truth parameter value θ. This is shown in Proposition 27. The key property of our hard instance leveraged in this result is that any two distinct staircase maps tθ , tθ′ for θ, θ′ ∈ Θm (where θ ̸= θ′ ) must be well-separated in L1 distance. This wellseparation property (Lemma 24) more precisely states that any such pair of staircase maps tθ , tθ′ are at least Ω(1/m) apart in L1 -distance, and follows from the packing property of the code Θm via a direct connection via Hamming distance. With this well-separation property in hand, it is then clear that by driving down the prediction error below Õ(1/m), and then taking the nearest neighbor of the best estimate θ̂ within the code Θm , the ground-truth θ can be recovered exactly.

6

Step 3: An exact θ-decoder has high sample complexity: Now consider any learner who with high probability is able to exactly determine, from an i.i.d. sample of size n from Pθ , the true distribution parameter θ ∈ Θm . At this point, we can invoke Fano’s inequality to demonstrate that this determination requires a large sample size. Quantitatively, Lemma 28 observes that (1) the parameter space Θm is very large (exponential in m), and (2) by a regularity property of distribution means (more explicitly, by a standard quadratic upper bound on KL divergence), it holds that any two disributions in Hm are O(1/m2 )-close in KL divergence — and that by Fano’s inequality, these two properties imply the sought sample complexity bound     log |Θm | m n≥Ω = Ω = Ω(m3 ) = Ω̃(ϵ−3 ). 1/m2 1/m2 Generalization to regular properties and Lp metrics: The extension to an optimal lower bound for other Lp multicalibration metrics turns out to be immediate for p ∈ [1, 2]. For this range of p, simply applying Holder’s inequality with our ECE (L1 ) lower bound extends it to the lower sample complexity bound Ω̃(ϵ−3/p ), and our upper bounding section later confirms this to be optimal via an online-to-batch reduction from the method of [HLSS25], whose bounds (after conversion) turn out to match this. However, as we also briefly mention in the future work (conclusion) section, proving tight lower bounds for Lp multicalibration for p ∈ (2, ∞] — which is lossy with respect to the Holder conversion that we just described — does not appear to easily follow from our L1 lower bound construction. We therefore leave tight Lp -multicalibration bounds for p > 2 to future work, and note that this future direction underscores the nuanced nature of obtaining multicalibration lower bounds. Next, generalizing our lower bounds to multicalibration of distributional properties Γ beyond means requires care. Instead of the mean residuals v − µ(i), the general proof deals with the expected identification function MΓ (v, t), and is not automatic without further assumptions on Γ. We define “regular” properties Γ as those that satisfy a certain collection of assumptions (see Definition 11). In a nutshell, first, the identification function must be quantitatively non-flat. Secondly — and critically — our Γ-specific hard distribution family must satisfy a Fano-type requirement that all constituent pairs of distributions Pθ , Pθ′ be quadratically close in KL distance. This ensures that exact θ-decoders of Pθ remain subject to a sample lower bound via Fano’s inequality. We note that in terms of adjustments to the above-explained hard instance, only the hard distribution family needs to vary with the property Γ; meanwhile, the hard group family Gm remains Γ-agnostic. Finally, our regularity assumptions on Γ are not very restrictive, and we illustrate this by proving that — aside from means — quantiles are also regular properties, subject to natural mild Lipschitzness, as are expectiles; see the Appendix.

1.3

Upper Bound Proof Overview

The upper bound proofs are contained in Section 4. The blueprint is somewhat standard, and proceeds by constructing and proving appropriate online-to-batch reduction statements. However, one does encounter several technical subtleties in comparison to familiar online-to-batch reductions for no-regret learning, and so we discuss the outline here. First, we describe the canonical meanECE case, whose upper bound guarantee is stated in Theorem 32 and proved in Section 4.4. Then,

7

we turn to the general upper bound for Lp property multicalibration, which is formally stated in Theorem 30 and proved in Sections 4.2 and 4.3. Upper bound for mean ECE multicalibration. For the ECE metric, the online-to-batch conversion is relatively straightforward. An online algorithm processes a stream of i.i.d. samples (X1 , Y1 ), . . . , (XT , YT ) and, at round t, outputs a distribution-valued rule qt : X → ∆(Λ) on a finite grid Λ = (vk )K the k=1 . The realized prediction at round t is then sampled from qt (Xt ). We convert 1 PT transcript into a batch predictor by averaging the roundwise grid distributions: QS := T t=1 qt . d T (S; G, Λ) denote the normalized empirical multicalibration error of the transcript on Let MC bk (S; g) and Bk (S; g) denote the corresponding the grid Λ, and for each group g and bucket k let B empirical and population bucket biases. Then the population bias of QS on each group–bucket pair bk (S; g) = differs from the corresponding empirical bias by a martingale difference: Bk (S; g) − B 1 PT t=1 Mt , where each Mt is bounded and has conditional mean zero given the history. An T Azuma–Hoeffding bound over groups and sign patterns yields E[MCP (QS ; G)] ≤ qwith a union  h i K+log |G| d T (S; G, Λ) + O E MC . T Now, to instantiate the batch predictor, we utilize the online algorithm √ of [NRRX25]. As they e prove, it achieves cumulative bucketed multicalibration error O(T /K + T K) with K prediction buckets. After normalizing by T and buckets to their centers, the empirical ECE of their  rounding q  d T (S; G, Λ) ≤ O e 1 + K . Setting K = Θ(T e 1/3 ) makes both online terms algorithm is MC K

T

e −1/3 ), and the online-to-batch transfer term is on the same order, O(T e −1/3 ), giving the bound O(T

e −1/3 ) and thus sample complexity O(ε e −3 log |G|) after Markov’s inequality. E[MCP (QS ; G)] ≤ O(T We highlight that it is due to this same-order transfer loss that our batch lower bound does not recover the incomparable online multicalibration lower bound of [CLNR26]. General (Lp , property) upper bound. In the general case the reduction is more delicate. The main reason is that the Lp error metric involves the ratio |Bk |p /πkp−1 , where πk is the population mass of bucket k. This quantity is both nonlinear, and can blow up in “light” buckets where πk is small. This requires a more nuanced online-to-batch reduction, which must in particular use a more complex concentration bound than the familiar Azuma-Hoeffding. To address this, we follow a variance-adaptive Freedman strategy (with a dyadic peeling component) introduced by [HLSS25], and handle the ratio structure of the metric via a two-part argument. e Namely, we set a threshold τ = Θ(1/T ) and separately consider light and heavy buckets. (1) Light buckets (population mass πk < τ ) contribute at most Kτ total Lp error, by the trivial bound |Bk |p /πkp−1 ≤ πk . (2) Heavy buckets (πk ≥ τ ) are handled with the aforementioned strengthened Freedman’s inequality of [HLSS25], a variance-adaptive concentration inequality; it is needed because while standard Freedman inequality controls a martingale sum in terms of its predictable quadratic variation, here the variance proxy πk is itself a random quantity (it depends on the online algorithm’s choices). As in [HLSS25], the proof takes a union over dyadic scales of πk , paying only a log T factor, and then uses πk ≥ τ on each scale to absorb the lower-order terms. Having obtained the just-described online-to-batch transfer guarantee, we instantiate the batch predictor with the recent online Lp multicalibration algorithm of [HLSS25]. This algorithm targets online swap multicalibration guarantees, which are in fact somewhat stronger than ordinary multicalibration (and we in fact present the above online-to-batch reduction in the language of the 8

e 1/3 ) and swap error metric). For p ∈ [1, 2], the algorithm of [HLSS25] uses discretization K = Θ(T e −3/p ), which leads, after the batch conversion, to the general multicalibration upper bound of O(ε matches our general multicalibration lower bound.

1.4

Additional Related work

Uniform Convergence Bounds A related but distinct line of work studies uniform convergence of multicalibration error over a fixed predictor class. [SCM20] give uniform convergence bounds for bucketed multicalibration error with logarithmic dependence on the size of a finite predictor class and graph-dimension dependence for infinite classes, together with a matching lower bound for that uniform-convergence problem. [RBFJ22] show more generally that such multicalibration uniformconvergence guarantees can often be obtained by reparametrizing standard ERM sample-complexity bounds, and instantiate this viewpoint using VC- and Rademacher-complexity analyses for several model classes. These results do not establish the sample complexity of learning a predictor with low multicalibration error: they control the gap between empirical and population multicalibration error uniformly over a fixed class H, but they do not imply that H contains any predictor with small population multicalibration error, which also requires that the class itself is sufficiently expressive. In particular, they are compatible with every predictor in H having large multicalibration error, whereas our results characterize the sample complexity of producing a predictor whose population multicalibration error is small. Other Multicalibration Lower Bounds [GT25] prove the only previous lower bound that we are aware of on the sample complexity of batch multicalibration, beyond the Ω(ε−2 ) lower bound that follows from marginal calibration/mean estimation (in fact their lower bound is for the strictly weaker measure of calibrated multiaccuracy). In our notation, their result implies that for the problem of mean regression, learning a deterministic predictor with expected (mean) multicalibration error ε requires at least n ≥ Ω(ε−5/2 ) many samples. They also give an n ≤ O(ε−3 ) sample complexity upper bound for the weaker notion of calibrated multiaccuracy. In contrast, we e −3 ), and our lower bound identify the minimax optimal sample complexity for multicalibration: Θ(ε holds even for randomized predictors; similarly our analysis extends also to other multicalibration error metrics and to other elicitable properties beyond the mean. In a complementary direction, [GHR24] study computationally efficient multi-class calibration when the label space has size k. Their lower bounds are mainly about the auditing or recalibration problem of improving a given predictor while preserving squared loss, and show that more expressive multi-class notions such as canonical calibration and full smooth calibration require exponentially many samples in k (and, for some notions, also face computational hardness). These results concern high-dimensional label spaces and a different recalibration task, and are therefore orthogonal to our minimax sample-complexity lower bounds for scalar multicalibration. [CLNR26] characterize the optimal rate for mean multicalibration in the online adversarial e −1/3 ) normalized error rate. Their result setting under the same ECE metric, proving a tight Θ(T and ours are incomparable: just as we characterize the optimal batch sample complexity, they characterize the optimal online rate, and neither theorem implies the other. In particular, our e −1/3 ), so our batch lower bounds online-to-batch reductions incur an additive loss term of order Ω(T do not lift to non-vacuous online lower bounds by contrapositive. Our high-level lower bound proof outline intersects with, but substantially differs from, that of [CLNR26]. As a place of substantial difference, their hard distribution is tailored to the adversarial 9

setting and encodes the mean as E[Y | X] = X exactly, whereas our batch lower bound uses a parametric monotone stochastic staircase family powered by certain (packing-type) binary codes. On the other hand, there is overlap insofar group family component of the hard instance is concerned. Specifically, a major technical purpose of the group construction in both proofs is that it provides a succinct basis for approximating families of sign threshold functions on a finite domain; this aids with the high-level step of proving that low multicalibration error implies low prediction error (which they refer to as “truthfulness”). However, the exact group construction we use here is different: [CLNR26] use a subsampled Walsh basis technique, while we employ a coding theory approach coupled with a dyadic representation inspired by [GOR+ 24]. (We note that their subsampled Walsh approach could also be used to define groups in the place of our coding approach, but we present a fully coding theory-based construction as a simple and consistent approach.)

2

Preliminaries

We begin with the population notion used in the mean-calibration lower and upper bounds. In this section we first define multicalibration for the mean property, then introduces the analogous definitions for general elicitable properties. Fix a context space X , a distribution P on X × [0, 1], and a family G of binary groups g : X → {0, 1}. Let µ(x) := E[Y | X = x] denote the regression function of P .

2.1

Mean multicalibration for finitely supported randomized predictors

Definition 1 (Finitely supported randomized predictor). A finitely supported randomized predictor on X is a rule Q = (Qx )x∈X that assigns to each context x ∈ X a probability distribution Qx on [0, 1], and for which there exists a finite set V (Q) ⊆ [0, 1] such that Qx (V (Q)) = 1 for all x ∈ X . Equivalently, after observing X = x, the predictor outputs a random value V ∼ Qx , and only finitely many prediction values can occur overall. We work with this form throughout the main text because it lets us write calibration error as an explicit sum over prediction values. Restricting to a finite support is without loss of generality: Appendix Proposition 46 shows that any arbitrary randomized predictor can be quantized to a finite grid while changing multicalibration and prediction error by at most an arbitrarily small additive term. Definition 2 (Population mean multicalibration). For a signed weight function w : X → [−1, 1] and a prediction value v ∈ V (Q), define the population signed bias by BP (Q; v, w) := E[w(X) QX ({v}) (v − Y )] = E[w(X) QX ({v}) (v − µ(X))] . Define the corresponding signed-weight error by X ErrP (Q; w) := |BP (Q; v, w)|. v∈V (Q)

When g : X → {0, 1} is a binary group, this is its Expected Calibration Error (ECE): X ErrP (Q; g) := |BP (Q; v, g)|. v∈V (Q)

10

Finally define the Expected Multicalibration Error of Q with respect to G by MCP (Q; G) := max ErrP (Q; g). g∈G

Definition 3 (Prediction error). The average absolute prediction error of Q is defined as Z  X ∆P (Q) := E E[QX ({v}) |v − µ(X)|] , |v − µ(X)| QX (dv) = v∈V (Q)

with the equality holding because Q is finitely supported. Remark 4. A deterministic predictor f : X → [0, 1] is the special case in which Qx = δf (x) for every x ∈ X . In that case V (Q) = f (X ), and for every signed weight w and every v ∈ f (X ), BP (Q; v, w) = E[w(X)1{f (X) = v} (v − Y )] = E[w(X)1{f (X) = v} (v − µ(X))] . Accordingly, ErrP (Q; w) =

X

|E[w(X)1{f (X) = v} (v − Y )]|

and

∆P (Q) = E[|f (X) − µ(X)|] .

v∈f (X )

The randomized notation is thus a direct extension of the usual, deterministic, multicalibration. We will freely identify deterministic predictors with corresponding point-mass randomized predictors.

2.2

Learners and minimax sample complexity

We now formalize the statistical problem studied in the paper. The learner is given the group family G together with the sample, and we measure sample complexity in a minimax sense over all distributions and all group families of bounded size. Definition 5 (Learners given a group family). A learner is a sequence A = (An )n≥1 such that for every context space X , every outcome space Y, every finite family of binary groups G ⊆ {0, 1}X , and every sample S ∈ (X × Y)n , and every internal random seed ζ, the output An (G, S, ζ) is a finitely supported randomized predictor on X . Definition 6 (Minimax sample complexity). Fix a nonnegative error functional E that assigns a value E(P, G, Q) ∈ [0, ∞) to each distribution P on X × Y, each finite family of binary groups G ⊆ {0, 1}X , and each finitely supported randomized predictor Q on X . For a learner A as in Definition 5, define its instance-wise sample complexity by n 2o . nA (ε; P, G, E) := inf n ≥ 1 : PS∼P n , ζ (E(P, G, An (G, S, ζ)) ≤ ε) ≥ 3 For a size budget M : (0, 1) → N, define the minimax sample complexity by SCE (ε; M ) := inf A

sup

nA (ε; P, G, E).

X , P, G: G⊆{0,1}X , |G|≤M (ε)

For every κ > 0, define the polynomial-size budget Mκ (ε) := ⌈ε−κ ⌉ and write (κ)

SCE (ε) := SCE (ε; Mκ ). 11

Remark 7 (Restricted minimax sample complexity). If P is a class of admissible distributions on context–outcome spaces, we write SCP E (ε; M ) := inf A

nA (ε; P, G, E)

sup (X ,Y,P )∈P, G⊆{0,1}X , |G|≤M (ε)

for the corresponding minimax sample complexity with the supremum restricted to P ∈ P, and P,(κ)

SCE

(ε) := SCP E (ε; Mκ ).

When P is the unrestricted class of all distributions, this reduces to Definition 6. (κ)

Note that SCE allows the cardinality of the group function class |G| to grow at a polynomial rate with 1/ϵ. This is the regime that will allow us to prove bounds that tightly match the best known upper bounds’ dependence on ϵ (up to polylogarithmic factors), as these upper bounds have only a logarithmic dependence on |G|. Remark 8. For the mean ECE metric, we write Emean-ECE (P, G, Q) := MCP (Q; G),

SCmean-ECE := SCEmean-ECE .

We will introduce analogous shorthand for the weighted Lp metrics and for elicitable properties when those notions are defined later in the paper.

2.3

Elicitable properties

We now extend the mean-specific notions above to general scalar elicitable properties. This section introduces the property-specific multicalibration metrics used later, the regularity condition underlying our lower-bound template, and the concrete examples needed in the sequel. The general lower bound for regular properties is proved in Section 3, while the corresponding upper bounds under the online hypothesis in [HLSS25] are proved in Section 4. Proofs of the example regularity verifications are deferred to Appendix A. The learner and minimax sample-complexity definitions from Definitions 5 and 6, together with the restricted version in Remark 7, extend verbatim when the outcome space [0, 1] is replaced by an arbitrary label space Y. Throughout this section we use that extension. Fix an elicitable property Γ with a bounded identification function V : [0, 1] × Y → [−1, 1]. Definition 9 (Property multicalibration [NR23, HLSS25]). For a distribution P on X × Y, a finitely supported randomized predictor Q, a prediction value v ∈ V (Q), and a signed weight w : X → [−1, 1], define the property-specific signed bias by BPΓ (Q; v, w) := E[w(X) QX ({v}) V(v, Y )] . For a binary group g : X → {0, 1}, define its ECE-type error by X ErrΓP (Q; g) := BPΓ (Q; v, g) , MCΓP (Q; G) := max ErrΓP (Q; g). g∈G

v∈V (Q)

12

Also define the weighted Lp version, for every p ≥ 1, by πP (Q; v) := E[QX ({v})] ,

Γ,(p)

ErrP

X |B Γ (Q; v, g)|p P (Q; g) := , πP (Q; v)p−1

Γ,(p)

MCP

Γ,(p)

(Q; G) := max ErrP

v∈V (Q) πP (Q;v)>0

g∈G

(Q; g).

When Γ is the mean property and V(v, y) = v − y, the case p = 1 recovers Definition 2. Remark 10. For an elicitable property Γ, we write EΓ (P, G, Q) := MCΓP (Q; G),

SCΓ := SCEΓ .

For the corresponding weighted Lp metric, we write Γ,(p)

EΓ,p (P, G, Q) := MCP

(Q; G),

SCΓ,p := SCEΓ,p .

The next definition packages the ingredients needed for our lower bound construction. We need a one-parameter family of conditional label distributions whose parameter really is the target property, whose expected identification signal points toward the true parameter with linear strength, and whose nearby parameters are statistically hard to distinguish. Definition 11 (Regular property). Fix a bounded scalar property Γ with identification function V . Let I0 ⊂ (0, 1) be a nondegenerate closed interval. A one-parameter family {Dt : t ∈ I0 } is a regularity witness for Γ on I0 if, for some constants cΓ , CΓ,KL > 0, the following conditions hold: 1. for every t ∈ I0 , Γ(Dt ) = t; 2. for every t ∈ I0 and every v ∈ [0, 1], (v − t)MΓ (v, t) ≥ cΓ (v − t)2 , 3. for every t, t′ ∈ I0 ,

where MΓ (v, t) := EY ∼Dt [V (v, Y )];

DKL (Dt ∥ Dt′ ) ≤ CΓ,KL (t − t′ )2 .

Γ is called regular if it admits a regularity witness on some nondegenerate closed I0 ⊂ (0, 1). Whenever {Dt : t ∈ I0 } is a regularity witness, condition (2) implies that MΓ (v, t) has the same sign as v − t and that cΓ |v − t| ≤ |MΓ (v, t)| (v ∈ [0, 1], t ∈ I0 ). Remark 12. Each part of Definition 11 plays a specific role in the proof. Condition (1) says that the scalar parameter t genuinely indexes the property value we are trying to predict. Condition (2) is the property analogue of the mean identity E[v − Y | t] = v − t: it says that the expected identification signal has the correct sign and is not too flat, so small property multicalibration forces predictions to be close to the true parameter. Condition (3) is the information-theoretic input needed for Fano’s inequality: it says that changing the hidden parameter by δ changes the conditional law by only O(δ 2 ) in KL. In the examples below, means, expectiles, and bounded-density quantiles all fit this template. Next, we ascertain that our regularity definition is benign enough to include some fundamental distributional properties. The regularity proofs for these properties are deferred to Appendix A. 13

Theorem 13 (Examples of Regular Properties). The following properties are regular: 1. The mean property, with identification function Vmean (v, y) = v − y, admits a Bernoulli regularity witness on every closed interval I0 ⊂ (0, 1); on I0 = [1/4, 3/4] one may take cΓ = 1 and CΓ,KL = 16/3. 2. For every expectile level τ ∈ (0, 1), with identification function Vτ (v, y) := |τ − 1{y ≤ v} |(v − y), the expectile property admits a regularity witness on the fixed interval [1/4, 3/4], and for every distribution ν on [0, 1] the map v 7→ EY ∼ν [Vτ (v, Y )] is 1-Lipschitz on [0, 1]. 3. For every quantile level q ∈ (0, 1), with identification function Vq (v, y) := 1{y ≤ v} − q, there exist a constant Λq > 0, a closed interval Iq ⊂ (0, 1), and a constant Cq < ∞ such that the truncated-exponential family {Dλ : λ ∈ [−Λq , Λq ]}, reparameterized by its q-quantile, is a regularity witness on Iq , and every distribution in that witness family has density bounded above by Cq . Proof of Theorem 13. The mean claim is Proposition 41, the expectile claim is Proposition 43, and the quantile claim is Proposition 45.

3

Lower Bounds

We now provide our general sample complexity lower bound for multicalibration. This bound holds not only for classical — mean ECE — multicalibration, but in fact for all regular properties Γ and all Lp -multicalibration metrics for p ∈ [1, 2]. We now formally state our lower bound as the following Theorem 14, which we prove in the rest of this Section. Theorem 14 (General Multicalibration Lower Bound). Fix a regular property Γ, and fix p ∈ [1, 2].  Then for small enough ε > 0, there exists a parameter m = Θ

(1/ε)1/p log(1/ε)

and:

• a family Gm of binary groups on [m] with
|Gm | = O log4 (1/ε) , Γ of distributions on [m] × [0, 1], • and a finite family Hm

such that the following holds. Consider any possibly randomized learner whose input consists of: (1) the group family Gm , Γ , and whose output is a finitely and (2) n i.i.d. samples from an unknown distribution P ∈ Hm supported randomized predictor Q. Then, to ensure that Q satisfies Γ,(p)

P MCP

2 (Q; Gm ) ≤ ε ≥ 3 14

Γ for every P ∈ Hm ,

the learner’s sample size must be at least2 :   1 e Γ (ε−3/p ). =Ω n = ΩΓ 3/p 3 ε log (1/ε) Corollary 15 (Minimax lower bound for regular properties). For every regular property Γ, every p ∈ [1, 2], and every fixed κ > 0, (κ) e −3/p ). SCΓ,p (ε) = Ω(ε Proof. Fix κ > 0.
By Theorem 14, the hard family at accuracy ε uses a group family of size |Gm | = O log4 (1/ε) = o(ε−κ ). Hence the same hard instances witness the lower bound on the minimax sample complexity.

3.1

Coding theory primitives

Our sample complexity lower bound will rely on some simple coding theory results. In this subsection, we give a self-contained overview of the requisite notions, and state and prove the existence of two (families of) codes that will power our lower-bounding instance construction. We point out that the results in the subsection are folklore and presented for a fully self-contained exposition highlighting the simplicity and unified nature of the coding primitive needed for our hard instance — both on the group family side and on the distribution family side. For a general overview of coding theory, we refer i.a. to monographs such as [Rot06]. For a deeper look at the specific themes associated with the below lemmas, including i.a. balanced codes and Gilbert-Varshamov theory, we refer the reader i.a. to the seminal paper of Ta-Shma [TS17]; however, our arguments do not require any of the complexity of more advanced coding theory. Recall that a binary code of block length k is a subset C ⊆ {0, 1}k . The distance between two codewords c, c′ ∈ C will be taken to be the Hamming distance distH (c, c′ ) := {t ∈ [k] : c(t) ̸= c′ (t)} . Rather than working with binary codes, it is often more convenient to deal with sign vectors z ∈ {±1}k . These two viewpoints are equivalent via the conversion c(z)(t) := 1−z(t) 2 , such that the k−⟨z,z ′ ⟩ ′ Hamming distance becomes distH (c(z), c(z )) = . Thus, small inner products among sign 2 vectors are the same as large Hamming separation among the associated binary codewords. We are now ready to prove a simple yet key fact about the existence of certain codes. It is a standard probabilistic method argument via Hoeffding’s inequality [Hoe63, Theorem 2]. Via two distinct instantiations, which we will present next, this fact will underlie both facets of our lower bounding instance: the hard groups construction and the hard distribution family construction. Lemma 16 (Low-correlation codes). Let N ≥ 2, let ρ ∈ (0, 1), and let k be an integer satisfying k ≥ 8ρ−2 log(2N ). Then there exist vectors z0 , . . . , zN −1 ∈ {±1}k such that for all distinct a, b ∈ {0, . . . , N − 1}, ⟨za , zb ⟩ ≤ ρk. 2

Here and in what follows, we may endow our asymptotic notation (such as Ω) with a property subscript Γ to highlight hidden dependencies on property-specific regularity constants.

15

Equivalently, the associated binary codewords c(z0 ), . . . , c(zN −1 ) ∈ {0, 1}k satisfy   k − ⟨za , zb ⟩ 1−ρ 1+ρ distH (c(za ), c(zb )) = ∈ k, k (a ̸= b). 2 2 2 Proof. Sample Z0 , . . . , ZN −1 ∈ {±1}k independently and uniformly at random. For fixed a ̸= b, ⟨Za , Zb ⟩ =

k X

Za (t)Zb (t)

t=1

is a sum of k independent Rademacher random variables. By Hoeffding’s inequality,  2 
ρ k 1 ≤ 2e−4 log(2N ) ≤ . P ⟨Za , Zb ⟩ > ρk ≤ 2 exp − 2 8N 4 There are fewer than N 2 /2 unordered pairs {a, b}, so a union bound shows that with positive probability no pair violates the displayed correlation bound. Hence a desired realization exists. The identity relating inner products and Hamming distance is distH (c(za ), c(zb )) =

k X 1 − za (t)zb (t)

2

t=1

=

k − ⟨za , zb ⟩ , 2

which immediately yields the equivalent binary-code formulation. Our first instantiation of the above lemma will provide a dyadic collection of codes that will be used in the definition of our hard group families (Section 3.2.1). Namely, at all dyadic scales, it gives short sign signatures for dyadic blocks that are nearly orthogonal across distinct blocks. 1 Lemma 17 (Dyadic low-correlation code). Let m be a power of two, L := log2 m, and ρm := 8(1+L) .   m −2 For each scale h ∈ {0, 1, . . . , L−1}, define nh := 2h , kh := 8ρm log(2nh ) . Then there exist vectors (h)

(h)

z0 , . . . , znh −1 ∈ {±1}kh such that

(h)

⟨za(h) , zb ⟩ ≤ ρm kh

for all distinct a, b ∈ {0, . . . , nh − 1}.

Proof. Apply Lemma 16 with N = nh , ρ = ρm , and k = kh separately for each scale h. The second instantiation of Lemma 16 guarantees the existence of a packing code that will be a key ingredient in defining our hard data distribution instances (Section 3.2.2). Lemma 18 (Packing code). There exists a universal constant cpack > 0 such that for every sufficiently large integer d there is a set Θd ⊆ {0, 1}d with the following properties: (1) every two distinct elements of Θd have Hamming distance at least ⌊d/8⌋; and (2) the size is log |Θd | ≥ cpack d. 
 9d Proof. Fix ρ⋆ := 3/4 and let Nd := 21 exp 128 . For all d large enough, Nd ≥ 2 and d ≥ −2 8ρ⋆ log(2Nd ). Therefore, by Lemma 16, there exists a set of vectors z0 , . . . , zNd −1 ∈ {±1}d such that ⟨za , zb ⟩ ≤ ρ⋆ d Let Θd := {c(za ) : 0 ≤ a ≤ Nd − 1} ⊆ {0, 1}d . 16

(a ̸= b).

Then for every distinct a, b (using in the implication that Hamming distance is integer-valued):   1 − ρ⋆ d d d − ⟨za , zb ⟩ ≥ d= =⇒ distH (c(za ), c(zb )) ≥ . distH (c(za ), c(zb )) = 2 2 8 8   Also, once d is large enough that 21 e9d/128 ≥ 2, we have Nd = 12 e9d/128 ≥ 14 e9d/128 and hence log |Θd | = log Nd ≥

3.2

9 9d − log 4 ≥ d. 128 256

The hard instance: compressed groups and staircase distributions

In this subsection, we will describe the two components of our lower-bound instances, whose complexity will be parameterized by an integer m (which we will take as a power of two). Namely, Section 3.2.1 presents our hard group family Gm in Definition 19, while Section 3.2.2 constructs Γ in Definition 23. the (property-Γ-dependent) hard data distribution family Hm The coding primitives that we just discussed will underlie both of these constructions and their properties: Lemma 17 supplies the short dyadic block signatures from which we build our compressed group family Gm , while Lemma 18 supplies the packing code Θm that indexes the Γ. family of hard distributions in Hm 3.2.1

Hard group family Gm

We will now introduce our m-indexed hard group family Gm , and next establish a key combinatorial property of Gm : that despite its polylogarithmic size in m, it succinctly captures a large (of size proportional to m) collection of threshold functions. Our construction is dyadic in nature, and is inspired by [GOR+ 24]. Definition 19 (Hard group family Gm ). Let m ≥ 16 be a power of two and L := log2 m. Let ρm :=

1 , 8(1 + L)

and define nh :=

  m , kh := 8ρ−2 m log(2nh ) for all scales h ∈ {0, . . . , L − 1}. h 2

With respect to these dyadic parameters, use Lemma 17 to supply a low-correlation set of vectors: (h)

(h)

z0 , . . . , znh −1 ∈ {±1}kh . For each h ∈ {0, . . . , L − 1} and q ∈ {1, . . . , kh }, define σh,q : {0, 1, . . . , m − 1} → {±1} (h)

by setting σh,q (u) = za (q) on the dyadic block [a2h , (a + 1)2h ). Define signed probes on i ∈ [m]: w0 (i) := 1,

wh,q (i) := σh,q (i − 1).

Now, to ensure all groups are binary, split each signed probe into two half-groups: gall (i) := 1,

gh,q,+ (i) :=

1 + wh,q (i) , 2

gh,q,− (i) :=

1 − wh,q (i) . 2

Then, the compressed dyadic sign group family at scale m is defined as: Gm := {gall } ∪ {gh,q,+ , gh,q,− : 0 ≤ h ≤ L − 1, 1 ≤ q ≤ kh }. 17

Observation 20 (Group family size is polylogarithmic). Because kh = O((1 + L)3 ) for all h, there is a universal constant CG > 0 such that |Gm | = 1 + 2

L−1 X

kh ≤ CG (1 + log2 m)4 .

h=0

We now establish a crucial property of the group family Gm : its powerful representational ability. Namely, we will now see that every threshold sign on the ordered domain [m] can be approximated by a short linear combination of the compressed probes from Definition 19. The decomposition of a prefix into disjoint dyadic intervals used below is a standard discrepancy theory tool; compare the standard reference by Matoušek [Mat94, Example 2.2]. Definition 21 (Threshold sign function). For r ∈ {0, 1, . . . , m} define the threshold-sign function ( +1, u ≤ r − 1, τr (u) := u ∈ {0, 1, . . . , m − 1}. −1, u ≥ r, Lemma 22 (Threshold function approximation). Let m be a power of two, let L := log2 m, and use the sign probes σh,q from Definition 19. There exist families of coefficients (α0 (r))m r=0 ,

(αh,q (r))m r=0

(0 ≤ h ≤ L − 1, 1 ≤ q ≤ kh ),

such that, for every r ∈ {0, . . . , m}, the function τbr (u) := α0 (r) +

kh L−1 XX

αh,q (r)σh,q (u)

satisfies

h=0 q=1

1 ∥τr − τbr ∥∞ ≤ . 4

Moreover, the coefficients satisfy the following boundedness conditions: sup

|α0 (r)| ≤ 1,

r∈{0,...,m}

kh L−1 XX

|αh,q (r)| ≤ 2L.

sup

h=0 q=1 r∈{0,...,m}

Proof. For each scale h and block index 0 ≤ a ≤ nh − 1, let Ih,a := {a2h , . . . , (a + 1)2h − 1} and let 1 1{·^ ∈ Ih,a }(u) := kh

kh X

za(h) (q)σh,q (u) =

q=1

kh X

(h)

βh,a,q σh,q (u),

q=1

za (q) βh,a,q := . kh

If u ∈ Ih,a then 1{·^ ∈ Ih,a }(u) = 1, while if u ∈ Ih,b with b ̸= a then 1{·^ ∈ Ih,a }(u) ≤ ρm . Hence 1{· ∈ Ih,a } − 1{·^ ∈ Ih,a } ∞ ≤ ρm ,

kh X

|βh,a,q | = 1.

q=1

For r = 0 and r = m, set τb0 ≡ −1 and τbm ≡ 1; equivalently, take α0 (0) = −1, α0 (m) = 1, and αh,q (0) = αh,q (m) = 0. These two cases alreadyP satisfy the claim. t hj with h > · · · > h ≥ 0. Set s := 0, Now fix 1 ≤ r ≤ m − 1, and write r = 1 t 1 j=1 2 Pj−1 hu h j sj := u=1 2 for j ≥ 2, and Ij := {sj , . . . , sj + 2 − 1}. Then the intervals I1 , . . . , It are disjoint 18

dyadic intervals whose union is {0, . . . , r − 1}, and there is at most one such interval at each scale. Define t X ^ χ br := 1{· ∈ Ij }, χr (u) := 1{u < r} . j=1

Since χr =

Pt

j=1 1{· ∈ Ij }, we get

∥χr − χ br ∥∞ ≤

t X

^ 1{· ∈ Ij } − 1{· ∈ Ij } ∞ ≤ tρm ≤ Lρm .

j=1

Collecting coefficients by scale gives χ br (u) =

kh L−1 XX

βh,q (r)σh,q (u),

h=0 q=1

where, because at most one interval of each scale appears, supr |βh,q (r)| ≤ 1/kh and hence kh X q=1

sup |βh,q (r)| ≤ 1

(0 ≤ h ≤ L − 1).

r

Summing over h yields kh L−1 XX h=0 q=1

sup |βh,q (r)| ≤ L. r

Finally, for 1 ≤ r ≤ m − 1, set α0 (r) := −1, αh,q (r) := 2βh,q (r), and τbr := 2b χr − 1. Since τr = 2χr − 1, 1 ∥τr − τbr ∥∞ = 2∥χr − χ br ∥∞ ≤ 2Lρm ≤ . 4 P The coefficient bounds become supr |α0 (r)| ≤ 1 and h,q supr |αh,q (r)| ≤ 2L, as required. 3.2.2

Hard distribution family

We now present our hard distribution family construction. Unlike our group family construction Γ will depend on the property Γ. Gm , which is property-agnostic, the hard distribution families Hm Henceforth, as a useful piece of notation, write Um := Unif([m]). At a high level, we build Γ from a collection of Θ -indexed distributions, where Θ is an m/2-dimensional packing code Hm m m obtained from Lemma 18. Each constituent distribution corresponds to some θ ∈ Θm , and has X sampled uniformly at random from X = [m], while the conditional label distributions (Y |X = i), i ∈ [m], are indexed by a “parameter map” — a monotonically increasing sequence of numbers whose jumps are encoded by θ. Γ ). Consider any regular property Γ. Fix a regularity Definition 23 (Hard distribution family Hm witness {Dt : t ∈ I0 } for it, and a nondegenerate interval J = [a, b] ⊆ I0 . d Fix power-of-two m ≥ 16. Let d := m/2, γm := b−a 8m . Let Θm ⊆ {0, 1} be any packing code whose existence has been established by Lemma 18.

19

parameter value

vertical axis shown schematically as (tθ (i) − a)/γm

θj

1

2

1

3

4

0

5

6

1

7

8

9

1

10

11

12

0

13

14

1

15

0

16

1

i

Figure 1: A schematic staircase map. When specialized to the mean property, this is exactly the regression function µθ . The odd indices (blue) form a base ladder with spacing 4γm , while each even index (orange) either stays flat or rises by γm according to the corresponding bit θj . For each θ = (θ1 , . . . , θd ) ∈ Θm , define the staircase map tθ as: tθ (2j − 1) := cj ,

tθ (2j) := cj + γm θj ,

j = 1, . . . , d,

where we define an increasing arithmetic progression cj := a + 4γm (j − 1) for j = 1, . . . , d. Each staircase map tθ gives rise to an associated distribution Pθ , defined as: PθΓ :

X ∼ Unif([m]),

Y | X = i ∼ Dtθ (i) .

Then, the hard distribution family is defined as the collection of all Θ-indexed distributions: Γ Hm := {PθΓ : θ ∈ Θm }.

To shed light on this construction, Figure 1 illustrates the nature of the staircase map in the special case when Γ is the distribution mean. In this case, in fact, the staircase map tθ simply corresponds to the regression function µθ . We now prove a crucial property of the just defined hard distribution family: that it is wellseparated. This fact is powered by the properties of the code Θm underlying the hard family. Lemma 24 (Separation in the staircase family). For every distinct θ, θ′ ∈ Θm , ∥tθ − tθ′ ∥L1 (Um ) ≥

γm . 16

Proof. First note that every tθ is nondecreasing and takes values in the selected interval J. Indeed, for each j, we have tθ (2j − 1) = cj ≤ cj + γm θj = tθ (2j), and for each j = 1, . . . , d − 1, we also have tθ (2j) ≤ cj + γm < cj + 4γm = cj+1 = tθ (2j + 1). Also, all values lie in J because tθ (m) ≤ cd + γm = a + 4γm (d − 1) + γm = a + 2γm m − 3γm ≤ a + 20

b−a < b. 4

If θ and θ′ differ in coordinate j, then tθ and tθ′ differ at the location 2j, by exactly γm . Thus m X

|tθ (i) − tθ′ (i)| = γm distH (θ, θ′ ),

∥tθ − tθ′ ∥L1 (Um ) =

i=1

γm distH (θ, θ′ ). m

Because d = m/2 is divisible by 8 and Θm comes from Lemma 18, every distinct θ, θ′ ∈ Θm satisfy distH (θ, θ′ ) ≥

d m = . 8 16

Substituting into the displayed identity gives the claimed separation. Next, we record that as a consequence of our regularity assumptions, same-size i.i.d. samples from any pair of distributions in the hard family must be pairwise close in KL divergence. Lemma 25 (Pairwise KL bound for the hard distribution family). The following n-i.i.d.-sample bound holds for every θ, θ′ ∈ Θm :
CΓ,KL 2 nγm . DKL (PθΓ )n ∥ (PθΓ′ )n ≤ 2 Proof. First consider the case of a single (n = 1) sample. Conditioning on X and using regularity, DKL (PθΓ ∥ PθΓ′ ) =

m

m

i=1

i=1

CΓ,KL X 1 X DKL Dtθ (i) ∥ Dtθ′ (i) ≤ |tθ (i) − tθ′ (i)|2 . m m

2. The two parameter maps can differ only at even locations, and each such location contributes γm ′ Therefore, since distH (θ, θ ) ≤ d = m/2, we have

DKL (PθΓ ∥ PθΓ′ ) ≤

CΓ,KL CΓ,KL 2 2 distH (θ, θ′ ) γm ≤ γm , m 2

The n-sample bound then follows by the additivity of KL for product measures.

3.3

Multicalibration implies exact decoding

Having defined the hard instance, consisting of the hard group family Gm and the hard distribution family, we will now jointly leverage the structural properties of both. In a nutshell, we will now demonstrate that approximate Gm -multicalibration on any distribution Pθ coming from the hard Γ in fact results in exact recovery of the hidden parameter θ ∈ Θ . distribution family Hm m As a stepping stone to this, we will first prove that a learner’s prediction error on the underlying distribution will be at most a log m factor away from the learner’s Gm -multicalibration error. In other words, Gm -multicalibration implies low prediction error on instances that we have defined. To formalize this, fix a nondecreasing map t : [m] → I0 . The reader may think of this map as t = tθ , one of the staircase maps from Definition 23, but the following proposition only, and crucially, uses the map’s monotonicity. Let Pt denote the induced distribution X ∼ Um , (Y | X = i) ∼ Dt(i) , and write MCΓt (Q; Gm ) := MCΓPt (Q; Gm ). Finally, recall (see Definition 3) that for a predictor Q = (Q1 , . . . , Qm ) on [m], its prediction error is m Z 1 X |v − t(i)| Qi (dv). ∆t (Q) := m i=1

21

Proposition 26 (Multicalibration implies low prediction error). Let t : [m] → I0 be nondecreasing. Then every randomized predictor Q = (Q1 , . . . , Qm ) on [m] with finite prediction support satisfies ∆t (Q) ≤

6(1 + log2 m) MCΓt (Q; Gm ). cΓ

Proof. Write L := log2 m. For each prediction value v ∈ V (Q) and bounded signed weight w : [m] → R, define m

1 X Bv (w) := w(i)Qi ({v})MΓ (v, t(i)), m

Err(w) :=

X

Bv′ (w) .

v ′ ∈V (Q)

i=1

For binary groups g : [m] → {0, 1}, this notation agrees with the population quantity under Pt : Err(g) = ErrΓPt (Q; g). For each v ∈ V (Q), let r(v) := |{i ∈ [m] : t(i) ≤ v}|, define sv (i) := τr(v) (i − 1) and sbv (i) := τbr(v) (i − 1), and note that sv (i) is the sign of v − t(i) because t is nondecreasing. When v = t(i), regularity gives MΓ (v, t(i)) = 0, so in all cases sv (i)MΓ (v, t(i)) = |MΓ (v, t(i))| ≥ cΓ |v − t(i)|. Hence, with

m

1 X Av := Bv (sv ) = Qi ({v})|MΓ (v, t(i))|, m i=1

we have ∆t (Q) ≤

1 X Av . cΓ v∈V (Q)

Now let ev := sv − sbv . By Lemma 22, ∥ev ∥∞ ≤ 1/4, so m

1 X 1 Bv (ev ) ≤ |ev (i)|Qi ({v})|MΓ (v, t(i))| ≤ Av . m 4 i=1

sv ) . Summing over v gives Since Bv (sv ) = Bv (b sv ) + Bv (ev ), this implies 34 Av ≤ Bv (b ∆t (Q) ≤

4 X Bv (b sv ) . 3cΓ v∈V (Q)

Writing sbv (i) = α0 (r(v))w0 (i) +

kh L−1 XX

αh,q (r(v))wh,q (i),

h=0 q=1

linearity of Bv (·) and the coefficient bounds from Lemma 22 give X v∈V (Q)

Bv (b sv ) ≤ sup |α0 (r)| Err(w0 ) + r

kh L−1 XX h=0 q=1

22

sup |αh,q (r)| Err(wh,q ). r

Now w0 = gall , so Err(w0 ) = ErrΓPt (Q; gall ) ≤ MCΓt (Q; Gm ). Also, for each 0 ≤ h ≤ L − 1, each 1 ≤ q ≤ kh , and each v ∈ V (Q), we have wh,q = gh,q,+ − gh,q,− and hence Bv (wh,q ) = Bv (gh,q,+ ) − Bv (gh,q,− ). Therefore Bv (wh,q ) ≤ Bv (gh,q,+ ) + Bv (gh,q,− ) , and summing over v gives Err(wh,q ) ≤ ErrΓPt (Q; gh,q,+ ) + ErrΓPt (Q; gh,q,− ) ≤ 2MCΓt (Q; Gm ). Thus, using again the coefficient bounds from Lemma 22, the right-hand side is at most (1 + 4L)MCΓt (Q; Gm ). Therefore, as claimed, we obtain ∆t (Q) ≤

6(1 + L) 4 (1 + 4L)MCΓt (Q; Gm ) ≤ MCΓt (Q; Gm ). 3cΓ cΓ

Now, we are ready to show that on our hard instance, multicalibration in fact implies exact decoding. Indeed, as we just saw, a multicalibrated learner must have low prediction error on our instance. Now, a simple geometric argument leveraging the L1 (Um ) well-separation property of the hard distribution family — which we proved earlier in Lemma 24 — will be seen to turn low prediction error into exact recovery of the underlying distribution parameter θ ∈ Θm . Proposition 27 (Multicalibration implies exact decoding). Given a finitely supported randomized predictor Q = (Q1 , . . . , Qm ), define its mean prediction function by Z f¯Q (i) := v Qi (dv), and consider any nearest-neighbor decoder in L1 (Um ): θbΓ (Q) ∈ arg min ∥tϑ − f¯Q ∥L1 (Um ) . ϑ∈Θm

Then, MCΓtθ (Q; Gm ) ≤

cΓ γm 384(1 + log2 m)

implies

θbΓ (Q) = θ.

Proof. By Jensen’s inequality, |f¯Q (i) − tθ (i)| ≤

Z |v − tθ (i)| Qi (dv).

Summing over i gives ∥f¯Q − tθ ∥L1 (Um ) ≤ ∆tθ (Q). By construction tθ is nondecreasing, so Proposition 26 applies and gives ∥f¯Q − tθ ∥L1 (Um ) ≤

γm 6(1 + log2 m) MCΓtθ (Q; Gm ) ≤ . cΓ 64

m However, by Lemma 24, for every θ′ ̸= θ, we have ∥tθ′ − tθ ∥L1 (Um ) ≥ γ16 , and therefore γm γm γm ∥f¯Q − tθ′ ∥L1 (Um ) ≥ ∥tθ′ − tθ ∥L1 (Um ) − ∥f¯Q − tθ ∥L1 (Um ) ≥ − > . 16 64 64 So tθ is the unique nearest codeword to f¯Q , and hence θbΓ (Q) = θ.

23

3.4

Exact decoding has high sample complexity

We have just seen that sufficiently multicalibrated learners must be exact decoders of the hidden distribution parameter θ ∈ Θm . We will now show that in order to exactly decode θ, the learner’s sample complexity must be large. Specifically, recall the pairwise-(KL-)closeness property of the hard distribution family (Lemma 25). Applying Fano’s inequality together with this property, we will demonstrate that exact decod2. ing/learning of the family requires sample complexity on the order of m/γm Lemma 28 (Exact decoding has high sample complexity). Suppose a learner gets n i.i.d. samples Γ and outputs predictors Q from an unknown distribution in Hm S,ζ such that for every θ ∈ Θm ,  γm  2 PS∼(P Γ )n , ζ ∥f¯QS,ζ − tθ ∥L1 (Um ) ≤ ≥ . θ 64 3 Then, n ≥ c2,Γ γm2 , where c2,Γ > 0 is a constant that depends only on Γ. m

Proof. Define the nearest-neighbor decoder e ζ) ∈ arg min ∥tϑ − f¯Q ∥L (U ) . θ(S, S,ζ m 1 ϑ∈Θm

Lemma 24 implies that on the event ∥f¯QS,ζ − tθ ∥L1 (Um ) ≤

γm , 64

e ζ) = θ. Therefore tθ is the unique nearest codeword to f¯QS,ζ , so θ(S,   e ζ) ̸= θ ≤ 1 . sup PS∼(P Γ )n , ζ θ(S, θ 3 θ∈Θm Now let Rζ be the law of the learner’s seed, and view (S, ζ) as one sample from the product family {(PθΓ )n ⊗ Rζ : θ ∈ Θm }. e b := θ(Z). Let Θ be uniform on Θm , let Z denote the resulting observation, and let Θ Write Q :=

1 X (PθΓ )n ⊗ Rζ . |Θm | θ∈Θm

By Fano’s inequality [CT06],   1 X e ζ) ̸= θ ≥ 1 − I(Θ; Z) + log 2 . PS∼(P Γ )n , ζ θ(S, θ |Θm | log |Θm | θ∈Θm

Also, by convexity of KL in its second argument, I(Θ; Z) =

1 X 1 DKL (PθΓ )n ⊗ Rζ ∥ Q ≤ |Θm | |Θm |2 θ∈Θm

24

X θ,θ′ ∈Θm

DKL (PθΓ )n ⊗ Rζ ∥ (PθΓ′ )n ⊗ Rζ ,

Because Rζ does not depend on θ,

CΓ,KL 2 DKL (PθΓ )n ⊗ Rζ ∥ (PθΓ′ )n ⊗ Rζ = DKL (PθΓ )n ∥ (PθΓ′ )n ≤ nγm 2 for every θ, θ′ ∈ Θm , by Lemma 25. Therefore I(Θ; Z) ≤

CΓ,KL 2 nγm . 2

Now note that the worst-case error is at least the average error. Then, using that log |Θm | ≥ c1 m, CΓ,KL   2 e ζ) ̸= θ ≥ 1 − 2 nγm + log 2 . sup PS∼(P Γ )n , ζ θ(S, θ c1 m θ∈Θm 1 Choose m0 large enough that log 2 ≤ c1 m/4 for all m ≥ m0 . Then for m ≥ m0 , if n ≤ 2CcΓ,KL · γm2 , m the Fano lower bound becomes at least 1/2, contradicting the displayed worst-case error bound 1 1/3. Hence the claim holds with c2,Γ := 2CcΓ,KL .

3.5

Proof of Theorem 14

We now finish the lower bound proof. First, we record a consequence of Hölder’s inequality: that a lower bound for ECE multicalibration will imply a lower bound for Lp -multicalibration, for every p ∈ 1[, 2]. In fact, as we will later see, the implied lower bound will also be optimal for all p ∈ [1, 2]. Lemma 29 (From Lp to ECE multicalibration). For every distribution P on a context–label space, every finite family G of binary groups, and every finitely supported randomized predictor Q,  1/p Γ,(p) MCΓP (Q; G) ≤ MCP (Q; G) . Proof. If p = 1, this is immediate from the definition. Assume p > 1, fix a group g ∈ G, and write av := |BPΓ (Q; v, g)|,

πv := πP (Q; v)

on the support where πv > 0. By Hölder’s inequality, X v

av =

av

X

(p−1)/p

v

πv

! πv(p−1)/p ≤

X apv v

πvp−1

!1/p

!(p−1)/p X

πv

=



1/p Γ,(p) ErrP (Q; g) .

v

Taking the maximum over g ∈ G gives the claim. Proof of Theorem 14. Fix a regular property Γ and p ∈ [1, 2]. Fix a regularity witness {Dt : t ∈ I0 } cΓ and interval J = [a, b]. Let cΓ , CΓ,KL be the corresponding regularity constants. Set c3,Γ := 384 . Choose the largest power of two m such that  p γm b−a c3,Γ ≥ ε, γm := . 1 + log2 m 8m

25

Since γm = ΘΓ (1/m), this choice gives m = ΘΓ

(1/ε)1/p log(1/ε)

! .

Γ = {P Γ : θ ∈ Θ } be the hard distribution family from Definition 23, and let G Let Hm m m be the θ hard group family from Definition 19. By the bound after Definition 19, the group family has size

|Gm | = O (1 + log2 m)4 = O log4 (1/ε) .

Assume for contradiction that a learner with internal random seed ζ, given Gm and n i.i.d. Γ , outputs a predictor Q samples from an unknown distribution in Hm S,ζ satisfying   2 Γ,(p) PS∼(P Γ )n , ζ MCP Γ (QS,ζ ; Gm ) ≤ ε ≥ θ 3 θ

for every θ ∈ Θm .

By Lemma 29, on the displayed success event we also have MCΓP Γ (QS,ζ ; Gm ) ≤ ε1/p ≤ c3,Γ θ

cΓ γm γm = . 1 + log2 m 384(1 + log2 m)

For the hard family this is exactly MCΓtθ (QS,ζ ; Gm ) ≤

cΓ γm . 384(1 + log2 m)

Since tθ is nondecreasing, Proposition 26 and Jensen’s inequality imply that on the same event, ∥f¯QS,ζ − tθ ∥L1 (Um ) ≤ ∆tθ (QS,ζ ) ≤

6(1 + log2 m) γm MCΓtθ (QS,ζ ; Gm ) ≤ . cΓ 64

Thus the hypothesis of Lemma 28 is satisfied, and we obtain n ≥ c2,Γ

m = ΩΓ (m3 ). 2 γm

Substituting the chosen value of m then gives the claimed lower bound:   1 e Γ (ε−3/p ). n = ΩΓ 3/p =Ω ε log3 (1/ε)

4

Upper Bounds

This section proves a constructive upper bound that covers ordinary (and in fact, even swap) weighted Lp property multicalibration, for every finite p ≥ 1 and every property with a bounded identification function (including limited to mean multicalibration). The main result is given in e −3/p ): this exponent matches the lower-bound Theorem 30. For 1 ≤ p ≤ 2, the upper bound is O(ϵ exponent of Section 3 up to polylogarithmic factors, and thus implies the tightness of our sample complexity bounds for property Lp -multicalibration for all p ∈ [1, 2]. In addition, Theorem 30 e −(p+1)/p ); in this regime, Section 3 does not supply a gives an upper bound for p > 2, which is O(ϵ 26

matching lower bound, and therefore, the tight sample complexity of Lp -multicalibration for p > 2 is left as an open question. Before stating the next theorem, we note that it is stated in terms of the (population) swap multicalibration metric (SMC), which is stronger than multicalibration due to an interchange of the summation and the maximum operator. By definition, it is the population analog of the empirical SMC, which is formalized below in Definition 33. Theorem 30 (General Multicalibration Upper Bound). Fix p ≥ 1. Let P be a distribution on X ×Y. Fix any [0, 1]-valued property Γ with a bounded (w.l.o.g. by 1 in absolute value) identification function V . Suppose the expected conditional identification function mx (v) := E[V (v, Y ) | X = x] is ρ-Lipschitz on [0, 1] and satisfies mx (0) ≤ 0 ≤ mx (1) for PX -almost every x ∈ X . Then there exists a randomized batch learner with the following sample-complexity guarantee. For every ε > 0, if the learner is given any finite family of binary groups g : X → {0, 1}, denoted by G, together with T i.i.d. samples from P , where     ep,ρ ε−3/p log3/2 (2|G|) (for p ∈ [1, 2]), and T = O ep,ρ ε−(p+1)/p log(p+1)/2 (2|G|) (for p ≥ 2), T =O then it outputs a finitely supported randomized predictor Q such that Γ,(p)

P MCP

2 Γ,(p) (Q; G) ≤ ε ≥ P SMCP (Q; G) ≤ ε ≥ . 3

ep,ρ (ε−3/p ) (1 ≤ p ≤ 2), and T = O ep,ρ (ε−(p+1)/p ) (p ≥ 2). If |G| ≤ ε−O(1) , this implies T = O Observation 31 (Theorem 30 subsumes mean multicalibration). For the mean property, V (v, y) = v − y and mx (v) = E[v − Y | X = x] = v − E[Y | X = x]. Hence, it satisfies the conditions of Theorem 30, with Lipschitz parameter ρ = 1. The proof of Theorem 30 is provided below, in two steps. In Section 4.2, we prove a general online-to-batch reduction that converts an empirical swap multicalibration guarantee on a grid into a population guarantee for the averaged batch predictor. In Section 4.3, we then instantiate the batch predictor by conversion of the online algorithm of Hu et al. [HLSS25, Corollary 1]. A sharper upper bound for mean ECE multicalibration As it turns out, at p = 1, the multicalibration upper bound can be obtained more directly, and with a better logarithmic dependence on |G|, via an online-to-batch conversion of the online L1 ECE-multicalibration algorithm of Noarov et al. [NRRX25, Theorem 2.4] — the first O(T 2/3 ) online multicalibration algorithm. The online-to-batch conversion here does not require the technicalities of going through swap multicalibration or adaptive Freedman-type concentration. The main technical reasons for the simplification are that for p = 1 in particular, unlike for other Lp metrics, (1) duality enables us to linearize the “inner component” of the mulicalibration metric, and (2) there are no bucket mass-dependent denominators that could blow up the error. As such, the online-to-batch reduction can proceed via a standard Azuma-Hoeffding concentration argument. The result is presented below as Theorem 32, and the proof is provided in Section 4.4. Thus, readers interested in the proof of the upper bound just for the canonical (mean ECE) multicalibration case, or wishing to gain intuition for the proof of the general upper bound, may proceed directly to Section 4.4 after reading Section 4.1. 27

Theorem 32 (Sharper Mean-ECE Multicalibration Upper Bound). There is a randomized batch learner which, given any finite group family G, outputs a predictor whose population mean ECE multicalibration error is at most ε with probability at least 2/3, and which uses only
e ε−3 log(2|G|) T =O e −3 ). i.i.d. samples. In particular, if |G| ≤ ε−O(1) , the learner’s sample complexity is O(ε

4.1

Online-setting notation and constructing the averaged predictor

Notation

We now introduce the transcript notation used throughout the upper-bound proofs.

Definition 33 (Online notation). Fix a finite prediction grid Λ = {v1 , . . . , vK } ⊆ [0, 1], and let qt : X → ∆(Λ) be roundwise randomized predictions. For an i.i.d. transcript S = ((X1 , Y1 ), . . . , (XT , YT )) ∼ P T , define the empirical bucket masses and empirical bucket biases by T

π bT,k (S) :=

1X qt,k (Xt ), T

b Γ (S; g) := 1 B T,k T

t=1

T X

g(Xt )qt,k (Xt )V (vk , Yt ).

t=1

The empirical ordinary and swap weighted Lp transcript objectives are p X X b Γ (S;g) Γ,(p) Γ,(p) B T,k d [ T (S; G, Λ) := MCT (S; G, Λ) := max , SMC p−1 π b (S)

p

b Γ (S;g) B max πb T,k(S)p−1 . T,k g∈G k∈[K]: π bT,k (S)>0

T,k g∈G k∈[K]: π bT,k (S)>0

We now recall (and briefly reprove for completeness) that swap multicalibration yields guarantees that are stronger than those of ordinary multicalibration. Lemma 34 (Swap multicalibration implies ordinary multicalibration). For every p ≥ 1, Γ,(p)

MCP

Γ,(p)

(QS ; G) ≤ SMCP

(QS ; G),

Γ,(p)

d Γ,(p) [T MC (S; G, Λ) ≤ SMC T

and

(S; G, Λ).

Proof. We prove the first claim; the second follows identically. For each bucket k and group g, if Γ (Q ; g) p BP,k S πP,k (QS ) = 0 then let ak (g) := 0, and if if πP,k (QS ) > 0 then let ak (g) := . Then, πP,k (QS )p−1 X X Γ,(p) Γ,(p) MCP (QS ; G) = max ak (g) ≤ max ak (g) = SMCP (QS ; G). g∈G

k

k

g∈G

Constructing a batch predictor from an online predictor Now, we formalize how an online predictor should be converted to a batch predictor. This requires a bit more care than in the classical online-to-batch reduction for no-regret learning algorithms: rather than simply sampling the predictor from a random round in the transcript, we need to average the predictors over all rounds. Formally, this yields the following construction. Definition 35 (Batch predictor). Define the averaged batch predictor QS with support Λ by T

qS,k (x) :=

1X qt,k (x), T

(QS )x :=

t=1

K X

qS,k (x) δvk .

k=1

Its population bucket masses and population bucket biases are     Γ πP,k (QS ) := E(X,Y )∼P qS,k (X) , BP,k (QS ; g) := E(X,Y )∼P g(X)qS,k (X)V (vk , Y ) . 28

4.2

The online-to-batch reduction for swap multicalibration

First, we prove a form of Freedman’s inequality that incorporates the (random) second-moment martingale difference bounds into the bound. This lemma packages the Freedman-plus-dyadicpeeling argument of [HLSS25, Lemma 6 and the proof of Theorem 2, esp. equations (8)–(9)]. Lemma 36 (Variance process-adaptive Freedman bound). Let (Ft )Tt=0 be a filtration, let b ≥ 1, and let Z1 , . . . , ZT be a martingale difference sequence adapted to it with |Zt | ≤ b for all t. Let u1 , . . . , uT be Ft−1 -measurable random variables in [0, 1] such that E[Zt2 | Ft−1 ] ≤ ut

(t ∈ [T ]).

Then for every L ≥ 1, for a universal C > 0 it holds that !! r T 1X πL bL Zt > C ≤ 2(⌈log2 T ⌉ + 1)e−L , P + T T T

T

where π :=

t=1

Pt

1X ut . T t=1

PT

Pt

Proof. Let St := s=1 Zs , Wt := s=1 E[Zs2 | Fs−1 ]. Then WT ≤ t=1 ut = T π. Set J := ⌈log2 T ⌉. For j = 0, . . . , J − 1, let Ij := (2−j−1 , 2−j ], and let IJ := [0, 2−J ]. (The standard form of) Freedman’s inequality gives, for every v > 0 and every L ≥ 1, √
P |ST | > 2 vL + 2bL, WT ≤ v ≤ 2e−L . √
If π ∈ Ij with j ≤ J − 1, then WT ≤ T 2−j , and hence P |ST | > 2 T 2−j L + 2bL, π ∈ Ij ≤ 2e−L . √
If π ∈ IJ , then 2−J ≤ 1/T , so WT ≤ 1, and therefore P |ST | > 2 L + 2bL, π ∈ IJ ≤ 2e−L . A union bound over 0 ≤ j ≤ J shows that the corresponding bound holds on all intervals at once, with probability at least 1 − 2(J + 1)e−L . q ST 2πL 2bL T ≤2 T + T . √ √ 4bL ≤ 2 T L + 2bL L ≤ L ≤ bL. T ≤ T , because b ≥ 1 and L ≥ 1 imply

On that event, if π ∈ Ij with j ≤ J − 1, then 2−j ≤ 2π, and hence

If instead π ∈ IJ , then STT Enlarging the constant gives the claim.

With this concentration bound in hand, we are ready to establish the bridge between the empirical online, and the population, swap multicalibration. Proposition 37 (Online-to-batch reduction for swap Lp -multicalibration). Fix p ≥ 1, and let QS be the averaged batch predictor defined above. There is a constant Cp > 0 such that, with L := log(4K|G|T ), we have #  " p/2  KL KL C    h i + , 1 ≤ p ≤ 2, p Γ,(p) Γ,(p) T T [ ES∼P T SMCP (QS ; G) ≤ Cp ES∼P T SMCT (S; G, Λ) +   Cp KL , p ≥ 2. T i h Γ,(p) Consequently, the same bound holds for ES∼P T MCP (QS ; G) .

29

Proof. Define for k ∈ [K] the population bucket mass, and for g ∈ G, the population bucket bias: πk (S) := E(X,Y )∼P [qS,k (X)]

and

Bk (S; g) := E(X,Y )∼P [g(X)qS,k (X)V (vk , Y )].

For the empirical quantities, write the shorthands: bk (S; g) := B b Γ (S; g), B T,k

π bk (S) := π bT,k (S), Thus, in this notation we can write: Γ,(p)

SMCP

(QS ; G) =

X

k: πk (S)>0

|Bk (S; g)|p , g∈G πk (S)p−1

Γ,(p)

[T SMC

max

X

(S; G, Λ) =

k: π bk (S)>0

bk (S; g)|p |B . g∈G π bk (S)p−1

max

For each t ∈ [T ] and k ∈ [K], and each g ∈ G, let αt,k := E[qt,k (Xt ) | Ht−1 ] Then

bt,k (g) := E[g(Xt )qt,k (Xt )V (vk , Yt ) | Ht−1 ].

and

T

πk (S) =

1X αt,k T

T

and

Bk (S; g) =

t=1

1X bt,k (g). T t=1

Define the martingale differences Nt,k := qt,k (Xt ) − αt,k ,

Mt,k (g) := g(Xt )qt,k (Xt )V (vk , Yt ) − bt,k (g).

Since qt,k (Xt ) ∈ [0, 1], we have |Nt,k | ≤ 1. Also |g(Xt )qt,k (Xt )V (vk , Yt )| ≤ 1, so |Mt,k (g)| ≤ 2. Moreover, 2 | Ht−1 ] ≤ E[qt,k (Xt )2 | Ht−1 ] ≤ αt,k , E[Nt,k   E[Mt,k (g)2 | Ht−1 ] ≤ E g(Xt )2 qt,k (Xt )2 V (vk , Yt )2 | Ht−1 ≤ αt,k . Therefore

T X t=1

2 | Ht−1 ] ≤ T πk (S), E[Nt,k

T X

E[Mt,k (g)2 | Ht−1 ] ≤ T πk (S).

t=1

Set L0 := 3L. Apply the variance process-adaptive Freedman’s inequality (Lemma 36) to each of the K sequences (Nt,k )Tt=1 with b = 1, and to each of the K|G| sequences (Mt,k (g))Tt=1 with b = 2. Each application of Lemma 36 at level L0 = 3L fails with probability at most 2(⌈log2 T ⌉ + 1)e−3L . Since there are K + K|G| ≤ 2K|G| sequences and ⌈log2 T ⌉ + 1 ≤ 2T , a union bound gives total failure probability at most 1 2K|G| · 2(⌈log2 T ⌉ + 1)e−3L ≤ . T Therefore, there is a constant C > 0 such that with probability at least 1 − 1/T , the following two inequalities hold simultaneously for all k ∈ [K] and all g ∈ G — which we define as an event E: ! r πk (S)L L |b πk (S) − πk (S)| ≤ C + , (1) T T r bk (S; g) − Bk (S; g)| ≤ C |B 30

πk (S)L L + T T

! .

(2)

Fix a sufficiently large constant c⋆ > 0 and define the threshold τ := c⋆ TL . Now, let us partition the buckets into “light” and “heavy” ones according to τ : L := {k ∈ [K] : πk (S) < τ }

and

H := {k ∈ [K] : πk (S) ≥ τ }.

We will first easily address the light (infrequently used) buckets, and then focus on bounding the empirical-population term deviations for heavy (frequently-used) buckets.   Light buckets. For all k and g ∈ G, |Bk (S; g)| ≤ E g(X)qS,k (X)|V (vk , Y )| ≤ E[qS,k (X)] = πk (S). p k (S;g)| ≤ πk (S), and since the swap objective only Hence, for every k with πk (S) > 0, maxg∈G |B πk (S)p−1 sums buckets with positive mass, it follows that X

X |Bk (S; g)|p πk (S) ≤ Kτ. ≤ g∈G πk (S)p−1

max

k∈L: πk (S)>0

k∈L

Heavy buckets. Work on the event Eh and fix k ∈ iH. If c⋆ is chosen large enough, then (1) implies |b πk (S) − πk (S)| ≤ πk2(S) , so π bk (S) ∈ πk2(S) , 3πk2(S) . In particular, 1 1 ≤ 2p−1 . p−1 πk (S) π bk (S)p−1 Also, by (2) and πk (S) ≥ τ = c⋆ L/T , r bk (S; g)| + C |Bk (S; g)| ≤ |B

πk (S)L L + T T

!

r bk (S; g)| + Cp ≤ |B

πk (S)L . T

Using (u + v)p ≤ 2p−1 (up + v p ), we obtain  p/2 p b |Bk (S; g)|p L p−1 |Bk (S; g)| ≤2 + Cp πk (S)1−p/2 . p−1 p−1 πk (S) πk (S) T Combining this with the denominator comparison yields  p/2 bk (S; g)|p |Bk (S; g)|p |B L max ≤ Cp max + Cp πk (S)1−p/2 . g∈G πk (S)p−1 g∈G π bk (S)p−1 T On the event E, summing over k ∈ H and adding the light-bucket contribution gives X Γ,(p) Γ,(p) [ T (S; G, Λ) + Cp SMCP (QS ; G) ≤ Cp SMC k∈H

 p/2 L πk (S)1−p/2 + Kτ. T

(3)

We now explicitly bound the heavy-bucket sum in (3), separately for p ∈ [1, P 2] and for p > 2. If 1 ≤ p < 2, then a := 1 − p/2 ∈ (0, 1). The concavity of x 7→ xa and K k=1 πk (S) = 1 imply X k∈H

πk (S)1−p/2 ≤

K X

πk (S)a ≤ K 1−a = K p/2 ,

k=1

31

For the case p = 2, it also holds that

1−p/2 = k∈H πk (S)

P

Γ,(p) Γ,(p) [ T (S; G, Λ) + Cp SMCP (QS ; G) ≤ Cp SMC

"

KL T

P

p/2

k∈H 1 = |H| ≤ K = K

KL + T

# on the event E (for 1 ≤ p ≤ 2).

πk (S)1−p/2 ≤ Kτ 1−p/2 . k∈H
L p/2 1−p/2 τ = Cp KL T T . Thus, we obtain

For p ≥ 2, heavy buckets satisfy πk (S) ≥ τ , so πk (S)1−p/2 ≤ τ 1−p/2 and Thus the heavy-bucket term in (3) is at most Cp K Γ,(p)

SMCP

Γ,(p)

[T (QS ; G) ≤ Cp SMC

p/2 . Therefore,

(S; G, Λ) + Cp

P

KL on the event E (for p ≥ 2). T

Γ,(p)

Γ,(p) [ T (S; G, Λ) lie in [0, 1], because every bucket contriFinally, both SMCP (QS ; G) and SMC bution is at most the corresponding bucket mass and the bucket masses sum to 1. Therefore

    Γ,(p) Γ,(p) [ T (S; G, Λ) + transfer term + P(E c ). E SMCP (QS ; G) ≤ Cp E SMC Since P(E c ) ≤ 1/T and K, L ≥ 1, the final 1/T term is absorbed into Cp KL/T . This proves the swap bound. The ordinary bound then follows from Lemma 34.

4.3

Instantiating the batch swap multicalibration algorithm

Proposition 38 ([HLSS25]). Assume the hypotheses of Theorem 30. Then there is a grid-supported online forecaster, i.e. a sequence of roundwise distributions qt : X → ∆(Λ), such that: e 1/3 ) and satisfies 1. if 1 ≤ p ≤ 2, the forecaster uses a grid of size K = Θ(T     Γ,(p) ep,ρ (log(2|G|))p/2 T −p/3 ; [ E SMCT (S; G, Λ) ≤ O e 1/(p+1) ) and satisfies 2. if p ≥ 2, the forecaster uses a grid of size K = Θ(T     Γ,(p) ep,ρ (log(2|G|))p/2 T −p/(p+1) . [ E SMCT (S; G, Λ) ≤ O Proof. Hu et al. [HLSS25, Corollary 1], specialized to the finite class G of binary groups, give a high-probability bound for cumulative swap multicalibration under exactly the displayed Lipschitz and endpoint assumptions. We encode their deterministic grid prediction pt : X → Λ in our notation by the point-mass vector qt,k (x) := 1{pt (x) = vk }. If the forecaster uses internal randomness, we absorb it into the history as before. With this choice Γ,(p) [ T (S; G, Λ) is exactly the normalized swap objective of of qt , our empirical swap objective SMC [HLSS25]. We now recall the bounds that they give for p ∈ [1, 2] and p ≥ 2 (coinciding at p = 2).

32

e 1/(p+1) ), and Corollary 1 For p ≥ 2, their finite-class construction uses a grid of size K = Θ(T
ep,ρ (log(2|G|) + log(1/δ))p/2 T 1/(p+1) with probability at least gives the cumulative swap bound O 1 − δ. Dividing by T yields (on the same event) the normalized empirical bound   Γ,(p) ep,ρ (log(2|G|) + log(1/δ))p/2 T −p/(p+1) . [ T (S; G, Λ) ≤ O SMC ep,ρ (log(2|G|) + log(1/δ))p/2 T 1−p/3 For 1 ≤ p < 2, Corollary 1 gives the cumulative swap bound O with probability at least 1 − δ. In this regime Hu et al. obtain the displayed p < 2 rate from the e 1/3 ) (via their Hölder reduction from the same finite-class construction with grid size K = Θ(T p = 2 case). Dividing by T yields (on the same event) the normalized empirical bound   Γ,(p) ep,ρ (log(2|G|) + log(1/δ))p/2 T −p/3 . [ T (S; G, Λ) ≤ O SMC Finally, the empirical swap error always lies in [0, 1], so setting δ := 1/T and using E[X] ≤ a + δ whenever 0 ≤ X ≤ 1 and X ≤ a with probability at least 1 − δ, we obtain the displayed expectation e notation. bound after absorbing the extra T −1 term into the O(·) Proof of Theorem 30. Apply Proposition 38 and then Proposition 37 to the resulting online foree 1/3 caster. If 1 ≤ p ≤  2, then K = Θ(T ), and the transfer term in Proposition 37 is therefore 
ep (T −p/3 ), which is of the same order as the empirical online bound from ep KL p/2 + KL = O O T T Proposition 38. Hence     Γ,(p) ep,ρ (log(2|G|))p/2 T −p/3 E SMCP (QS ; G) ≤ O (1 ≤ p ≤ 2).
e 1/(p+1) ), so the transfer term becomes O ep KL = O ep (T −p/(p+1) ), again If p ≥ 2, then K = Θ(T T of the same order as the empirical online bound. Therefore     Γ,(p) ep,ρ (log(2|G|))p/2 T −p/(p+1) E SMCP (QS ; G) ≤ O (p ≥ 2).
Γ,(p) If the expected error is at most ε/3, the output will satisfy P SMCP (QS ; G) ≤ ε ≥ 32 . by Markov’s inequality. Solving the displayed expectation bounds for T yields exactly the samplecomplexity bounds in the theorem. The ordinary bound follows from Lemma 34.

4.4

Sharper upper bound for mean ECE multicalibration

Proposition 39 (ECE online-to-batch reduction). Consider the mean property, with the identification function V (v, y) = v − y. Then, there is a universal constant Cmean > 0 such that r   h i Γ,(1) K + log(2|G|) + 1 Γ,(1) d , ES∼P T MCP (QS ; G) ≤ ES∼P T MCT (S; G, Λ) + Cmean T where Γ is the mean property, so that the ordinary weighted L1 objective is exactly mean ECE. Proof. For σ = (σ1 , . . . , σK ) ∈ {±1}K , define Ag,σ := g(Xt ) t

K X

σk qt,k (Xt )(vk − Yt ).

k=1

33

Also define the population and empirical signed scores ag,σ (S) :=

K X

T

σk E(X,Y )∼P [g(X)qS,k (X)(vk − Y )]

and

b ag,σ (S) :=

1 X g,σ At . T t=1

k=1

Using the definition of qS,k and then averaging over t, " # T K X 1X ag,σ (S) = E(X,Y )∼P g(X) σk qt,k (X)(vk − Y ) . T t=1

k=1

Since qt is Ht−1 -measurable and (Xt , Yt ) is a fresh draw from P independent of Ht−1 , " # K X g,σ E[At | Ht−1 ] = E(X,Y )∼P g(X) σk qt,k (X)(vk − Y ) almost surely. k=1

| Ht−1 ]−Ag,σ Thus, letting (Mtg,σ )Tt=1 be a martingale difference sequence defined as Mtg,σ := E[Ag,σ t t , T

ag,σ (S) − b ag,σ (S) =

1 X g,σ Mt . T t=1

Because g(Xt ) ∈ {0, 1}, the coefficients qt,k (Xt ) form a probability vector, and each vk −Yt ∈ [−1, 1], ∈ [−1, 1] and hence |Mtg,σ | ≤ 2. Thus, by Azuma–Hoeffding, for every (g, σ) and η > 0, we have Ag,σ t  
T η2 P ag,σ (S) − b ag,σ (S) ≥ η ≤ exp − . 8 Now define (with the second equality using that −σ ∈ {±1}K whenever σ ∈ {±1}K ):
Ξ(S) := max max ag,σ (S) − b ag,σ (S) = max max |ag,σ (S) − b ag,σ (S)| . g∈G σ∈{±1}K

g∈G σ∈{±1}K

For every real vector (b1 , . . . , bK ), K X

|bk | =

k=1

max

σ∈{±1}K

K X

σk bk .

k=1

Applying this identity bucketwise shows that Γ,(1)

MCP

d Γ,(1) (QS ; G) ≤ MC (S; G, Λ) + Ξ(S). T

Thus, it suffices to bound E[Ξ(S)]. First, since there are |G|2K pairs (g, σ), a union bound gives  
T η2 K (η > 0). P Ξ(S) ≥ η ≤ |G|2 exp − 8 q N Now, let N := max{e, |G|2K }, η0 := 8 log . Since Ξ(S) ≥ 0, T Z ∞

Z ∞

P Ξ(S) ≥ η dη ≤ η0 +

E[Ξ(S)] = 0

η0

34

  T η2 N exp − dη. 8

R∞ −u2 2 Using the Gaussian tail bound u e−s ds ≤ e 2u (u > 0), and that N ≥ e, we can see that the 2 second term is at most 4N (T η0 )−1 e−T η0 /8 ≤ η0 . Hence, for a universal constant Cmean > 0, r K + log(2|G|) + 1 E[Ξ(S)] ≤ 2η0 ≤ Cmean . T Lemma 40 (Rounding interval buckets to a prediction grid). Fix an integer K ≥ 1, let   k−1 k   , k = 1, . . . , K − 1, ,  2k − 1 K K Ik :=  vk := . K − 1  2K  ,1 , k = K,  K For each round t, let p̄t be a probability distribution on [0, 1], and define qt,k := PP ∼p̄t [P ∈ Ik ]. Then for every choice of labels y1 , . . . , yT ∈ [0, 1] and weights g1 , . . . , gT ∈ {0, 1}, T K T K X X 1X 1 1X gt qt,k (vk − yt ) ≤ + EP ∼p̄t [gt 1{P ∈ Ik }(P − yt )] . T 2K T t=1

k=1

k=1

t=1

Proof. For each k, T

T

T

t=1

t=1

t=1

1X 1X 1X gt qt,k (vk − yt ) = EP ∼p̄t [gt 1{P ∈ Ik }(P − yt )] + EP ∼p̄t [gt 1{P ∈ Ik }(vk − P )]. T T T Summing the triangle inequality over k therefore yields T K T K K X X X 1X 1X |Dk |, gt qt,k (vk − yt ) ≤ EP ∼p̄t [gt 1{P ∈ Ik }(P − yt )] + T T k=1

t=1

t=1

k=1

where

k=1

T

1X Dk := EP ∼p̄t [gt 1{P ∈ Ik }(vk − P )]. T t=1

If P ∈ Ik , then |vk − P | ≤ 1/(2K). Hence we obtain the claim by noting that K X k=1

T

K

T

t=1

k=1

t=1

1 X 1 1 X X gt PP ∼p̄t [P ∈ Ik ] = gt ≤ |Dk | ≤ . 2KT 2KT 2K

  1/3   T Proof of Theorem 32. Let K := max 1, log(2|G|T , Λ := 2k−1 2K : k ∈ [K] . Run the online ) algorithm of [NRRX25] on the i.i.d. transcript S = ((X1 , Y1 ), . . . , (XT , YT )) ∼ P T . At round t, H after observing the history Ht−1 , let p̄t = p̄t t−1 : X → ∆([0, 1]) denote the resulting randomized prediction rule.

35

For each interval bucket Ik from Lemma 40, define the rounded grid weights by qt,k (x) := PP ∼p̄t (x) [P ∈ Ik ]. Since the intervals (Ik )K k=1 partition [0, 1], this defines a roundwise distributionvalued rule qt : X → ∆(Λ) and therefore an averaged batch predictor QS as in Subsection 4.1. Fix g ∈ G and k ∈ [K], and consider the bucket event Eg,k (x, p) := g(x)1{p ∈ Ik }. PT E [Eg,k (Xt , P )]. Note that Define the incidence of the bucket event as ng,k (S) := PK t=1 P ∼p̄t (Xt ) PK PT PK k=1 qt,k (Xt ) = 1 and g(Xt ) ∈ {0, 1}. k=1 qt,k (Xt ) ≤ T , since t=1 g(Xt ) k=1 ng,k (S) = We use Noarov et al. [NRRX25, Theorem 2.4] in the pathwise bias-guarantee form, so the following inequality holds for every realized transcript S. Applied to the event family {Eg,k : g ∈ G, k ∈ [K]}, it gives simultaneously for all g ∈ G and k ∈ [K] the cumulative bias bound T X

 EP ∼p̄t (Xt ) [g(Xt )1{P ∈ Ik }(P − Yt )] ≤ CN

 q L + ng,k (S)L

t=1

where L := log(2K|G|T ) and CN > 0 is aP constant. Dividing this cumulative bound by T , summing over k, and using Cauchy–Schwarz with k ng,k (S) ≤ T gives: T K X KL 1X EP ∼p̄t (Xt ) [g(Xt )1{P ∈ Ik }(P − Yt )] ≤ CN + CN T T k=1

t=1

r

KL . T

Now, to round the interval predictions to a prediction grid, we apply Lemma 40 with gt := g(Xt ) and yt := Yt and take the maximum over g ∈ G, yielding the empirical mean-ECE bound q Γ,(1) 1 KL d MCT (S; G, Λ) ≤ 2K + CN T + CN KL T . Taking expectations and applying the online-to-batch reduction Proposition 39, we then obtain (substituting the choice of K from above) the bound:  q q 1/3    Γ,(1) K+log(2|G|)+1 log(2|G|T ) 1 KL KL e E MCP (QS ; G) ≤ 2K + CN T + CN =O . T + Cmean T T Since the objective is always in [0, 1], Markov’s inequality converts this expectation bound into success probability at least 2/3 after adjusting constants. Finally, solving for T yields
e ε−3 log(2|G|) . T =O

5

Discussion and Open Problems

An interesting question that our paper leaves open is whether randomization is necessary to achieve the minimax optimal sample complexity rates that we derive. In the notation of Definition 6, (κ) (κ) this asks whether restricting the infimum in SCmean-ECE (ε), SCLp (ε), and their property-specific analogues to learners that output deterministic models changes the asymptotic rate. One natural route to derandomization is to (randomly) fix the model’s internal randomness in advance and appeal to concentration: if no single context x carries substantial probability mass, then a random 36

realization of the predictor should preserve its calibration guarantees on most of the distribution. This heuristic breaks down in the presence of atoms of nontrivial mass, where a single unlucky realization at one context can create a large calibration error. It would be interesting to understand whether deterministic predictors can match the randomized minimax rates in full generality, or whether there is a genuine gap between deterministic and randomized multicalibration. Our results characterize the minimax dependence on ε for mean ECE and weighted Lp multicalibration throughout the entire regime of polynomial group growth, and, under the corresponding upper-bound hypotheses, the same exponents extend to relevant concrete property classes such as quantiles and expectiles. The point is that our lower-bound constructions themselves use only polylogarithmically many groups: after choosing the hard-instance parameter as a function of ε, e −3 ) for mean ECE and we have |G| = polylog(1/ε). Consequently the sharp lower bounds Ω(ε e −3/p ) for weighted Lp already fit every polynomial budget |G| ≤ ε−κ with fixed κ > 0, and Ω(ε therefore match the corresponding upper bounds up to polylogarithmic factors. Some growth in |G| is nevertheless essential. For a fixed binary group family G, the groups induce a partition of the domain into at most 2|G| parts, corresponding to the possible intersection patterns of the groups. Estimating the mean on each cell and predicting that cellwise empirical e |G| /ε2 ) for mean ECE. Thus one cannot hope for a uniform mean yields the trivial upper bound O(2 e −3 ) lower bound when |G| is fixed, and at the exponent level the constant-budget regime behaves Ω(ε like ordinary mean estimation. The remaining open problem is therefore to determine the optimal joint dependence of the minimax sample complexity on both ε and the group-budget parameter M . In particular, it would e be very interesting to know whether the current O((log |G|)/ε3 ) upper bounds for mean ECE can e (|G|)/ε3 ) for some f (x) = o(log x), or whether such sublogarithmic dependence be improved to O(f can be ruled out in regimes where |G| grows with 1/ε but remains subpolynomial. More generally, one can ask for the sharp interpolation between the trivial 2|G| /ε2 upper bound for small |G| and the ε−3/p behavior that our lower bounds show is unavoidable throughout the polynomial-budget regime, as well as for analogous statements in terms of structural complexity parameters such as VC dimension.

Acknowledgments The authors used AI tools, specifically GPT 5.4 Pro, and GPT 5.4 in the Codex environment in the development of this paper; all of the final theorems and proofs are written and verified by the authors, and all of the exposition and discussion of related work was written without AI assistance.

References [BGJ+ 22] Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Practical adversarial multivalid conformal prediction. In Advances in Neural Information Processing Systems, volume 35, 2022. [CDV24] 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. [CGGR25] Natalie Collina, Surbhi Goel, Varun Gupta, and Aaron Roth. Tractable agreement 37

protocols. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1532–1543, 2025. [CGHG+ 26] 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, 2026. [CGKR25] Sı́lvia Casacuberta, Parikshit Gopalan, Varun Kanade, and Omer Reingold. How global calibration strengthens multiaccuracy. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1198–1227, 2025. [CLNR26] Natalie Collina, Jiuyao Lu, Georgy Noarov, and Aaron Roth. Optimal lower bounds for online multicalibration. arXiv preprint arXiv:2601.05245, 2026. [CT06] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. WileyInterscience, 2 edition, 2006. [Daw82] A Philip Dawid. The well-calibrated bayesian. Journal of the American Statistical Association, 77(379):605–610, 1982. [DDF+ 25] 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. [DDZ23] Zhun Deng, Cynthia Dwork, and Linjun Zhang. Happymap: A generalized multicalibration method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), page 41:1–41:23. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023. [DT25] Cynthia Dwork and Pranay Tankala. arXiv:2509.17994, 2025.

Supersimulators.

arXiv preprint

[GHHK+ 23] Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. Multicalibration as boosting for regression. In Proceedings of the 40th International Conference on Machine Learning, pages 11459–11492. PMLR, 2023. [GHK+ 23] 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), 2023. [GHR24] Parikshit Gopalan, Lunjia Hu, and Guy N. Rothblum. On computationally efficient multi-class calibration. In Proceedings of Thirty Seventh Conference on Learning Theory, pages 1983–2026. PMLR, 2024. [GJN+ 22] 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 – Leibniz-Zentrum für Informatik, 2022. 38

[GJRR24] 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. [GKR+ 22] 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. [GKSZ22] Parikshit Gopalan, Michael P. Kim, Mihir A. Singhal, and Shengjia Zhao. Low-degree multicalibration. In Proceedings of Thirty Fifth Conference on Learning Theory, pages 3193–3234. PMLR, 2022. [GMS25] 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. [GOR+ 24] Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, and Mihir Singhal. Omnipredictors for regression and the approximate rank of convex functions. In The Thirty Seventh Annual Conference on Learning Theory, pages 2027– 2070. PMLR, 2024. [GT25] Isaac Gibbs and Ryan J. Tibshirani. Sample-efficient omniprediction for proper losses. arXiv preprint arXiv:2510.12769, 2025. [HJKRR18] 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. [HJZ23] Nika Haghtalab, Michael I. Jordan, and Eric Zhao. A unifying perspective on multicalibration: Game dynamics for multi-objective learning. In Advances in Neural Information Processing Systems, volume 36, pages 72464–72506, 2023. [HLSS25] Lunjia Hu, Haipeng Luo, Spandan Senapati, and Vatsal Sharan. Efficient swap multicalibration of elicitable properties. arXiv preprint arXiv:2511.04907, 2025. [Hoe63] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. [JLP+ 21] Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, and Rakesh Vohra. Moment multicalibration for uncertainty estimation. In Proceedings of Thirty Fourth Conference on Learning Theory, pages 2634–2678. PMLR, 2021. [JNRR23] Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Batch multivalid conformal prediction. In The Eleventh International Conference on Learning Representations, 2023.

39

[LNPR22] 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. [Mat94] Jiri Matousek. Geometric range searching. ACM Computing Surveys, 26(4):421–461, 1994. [NR23] Georgy Noarov and Aaron Roth. The statistical scope of multicalibration. In Proceedings of the 40th International Conference on Machine Learning, pages 26283–26310. PMLR, 2023. [NRRX25] Georgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan Xie. Highdimensional prediction for sequential decision making. In Proceedings of the 42nd International Conference on Machine Learning, pages 46762–46783. PMLR, 2025. [OKK25] 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. [QV21] 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. [RBFJ22] Harrison Rosenberg, Robi Bhattacharjee, Kassem Fawaz, and Somesh Jha. An exploration of multicalibration uniform convergence bounds. arXiv preprint arXiv:2202.04530, 2022. [Rot06] Ron Roth. Introduction to coding theory. Cambridge University Press, 2006. [SCM20] 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. [TS17] Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 238–251, 2017.

A

Regularity Verifications

A.1

The mean property

Proposition 41 (The mean admits a Bernoulli regularity witness). Let Γmean be the mean property, Vmean (v, y) := v − y, and Dt := Ber(t). Then for every closed interval I0 ⊂ (0, 1), the family (Γmean , Vmean , {Dt : t ∈ I0 }) is a regularity witness on I0 . Moreover, on I0 = [1/4, 3/4] one may take cΓ = 1,

CΓ,KL = 40

16 . 3

Proof. For Y ∼ Ber(t), MΓ (v, t) = E[v − Y ] = v − t, so (v − t)MΓ (v, t) = (v − t)2 . Thus condition (2) in Definition 11 holds with cΓ = 1, and condition (1) is immediate. Fix any closed interval I0 ⊂ (0, 1) and let δI0 := min u(1 − u) > 0. u∈I0

If p, q ∈ I0 , then by log x ≤ x − 1, p 1−p DKL (Ber(p) ∥ Ber(q)) = p log + (1 − p) log q 1−q     p 1−p ≤p − 1 + (1 − p) −1 q 1−q (p − q)2 (p − q)2 ≤ . = q(1 − q) δ I0 This proves condition (3) on I0 . On I0 = [1/4, 3/4], the same calculation sharpens to DKL (Ber(p) ∥ Ber(q)) ≤

16 (p − q)2 = (p − q)2 , (1/4)(3/4) 3

which is the claimed constant.

A.2

Expectiles

Definition 42 (τ -expectile). Fix an expectile level τ ∈ (0, 1). For a distribution ν on [0, 1], the τ -expectile Γτ (ν) is the unique value v ∈ [0, 1] satisfying EY ∼ν [Vτ (v, Y )] = 0,

Vτ (v, y) := |τ − 1{y ≤ v}| (v − y).

Proposition 43 (Expectiles admit a regularity witness). Fix τ ∈ (0, 1). For t ∈ [1/4, 3/4], define pτ (t) :=

(1 − τ )t τ + (1 − 2τ )t

and

Dt := Ber pτ (t) .

Then (Γτ , Vτ , {Dt : t ∈ [1/4, 3/4]}) is a regularity witness. Moreover, for every distribution ν on [0, 1], the map v 7→ EY ∼ν [Vτ (v, Y )] is 1-Lipschitz on [0, 1]. Proof. For v ∈ [0, 1] and Y ∼ Ber(p), E[Vτ (v, Y )] = (1 − p)(1 − τ )v + pτ (v − 1). Substituting p = pτ (t) gives EY ∼Dt [Vτ (v, Y )] = aτ,t (v − t), 41

aτ,t :=

τ (1 − τ ) . τ + (1 − 2τ )t

Hence Γτ (Dt ) = t and (v − t)EY ∼Dt [Vτ (v, Y )] = aτ,t (v − t)2 . Since τ + (1 − 2τ )t ∈ [min{τ, 1 − τ }, max{τ, 1 − τ }]

(t ∈ [0, 1]),

we have aτ,t ≥ min{τ, 1 − τ } > 0. So the quantitative sign condition holds with cΓτ := min{τ, 1 − τ }. For the KL condition, note that pτ is smooth on [0, 1] with derivative p′τ (t) =

τ (1 − τ ) . (τ + (1 − 2τ )t)2

Thus pτ is Lipschitz on [1/4, 3/4]; let Lτ :=

|p′τ (t)|.

sup t∈[1/4,3/4]

Also pτ ([1/4, 3/4]) is a compact subset of (0, 1), so there is ητ > 0 such that pτ (t) ∈ [ητ , 1 − ητ ]

(t ∈ [1/4, 3/4]).

For t, t′ ∈ [1/4, 3/4], DKL (Dt ∥ Dt′ ) ≤

(pτ (t) − pτ (t′ ))2 L2τ ≤ (t − t′ )2 . ητ (1 − ητ ) ητ (1 − ητ )

So the KL regularity condition holds as well. For the final claim, fix y ∈ [0, 1]. The function v 7→ Vτ (v, y) is continuous and piecewise linear, with slope τ on (−∞, y) and slope 1 − τ on (y, ∞). Hence it is 1-Lipschitz on [0, 1]. Taking expectation over Y ∼ ν preserves the same Lipschitz constant.

A.3

Quantiles

Definition 44 (q-quantile). Fix a quantile level q ∈ (0, 1). Consider a distribution ν on [0, 1], and let Fν be the CDF of ν. Then, the q-quantile Γq (ν) of this distribution is Γq (ν) := inf{v ∈ [0, 1] : Fν (v) ≥ q}. We use the standard identification function Vq (v, y) := 1{y ≤ v} − q. For λ ∈ R, let Dλ be the truncated exponential distribution on [0, 1] with density Z 1 fλ (y) := exp(λy − A(λ)), A(λ) := log eλz dz. 0

42

Proposition 45 (Quantiles admit a regularity witness). For every q ∈ (0, 1) there exist a constant Λq > 0 and a closed interval Iq ⊂ (0, 1) such that, after reparameterizing the family {Dλ : λ ∈ [−Λq , Λq ]} by its q-quantile, (Γq , Vq , {Dt : t ∈ Iq }) is a regularity witness. Moreover, the family {Dt : t ∈ Iq } has densities uniformly bounded above by some constant Cq < ∞. Proof. For λ ̸= 0, the CDF of Dλ is Fλ (v) =

eλv − 1 , eλ − 1

v ∈ [0, 1],

and for λ = 0 it is the uniform CDF F0 (v) = v. Hence the q-quantile of Dλ is   1 log 1 + q(eλ − 1)
, λ ̸= 0, tq (λ) := λ q, λ = 0. This function is smooth and satisfies t′q (0) =

q(1 − q) > 0. 2

By continuity, there is Λq > 0 and constants 0 < ℓq ≤ Lq < ∞ such that ℓq ≤ t′q (λ) ≤ Lq

for every λ ∈ [−Λq , Λq ].

Shrinking Λq further if necessary, we may also ensure that tq ([−Λq , Λq ]) ⊂ (0, 1). Therefore tq is bi-Lipschitz on that interval. Let Iq := tq ([−Λq , Λq ]) and let λq : Iq → [−Λq , Λq ] be the inverse map. For t ∈ Iq , define Dt := Dλq (t) . By construction, Γq (Dt ) = t. Now fix t ∈ Iq and v ∈ [0, 1]. Since EY ∼Dt [Vq (v, Y )] = Fλq (t) (v) − q = Fλq (t) (v) − Fλq (t) (t), the mean value theorem gives EY ∼Dt [Vq (v, Y )] = fλq (t) (ξ)(v − t) for some ξ between v and t. The function (λ, y) 7→ fλ (y) is continuous and strictly positive on the compact set [−Λq , Λq ] × [0, 1], so there are constants 0 < cq ≤ Cq < ∞ such that cq ≤ fλ (y) ≤ Cq

(λ ∈ [−Λq , Λq ], y ∈ [0, 1]).

43

Hence cq (v − t)2 ≤ (v − t)EY ∼Dt [Vq (v, Y )] ≤ Cq (v − t)2 , so the sign condition holds with cΓq = cq . For the KL condition, note that Dλ is a one-dimensional exponential family. Therefore DKL (Dλ ∥ Dλ′ ) = A(λ′ ) − A(λ) − (λ′ − λ)A′ (λ). Taylor’s theorem gives DKL (Dλ ∥ Dλ′ ) =

A′′ (ξ) (λ − λ′ )2 2

for some ξ between λ and λ′ . Since 1 A′′ (ξ) = VarDξ (Y ) ≤ , 4 we obtain

1 DKL (Dλ ∥ Dλ′ ) ≤ (λ − λ′ )2 . 8 Finally, the inverse map λq is Lipschitz on Iq with constant 1/ℓq , so |λq (t) − λq (t′ )| ≤ Therefore DKL (Dt ∥ Dt′ ) ≤

1 |t − t′ |. ℓq

1 (t − t′ )2 , 8ℓ2q

which proves that the displayed family is a regularity witness. The same compactness argument already gave the uniform density upper bound Cq .

B

Details for the related-work rate conversions

This appendix records the calculations behind the converted upper-bound rates summarized in Table 1. We translate each prior guarantee into the mean ECE metric used in the main body. Throughout this section, G is a finite family of binary groups, confidence is a fixed constant, and e hides polylogarithmic factors in 1/ε, |G|, and any confidence parameter. When a paper states O(·) a bound in terms of VC(G), we use the standard inequality VC(G) ≤ log2 |G| for finite classes. The conversions repeatedly use the same bucket-to-ECE calculation. Suppose a predictor uses λ prediction buckets and has per-bucket bias at most α on every group. Rounding each prediction to the center of its bucket changes the bias on any example by at most O(1/λ), and the sum of the absolute bucket biases is at most λα. Thus the resulting mean ECE is at most λα + O(1/λ). This is the same center-rounding calculation formalized in Lemma 40.

44

[HJKRR18] Definition 2 of [HJKRR18] defines α-calibration on a group after discarding an α fraction of the mass, and Theorem 2 proves that when every group in G has mass at least γ, running their algorithm with λ = α returns a (G, 2α)-multicalibrated predictor from   log |G| e O α11/2 γ 3/2 samples. Immediately after Definition 2 they note that β-calibration implies 2β accurate-inexpectation error. Applying this with β = 2α, their theorem yields mean ECE of order α on every group of mass at least γ. For a group of mass below γ, our ECE metric is trivially at most γ because |v − Y | ≤ 1. Hence the unrestricted mean ECE is at most O(α + γ). Choosing α ≍ γ ≍ ε gives   e log |G| . O ε7 Under their original minimum-group-mass assumption, one may instead regard γ as a fixed parameter and recover the sharper conditional rate   log |G| e O 11/2 3/2 . ε γ [GJN+ 22] Definition 2 of [GJN+ 22] is bucketed (α, n)-mean multicalibration: predictions are grouped into n buckets of width 1/n, and every group-bucket pair must have mean bias at most α. Their Theorem 6 gives online bucketed mean multicalibration with ! r log(|G|n) e α=O , T and their Appendix A givespthe corresponding randomized batch predictor; specifically, Theoe log(|G|n)/T ) bucketed guarantee in the batch setting. Rounding rem A.1 states the same O( every bucket to its center therefore gives mean ECE at most ! r log(|G|n) 1 e n + O . T n Setting n ≍ 1/ε and requiring each term to be O(ε) gives   log |G| e T =O . ε4 Haghtalab, Jordan, and Zhao. Definition 2.1 of [HJZ23] is the standard λ-bucket multicalibration condition: for each group, bucket, and class coordinate, the bucket bias is at most ε in absolute value. In the binary mean setting, Theorem 4.1 returns a randomized predictor that is (G, ε, λ)-multicalibrated using   log |G| + log λ O ε2 samples. Rounding every bucket to its center gives mean ECE at most λε + O(1/λ). 45

Choosing λ ≍ 1/η and ε ≍ η 2 to target mean ECE η yields   log |G| e O η4 samples. [GKSZ22] (Low-Degree Multicalibration).

[GKSZ22] study the generalized condition

|E[c(X) w(f (X))(Y − f (X))]| ≤ α over a hypothesis class C and a weight class W . For fixed degree k, the low-degree part of Theorem 35 gives sample complexity   log |G| e O α4 for degree-(k +1) multicalibration in the binary setting. To recover a rate for our mean ECE metric, specialize instead to their full multicalibration notion, which uses the interval basis Iδ of width δ. Proposition 34 with |Iδ | = O(1/δ) gives sample complexity   log |G| e O α4 for (G, Iδ , α)-multicalibration. In the binary case this implies mean ECE at most O(α/δ + δ), because there are O(1/δ) interval buckets and center-rounding contributes another O(δ) term. Choosing δ ≍ ε and α ≍ ε2 gives   log |G| e O . ε8 [GHHK+ 23]

Definition 2.1 of [GHHK+ 23] is the exact weighted L2 multicalibration quantity X K 2 (f, h, D) := Pr[f (X) = v] E[h(X)(Y − v) | f (X) = v]2 . v∈R(f )

Their Theorem 4.3 gives an in-sample boosting algorithm, and Theorem C.9 gives the out-of-sample guarantee: with  5 dB e n=O α5 samples, where d = Pdim(H), the output predictor is O(α)-approximately multicalibrated in this weighted L2 sense. For finite classes, d = O(log |G|). By Cauchy–Schwarz, !1/2 X X 2 πv |biasv | ≤ πv biasv , v

v

so mean ECE is at most the square root of their weighted L2 error. Therefore to achieve mean ECE at most ε, it suffices to take α ≍ ε2 , which yields   log |G| e O . ε10 e −5 log |G|) at target error ρ. Equivalently, their own weighted L2 metric has sample complexity O(ρ 46

[NRRX25]

Theorem 2.4 of [NRRX25] gives a per-event cumulative bias bound of order  p e nT (E) O

simultaneously for all conditioning events E. Their Section 2.2 applies this to mean multicalibration with m prediction buckets and obtains cumulative bucketed multicalibration error   √ T e O + Tm . m Dividing by T gives normalized bucketed error r   m 1 e . O + m T e −1/3 ). Lemma 40 converts this to the Choosing m ≍ T 1/3 yields normalized bucketed error O(T same ECE rate on the transcript, and our online-to-batch conversion then yields the same order in batch. Hence their online theorem implies batch mean ECE sample complexity   log |G| e O , ε3 which is the sharp upper bound used in the main text.

C

Quantizing arbitrary randomized predictors

The main text works with finitely supported randomized predictors because that is the form produced by the online-to-batch reduction and because it lets us write ECE as an explicit sum over prediction values. For lower-bound purposes this is essentially without loss of generality: an arbitrary randomized predictor can be quantized to a finite grid with arbitrarily small additive loss relative to the total-variation extension below. Let P be a distribution on X × [0, 1], let µ(x) := E[Y | X = x], and let Q = (Qx )x∈X be an arbitrary randomized predictor. For a signed weight w : X → [−1, 1], define the signed measure   Z νP,Q;w (A) := E w(X) (v − Y ) QX (dv) A

for Borel sets A ⊆ [0, 1], and set ErrTV P (Q; w) := ∥νP,Q;w ∥TV , ∆TV P (Q) := E If Q is finitely supported, then νP,Q;w = MCTV P (Q; G) = MCP (Q; G).

Z

TV MCTV P (Q; G) := max ErrP (Q; g), g∈G

 |v − µ(X)| QX (dv) .

TV v∈V (Q) BP (Q; v, w) δv , so ErrP (Q; w) = ErrP (Q; w) and

P

47

Proposition 46 (Quantization of arbitrary randomized predictors). For every η > 0 there exists a map Tη : [0, 1] → [0, 1] with finite image and |Tη (v) − v| ≤ η for all v ∈ [0, 1]. Let Q(η) be defined (η) by Qx := (Tη )# Qx . Then Q(η) is finitely supported and, for every signed weight w : X → [−1, 1], ErrP (Q(η) ; w) ≤ ErrTV P (Q; w) + η

and

∆P (Q(η) ) ≤ ∆TV P (Q) + η.

Consequently, for every family G of binary groups, MCP (Q(η) ; G) ≤ MCTV P (Q; G) + η. Proof. Choose any finite-grid rounding map Tη with mesh at most η, for example nearest-grid rounding onto {0, η, 2η, . . . , ⌊1/η⌋η, 1}. For each grid value z in the finite image of Tη , let Cz := Tη−1 ({z}); these sets partition [0, 1], so Q(η) is finitely supported. Fix a signed weight w. For each such z,   Z (Tη (v) − Y ) QX (dv) BP (Q(η) ; z, w) = E w(X) Cz   Z = νP,Q;w (Cz ) + E w(X) (Tη (v) − v) QX (dv) . Cz

Since {Cz }z is a finite measurable partition of [0, 1], we have fore, X ErrP (Q(η) ; w) = |BP (Q(η) ; z, w)|

P

z |νP,Q;w (Cz )| ≤ ∥νP,Q;w ∥TV . There-

z

≤

X

 |νP,Q;w (Cz )| + E |w(X)|

Z

 |Tη (v) − v| QX (dv)

z

≤ ∥νP,Q;w ∥TV + η = ErrTV P (Q; w) + η. Taking the maximum over g ∈ G gives the multicalibration claim. For the prediction error, Z  (η) ∆P (Q ) = E |Tη (v) − µ(X)| QX (dv) Z  Z  ≤E |v − µ(X)| QX (dv) + E |Tη (v) − v| QX (dv) ≤ ∆TV P (Q) + η.

Corollary 47 (Main lower bound extends to arbitrary randomized predictors up to constant-factor slack). Under the same construction and choice of constants as in Theorem 14, suppose a learning algorithm receives n i.i.d. samples from Pθ and outputs an arbitrary randomized predictor QS = (QS,1 , . . . , QS,m ), where each QS,i is a probability measure on [0, 1]. Assume that for every θ ∈ Θm ,
2 PS∼Pθn , A MCTV Pθ (QS ; Gm ) ≤ ε ≥ . 3

48

If ε≤

c3 γ , 2 1 + log2 m

then necessarily n ≥ c2

m . γ2

In particular, along the sequence γ ≍ 1/m, arbitrary randomized predictors also require e −3 ) n = Ω(ε for this ECE notion of multicalibration. Proof. Fix η := ε. Given the learner’s output QS , apply Proposition 46 to obtain a finitely sup(η) ported predictor QS with (η)

MCPθ (QS ; Gm ) ≤ MCTV Pθ (QS ; Gm ) + η ≤ 2ε ≤ c3

γ . 1 + log2 m

Thus the post-processed learner satisfies the hypothesis of Theorem 14, which gives n ≥ c2 m/γ 2 . e −3 ) reformulation as before. Taking γ ≍ 1/m gives the same Ω(ε

49