Research map / Learning theory and algorithms / Fairness
Simple and near-optimal algorithms for hidden stratification and multi-group learning
Christopher J Tosh, Daniel Hsu
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace suboptimal decision-list PREPEND learner with sleeping-experts reduction (MLC-HEDGE based) for multi-group learning | multi-group agnostic learning · theoretical per-group excess risk bound | per-group excess conditional risk rate | Improved |
| Restrict group-realizable setting to ERM-per-group majority vote predictor (no sample splitting or complex reweighting) | group-realizable multi-group learning · theoretical per-group conditional zero-one risk | per-group excess risk rate | No clear effect |
| Use evaluation-function (order-1) scoring to order group-hypothesis pairs for decision lists | multi-group learning decision lists · two-distribution counterexample | worst-case per-group excess conditional risk: at least 1/8 excess risk | Hurt |
| Use the group-realizable majority-vote predictor (Algorithm 3) for general agnostic multi-group learning | agnostic multi-group learning · constructed distribution with three groups | per-group excess zero-one risk: some group has excess risk > 1/4 | Hurt |
| Replace log|H| dependence in sleeping-experts reduction with pseudo-dimension of loss-composed class via ERM on half the data per group | Algorithm 2 (sleeping experts reduction) · theoretical per-group risk bound | per-group excess risk rate | No clear effect |
Closest papers by meaning
- Multi-group Learning for Hierarchical Groups (ICML 2024 · similarity 0.89)
- Metric-Agnostic Continual Learning for Sustainable Group Fairness (AAAI 2025 · similarity 0.84)
- Group-wise oracle-efficient algorithms for online multi-group learning (NeurIPS 2024 · similarity 0.83)
- Improving Subgroup Robustness via Data Selection (NeurIPS 2024 · similarity 0.83)
- Learning With Multi-Group Guarantees For Clusterable Subpopulations (ICML 2025 · similarity 0.83)
- Multigroup Fairness and Omniprediction: Separations and Equivalences (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
