Research map / Learning theory and algorithms / Prediction and decision losses

Multigroup Fairness and Omniprediction: Separations and Equivalences

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Losses for decision-making

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows omniprediction (for proper/convex-Lipschitz losses) does not require accuracy in expectation, while loss outcome indistinguishability is equivalent to calibrated multiaccuracy under a neutral-action assumption.

Problem

Whether omniprediction, and its stronger variant loss outcome indistinguishability (loss OI), require multigroup fairness notions such as multiaccuracy, multicalibration, or calibration.

Approach

Omnipredictors are closed under moving pointwise toward the Bayes-optimal predictor, so starting from a perfect omnipredictor built from a hard-on-average Boolean function, one obtains an omnipredictor violating accuracy in expectation (EAE >= 1/4). Conversely, for losses with a neutral action, loss OI implies decision OI (calibration-type) and hypothesis OI (multiaccuracy-type), so loss OI is equ

Key results

• Theorem: under a strong hard-on-average Boolean function for C, there is a predictor that is an (L, C, O(eps))-omnipredictor for all convex Lipschitz losses yet has expected accuracy error EAE >= 1/4.
• Loss OI with a neutral-action loss and A subset of C implies decision OI (alpha) and hypothesis OI (2alpha), so loss OI is equivalent to calibrated multiaccuracy (up to O(alpha)).

Surprising findings

• Omnipredictors need not be accurate in expectation, even though accuracy in expectation is implied by calibration, multiaccuracy, and multicalibration.
• Perfect omnipredictors (epsilon=0) can violate accuracy in expectation, so the separation holds even without approximation error.

Limitations

• The omnipredictor separation requires a strong hard-on-average Boolean function for C, an unproven complexity-theoretic assumption for efficient constructions.
• The loss OI equivalence requires a neutral action (or similar mild condition) in the loss and A subset of C.
• The results do not address the computational efficiency of learning omnipredictors.

Experimental setup

Builds on: omniprediction (GKR+22) loss outcome indistinguishability multicalibration (HKRR18) calibrated multiaccuracy decision and hypothesis OI

Closest papers by meaning

• On the Burden of Achieving Fairness in Conformal Prediction (NeurIPS 2026 · similarity 0.87)
• Improved Bounds for Swap Multicalibration and Swap Omniprediction (NeurIPS 2025 · similarity 0.87)
• Multiaccuracy and Multicalibration via Proxy Groups (ICML 2025 · similarity 0.86)
• Metric-Agnostic Continual Learning for Sustainable Group Fairness (AAAI 2025 · similarity 0.86)
• Multigroup Robustness (ICML 2024 · similarity 0.85)
• FRAPPÉ: A Group Fairness Framework for Post-Processing Everything (ICML 2024 · similarity 0.85)