Research map / Learning theory and algorithms / Fairness

Accuracy vs. Accuracy: Computational Tradeoffs Between Classification Rates and Utility

NeurIPS 2026 · Learning theory and algorithms › Fairness · approach: Fairness-constrained classification · 0 citations (OpenAlex)

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.

Theoretical study of fairness notions (decision-accuracy, classification-accuracy) under rich labels, showing computational impossibilities against calibration and loss minimization while each notion is individually achievable via multi-accuracy/multi-calibration.

Problem

Whether evidence-based fairness notions requiring accurate subgroup classification rates (relative to the Bayes-optimal predictor) can be simultaneously achieved with calibration and loss minimization when training labels are rich (probabilities, ranks, types) rather than binary.

Approach

Defines decision-accuracy and classification-accuracy relative to the Bayes-optimal predictor under rich labels; shows affine decision rules inherit accuracy from multi-accuracy, while non-affine (loss-minimizing) rules make calibration plus decision-accuracy computationally infeasible via one-way-function indistinguishable subsets.

Key results

• Affine decision rules: multi-accuracy on predictions implies decision-accuracy with error k·alpha/delta + 2·epsilon.
• For Lipschitz rules far from affine, under one-way functions no polynomial-time learner outputs a predictor that is both coordinate-wise calibrated and decision-accurate.
• For any non-trivial loss, an efficient classification-accurate action function has loss larger than either constant classifier (up to a gap of order alpha/8).

Surprising findings

• Calibration and decision-accuracy are computationally incompatible for non-affine rules even for a single group, although both are individually efficiently achievable.
• Classification-accuracy is incompatible with loss minimization even against the constant-action benchmark class.

Limitations

• Results are purely theoretical with no empirical evaluation.
• Impossibility results rely on cryptographic assumptions (one-way functions) or on constructed distributions.
• Positive multi-calibration results require strong canonical multi-calibration that can be expensive.

Experimental setup

Builds on: multi-calibration omnipredictors outcome indistinguishability evidence-consistent rankings

Closest papers by meaning

• Average Individual Fairness: Algorithms, Generalization and Experiments (NeurIPS 2019 · similarity 0.89)
• Desirable Effort Fairness and Optimality Trade-offs in Strategic Learning (ICML 2026 · similarity 0.88)
• Stability and Multigroup Fairness in Ranking with Uncertain Predictions (ICML 2024 · similarity 0.88)
• Utility-Fairness Trade-Offs and How to Find Them (CVPR 2024 · similarity 0.87)
• Arbitrariness and Social Prediction: The Confounding Role of Variance in Fair Classification (AAAI 2024 · similarity 0.87)
• Individual Fairness In Strategic Classification (NeurIPS 2025 · similarity 0.87)