The price of multi-group transductive learning
2026-06-03 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how learning from multiple groups of data at once can affect the error rate in a special setting called transductive learning. They find that when handling many groups, the error for some groups can become much worse, increasing proportionally with the number of groups and up to about the square root of the sample size. This is very different from a related setting where the error only grows slowly with the sample size and doesn't depend on the number of groups. Their work highlights a big difference in learning behavior between these two scenarios.
transductive learningmulti-group learningerror ratesample sizestatistical learninggroup-realizable settingmultiplicative penaltylearning theory
Authors
Noah Bergam, Samuel Deng, Daniel Hsu
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.