Complexity-Theoretic Implications of Multicalibration

1.1 Multicalibration in algorithmic fairness

• Multicalibration requires calibrated predictions simultaneously on every potentially intersecting subgroup in a prespecified family, extending group fairness to intersections of demographic categories [Héb+18].Low-complexity multicalibrated predictors exist when calibration is required only on sufficiently large level sets.Source: §1.1 · p. 3

1.2 The Complexity-Theoretic Regularity Lemma

• The Regularity Lemma [TTV09] equates multiaccuracy with indistinguishability: an arbitrary function can be simulated by a low-complexity oracle circuit that the test family cannot distinguish.In typical applications, polynomial-size tests and inverse-polynomial error yield a polynomial-size simulator; the paper focuses on evaluating it with oracle access rather than learning it from samples.Source: §1.2 · p. 4

1.3 Multicalibrated partitions

• The multicalibration theorem represents predictions as a low-complexity partition, and on each sufficiently large piece g is indistinguishable from a constant-Bernoulli function with parameter v_P.Pieces below mass γ occupy at most O(γ/ϵ) total mass, while the constant-Bernoulli condition supplies the stronger indistinguishability used in later proofs.Source: §1.3 · p. 5

1.4 Our contributions

• IHCL++ gives every sufficiently large partition piece a local hardcore set of size at least 2b_P|P| for arbitrary g, with hardness 1/2−ϵ_P.Here b_P=min{E[g],1−E[g]} measures balance on the piece; gluing pieces recovers optimal global density 2δ under the original hardness assumption [Imp95; Hol05].Source: §1.4 · pp. 6–7
• PAME++ states that on every sufficiently large piece, conditional PAME equals the conditional min-entropy H∞(B_P), extending the original characterization [VZ12; Zhe14].The result assumes ℓ=O(log log n) because multiclass multicalibration has doubly-exponential dependence on ℓ; it applies in the nonuniform setting.Source: §1.4 · pp. 8–9
• DMT++ constructs a low-complexity partition whose sufficiently large pieces make the uniform distribution on P∩V indistinguishable from P∩S, strengthening the Dense Model Theorem [GT08; TZ08; Rei+08].When S is pseudodense, an appropriate convex combination of balanced piecewise models yields a truly dense distribution indistinguishable from S.Source: §1.4 · p. 9
• Theorem 5.3 is proved by applying the Multicalibration Theorem to the characteristic function of S under a distribution mixing uniform samples from S and V.Source: §1.4 · p. 9

1.5 Common themes

• Multicalibration reproduces IHCL, PAME, and DMT locally on low-complexity partition pieces, removes their hardness assumptions, and relates each piece’s density guarantee to its balance.The resulting theorems apply respectively to arbitrary functions, conditional distributions, and sets; under the original assumptions, piecewise objects can be stitched together to recover the original conclusions.Source: §1.5 · p. 10

1.6 Proof techniques

• Indistinguishability from a constant-Bernoulli function yields a hardcore set of density 2b, an indistinguishable Bernoulli distribution, and indistinguishable uniform distributions on the function’s two level sets.These three consequences respectively support the local hardcore-set, high-min-entropy-distribution, and dense-model constructions.Source: §1.6 · p. 11

1.7 Organization of the paper

• The paper introduces definitions and multicalibration in Section 2, develops IHCL++, PAME, and Dense Model results in Sections 3–5, and concludes with future-work directions in Section 6.A preliminary expository version appears in an author’s thesis, with relevant content differences.Source: §1.7 · p. 11

2 Notation and Preliminaries

• Multiaccuracy is exactly indistinguishability from g with respect to F, while multicalibration strengthens this condition on every predictor level set.Approximate multicalibration ignores pieces smaller than γ and aims to use O(1/ϵ) pieces rather than the trivial O(1/γ) bound.Source: §2 · pp. 12–13
• The multicalibration theorem guarantees an approximately multicalibrated partition that is low-complexity relative to the distinguisher class F.The partition is represented through a low-complexity membership function, enabling efficient identification of each piece.Source: §2 · p. 14

2.1 Hardness and indistinguishability notions

