The price of multi-group transductive learning

arXiv:2606.04423v2 Announce Type: replace Abstract: We show every multi-group learner in the leave-one-out transductive setting may incur a surprisingly large multiplicative penalty in its error rate on some group relative to the error rate achievable in the single-group setting. Indeed, the penalty can increase linearly with the number of groups, up to roughly the square-root of the sample size. We also show that in the analogous (group-realizable) statistical setting, the penalty is always at most a poly-logarithmic factor in the sample size, independent of the number of groups.