mlsanityData to 14 Oct 2026

Sample-Optimal Multi-Group Learning with an ERM Oracle

arXiv 2610.15916 ↗First posted 11 Oct 2026cs.LG cs.DS cs.GTcited by 0

Not on the map. Why?

Abstract (arXiv)

In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of subpopulations. The known algorithms with the optimal sample complexity keep track of every pair of a group and a hypothesis, which is impossible for the large classes of interest, and the known oracle-based algorithms have a worse rate. We ask whether the optimal rate can be attained by a learner that accesses the classes only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses tildeO((dG+dH)/varepsilon2) samples and polynomially many calls to a weighted ERM oracle over pairs of a group and a hypothesis, where dG and dH are the VC dimensions of the group and hypothesis classes and varepsilon bounds the excess risk on every group, weighted by its probability. We also show a matching lower bound of Omega((dG+dH)/varepsilon2) samples for every learner even with unlimited computation, so oracle efficiency costs no additional samples. We also consider a natural special case in which every input belongs to at most k groups and these groups can be listed. In this case, an ERM oracle for the hypothesis class alone suffices, with tildeO((dH+log k)/varepsilon2) samples in the agnostic setting and tildeO((dH+log k)/varepsilon) samples when every group has a hypothesis that is correct on it.

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

Builds on

24 of 48 references.

References · 24

  1. 2017Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairnesscited by 384
  2. 2018Multiaccuracy: Black-Box Post-Processing for Fairness in Classificationcited by 222
  3. 2014A Second-order Bound with Excess Lossescited by 95
  4. 2020Outcome Indistinguishabilitycited by 75
  5. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 52
  6. 2021Multi-group Agnostic PAC Learnabilitycited by 44
  7. 2015The Computational Power of Optimization in Online Learningcited by 39
  8. 2023Oracle Efficient Online Multicalibration and Omnipredictioncited by 37
  9. 2019Advancing subgroup fairness via sleeping expertscited by 30
  10. 2023A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learningcited by 30
  11. 2021Simple and near-optimal algorithms for hidden stratification and multi-group learningcited by 28
  12. 2021Online Minimax Multiobjective Optimization: Multicalibeating and Other Applicationscited by 27
12 more
  1. 2022An Algorithmic Framework for Bias Bountiescited by 21
  2. 2024Group-wise oracle-efficient algorithms for online multi-group learningcited by 9
  3. 2023Oracle Efficient Algorithms for Groupwise Regretcited by 8
  4. 2024Multi-group Learning for Hierarchical Groupscited by 8
  5. 2023Agnostic Multi-Group Active Learningcited by 7
  6. 2024Oracle-Efficient Hybrid Online Learning with Unknown Distributioncited by 4
  7. 2026Group-realizable multi-group learning by minimizing empirical riskcited by 3
  8. 2026Oracle-efficient Hybrid Learning with Constrained Adversariescited by 3
  9. 2026Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputscited by 3
  10. 2026Optimal Deterministic Multicalibration and Omnipredictioncited by 2
  11. 2026The price of multi-group transductive learningcited by 1
  12. 2026The Sample Complexity of Multicalibration with an ERM Oraclecited by 1

Built on by

Not cited yet.