How global calibration strengthens multiaccuracy

Conference item

Multiaccuracy and multicalibration are multi-group fairness notions for prediction that have found numerous applications in learning and computational complexity [HKRR18]. They can be achieved from a single learning primitive: weak agnostic learning. A line of work starting from [GKR⁺22] has shown that multicalibration implies a very strong form of 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 [TTV09], [CDV24]. 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.

Authors: Casacuberta, S; Gopalan, P; Kanade, V; Reingold, O

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: IEEE
• Host title: 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS)
• Pages: 1198-1227
• Publication date: 2025-12-12
• Acceptance date: 2025-07-08
• Event title: 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025)
• Event location: Sydney, Australia
• Event website: https://focs.computer.org/2025/
• Event start date: 2025-12-14
• Event end date: 2025-12-17
• DOI: 10.1109/FOCS63196.2025.00063
• EISSN: 2575-8454
• ISSN: 1523-8288
• EISBN: 97-8331571320
• ISBN: 9798331571337
• Language: English
• Keywords: weight measurement; hands; computer science; correlation; density measurement; calibration; computational complexity; standards