Research map / Learning theory and algorithms / Prediction and decision losses
Multi-group Learning for Hierarchical Groups
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a simple, deterministic decision-tree multi-group learner (MGL-Tree) for hierarchically structured groups that achieves near-optimal group-wise excess error O(sqrt(log(|H||G|)/n_g)), and empirically evaluates it on US Census Folktables datasets against PREPEND and ERM baselines.
Problem
Multi-group agnostic PAC learning requires one predictor to perform well on many overlapping groups; prior near-optimal methods are randomized ensembles, while simple deterministic methods (PREPEND) have suboptimal rates depending on the minimum group mass.
Approach
Exploit hierarchical group structure: build a decision tree of group-conditional ERM predictors in breadth-first order, where a child's predictor replaces its parent's only when it beats the parent by a margin epsilon_n(g); this yields near-optimal rates without the group-mass dependence of PREPEND.
Key results
- MGL-Tree achieves group-wise excess error O(sqrt(log(|H||G|)/n_g)) for finite H with hierarchical G, removing PREPEND's dependence on minimum group mass gamma (rate O((log/(gamma n_g))^(1/3))).
- Across twelve Folktables datasets, MGL-Tree performs on par with or better than PREPEND on all groups per the paper's claims, and consistently improves on global ERM and group ERM minima.
- On CA Employment, MGL-Tree with logistic regression substantially improves over the ERM random forest baseline on almost all groups.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MGLTree instead of global ERM | MGLTree · U.S. Census datasets with hierarchical demographic groups | misclassification error | Helped |
| Use MGLTree instead of group-specific ERM | MGLTree · U.S. Census datasets with hierarchical demographic groups | misclassification error | Helped |
| Use MGLTree instead of Prepend | MGLTree · U.S. Census datasets with hierarchical demographic groups | misclassification error | Mixed |
| Use MGLTree with logistic regression instead of the ERM random forest baseline | MGLTree · California Employment | misclassification error | Helped |
| Use simpler benchmark hypothesis classes for MGLTree | MGLTree · CA Employment and CA Income | misclassification error | Helped |
| Vary the ordering of hierarchical attributes (ablation) | MGLTree · Hierarchical group collections | misclassification error | No clear effect |
Surprising findings
- Simple benchmark classes (logistic regression, depth-2 trees) gain more from MGL-Tree than complex ones like random forests and XGBoost.
- MGL-Tree can outperform more complex tree ensembles even when using a simple linear benchmark class.
Limitations
- Theory assumes hierarchical (laminar) group structure; general overlapping groups not covered.
- Guarantees are for finite H or finite VC dimension with bounded loss; the algorithm relies on known groups a priori.
- Empirical gains are sometimes small where ERM already near Bayes-optimal on datasets.
Experimental setup
Datasets: Folktables US Census datasets (Employment, Income, Coverage)
Benchmarks: Folktables CA Employment Folktables CA Income Folktables NY/FL datasets nationwide census datasets
Metrics: group-wise misclassification error excess error over group ERM
Baselines: ERM Group ERM PREPEND random forest XGBoost
Builds on: PREPEND (multi-group learning) multi-group agnostic PAC learning decoupled group ERM
Closest papers by meaning
- Group-wise oracle-efficient algorithms for online multi-group learning (NeurIPS 2024 · similarity 0.85)
- Transformer Learns Optimal Variable Selection in Group-Sparse Classification (ICLR 2025 · similarity 0.83)
- Learning-Augmented Hierarchical Clustering (ICML 2025 · similarity 0.83)
- Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.83)
- Metric-Agnostic Continual Learning for Sustainable Group Fairness (AAAI 2025 · similarity 0.83)
- DMTG: One-Shot Differentiable Multi-Task Grouping (ICML 2024 · 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.