# Simple and near-optimal algorithms for hidden stratification and multi-group learning

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 58 references that are in the map.
- First posted on arXiv 22 Dec 2021.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Just Train Twice: Improving Group Robustness without Training Group Information](https://mlsanity.com/paper/2107.09044/) (2021)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [An Investigation of Why Overparameterization Exacerbates Spurious Correlations](https://mlsanity.com/paper/2005.04345/) (2020)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Hidden Stratification Causes Clinically Meaningful Failures in Machine Learning for Medical Imaging](https://mlsanity.com/paper/1909.12475/) (2019)
- [No Subclass Left Behind: Fine-Grained Robustness in Coarse-Grained Classification Problems](https://mlsanity.com/paper/2011.12945/) (2020)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Regularized Learning for Domain Adaptation under Label Shifts](https://mlsanity.com/paper/1903.09734/) (2019)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Data-Driven Robust Optimization](https://mlsanity.com/paper/1401.0212/) (2013)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Marginal Singularity, and the Benefits of Labels in Covariate-Shift](https://mlsanity.com/paper/1803.01833/) (2018)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Distributionally Robust Losses for Latent Covariate Mixtures](https://mlsanity.com/paper/2007.13982/) (2020)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Advancing subgroup fairness via sleeping experts](https://mlsanity.com/paper/1909.08375/) (2019)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Multiaccurate Proxies for Downstream Fairness](https://mlsanity.com/paper/2107.04423/) (2021)
- [Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functions](https://mlsanity.com/paper/1310.5796/) (2013)
- [An adaptive nearest neighbor rule for classification](https://mlsanity.com/paper/1905.12717/) (2019)

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

- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Why does Throwing Away Data Improve Worst-Group Error?](https://mlsanity.com/paper/2205.11672/) (2022)
- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [Fair Risk Control: A Generalized Framework for Calibrating Multi-group Fairness Risks](https://mlsanity.com/paper/2405.02225/) (2024)
- [Optimal Multi-Distribution Learning](https://mlsanity.com/paper/2312.05134/) (2023)
- [The sample complexity of multi-distribution learning](https://mlsanity.com/paper/2312.04027/) (2023)
- [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)
- [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)
- [Derandomizing Multi-Distribution Learning](https://mlsanity.com/paper/2409.17567/) (2024)
- [Panprediction: Optimal Predictions for Any Downstream Task and Loss](https://mlsanity.com/paper/2510.27638/) (2025)
- [Group-realizable multi-group learning by minimizing empirical risk](https://mlsanity.com/paper/2601.16922/) (2026)
- [Pushing the Accuracy-Group Robustness Frontier with Introspective Self-play](https://mlsanity.com/paper/2302.05807/) (2023)
- [Agnostic Multi-Robust Learning Using ERM](https://mlsanity.com/paper/2303.08944/) (2023)
- [Group conditional validity via multi-group learning](https://mlsanity.com/paper/2303.03995/) (2023)
- [Diversified Ensembling: An Experiment in Crowdsourced Machine Learning](https://mlsanity.com/paper/2402.10795/) (2024)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)
- [The price of multi-group transductive learning](https://mlsanity.com/paper/2606.04423/) (2026)
- [Locally Adaptive Multi-Objective Learning](https://mlsanity.com/paper/2602.14952/) (2026)
- [Federated Measurement of Demographic Disparities from Quantile Sketches](https://mlsanity.com/paper/2602.18870/) (2026)
- [ShakyPrepend: A Multi-Group Learner with Improved Sample Complexity](https://mlsanity.com/paper/2603.07319/) (2026)
- [A One-Inclusion Graph Approach to Multi-Group Learning](https://mlsanity.com/paper/2603.23208/) (2026)
- [Beyond Metadata: CAPRA for Hidden Subgroup Analysis under Missing Metadata in Medical Imaging](https://mlsanity.com/paper/2607.09102/) (2026)
- [Groupwise Distortion Guarantees for Preference-Based Alignment](https://mlsanity.com/paper/2610.05450/) (2026)
- [Sample-Optimal Multi-Group Learning with an ERM Oracle](https://mlsanity.com/paper/2610.15916/) (2026)

## Abstract (arXiv)

Multi-group agnostic learning is a formal learning criterion that is concerned with the conditional risks of predictors within subgroups of a population. The criterion addresses recent practical concerns such as subgroup fairness and hidden stratification. This paper studies the structure of solutions to the multi-group learning problem, and provides simple and near-optimal algorithms for the learning problem.