mlsanityData to 7 Oct 2026

Group-realizable multi-group learning by minimizing empirical risk

arXiv 2601.16922 ↗First posted 23 Jan 2026cs.LG stat.MLcited by 2

Not on the map. Why?

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.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 15 of its 32 references that are in the map. First posted on arXiv 23 Jan 2026.

Builds on

15 of 32 references.

References · 15

  1. 2017Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairnesscited by 381
  2. 2018Multiaccuracy: Black-Box Post-Processing for Fairness in Classificationcited by 221
  3. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  4. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  5. 2021Multi-group Agnostic PAC Learnabilitycited by 42
  6. 2023Oracle Efficient Online Multicalibration and Omnipredictioncited by 36
  7. 2025Near-Optimal Algorithms for Omnipredictioncited by 33
  8. 2023A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learningcited by 29
  9. 2019Advancing subgroup fairness via sleeping expertscited by 28
  10. 2021Simple and near-optimal algorithms for hidden stratification and multi-group learningcited by 26
  11. 2022An Algorithmic Framework for Bias Bountiescited by 19
  12. 2024Group-wise oracle-efficient algorithms for online multi-group learningcited by 8
3 more
  1. 2022Adaptive Oracle-Efficient Online Learningcited by 7
  2. 2024Multi-group Learning for Hierarchical Groupscited by 7
  3. 2023Agnostic Multi-Group Active Learningcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026A One-Inclusion Graph Approach to Multi-Group Learningcited by 0
  2. 2026The price of multi-group transductive learningcited by 0