A general condition for fast rates in multi-group learning
Abstract
In multi-group learning, a single predictor must control its excess risk simultaneously over overlapping groups. Tosh and Hsu (2022) obtained 1/√n slow rates via a reduction to online learning with sleeping experts, and 1/n rates only under realizability (and for a different strategy). We identify a group-wise Bernstein condition under which the same adaptive predictor attains the fast rate 1/n without knowing whether the condition holds, while retaining the slow rates on the groups where it fails. The condition is implied by some natural assumptions weaker than realizability. Lower bounds show that weakened versions leave every learner with slow rates. Intermediate rates under relaxed conditions and an extension to VC classes are also obtained.
Related
- The price of multi-group transductive learning
- Learning a general class of admissible multi-species collision operators from molecular dynamics
- Bandit Learning in General Open Multi-agent Systems
- Solutions for neutron stars in General Relativity from a complexity structure scalar boundary condition
- The Unified Separation Condition: A General Constraint Qualification for Smooth and Nonsmooth Optimization
BibTeX
@misc{sun2026general,
title = {{A general condition for fast rates in multi-group learning}},
author = {Hanqi Sun and Evgenii Chzhen and Luca Ganassali and Gilles Stoltz},
howpublished = {HAL},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26198},
eprint = {2610.26198},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05803488v1},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - A general condition for fast rates in multi-group learning
AU - Hanqi Sun
AU - Evgenii Chzhen
AU - Luca Ganassali
AU - Gilles Stoltz
PY - 2026
DA - 2026/10/16
PB - HAL
DO - 10.48550/arxiv.2610.26198
UR - https://hal.science/hal-05803488v1
AB - In multi-group learning, a single predictor must control its excess risk simultaneously over overlapping groups. Tosh and Hsu (2022) obtained 1/√n slow rates via a reduction to online learning with sleeping experts, and 1/n rates only under realizability (and for a different strategy). We identify a group-wise Bernstein condition under which the same adaptive predictor attains the fast rate 1/n without knowing whether the condition holds, while retaining the slow rates on the groups where it fails. The condition is implied by some natural assumptions weaker than realizability. Lower bounds show that weakened versions leave every learner with slow rates. Intermediate rates under relaxed conditions and an extension to VC classes are also obtained.
ER -