Source-linked AI summary
Multigroup Fairness and Omniprediction: Separations and Equivalences
Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold, Konstantinos Stavropoulos, Pranay Tankala
TL;DR
The paper asks whether omniprediction needs multigroup fairness, given that known approaches often use fairness guarantees. It studies omnipredictor closure and loss OI, showing that omniprediction can lack even accuracy in expectation, whereas loss OI is equivalent to calibrated multiaccuracy under a mild loss condition.
Problem
Although prior constructions often derive omniprediction from multigroup fairness, whether standard omniprediction requires such a guarantee remained open.
Source: §1 · p. 2, §1.1 · p. 3Method
The authors use closure of omnipredictors under pointwise movement toward the Bayes-optimal predictor and analyze loss OI using a neutral action.
Source: §1.1 · p. 4Results
Omniprediction can fail even accuracy in expectation, while loss OI is equivalent to calibrated multiaccuracy under a mild neutral-action condition.
Source: §1.1 · pp. 3–4Takeaways & Limitations
Omnipredictors are more plentiful than predictors satisfying loss OI, so approaches through loss OI might sacrifice efficiency.
Source: §1.1 · p. 5The loss OI converse assumes a neutral action, or similarly mild conditions excluding losses whose label-dependence is essentially constant.
Source: §4 · p. 15
Abstract
from arXiv · showhide
Omniprediction is a learning guarantee which requires a single predictor to be competitive relative to the best hypothesis from a benchmark class for any loss chosen from a family of loss functions. Loss Outcome Indistinguishability (loss OI for short) is a stronger notion that implies omniprediction. It requires the predicted distribution on labels to be indistinguishable from the true distribution to tests that depend on the loss functions and the benchmark class. Multiaccuracy and multicalibration are multigroup fairness notions that generalize classical notions of calibration and accuracy in expectation. Most known learning algorithms for omniprediction (both for the standard notion and for strengthenings like loss OI) rely on some version of these multigroup fairness notions, or on an intermediate notion called calibrated multiaccuracy. We ask if this is necessary: Does omniprediction require some form of multigroup fairness? We show that the answer is no for (plain) omniprediction, and yes for loss OI. First, a sequence of works shows that multicalibration or calibrated multiaccuracy imply omniprediction. We rule out even a weak converse, by showing that omniprediction for proper losses does not imply even accuracy in expectation, a much weaker notion than any of calibration, multiaccuracy, or multicalibration. Second, prior work showed how to achieve loss OI from a combination of calibration and multiaccuracy. We show a converse: loss OI is equivalent to a form of calibrated multiaccuracy.
1 Introduction
The paper asks whether omniprediction requires multigroup fairness, after prior work derived omniprediction guarantees from fairness notions. It answers no for omniprediction—even accuracy in expectation can fail—and yes for loss OI, which is equivalent to a form of calibrated multiaccuracy.
1 Introduction
1.1 Results Overview
- Omniprediction can fail even accuracy in expectation, while loss OI is equivalent to a form of calibrated multiaccuracy.The result rules out a weak converse from omniprediction to fairness and proves a converse to prior sufficiency results for loss OI.Source: §1.1 · pp. 3–4
- For any class admitting a strong hard-on-average Boolean function, some omnipredictor has expected accuracy error at least 1/4.The paper extends this separation to proper losses using a recent result [OKK25].Source: §1.1 · pp. 3–4
- Omnipredictors are closed under moving predictions pointwise between an omnipredictor and the Bayes-optimal predictor.This closure lets the authors construct omnipredictors with large expected accuracy error, including when the starting predictor is perfect.Source: §1.1 · p. 4
- For loss OI, a neutral action lets the authors derive decision OI and then hypothesis OI; the condition holds for squared and cross-entropy loss at 1/2.The neutral-action condition can be relaxed under other mild assumptions.Source: §1.1 · p. 5
1.2 Related Work
- Earlier equivalences concerned swap variants, leaving open whether standard omniprediction required a weaker multigroup fairness notion or calibration.The paper also situates its results among work connecting multigroup fairness to learning theory, pseudorandomness, and complexity [CDV24] [CGKR25].Source: §1 · pp. 2–3, §1.2 · p. 6
2 Preliminaries
The preliminaries establish notation for predictors, hypotheses, losses, and simulated labels, then define fairness criteria and proper losses. They also relate expected accuracy and calibration errors to multigroup guarantees.
Preliminaries
- A predictor maps features to label probabilities, while a hypothesis maps features to actions or values in [-1, 1]; the Bayes-optimal predictor is p*(x) = E[y|x].The simulated distribution D(p) draws labels from Ber(p(x)), making p its Bayes-optimal predictor.Source: §2 · p. 6
- Multiaccuracy controls prediction-label correlation over a hypothesis class, while weight-restricted calibration controls calibration errors using functions of the prediction.With the constant function included, either guarantee bounds expected accuracy error; multicalibration bounds expected calibration error, and EAE(p) ≤ ECE(p).Source: §2 · p. 7
- Loss minimization selects an action from a hypothesis class, while omniprediction allows one predictor to support loss minimization across a family of losses.The loss is extended linearly to probabilities, so its expected value matches the loss under a Bernoulli label with that probability.Source: §2 · p. 7
- A proper loss is minimized in expectation by reporting the true Bernoulli probability, and proper losses admit a representation using a concave function and its Bregman divergence.The associated concave function is h(p) = ℓpr(p, p), with derivative or superderivative h′(p) = ℓpr(1, p) − ℓpr(0, p).Source: §2 · pp. 7–8
3 Omniprediction and Accuracy in Expectation
This section shows that omniprediction can coexist with failure of accuracy in expectation, even for proper losses. It establishes a closure property that lets the authors turn predictors into such counterexamples, including under average-case hardness assumptions.
3 Omniprediction and Accuracy in Expectation
- Any predictor between an omnipredictor and the Bayes-optimal predictor remains an omnipredictor.The proof reduces to proper losses and uses their characterization through Bregman divergences of concave functions.Source: §3 · p. 9
- For concave h, the supergradient approximation to h(p∗) decreases, and hence improves, as the prediction moves from q toward p∗, as stated geometrically in the passage.The proof also uses h(q) + (r − q)h′(q) ≥ h(r) and h′(q) ≥ h′(r) when q < r.Source: §3 · p. 10
- If an omnipredictor differs from the Bayes-optimal predictor by at least α in expected absolute deviation, another omnipredictor has accuracy-in-expectation error at least α/2.The proof splits the absolute deviation into its two directional contributions and uses the larger one.Source: §3 · p. 10
- For parity labels and coordinate hypotheses, a perfect omnipredictor has EAE 1/4: its mean prediction is 3/4 while the label mean is 1/2.The constant predictor is multicalibrated; the example's second predictor lies between it and the Bayes-optimal predictor.Source: §3 · pp. 10–11
- Under average-case hardness, the section constructs an O(ε)-omnipredictor for convex, Lipschitz losses, showing that omniprediction need not ensure accuracy in expectation.The construction starts with the constant predictor, which is multicalibrated and hence an omnipredictor, then applies the between-predictor result.Source: §3 · pp. 10–11
- The separation extends to bounded-variation losses, including convex, Lipschitz, and proper losses, using thresholded hypotheses.The cited result yields an O(ε)-omnipredictor for the threshold class Th(C).Source: §3 · p. 12
- The section also concludes that neither calibration nor multiaccuracy is necessary for strong agnostic learning, although together they are sufficient.This consequence follows from the construction by considering the ℓ1 loss.Source: §3 · p. 12
4 Loss OI and Calibrated Multiaccuracy
This section characterizes loss OI as equivalent to calibrated multiaccuracy under mild conditions on the loss and hypothesis class. The result complements the prior direction that calibrated multiaccuracy implies loss OI.
4 Loss OI and Calibrated Multiaccuracy
- Loss OI tests whether loss-based distinguishers can tell real labels from labels sampled as yp|x ∼Ber(p(x)).The distinguisher compares the loss of a benchmark action c(x) with that of the action optimal for predicted probability v.Source: §4 · p. 13
- Prior work showed that decision OI and hypothesis OI together imply loss OI, with decision OI corresponding to weight-restricted calibration and hypothesis OI to multiaccuracy [GHK+23].The section's characterization provides the converse direction.Source: §4 · p. 14
- With a neutral action and all constant action functions in C, loss OI is equivalent to weight-restricted calibration and multiaccuracy, each with error O(α).The calibration weights are ∂ℓ◦kℓ, and the multiaccuracy class is ∂ℓ◦C.Source: §4 · pp. 14–15
- The neutral-action condition excludes losses whose label derivative is constant or nearly constant, including prediction-independent ℓ(y,p)=y and its rescalings or small perturbations.The authors describe the condition as mild and offer alternative range requirements.Source: §4 · pp. 14–15
- Under the theorem's assumptions, loss OI with error α implies decision OI with error α and hypothesis OI with error 2α.The proof uses a neutral action that is also in C.Source: §4 · p. 15