PaperlayerView exact revision on arXiv

Source-linked AI summary

How Global Calibration Strengthens Multiaccuracy

Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold

arXiv:2504.15206v2cs.LGcs.CC

TL;DR

This paper asks how powerful multiaccuracy is as a learning primitive, with and without global calibration. It shows that calibration substantially strengthens multiaccuracy, recovering strong agnostic learning and optimal-density hardcore constructions.

  • Problem

    The paper investigates whether multiaccuracy alone is as powerful as weak agnostic learning and how calibration changes its implications.

  • Method

    The paper analyzes multiaccuracy with global calibration and uses weighted multiaccuracy to construct hardcore measures.

  • Results

    Multiaccuracy alone yields only restricted weak agnostic learning, whereas calibrated multiaccuracy yields strong agnostic learning and optimal-density hardcore measures.

  • Takeaways & Limitations

    Calibration and multiaccuracy play complementary roles, together producing stronger guarantees than either notion alone.

  • Takeaways & Limitations

    Calibrated multiaccuracy does not provide the stronger IHCL++ theorem, which appears to require full multicalibration.

Abstract

from arXiv · show

Multiaccuracy and multicalibration are multigroup fairness notions for prediction that have found numerous applications in learning and computational complexity. They can be achieved from a single learning primitive: weak agnostic learning. Here we investigate the power of multiaccuracy as a learning primitive, both with and without the additional assumption of calibration. We find that multiaccuracy in itself is rather weak, but that the addition of global calibration (this notion is called calibrated multiaccuracy) boosts its power substantially, enough to recover implications that were previously known only assuming the stronger notion of multicalibration. We give evidence that multiaccuracy might not be as powerful as standard weak agnostic learning, by showing that there is no way to post-process a multiaccurate predictor to get a weak learner, even assuming the best hypothesis has correlation $1/2$. Rather, we show that it yields a restricted form of weak agnostic learning, which requires some concept in the class to have correlation greater than $1/2$ with the labels. However, by also requiring the predictor to be calibrated, we recover not just weak, but strong agnostic learning. A similar picture emerges when we consider the derivation of hardcore measures from predictors satisfying multigroup fairness notions. On the one hand, while multiaccuracy only yields hardcore measures of density half the optimal, we show that (a weighted version of) calibrated multiaccuracy achieves optimal density. Our results yield new insights into the complementary roles played by multiaccuracy and calibration in each setting. They shed light on why multiaccuracy and global calibration, although not particularly powerful by themselves, together yield considerably stronger notions.

1 Introduction

The paper examines how far multiaccuracy alone supports learning and hardcore-set constructions, and how global calibration changes its power. It shows that calibrated multiaccuracy recovers strong guarantees at lower cost than full multicalibration.

  • Computational learning: Multiaccuracy alone does not imply standard weak agnostic learning: even with a hypothesis of correlation 1/2, no post-processing may achieve nonzero correlation.This lower bound holds for classes fooled by suitable pseudorandom functions.
  • Computational learning: If some hypothesis has correlation α > 1/2, sign(p−1/2) from a multiaccurate predictor achieves correlation β = 2α−1.This restricted guarantee is nontrivial only when α exceeds 1/2, unlike standard weak agnostic learning.
  • Computational learning: Adding calibration makes sign(p −1/2) a strong agnostic learner whose correlation is at least that of the best hypothesis in C.Thus, calibration materially increases the predictive power available from multiaccuracy.
  • Hardcore set constructions: For hardcore measures, calibrated weighted multiaccuracy achieves optimal density 2δ with q = O(1/(ε2δ2)), matching the lower complexity bound associated with multiaccuracy.Weighted multiaccuracy emphasizes predictions near 1/2, where the target function is hardest for the class to predict.
  • The three tiers of multigroup fairness: The paper positions calibrated multiaccuracy as a middle tier: cheaper than multicalibration, stronger than multiaccuracy, but insufficient for IHCL++ or swap agnostic learning.Multiaccuracy remains attractive because it is comparatively cheap and can arise from squared-loss minimization or GLMs.
  • The case for calibrated multiaccuracy: Calibrated multiaccuracy combines global calibration with multiaccuracy to recover strong agnostic learning and optimal-density hardcore constructions.The paper presents this combination as substantially cheaper than full multicalibration while retaining important consequences.

2 Overview of our Results

