The price of multi-group transductive learning
The study investigates multi-group transductive learning, showing that a learner's error rate on one group can be multiplied by a factor increasing linearly with the number of groups, up to $\sqrt{n}$. This contrasts sharply with statistical settings where the penalty is always logarithmic and independent of group count. The findings highlight a significant difficulty in multi-group transductive learning compared to statistical learning.