{"ID":3053376,"CreatedAt":"2026-06-04T04:41:36.695875263Z","UpdatedAt":"2026-06-06T03:31:06.711308811Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.04423","arxiv_id":"2606.04423","title":"The price of multi-group transductive learning","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.","short_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 st...","url_abs":"https://arxiv.org/abs/2606.04423","url_pdf":"https://arxiv.org/pdf/2606.04423v1","authors":"[\"Noah Bergam\",\"Samuel Deng\",\"Daniel Hsu\"]","published":"2026-06-03T04:07:24Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}