The price of multi-group transductive learning
This work identifies a fundamental limitation of multi-group transductive learning for machine learning theorists, showing a sharp separation from the statistical setting.
The paper proves that multi-group transductive learning can incur a multiplicative error penalty that grows linearly with the number of groups, up to the square-root of sample size, contrasting with the statistical setting where the penalty is at most logarithmic.
We show every multi-group learner in the transductive setting may incur a multiplicative penalty in its error rate on some group relative to the error rate achievable in the single-group setting, and the penalty can increasing linearly with the number of groups, up to roughly the square-root of the sample size. This stands in stark contrast to optimal multi-group learners in an analogous (group-realizable) statistical setting, where the penalty is always at most logarithmic in the sample size and independent of the number of groups.