Skip to content
DraconiticResearch
Search Sources API
190,839 studies31 sourcesUpdated 42 min ago
PreprintarXiv licencearXiv

The price of multi-group transductive learning

  • Noah Bergam
  • Samuel Deng
  • Daniel Hsu
Open at sourcePDFDOICite

Abstract

We show every multi-group learner in the leave-one-out transductive setting may incur a surprisingly large multiplicative penalty in its error rate on some group relative to the error rate achievable in the single-group setting. Indeed, the penalty can increase linearly with the number of groups, up to roughly the square-root of the sample size. We also show that in the analogous (group-realizable) statistical setting, the penalty is always at most a poly-logarithmic factor in the sample size, independent of the number of groups.

Related

  1. Interval Carbon Price Forecasting Based on Multi-Task Learning
    Kaijie Chen, Dinggao Liu, Wen Han +2
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  2. Even Sharper Bounds for Transductive Learning and Its Applications
    Yingzhen Yang
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  3. A general condition for fast rates in multi-group learning
    Hanqi Sun, Evgenii Chzhen, Luca Ganassali +1
    HALPreprintCC BY-NC-ND 4.0Full textStatisticsHALarXiv
  4. Day-Ahead Electricity Price Forecasting Using a Multivariate Group Lasso Method
    Keyi Wang, Jiaxiang Ji, Mahan Mansouri +1
    arXivPreprintCC BY-NC-ND 4.0Full textStatisticsarXiv
  5. The Price of Privacy: Randomness Complexity of Graph-Based Multi-Secret Sharing
    Piotr Marszalik
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bergam2026price,
  title = {{The price of multi-group transductive learning}},
  author = {Noah Bergam and Samuel Deng and Daniel Hsu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2606.04423},
  eprint = {2606.04423},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.04423},
}
RIS
TY  - UNPB
TI  - The price of multi-group transductive learning
AU  - Noah Bergam
AU  - Samuel Deng
AU  - Daniel Hsu
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2606.04423
UR  - https://arxiv.org/abs/2606.04423
AB  - We show every multi-group learner in the leave-one-out transductive setting may incur a surprisingly large multiplicative penalty in its error rate on some group relative to the error rate achievable in the single-group setting. Indeed, the penalty can increase linearly with the number of groups, up to roughly the square-root of the sample size. We also show that in the analogous (group-realizable) statistical setting, the penalty is always at most a poly-logarithmic factor in the sample size, independent of the number of groups.
ER  -