• The paper recasts each sufficiently large multicalibrated piece P as a region where g is indistinguishable from the constant value vP.Here vP is the conditional expectation of g on P, and the balance bP = min{vP, 1−vP} measures how balanced g is there.Source: §2 · p. 12, §2.1 · p. 14, §2.2 · p. 16
• Yao’s lemma identifies indistinguishability from the constant 1/2 function with strong unpredictability: g is (Frand, 1/2 −2ϵ)-hard.This equivalence is the special balanced case that motivates extending hardness and pseudorandomness arguments to arbitrary constant-Bernoulli values.Source: §2.1 · p. 15

2.2 Characterizations of constant-Bernoulli functions

• If F is closed under negation and contains 0 and 1, and g is (F, ϵ)-indistinguishable from constant v, then b = min{v, 1−v} and Boolean g admits a distribution of density 2b where it is hard.The cited argument concludes that g is (Frand, 1/2 − ϵ′/2)-hard on µ.Source: §2.2 · pp. 16, 18
• These characterizations support the paper’s later extensions: statement (4) yields hardcore sets, statement (1) yields PAME, and statement (3) yields dense models.For dense models, indistinguishability of the conditional distributions on g’s Boolean level sets transfers to the relevant intersections of sets with each partition piece.Source: §2.2 · p. 16
• The implications are not fully reversible: statements (1) and (3) imply constant-Bernoulli indistinguishability, whereas statements (2) and (4) are strictly weaker.A counterexample uses a random function with conditional bias depending on the first input bit, showing hardness without indistinguishability from its mean against small circuits.Source: §2.2 · p. 18
• Statement (4) is weaker than Lemma 2.17’s assumption because statement (2) implies (4) by IHCL.Statement (2) corresponds to IHCL’s assumption, while statement (4) corresponds to its conclusion.Source: §2.2 · p. 18
• The implication from statement (2) to statement (4) follows from IHCL.The passage identifies statement (2) with IHCL’s assumption and statement (4) with its conclusion.Source: §2.2 · p. 18
• Statement (4) alone does not imply that g is a constant-Bernoulli function.Source: §2.2 · p. 18

3.1 The original IHCL statement

• The original IHCL converts weak hardness on D into strong hardness on a 2δ-dense distribution, with indistinguishability against a smaller distinguisher class.The density and indistinguishability guarantees are distinct components of the theorem.Source: §3.1 · p. 19

3.2 The IHCL++ Theorem

• IHCL++ removes the weak-hardness assumption: every function obtains strong hardness on each sufficiently large partition piece, with density 2bP determined by its balance.The partition has t = O(1/(ϵ^4γ) · log(|X|/ϵ)), q = O(1/ϵ^2), and k = O(1/ϵ); indistinguishability worsens as bP approaches 0 or 1/2.Source: §3.2 · p. 20
• Multicalibration enables the optimal 2bP density because each partition piece uses its constant conditional mean, unlike the multiaccuracy-based analysis of.The proof constructs a local distribution HP on each sufficiently large P and relates hardness to multicalibration through a Yao-style argument.Source: §3.2 · p. 21

3.3 Recovering IHCL from IHCL++

• IHCL++ recovers the original theorem by gluing local hardcore distributions over good pieces; under weak hardness, the resulting global distribution has density at least 2δ and strong hardness.The construction keeps only pieces with sufficient size and balance, then adjusts density by O(ϵ) while preserving strong hardness up to O(ϵ).Source: §3.3 · pp. 21–23

3.4 Set version of IHCL++

• The set version converts hardcore distributions into hardcore sets for uniform D, requiring an upper bound on |F| and yielding each HP with relative density at least 2bP.The theorem applies on pieces satisfying ηP ≥ γ and |F| ≤ exp(|X|(ϵ/4)^2bP^2).Source: §3.4 · p. 24

3.5 Previous instances of partitioning in the Regularity Lemma literature

• Compared with, IHCL++ replaces exponential-complexity partitions with polynomial complexity and removes the requirement that g be δ-hard.The improvement follows from the polynomial complexity of the Multicalibration Theorem; the second assumption is replaced by a balance threshold.Source: §3.5 · pp. 24–25

4.1 Definitions

• Pseudo-min-entropy and PAME computationally generalize min-entropy and average min-entropy by requiring indistinguishability from a high-entropy distribution [Hås+99; Zhe14].The section works in the non-uniform setting with Boolean circuits, while noting extensions to the uniform setting.Source: §4 · p. 25, §4.1 · pp. 25–26

4.2 The PAME Theorem

