# Multi-group Agnostic PAC Learnability

arXiv: https://arxiv.org/abs/2105.09989 · HTML: https://mlsanity.com/paper/2105.09989/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 20 May 2021.

## Builds on (most cited first, 12 of 12)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Why Is My Classifier Discriminatory?](https://mlsanity.com/paper/1805.12002/) (2018)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [Recovering from Biased Data: Can Fairness Constraints Improve Accuracy?](https://mlsanity.com/paper/1912.01094/) (2019)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Advancing subgroup fairness via sleeping experts](https://mlsanity.com/paper/1909.08375/) (2019)
- [Sample Complexity of Uniform Convergence for Multicalibration](https://mlsanity.com/paper/2005.01757/) (2020)
- [Decoupled classifiers for fair and efficient machine learning](https://mlsanity.com/paper/1707.06613/) (2017)

## Built on by (most cited first, 30 of 44)

- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Batch Multivalid Conformal Prediction](https://mlsanity.com/paper/2209.15145/) (2022)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications](https://mlsanity.com/paper/2108.03837/) (2021)
- [Why does Throwing Away Data Improve Worst-Group Error?](https://mlsanity.com/paper/2205.11672/) (2022)
- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [Omnipredictors for Regression and the Approximate Rank of Convex Functions](https://mlsanity.com/paper/2401.14645/) (2024)
- [Omnipredictors for Constrained Optimization](https://mlsanity.com/paper/2209.07463/) (2022)
- [Fair Risk Control: A Generalized Framework for Calibrating Multi-group Fairness Risks](https://mlsanity.com/paper/2405.02225/) (2024)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Group-wise oracle-efficient algorithms for online multi-group learning](https://mlsanity.com/paper/2406.05287/) (2024)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [Oracle Efficient Algorithms for Groupwise Regret](https://mlsanity.com/paper/2310.04652/) (2023)
- [Multi-group Learning for Hierarchical Groups](https://mlsanity.com/paper/2402.00258/) (2024)
- [Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability](https://mlsanity.com/paper/2203.04536/) (2022)
- [Agnostic Multi-Group Active Learning](https://mlsanity.com/paper/2306.01922/) (2023)
- [Decision-Making under Miscalibration](https://mlsanity.com/paper/2203.09852/) (2022)
- [Derandomizing Multi-Distribution Learning](https://mlsanity.com/paper/2409.17567/) (2024)
- [Sample-Efficient Omniprediction for Proper Losses](https://mlsanity.com/paper/2510.12769/) (2025)
- [An Exploration of Multicalibration Uniform Convergence Bounds](https://mlsanity.com/paper/2202.04530/) (2022)
- [Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2302.09267/) (2023)
- [Panprediction: Optimal Predictions for Any Downstream Task and Loss](https://mlsanity.com/paper/2510.27638/) (2025)
- [Group-realizable multi-group learning by minimizing empirical risk](https://mlsanity.com/paper/2601.16922/) (2026)

## Abstract (arXiv)

An agnostic PAC learning algorithm finds a predictor that is competitive with the best predictor in a benchmark hypothesis class, where competitiveness is measured with respect to a given loss function. However, its predictions might be quite sub-optimal for structured subgroups of individuals, such as protected demographic groups. Motivated by such fairness concerns, we study "multi-group agnostic PAC learnability": fixing a measure of loss, a benchmark class H and a (potentially) rich collection of subgroups G, the objective is to learn a single predictor such that the loss experienced by every group g ∈ G is not much larger than the best possible loss for this group within H. Under natural conditions, we provide a characterization of the loss functions for which such a predictor is guaranteed to exist. For any such loss function we construct a learning algorithm whose sample complexity is logarithmic in the size of the collection G. Our results unify and extend previous positive and negative results from the multi-group fairness literature, which applied for specific loss functions.