mlsanityData to 14 Oct 2026

Multi-group Agnostic PAC Learnability

arXiv 2105.09989 ↗First posted 20 May 2021cs.LGcited by 44

Not on the map. Why?

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.

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

12 of 28 references.

References · 12

  1. 2016Equality of Opportunity in Supervised Learningcited by 2,007
  2. 2016Fair prediction with disparate impact: A study of bias in recidivism prediction instrumentscited by 672
  3. 2016Inherent Trade-Offs in the Fair Determination of Risk Scorescited by 586
  4. 2017Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairnesscited by 384
  5. 2018Multiaccuracy: Black-Box Post-Processing for Fairness in Classificationcited by 222
  6. 2018Why Is My Classifier Discriminatory?cited by 143
  7. 2020Moment Multicalibration for Uncertainty Estimationcited by 63
  8. 2019Recovering from Biased Data: Can Fairness Constraints Improve Accuracy?cited by 50
  9. 2021Online Multivalid Learning: Means, Moments, and Prediction Intervalscited by 49
  10. 2019Advancing subgroup fairness via sleeping expertscited by 30
  11. 2020Sample Complexity of Uniform Convergence for Multicalibrationcited by 24
  12. 2017Decoupled classifiers for fair and efficient machine learningcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 12; 2023: 9; 2024: 7; 2025: 4; 2026: 8.

44 papers.

Sort:

By area:

  1. 2021Omnipredictorscited by 74
  2. 2022Batch Multivalid Conformal Predictioncited by 67
  3. 2022Loss Minimization through the Lens of Outcome Indistinguishabilitycited by 62
  4. 2022Low-Degree Multicalibrationcited by 45
  5. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  6. 2023Oracle Efficient Online Multicalibration and Omnipredictioncited by 37
  7. 2023A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learningcited by 30
  8. 2021Simple and near-optimal algorithms for hidden stratification and multi-group learningcited by 28
  9. 2021Online Minimax Multiobjective Optimization: Multicalibeating and Other Applicationscited by 27
  10. 2022Why does Throwing Away Data Improve Worst-Group Error?cited by 22
  11. 2022An Algorithmic Framework for Bias Bountiescited by 21
  12. 2024Omnipredictors for Regression and the Approximate Rank of Convex Functionscited by 15
32 more
  1. 2022Omnipredictors for Constrained Optimizationcited by 14
  2. 2024Fair Risk Control: A Generalized Framework for Calibrating Multi-group Fairness Riskscited by 14
  3. 2023Optimal Multi-Distribution Learningcited by 13
  4. 2023The sample complexity of multi-distribution learningcited by 12
  5. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  6. 2024Group-wise oracle-efficient algorithms for online multi-group learningcited by 9
  7. 2022Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classescited by 8
  8. 2023Oracle Efficient Algorithms for Groupwise Regretcited by 8
  9. 2024Multi-group Learning for Hierarchical Groupscited by 8
  10. 2022Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishabilitycited by 7
  11. 2023Agnostic Multi-Group Active Learningcited by 7
  12. 2022Decision-Making under Miscalibrationcited by 5
  13. 2024Derandomizing Multi-Distribution Learningcited by 5
  14. 2025Sample-Efficient Omniprediction for Proper Lossescited by 5
  15. 2022An Exploration of Multicalibration Uniform Convergence Boundscited by 4
  16. 2023Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyondcited by 4
  17. 2025Panprediction: Optimal Predictions for Any Downstream Task and Losscited by 4
  18. 2026Group-realizable multi-group learning by minimizing empirical riskcited by 3
  19. 2021Consider the Alternatives: Navigating Fairness-Accuracy Tradeoffs via Disqualificationcited by 2
  20. 2023Agnostic Multi-Robust Learning Using ERMcited by 2
  21. 2023Group conditional validity via multi-group learningcited by 1
  22. 2024On Calibration in Multi-Distribution Learningcited by 1
  23. 2025Towards Fundamental Limits for Active Multi-distribution Learningcited by 1
  24. 2025Sample-Adaptivity Tradeoff in On-Demand Samplingcited by 1
  25. 2026Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noisecited by 1
  26. 2026The price of multi-group transductive learningcited by 1
  27. 2022Fair Algorithm Design: Fair and Efficacious Machine Schedulingcited by 0
  28. 2026Learning Conditional Averagescited by 0
  29. 2026ShakyPrepend: A Multi-Group Learner with Improved Sample Complexitycited by 0
  30. 2026A One-Inclusion Graph Approach to Multi-Group Learningcited by 0
  31. 2026Groupwise Distortion Guarantees for Preference-Based Alignmentcited by 0
  32. 2026Sample-Optimal Multi-Group Learning with an ERM Oraclecited by 0