# A One-Inclusion Graph Approach to Multi-Group Learning

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

## Key facts

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

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

- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Advancing subgroup fairness via sleeping experts](https://mlsanity.com/paper/1909.08375/) (2019)
- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions](https://mlsanity.com/paper/2304.11059/) (2023)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [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)
- [Agnostic Multi-Group Active Learning](https://mlsanity.com/paper/2306.01922/) (2023)
- [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024)
- [Group-realizable multi-group learning by minimizing empirical risk](https://mlsanity.com/paper/2601.16922/) (2026)
- [PAC Learning is just Bipartite Matching (Sort of)](https://mlsanity.com/paper/2502.00607/) (2025)

## 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.