Classifiers that look excellent on average often fail badly on small, unlabeled subsets of their data. This is called hidden stratification. A chest X-ray model detects collapsed lungs well when a chest drain tube is visible and much worse when it is not. A bird classifier relies on the background and misjudges waterbirds photographed on land. Theorists have proposed a clean remedy called multi-group learning. You fix a large family of candidate subgroups in advance and build a predictor that is provably near-best on every member of the family at once, without knowing which subgroup will matter. Simple and near-optimal algorithms for hidden stratification and multi-group learning gives such algorithms with explicit error rates. Neither that paper nor the related Learning With Multi-Group Guarantees For Clusterable Subpopulations runs a single experiment.
The field also has a direct warning about this pattern. When WILDS put theoretically motivated robustness methods on realistic data, they failed to beat plain training on 8 of 10 datasets. This proposal asks one specific question. If the simplest multi-group algorithm is made computable, does it fix hidden failures on standard benchmarks? It must do so with group labels kept hidden from both training and model selection. And are its guarantees informative at the sample sizes those benchmarks actually have?
Core Claim
We claim that the decision-list algorithm PREPEND can be run in practice on deep models. Two choices make this possible. The first is to restrict the subgroup family to regions defined in a frozen embedding space. The second is to restrict the per-group predictors to linear heads on top of a pretrained model.
Run this way, PREPEND should recover most of the worst-group accuracy that oracle-label methods achieve on Waterbirds, CelebA, MultiNLI and CivilComments. It should also produce something no current label-free method produces: a held-out audit certificate. The certificate states, for every one of thousands of candidate subgroups, how far the model's error on that subgroup sits above the best achievable error for that subgroup.
The claim is falsifiable in two ways. If label-free reweighting methods match PREPEND's worst-group accuracy, PREPEND's only remaining value is the certificate, and we will report it that way. If the true hidden groups are not well approximated by any member of the family, the theory's premise fails on real data, and that negative result is itself the empirical validation the theory lacks.
PREPEND has a simple loop. It keeps a current predictor, $f_t$. At each step it searches the family $\mathcal{G}$ for a group $g$ where the current predictor is clearly beaten by the best predictor in a class $\mathcal{H}$ trained only on that group:
$$\hat{L}_g(f_t) > \min_{h \in \mathcal{H}} \hat{L}_g(h) + \epsilon .$$
Here $\hat{L}_g$ is the average loss on held-out examples falling in $g$, and $\epsilon$ is a tolerance. When such a group is found, the rule "if $x \in g$, use $h$" is put at the front of the list. The theory's rate for decision lists is $O(n^{-1/3})$ in sample size. That slow rate is exactly why finite-sample behaviour on groups of a few hundred examples is an open empirical question rather than a formality.
Research Program
The work has three parts.
Making the search tractable. The theory assumes one can enumerate the hypothesis class and the group family. We replace that enumeration with something finite and concrete. Each image or sentence is embedded once with frozen encoders: a cross-modal image-text encoder of the kind Domino uses, and the target model's own penultimate layer. Groups are then defined in two ways:
- as k-nearest-neighbour balls at several radii, centred on validation points;
- as clusters from mixture models at several resolutions, which gives the overlapping, multi-scale family that Dai et al. argue is better than committing to a single clustering.
The per-group predictor class is a logistic-regression head on the frozen features. One fit per candidate group takes seconds, so searching ten thousand groups is cheap. A third of the training data is held out to run the search, so the condition above is checked on data the heads were not fit on.
Measuring whether the theory's premise holds on real data. For each benchmark we compute a coverage score. It asks, for each ground-truth hidden group, how closely the best-matching family member overlaps it, measured by intersection over union. This tests what the theory silently assumes, namely that the failure-causing group lies in $\mathcal{G}$. It mirrors the coverage argument in Coverage, Not Averages, which showed that retrieval benchmarks leave 40–50% of semantic regions untested. Our version moves that argument from test-set coverage to coverage of the group family.
Checking the certificate against reality. On a final split, never used for search or tuning, we report two things for every group in the family: its error under the PREPEND model and the best head's error on that group. From these we derive a bound with a confidence interval. We then check whether the certified bound on the family member closest to each true hidden group actually brackets that group's measured error.
Baselines
Naive reference: plain training on a pretrained backbone. This is empirical risk minimization (ERM), training to minimize average error, using the same backbone and fine-tuning recipe as everything else. The reported reference points are:
- Waterbirds worst-group accuracy of 60.0% and MultiNLI of 65.7% in Sagawa et al.;
- CelebA worst-group accuracy of 39.7% in BARACK;
- CivilComments worst-group accuracy of 56.0% in WILDS.
We rerun ERM ourselves rather than reuse these numbers, so that backbone and data splits match exactly.
Strongest label-free competitor: Just Train Twice (JTT). JTT trains a model, then retrains it with the training points the first model got wrong upweighted. It is the most direct rival because, like our method, it needs no group labels. BARACK reports JTT at 77.8% worst-group accuracy on CelebA. No reported JTT result for Waterbirds, MultiNLI or CivilComments was found on Lacuna.
Cluster-then-reweight: GEORGE. No Subclass Left Behind clusters penultimate-layer features and then trains with group distributionally robust optimization (GDRO), which minimizes the loss of the worst cluster. The paper reports gains of up to 14 points in worst subclass accuracy and closes up to 62% of the gap to an oracle. To separate the clustering effect from the backbone effect, we also run a variant that clusters our cross-modal embeddings instead of the target model's features.
Oracle references. Two methods use group labels and therefore bound what label-free methods can hope to reach:
- GDRO trained with true group labels, which Sagawa et al. report at 90.5% on Waterbirds and 77.7% on MultiNLI;
- BARACK, which needs only a small labeled fraction and reports 83.8% on CelebA and 89.6% on Waterbirds.
Additive post-processing. The multiaccuracy boost of Multigroup Robustness audits a trained predictor against a group family and applies small additive corrections wherever a group is miscalibrated. We give it exactly our embedding-defined group family.
Fairness rules for all comparisons. Every method gets:
- the same pretrained backbone;
- the same training, search and audit splits;
- the same budget of 20 hyperparameter configurations.
Every method is also selected without group labels: by average validation accuracy, or by the family-wide audit for the methods that produce one. Many published worst-group numbers rely on validation sets that carry group labels. We therefore report each method under both selection regimes and label which is which.
What counts as beating JTT. The first condition is higher worst-group accuracy than JTT on at least three of the four datasets, under label-free selection, with the gap outside seed-to-seed variance across five seeds. The second is that PREPEND reaches that accuracy while also producing a certificate whose bounds bracket the true worst group's error.
Ablations. Two ablations isolate the key ingredient:
- replace the embedding-defined family with random partitions of the same sizes, to test whether the group structure matters;
- replace the ordered decision list with the additive boost on the same family, to test whether the list structure matters.
Why not just…?
Why not just use a bigger pretrained model? The Effect of Model Size on Worst-Group Generalization shows that scaling pretrained models reduces Waterbirds worst-group error by about 18.39%. The same paper reports that gains plateau on CelebA and that a large gap between average and worst-group accuracy remains. This is a real confound for us, because PREPEND sits on top of a frozen embedding. We will therefore run every method at two backbone sizes. The claim survives only if PREPEND's gain over ERM persists at the larger size.
Why not just run JTT, which is simpler? JTT is the most serious threat. It may well match PREPEND on worst-group accuracy. If it does, we will say so and narrow the contribution to two things: the certificate, and the empirical test of whether multi-group theory describes real data. JTT reweights a single error set and states nothing about other subgroups. In medical settings, Oakden-Rayner et al. document failures confined to specific subclasses, such as pneumothorax without a chest drain at AUROC 0.77 against 0.94 with one. Auditors there need a statement about many subgroups, not only the one that happened to be worst.
Why not just label a few examples per group and run BARACK? BARACK needs to know which groups exist before anyone can label them, and the hard cases are failure modes nobody had named before deployment. BARACK is still the right upper reference. If label-free PREPEND gets within a few points of it, that shows how much of the labeling cost can be avoided.
Why not just cluster once, as GEORGE does? Dai et al. argue that committing to a single clustering is brittle when groups overlap. Our coverage measurement tests this directly. If one clustering resolution already achieves high overlap with every true group, the multi-scale family is unnecessary and GEORGE plus GDRO should suffice.
Proposed Experiments
Main benchmarks. The four main benchmarks are Waterbirds, CelebA (blond hair, with gender as the spurious attribute), MultiNLI (with negation words as the shortcut), and CivilComments-WILDS. All group labels are hidden until the final audit. Primary metrics are worst-group accuracy, average accuracy, and the coverage score defined above. U-MNIST serves as a sanity check where the hidden subclass is known by construction.
Testing the certificate. We fit how certified excess error shrinks as the number of held-out examples per group grows. The theory predicts a decline at roughly the $n^{-1/3}$ rate for decision lists, which follows from the analysis of decision lists in Tosh and Hsu. We check whether this holds or whether constant factors make the bound vacuous on groups of fewer than a few hundred examples.
Clinical transfer. If budget allows, we run on CheXpert using the slice definitions from Error Slice Discovery via Manifold Compactness. The target is the method's worst-group accuracy of 59.8% on CelebA, which MCSD reached by collecting new data. Matching it without new data would test whether post-hoc correction can replace targeted data collection.
The decisive outcomes. Two results settle the proposal. The first is whether, on at least three datasets, label-free PREPEND beats JTT and stays within 10 points of oracle GDRO while its certificate brackets the true worst group. The second is whether the random-partition ablation collapses the gain. If both hold, multi-group theory has its first empirical support. If coverage of true groups is low, we will have shown where the theory's premise breaks on real data.
References
- Simple and near-optimal algorithms for hidden stratification and multi-group learning
- Learning With Multi-Group Guarantees For Clusterable Subpopulations
- WILDS: A Benchmark of in-the-Wild Distribution Shifts
- Domino: Discovering Systematic Errors with Cross-Modal Embeddings
- Coverage, Not Averages: Semantic Stratification for Trustworthy Retrieval Evaluation
- Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization
- BARACK: Partially Supervised Group Robustness With Guarantees
- No Subclass Left Behind: Fine-Grained Robustness in Coarse-Grained Classification Problems
- Multigroup Robustness
- The Effect of Model Size on Worst-Group Generalization
- Hidden Stratification Causes Clinically Meaningful Failures in Machine Learning for Medical Imaging
- Error Slice Discovery via Manifold Compactness