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

Tags
Apple
arxiv id
2505.16494
6 more properties
[Daily Giants on ArXiv]

Abstract Summary

•
The research examines fairness, utility, and efficiency in machine learning scenarios with richer label information than binary outcomes.
•
Proposed algorithms aim to achieve evidence-based fairness in subpopulation classification rates while supporting accurate classification and ranking techniques.
•
The study shows impossibility results regarding simultaneous achievement of accurate classification rates and optimal loss minimization, highlighting the computational challenges of learning a good approximation of the Bayes-optimal predictor.

Abstract

We revisit the foundations of fairness and its interplay with utility and efficiency in settings where the training data contain richer labels, such as individual types, rankings, or risk estimates, rather than just binary outcomes. In this context, we propose algorithms that achieve stronger notions of evidence-based fairness than are possible in standard supervised learning. Our methods support classification and ranking techniques that preserve accurate subpopulation classification rates, as suggested by the underlying data distributions, across a broad class of classification rules and downstream applications. Furthermore, our predictors enable loss minimization, whether aimed at maximizing utility or in the service of fair treatment. Complementing our algorithmic contributions, we present impossibility results demonstrating that simultaneously achieving accurate classification rates and optimal loss minimization is, in some cases, computationally infeasible. Unlike prior impossibility results, our notions are not inherently in conflict and are simultaneously satisfied by the Bayes-optimal predictor. Furthermore, we show that each notion can be satisfied individually via efficient learning. Our separation thus stems from the computational hardness of learning a sufficiently good approximation of the Bayes-optimal predictor. These computational impossibilities present a choice between two natural and attainable notions of accuracy that could both be motivated by fairness.