Pruning Training Data Without Erasing Intersectional Minorities

Deleting redundant training examples is one of the few green-ML practices that cuts energy on real hardware. Recent work removed a quarter of ImageNet-1K with no loss in top-1 accuracy and a 29% per-epoch energy saving (Stop Preaching and Start Practising Data Frugality). But "redundant" is judged against the average example. The people most likely to be judged redundant, or simply lost in a random cut, are those at rare intersections of protected attributes, such as older women of a particular ethnicity. A pruning method that saves energy by quietly removing these people trades one social cost for another. The obvious fix is to guarantee every intersection a minimum number of kept examples. With 20 or 25 binary attributes, though, that means over a million cells, nearly all empty or holding one example. Such guarantees either cannot be written down or force the method to keep almost everything.

We propose deciding which intersections need an explicit guarantee by using a theoretical result that bounds intersectional unfairness in terms of fairness over coarser attribute groupings. The data is then pruned aggressively everywhere else. The method guarantees kept examples only for the joint cells of a few strongly correlated attribute blocks. It then fills the remaining budget with the most informative examples. Every Joule is counted, including those spent scoring and selecting examples. The central question is whether this reaches the energy savings of unconstrained pruning while keeping worst-intersection accuracy near the full-data level, in regimes with too many attributes for naive per-cell stratification.

Core Claim

In settings with many protected attributes, the harm that pruning does to intersectional groups is concentrated in the joint cells of attributes that are strongly statistically dependent. Where attributes are close to independent, protecting each attribute separately is enough. This follows Bounding and Approximating Intersectional Fairness through Marginal Fairness, which proves two things. If protected attributes are mutually independent, intersectional unfairness is bounded by the sum of the unfairness along each attribute. When attributes are correlated, the extra gap is controlled by their total correlation, a measure of how far the joint distribution is from a product of its parts. The same paper uses this to greedily merge attributes into blocks.

That paper uses the blocks only to estimate unfairness from sparse data. We use them to construct a pruned training set. Selection quotas are imposed on joint cells within each block, and only on each attribute separately across blocks. The number of constraints then grows with the size of the blocks rather than as $2^d$, where $d$ is the number of binary protected attributes. The claim is falsifiable. It predicts that this structured guarantee beats guarantees on single attributes at equal energy. It also predicts matching a guarantee on every full cell whenever that is feasible, and staying feasible and useful at $d = 20$–25 where the full-cell guarantee is not.

Research Program

Scoring examples. The pipeline has three stages, each metered for energy. The first scores every training example for informativeness. It uses the training-dynamics uncertainty score (Dynamic Uncertainty) from the data-frugality work, computed on a small, briefly trained proxy model rather than the target model. This keeps the scoring cost from swamping the savings.

Choosing the protected blocks. The second stage runs the greedy total-correlation merge of Molina and Loiseau on the protected attributes. This yields blocks $A_1,\dots,A_J$ and a constraint set $C$: all joint cells within each block. Each cell $c \in C$ receives a floor $q_c$. Cells smaller than a minimum $m$ are kept whole; larger cells get a proportional share of the budget.

Selecting the subset. The third stage selects the subset by solving

$$\max_{z \in [0,1]^n} \sum_{i=1}^{n} s_i z_i \quad \text{s.t.} \quad \sum_i z_i \le B, \qquad \sum_{i \in c} z_i \ge q_c \ \ \forall c \in C,$$

where $z_i$ indicates whether example $i$ is kept, $s_i$ is its informativeness score, and $B$ is the example budget. The resulting fractional solution is then rounded. Overlapping cell quotas across blocks are the multi-category representation problem that Celis et al. show is NP-hard with three or more overlapping categories. We therefore follow their relaxation line (Celis et al.): solve the linear relaxation, round, and report the quota violations that remain. Keeping the constraint set small is what keeps this linear program cheap. This is also the first place the sustainability and scalability goals meet: fewer constraints means less selection energy.

Accounting. Energy is read from GPU power counters and a wall-socket meter, then converted to CO₂e using a fixed grid intensity. We report energy per stage. Because selection is a one-time cost reused across many downstream trainings, a benchmark dataset can be retrained tens of thousands of times: the frugality paper counts at least 46,179 ImageNet models. The headline sustainability metric is therefore the break-even count, meaning the number of downstream trainings after which total energy, selection included, falls below full-data training.

Auditing. We also audit intersections outside $C$. The Bias-Guided Generative Network (Intersectional Unfairness Discovery) is a generator trained to propose high-bias subgroups without exhaustive search. We use it as an independent auditor on each trained model. This tests whether protecting blocks leaves unseen intersections exposed, and it turns a discovery tool that its authors left without a mitigation step into an evaluation tool.

Relation to Prior Work

Three papers already couple fairness with data reduction, and each leaves the question here open in a different way.

Coresets for Clustering with Fairness Constraints composes per-group coresets to handle overlapping groups. It reports 5x–30x end-to-end speedups on Census1990, but only for clustering balance, with runtime rather than energy.

Fair Wasserstein Coresets synthesizes weighted examples under demographic parity for classifier training. It is tested on small group structures, generates synthetic points rather than keeping real ones, and pays an $O(mn)$ cost matrix, where $m$ is the coreset size and $n$ the dataset size.

The data-frugality paper links pruning, energy and bias, but only for a single color–digit spurious correlation.

