mlsanityData to 7 Oct 2026

A One-Inclusion Graph Approach to Multi-Group Learning

arXiv 2603.23208 ↗First posted 24 Mar 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We prove the tightest-known upper bounds on the sample complexity of multi-group learning. Our algorithm extends the one-inclusion graph prediction strategy using a generalization of bipartite b-matching. In the group-realizable setting, we provide a lower bound confirming that our algorithm's log n / n convergence rate is optimal in general. If one relaxes the learning objective such that the group on which we are evaluated is chosen obliviously of the sample, then our algorithm achieves the optimal 1/n convergence rate under group-realizability.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 31 references that are in the map. First posted on arXiv 24 Mar 2026.

Builds on

24 of 31 references.

References · 24

  1. 2018Multiaccuracy: Black-Box Post-Processing for Fairness in Classificationcited by 221
  2. 2020Outcome Indistinguishabilitycited by 74
  3. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  4. 2014Optimal Learners for Multiclass Problemscited by 65
  5. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  6. 2021Multi-group Agnostic PAC Learnabilitycited by 42
  7. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  8. 2022Bagging is an Optimal PAC Learnercited by 34
  9. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  10. 2019Advancing subgroup fairness via sleeping expertscited by 28
  11. 2021Simple and near-optimal algorithms for hidden stratification and multi-group learningcited by 26
  12. 2023Regularization and Optimal Multiclass Learningcited by 15
12 more
  1. 2023Optimal Multi-Distribution Learningcited by 13
  2. 2023Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensionscited by 12
  3. 2023The sample complexity of multi-distribution learningcited by 12
  4. 2022The One-Inclusion Graph Algorithm is not Always Optimalcited by 11
  5. 2022Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classescited by 8
  6. 2024Group-wise oracle-efficient algorithms for online multi-group learningcited by 8
  7. 2024Multi-group Learning for Hierarchical Groupscited by 7
  8. 2023Agnostic Multi-Group Active Learningcited by 6
  9. 2023Oracle Efficient Algorithms for Groupwise Regretcited by 6
  10. 2024Is Transductive Learning Equivalent to PAC Learning?cited by 4
  11. 2026Group-realizable multi-group learning by minimizing empirical riskcited by 2
  12. 2025PAC Learning is just Bipartite Matching (Sort of)cited by 1

Built on by

Not cited yet.