• The PAME theorem equates conditional pseudo-average min-entropy with computational unpredictability: hardness implies PAME, while PAME implies nonuniform hardness.The forward direction requires t = q = L · poly(n, log L, 1/ϵ), whereas the reverse direction uses t = q = O(1) and loses ϵ in the hardness parameter.Source: §4.2 · pp. 26–27

4.3 Multiclass multicalibration

• Multiclass approximate multicalibration constructs efficiently representable partitions, but its complexity parameters grow exponentially with the number of classes L.The multiclass theorem uses a branching-program algorithm whose parameters differ from the real-valued multicalibration theorem [Gop+22a; Héb+18].Source: §4.3 · pp. 27–28

4.5 Recovering the original PAME from PAME++

• PAME++ provides both local and global pseudo-average min-entropy, and gluing the piecewise distributions recovers the original PAME theorem.The recovery is restricted to L = O(log n), rather than the original L = O(n), because multiclass multicalibration has exponential dependence on L.Source: §4.4 · p. 28, §4.5 · p. 31
• PAME++ implies the PAME theorem with L = O(log n), after modifying the constructed distribution to achieve PAME at least log(1/(1 −δ)) while increasing indistinguishability by at most O(ϵ).The construction first establishes the required entropy lower bound and (F, ϵ)-indistinguishability, then applies the PAME definition.Source: §4.5 · p. 32

4.6 Relationship between IHCL and the PAME Theorem

• IHCL yields PAME by replacing a δ-hard function with a uniform random bit on a hardcore set, giving average min-entropy at least log(1/(1 −δ)) while preserving (F, ϵ)-indistinguishability.This construction uses the fact that hardcore sets imply indistinguishability from a random bit, which has maximal min-entropy.Source: §4.6 · p. 32
• IHCL++ similarly gives PAME++ by applying hardcore sets within a low-complexity partition, but the set-version proof requires an upper bound on |F|; the distribution version removes this limitation.For each sufficiently dense partition piece P, the construction obtains PAME at least log(1/(1 −bP)) with indistinguishability parameter ϵ/bP, then uses Bernoulli sampling from a hardcore distribution instead of probabilistically constructed sets.Source: §4.6 · pp. 32–33

5.1 Definitions

• Pseudodensity relaxes density by requiring distinguishers to perceive S as sufficiently dense, and the original DMT converts this assumption into a dense distribution indistinguishable from S.The theorem obtains a (δ − O(ϵ))-dense model that is (F, O(ϵ/δ))-indistinguishable from S.Source: §5.1 · p. 34

5.2 The DMT++ Theorem

• DMT++ partitions S ∪ V so every sufficiently large piece has distributions S_P and V_P that are indistinguishable to F, without assuming S is pseudodense.The partition has t = O(1/(ϵ^4γ) · log(|X|/ϵ)), q = O(1/ϵ^2), and k = O(1/ϵ).Source: §5.2 · pp. 34–35
• DMT++ generalizes DMT by assigning each partition piece its own density parameter δ_P = Pr_{x∼D}[x ∈ P] and providing local models that can be glued into a global model.Under the original pseudodensity assumption, gluing the local models yields global density O(δ − O(ϵ)).Source: §5.2 · p. 35
• On each sufficiently large piece, indistinguishability follows from multicalibration because the indicator function of S is indistinguishable from a constant-Bernoulli function.The resulting error is ϵ_P = ϵ v_P(1 − v_P), so balance of S on the piece controls the guarantee.Source: §5.2 · pp. 35–36

5.3 Recovering the original DMT from DMT++

• To recover DMT, the proof augments the domain, selects (γ, τ)-good pieces, and defines a weighted average of their local V-models as the global distribution μ.The weighting first selects pieces according to their S′ mass and then samples from V′|P.Source: §5.3 · pp. 37–38
• The glued distribution has density δ · (1 − O(ϵ)), can be adjusted to density δ − O(ϵ), and remains O(ϵ/δ)-indistinguishable from S, recovering the original DMT.The final adjustment preserves the indistinguishability guarantee.Source: §5.3 · p. 38
• The DMT and DMT++ results also admit an entropy interpretation through the relationship between pseudodensity and pseudo-min-entropy.A δ-dense distribution in an ϵ-pseudorandom set has ϵ-pseudo-min-entropy log |X| − log(1/δ) [Rei+08, Propositions 4.2, 4.3].Source: §5.3 · p. 39

Further generalizations of our results

