UniPROT Fixes a Hidden Bias That Hurts Minority Classes in AI Training Data
A new subset selection method forces equal weights on chosen prototypes, boosting minority class accuracy and LLM training on imbalanced data mixtures.
PRO- UniPROT selects prototype subsets that carry equal weights, fixing bias in facility location and k-medoids.
- Enforcing uniform weights makes the objective super-additive, but a partial OT reformulation restores submodularity.
- Greedy algorithm retains the classic (1 - 1/e) approximation guarantee for the original problem.
- Fast closed-form marginal gain drops per-step cost to O(n log n), matching standard k-medoids complexity.
- Boosts minority-class accuracy on CIFAR10-LT and MNIST without hurting majority classes.
- Code is public; beats GREATS and CoLM on PHI-3, PHI-2, Zephyr-3B fine-tuning.
Picking a small, representative subset from a large dataset sounds like a solved problem. Facility location, k-medoids, and their optimal transport cousins have been doing this for years. There is a subtle bug in how these methods work though: they hand out uneven importance weights to the prototypes they pick, and minority classes almost always get the short end of the stick.
A new paper accepted at AISTATS 2026 introduces UniPROT, a subset selection framework that forces every selected prototype to carry equal weight, and proves you can still get the classic (1 - 1/e) greedy approximation guarantee while doing it. The approach delivers measurable gains on long-tailed image classification and, more interestingly, on mini-batch selection for LLM fine-tuning and pretraining.
Why weighted prototypes quietly hurt minorities
Classical prototype selection methods pick a subset whose induced distribution is close to the target under some divergence, typically maximum mean discrepancy or Wasserstein distance. These algorithms often yield a weighted subset of representative instances, where the weights reflect the relative importance of each exemplar and are typically inferred implicitly during selection.
That implicit weighting causes trouble. Uniform weighting is generally preferred for interpretability, since disproportionate emphasis can bias human perception. The issue sharpens under long-tailed class distributions, where minority classes may receive lower-weighted prototypes, leading to unfair or under-representative selections. When the authors ran vanilla k-medoids on CIFAR10, the learned weights were heavily skewed, meaning several selected prototypes contributed almost nothing to the actual reconstruction of the target distribution.
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