The paper maps when multiaccuracy supports agnostic learning and hardcore measures, showing that calibration supplies the missing strength while weighted multiaccuracy supplies the hardcore property.

  • Agnostic Learning and Multiaccuracy: A multiaccurate predictor can fail to yield any post-processed learner, even when a concept has correlation 1/2; cryptographic constructions extend this failure to classes fooled by pseudorandom functions.The construction makes p∗−p essentially pseudorandom, preserving multiaccuracy while preventing useful correlation.
  • Agnostic Learning and Multiaccuracy: A C-multiaccurate predictor alone yields restricted weak agnostic learning: if the best concept has correlation α, post-processing achieves correlation 2α−1, useful only when α > 1/2.In the realizable case α = 1, the resulting correlation is 1.
  • Agnostic Learning and Multiaccuracy: Adding calibration to multiaccuracy yields strong agnostic learning, because calibration alone fails only when predictions remain at the uninformative value 1/2, while multiaccuracy prevents that when a concept correlates with labels.Theorem 4.7 uses both properties to show that sign(2p−1) is a strong agnostic learner.
  • Hardcore Sets of Optimal Density: Optimal density 2δ is achieved under (Cq, δ)-hardness with q = O(1/(ε2δ2)), matching [CDV24]'s density while retaining 's lower complexity bound.The construction starts from calibration and weighted multiaccuracy, both implied by multicalibration.
  • Hardcore Sets of Optimal Density: Calibration ensures optimal hardcore-measure density, while weighted multiaccuracy ensures the resulting measure is hardcore.The paper separates these complementary roles explicitly.
  • Multiaccuracy and Restricted Weak Agnostic Learning: Under cryptographic assumptions, weak agnostic-learning parameters cannot generally be boosted, and an (α, β) learner cannot in general yield multiaccuracy error below α/2−ε.These negative results establish limits on reversing or strengthening the learning reductions.

3 Notation & Preliminaries

The paper formalizes correlation-based weak and strong agnostic learning, then connects weak learning to squared-loss improvement over random guessing. It also defines calibration, multiaccuracy, and multicalibration as predictor properties over groups.

  • A predictor p estimates the probability of label y=1, while the Bayes predictor p*(x)=E[y|x] represents ground truth.
  • Correlation is defined as E[(2y−1)c(x)], with predictions converted from [0,1] to [−1,1] using 2p−1.
  • An (α,β)-weak agnostic learner returns correlation at least β whenever some hypothesis in C has correlation at least α.
  • Strong agnostic learning achieves error arbitrarily close to the best hypothesis and therefore yields weak learning guarantees for every α above the target tolerance.
  • Weak learning is equivalent to obtaining a predictor with squared loss better than random guessing, and conversely such a predictor gives a weak learner.
  • Calibration requires E[y|p(x)]=p(x), while multiaccuracy requires average prediction accuracy within every group c in C; calibrated multiaccuracy combines both.

4 From Multiaccuracy to Agnostic Learning

Multiaccuracy alone cannot generally be post-processed into standard weak agnostic learning, although it supports a restricted guarantee when the best correlation exceeds 1/2. Adding calibration upgrades the predictor to strong agnostic learning.

  • Multiaccuracy and Weak Agnostic Learning: A multiaccurate predictor can fail to yield any weak learner after post-processing, even when a class hypothesis has correlation 1/2.
  • Multiaccuracy and Weak Agnostic Learning: The lower-bound construction is maximally anti-calibrated, with labels conditionally uninformative at every prediction value.
  • Multiaccuracy and Weak Agnostic Learning: Under pseudorandom-function assumptions, this impossibility extends broadly: no post-processing of a multiaccurate predictor achieves correlation better than τ when a class member has correlation above τ.
  • Restricted Weak Agnostic Learning: Multiaccuracy does yield restricted weak learning: sign(2p−1) obtains correlation 2α−1−2τ when the best class correlation is α.
  • Strong Agnostic Learning from Calibrated Multiaccuracy: If p is both τ-multiaccurate and τ-calibrated, sign(2p−1) becomes a strong agnostic learner for C.
  • Strong Agnostic Learning from Calibrated Multiaccuracy: Calibration prevents predictions from remaining near 1/2 when C contains a hypothesis correlated with labels, while multiaccuracy supplies the groupwise correlation control.

5 Hardcore Measures with Optimal Density