None of the three prunes real examples for supervised learning under many intersecting attributes while measuring Joules. Beyond these, Lagrange Multiplier Models tackle the same constraint explosion inside training by predicting dual weights with an auxiliary network. We treat it as a competing way to spend compute on fairness, not as a component. The hardness and inapproximability results for fair clustering (Chakraborty et al.; Gadekar and Thejaswi) constrain the design. They are why we avoid exact per-cell guarantees and accept relaxed quotas.

Baselines

Full data. The naive reference is training on the full dataset with standard empirical risk minimization. It fixes the accuracy and worst-intersection ceiling and the energy cost to beat.

Uniform random subsampling. This is the "do nothing clever" reduction at the same budget $B$.

Unconstrained frugal pruning. This means Dynamic Uncertainty / InfoMax selection as in the data-frugality paper, using the same proxy-model scores as our method. It is the strongest competitor on energy. The file reports that pruning 25% of ImageNet-1K gave zero top-1 drop, and that on ResNet-34 this meant 32% less wall-clock time and 29% less energy per epoch. On intersectional worst-group accuracy for CelebA, Toxic Comments or Census1990, no reported result was found on Lacuna for this method. We will produce that number ourselves.

Stratification. We compare two versions. One sets floors on each attribute separately, which is marginal stratification. The other sets floors on every nonempty full intersection cell, applied wherever the linear program fits in memory.

Fair Wasserstein Coresets. This is the strongest existing fair-reduction method for classifiers. It reports an average 53% reduction in demographic disparity against baselines across its suite, including Communities and Crime. We run it with its demographic parity constraint on the joint attribute, at the same budget.

Lagrange Multiplier Models on full data. This spends compute on fairness during training rather than on the data. It reports suppressed 95th-percentile violations over 535 groups on Communities and Crime, with no scalar transcribed in the file.

Ablations. Two ablations isolate our key ingredients. The first replaces the total-correlation blocks with random blocks giving an equal number of constraints; this isolates whether the bound picks the right cells. The second keeps the quotas but selects at random within them; this isolates the informativeness score.

Fairness of the comparison. All methods use identical architectures, data splits and a fixed hyperparameter-tuning budget of equal GPU-hours per method, with tuning energy logged. The same meters are used throughout, and scoring, selection and training energy are all charged to each method.

Criterion for beating a baseline. Our method beats unconstrained pruning if it matches that method's energy within 5% while closing at least half of its gap to full data in worst-intersection accuracy. It beats full-cell stratification if it matches that baseline at small $d$ and dominates it at large $d$. Here "dominates" means higher worst-intersection accuracy at equal total energy, or equal accuracy with a lower break-even count.

Why not just…?

Why not just stratify over every intersection cell? At $d = 8$ on Census1990, this is a real threat, and we expect it to tie with our method. That regime is a sanity check, not a claimed win. At $2^{20}$ possible CelebA subgroups, the populated cells are mostly singletons. Guaranteeing each of them either keeps nearly the whole dataset, erasing the energy savings, or produces a selection program too large to solve cheaply. Molina and Loiseau's sparsity argument predicts that singleton cells carry little learnable signal anyway. Our sweep over $d$, taking random attribute subsets from 4 to 25, shows directly where the crossover occurs. If full-cell stratification is never beaten at any $d$, the core claim fails.

Why not just protect each attribute separately? This is cheap, but Molina and Loiseau prove it bounds intersectional unfairness only under independence, and Census attributes are strongly correlated. The random-block ablation and the marginal-stratification baseline together test whether the correlation structure matters in practice. The auditor measures gaps on intersections that neither method constrained.

Why not just use systems-level savings like Perseus? Reducing Energy Bloat in Large Model Training cuts up to 30% of per-iteration energy with no throughput loss. It is orthogonal, not competing: it removes idle time but still processes every redundant example, and it does nothing for representation. Where our training runs are large enough for pipeline parallelism, we compose it with each data-reduction method to show the savings stack. Our fairness claims do not depend on it.

Why not just skip data reduction and train with fairness multipliers? Lagrange Multiplier Models may achieve better worst-group numbers, because they act on the loss directly. However, they add an auxiliary network and a second optimizer to every training run, and they never shrink the dataset. We compare total Joules at matched worst-intersection accuracy. If the multiplier model wins on both energy and fairness, pruning is the wrong lever. We would report that result rather than argue around it.

Proposed Experiments

Datasets and models. Experiments use CelebA with the 20 binary attributes used by the discovery paper and a ResNet classifier on a held-out target attribute. They also use Toxic Comments with its 25 identity attributes and a small transformer classifier. Tabular MLPs are trained on Census1990 (8 protected attributes), Adult, and Communities and Crime. ImageNet-1K is used only to confirm that our selection reproduces unconstrained pruning's accuracy when no protected attributes are supplied.

Budgets and metrics. Budgets keep 50%, 25% and 10% of the data. Metrics are overall accuracy and worst-intersection accuracy over test cells with at least 30 examples. Unfairness on auditor-discovered subgroups is measured by precision of high-bias discoveries and the accuracy gap on them. Energy is reported per stage in Joules and kWh, along with CO₂e and the break-even count.

Decisive checks. Four checks carry the claim. First, at $d \ge 20$, our method must beat full-cell stratification and marginal stratification in worst-intersection accuracy at equal total energy. Second, at $d = 8$, it must tie with full-cell stratification. Third, the random-block ablation must be clearly worse; otherwise the total-correlation bound is not what is doing the work. Fourth, the break-even count must be small enough to matter for benchmark datasets. We will report it even if it turns out to be large.