• The PAME++ generalization remains limited to non-uniform distinguishers and ℓ = O(log log n), whereas the original PAME theorem covers uniform distinguishers and ℓ = O(log n).The authors identify recovering the original parameters as an open direction.Source: §6 · p. 39

Future multicalibration algorithms

• Two proposed routes to better PAME++ parameters are improving multiclass multicalibration complexity or obtaining the conclusion from a weaker multicalibration notion with polynomial class dependence.The authors frame both as future algorithmic directions.Source: §6 · p. 39
• The paper’s partition complexity parameters inherit the state-of-the-art multicalibration parameters because the approximate MC theorems are used as black boxes.Improvements to multicalibration algorithms would therefore apply directly to the paper’s results.Source: §6 · p. 39

Other possible applications of our ++ approach

• The framework may yield new insights for other Regularity Lemma applications, including leakage-resilient cryptography, weak zero-knowledge, Yao’s XOR Theorem, entropy chain rules, and Chang’s inequality.The authors expect their multicalibration partition perspective to clarify these established results and expose further connections.Source: §6 · pp. 39–40

Multicalibration on average

• The construction starts from multicalibration on average, which avoids a minimum level-set-size parameter by requiring calibration averaged over predictor level sets.This enables level-set complexity independent of γ.Source: A Multicalibrated Partitions · p. 45

Efficient realization

• The appendix also notes that approximate MCoA is efficiently realizable and that the MC theorem’s proof can be implemented with finite-precision arithmetic and projection operations.These operations are accounted for in the circuit implementation discussion.Source: A Multicalibrated Partitions · pp. 46–47

Discretization and rounding

• Rounding an MCoA predictor to a λ-discretization changes every prediction by at most λ/2 and increases its error parameter by at most λ/2.The rounded predictor has O(1/λ) level sets.Source: A Multicalibrated Partitions · p. 46

Approximate MC construction

• Choosing λ = ϵ/2 converts the rounded MCoA predictor into an approximate MC predictor with O(1/ϵ) level sets.The construction merges predictor values onto the discretization grid.Source: A Multicalibrated Partitions · p. 47

Multicalibrated partitions

• The Multicalibration Theorem then induces a partition from the predictor’s level sets, with t = O(1/(ϵ^4γ) · log(|X|/ϵ)) and q = O(1/ϵ^2).The partition has k = O(1/ϵ) pieces or level sets.Source: A Multicalibrated Partitions · pp. 45, 47

From distributions to sets

• A hardcore distribution of density at least δ yields a hardcore set H of size at least δ|X| under the stated domain, family-size, and parameter assumptions.The resulting set is (F, 4ϵ)-hardcore for g.Source: B From Hardcore Distributions to… · p. 47

Randomized set construction

• The proof includes each x ∈ X in H independently with probability μ(x), producing a randomized characteristic function χ_H.This construction is non-constructive but sufficient to establish existence.Source: B From Hardcore Distributions to… · p. 47

Concentration analysis

• Hoeffding’s inequality and a union bound control the correlation with every f ∈ F simultaneously, with failure probability below 1/10 under the family-size assumption.The sampled set also satisfies a density lower bound with high probability.Source: B From Hardcore Distributions to… · p. 48
• A second concentration argument establishes that |H| is sufficiently large, using d(μ) ≥ δ and δ ≥ 1/|X|^1/2.Combining the correlation and size events yields one set satisfying both guarantees.Source: B From Hardcore Distributions to… · pp. 48–49

• Theorem 3.2 is generalized to arbitrary g, removing the assumption that g is δ-hard while retaining a partition of complexity exp(poly(1/ϵ, 1/τ)).Source: C Generalizing the IHCL Statement from… · p. 49
• If Condition (1) fails, a distinguisher computes g correctly on more than a 1 − τ fraction of inputs.Source: C Generalizing the IHCL Statement from… · p. 49
• Condition (2) can hold only when the union of minority subsets has measure at least τ, contradicting Condition (1).Source: C Generalizing the IHCL Statement from… · p. 49
• Condition (1) corresponds to excluding partition pieces with very small balance or size parameters, since under the uniform distribution it implies b_P · η_P ≤ τ for every piece.Source: C Generalizing the IHCL Statement from… · p. 49
• Assuming instead that g is (F, δ)-weakly hard with δ > τ forces the minority subsets to cover at least δ · |X|, so Condition (1) fails and the theorem yields a hardcore distribution D_min.Source: C Generalizing the IHCL Statement from… · p. 49