mlsanityData to 7 Oct 2026

The price of multi-group transductive learning

arXiv 2606.04423 ↗First posted 3 Jun 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 18 of its 28 references that are in the map. First posted on arXiv 3 Jun 2026.

Builds on

18 of 28 references.

References · 18

  1. 2018Multiaccuracy: Black-Box Post-Processing for Fairness in Classificationcited by 221
  2. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  3. 2014Minimax Analysis of Active Learningcited by 61
  4. 2021Multi-group Agnostic PAC Learnabilitycited by 42
  5. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  6. 2023A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learningcited by 29
  7. 2019Advancing subgroup fairness via sleeping expertscited by 28
  8. 2021Simple and near-optimal algorithms for hidden stratification and multi-group learningcited by 26
  9. 2015Refined Error Bounds for Several Learning Algorithmscited by 24
  10. 2023Regularization and Optimal Multiclass Learningcited by 15
  11. 2023Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensionscited by 12
  12. 2022The One-Inclusion Graph Algorithm is not Always Optimalcited by 11
6 more
  1. 2024Group-wise oracle-efficient algorithms for online multi-group learningcited by 8
  2. 2023Agnostic Multi-Group Active Learningcited by 6
  3. 2023Oracle Efficient Algorithms for Groupwise Regretcited by 6
  4. 2025Sample-Efficient Omniprediction for Proper Lossescited by 4
  5. 2025Panprediction: Optimal Predictions for Any Downstream Task and Losscited by 4
  6. 2026Group-realizable multi-group learning by minimizing empirical riskcited by 2

Built on by

Not cited yet.