Machine learning models are often expected to perform well across many demographic or other groups at once. A new arXiv paper by Noah Bergam, Samuel Deng, and Daniel Hsu asks how much this requirement costs in the transductive setting, where the learner has access to unlabeled test points and must make predictions for them. The answer, in the leave-one-out variant, is that the cost can be surprisingly large.
Specifically, every multi-group learner can incur a multiplicative penalty in its error rate on some group compared with the error rate achievable by a learner focused only on that group. The penalty can increase linearly with the number of groups, up to roughly the square root of the sample size. That means the more groups a system is expected to serve, the worse its worst-group error can become relative to a specialized baseline.
The authors contrast this with the analogous group-realizable statistical setting. There, the penalty is always at most a poly-logarithmic factor in the sample size, and it does not grow with the number of groups. The gap between the two settings highlights that transductive learning, despite using unlabeled test data, does not automatically avoid the price of multi-group robustness.