# Group-realizable multi-group learning by minimizing empirical risk

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 32 references that are in the map.
- First posted on arXiv 23 Jan 2026.

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

- [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)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Near-Optimal Algorithms for Omniprediction](https://mlsanity.com/paper/2501.17205/) (2025)
- [Advancing subgroup fairness via sleeping experts](https://mlsanity.com/paper/1909.08375/) (2019)
- [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)
- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [Group-wise oracle-efficient algorithms for online multi-group learning](https://mlsanity.com/paper/2406.05287/) (2024)
- [Multi-group Learning for Hierarchical Groups](https://mlsanity.com/paper/2402.00258/) (2024)
- [Adaptive Oracle-Efficient Online Learning](https://mlsanity.com/paper/2210.09385/) (2022)
- [Agnostic Multi-Group Active Learning](https://mlsanity.com/paper/2306.01922/) (2023)

## Built on by (most cited first, 3 of 3)

- [The price of multi-group transductive learning](https://mlsanity.com/paper/2606.04423/) (2026)
- [A One-Inclusion Graph Approach to Multi-Group Learning](https://mlsanity.com/paper/2603.23208/) (2026)
- [Sample-Optimal Multi-Group Learning with an ERM Oracle](https://mlsanity.com/paper/2610.15916/) (2026)

## Abstract (arXiv)

The sample complexity of multi-group learning is shown to improve in the group-realizable setting over the agnostic setting, even when the family of groups is infinite so long as it has finite VC dimension. The improved sample complexity is obtained by empirical risk minimization over the class of group-realizable concepts, which itself could have infinite VC dimension. Implementing this approach is also shown to be computationally intractable, and an alternative approach is suggested based on improper learning.