The price of multi-group transductive learning
Noah Bergam, Samuel Deng, Daniel Hsu
cs.LG stat.ML
Abstract
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.
Topics
Classified with taxonomy v2 on Wed, 2 Sept 2026.