The hardcore-measure analysis uses weighted multiaccuracy and calibration to compare two measures, µTTV and µMax. Calibrated multiaccuracy yields the optimal hardcore density, whereas simpler constructions can lose a factor of two.

  • Balanced Under Calibration Measures: µMax weights prediction level sets near 1/2 more heavily, targeting regions where the Boolean function is hardest for C to predict.
  • Weighted Multiaccuracy: Weighted multiaccuracy controls the product of hardness correlation and measure density, enabling hardness guarantees under the induced distribution.
  • Density Comparisons: Every measure in M(p,g), including µTTV, has density at least δ, while calibration gives E[2p(x)(1−p(x))] between δ and 2δ.
  • Optimal Hardcore Density: Theorem 5.13 gives µMax density 2δ−τ and hardness 1/2−ε when p is weighted-multiaccurate and calibrated under the stated parameters.
  • Optimal Hardcore Density: The resulting IHCL construction achieves optimal hardcore density 2δ using calibrated multiaccuracy to control the relevant oracle complexity.
  • Density Comparisons: In the two-level example, µMax is nearly twice as dense as µTTV when η is much smaller than δ.

6 Restricted Weak Agnostic Learning and Multiacccuracy

This section shows that weak agnostic learning is more powerful than multiaccuracy in some regimes, while multiaccuracy supports restricted learning only when a hypothesis already has correlation above 1/2. Cryptographic constructions establish separations between learning at correlations α and α+ε and limit what multiaccuracy can yield.

  • Theorem 6.1 converts an (α, β)-weak agnostic learner into a (C, α + ε)-multiaccurate predictor using O(1/β^2) oracle calls.The reduction underlies the comparison between weak learning and multiaccuracy.
  • For every α, classes exist that are polynomial-time learnable when correlation is α+ε but hard to learn when correlation is bounded by α, even with stronger access in the hard case.The efficient learner is proper and sample-based, whereas the hard case permits membership queries and improper learning.
  • Under pseudorandom-function assumptions and high-error list-decodable codes, no efficient algorithm can generally produce a predictor with multiaccuracy better than α/2−ε from an (α, β)-weak learner.The construction uses Reed-Solomon concatenated with Hadamard codes and translates decoding hardness into computational learning gaps.

7 Conclusion and Future Work

The conclusion identifies calibrated multiaccuracy as powerful for agnostic learning and optimal hardcore-set constructions, while leaving several reduction and generalization questions open. The authors specifically highlight unresolved gaps in converting weak learners or multiaccurate predictors into stronger learning guarantees.

  • The paper concludes that multiaccuracy combined with global calibration has implications for agnostic learning and optimal hardcore-set constructions.
  • Theorem 6.5 leaves a gap between the (C, α/2)-multiaccuracy lower bound and the (C, α)-multiaccuracy construction from an (α, β)-weak learner.
  • It remains open whether more general reductions, including repeated oracle access or access to input points, can turn multiaccuracy into weak agnostic learning.Appendix A shows that richer post-processing using points x can yield agnostic learners in some cases.
  • The authors also ask whether complexity-theoretic consequences associated with multicalibration, such as dense-model and XOR results, can be obtained under weaker assumptions.

A Projecting Multiaccurate Predictors onto the Span of C

This appendix analyzes multiaccuracy geometrically by projecting predictors onto the span of the concept class. It shows that suitable sparse projections can produce weak learners, but range and approximation-error constraints limit the generality of this approach.

  • Multiaccuracy constrains the predictor’s agreement with labels over span(C), even though the predictor itself can have zero correlation with the labels.The appendix formalizes this using the Bayes predictor and orthogonal decompositions relative to span(C).
  • The projection approach requires care because the span component may be unbounded, and approximate multiaccuracy errors can accumulate across its representation in C.
  • Clipping the projected function to [−1,1] preserves the relevant squared-error guarantee and yields a correlation guarantee for the resulting hypothesis.
  • A suitable projection of a multiaccurate predictor onto span(C), especially an ℓ1-sparse projection, can suffice for weak agnostic learning.
  • Conversely, a proper weak learner that finds a concept correlated with the predictor can construct a projection decreasing squared error by at least α^2.

A.1 Multiaccuracy as a Query Oracle

This appendix treats a multiaccurate predictor as a query oracle and shows that predictor access can replace target-function queries for certain agnostic learning procedures. The resulting reduction also connects efficient multiaccuracy to the hardness of learning parities with noise.

  • If C is properly agnostically learnable with target-function queries, a (C, τ)-multiaccurate predictor can replace those queries while increasing accuracy error by at most 3τ.The reduction assumes the constant-one function belongs to C.
  • The procedure simulates target queries by drawing an independent Bernoulli variable with parameter p(x) from the multiaccurate predictor.
  • Goldreich–Levin query access identifies heavy Fourier coefficients, providing the projections needed for proper agnostic learning of parities.
  • For parity classes under the uniform marginal, finding a predictor with τ ≤ 0.1 multiaccuracy is at least as hard as properly agnostically learning with random classification noise at rate 0.1.
Loading 2504.15206v2…