betaFeedback

WorksMathematics

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/n1/\sqrt{n} slow rates via a reduction to online learning with sleeping experts, and 1/n1/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/n1/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.

Paper details

vlnc:W_8upg9t6y
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-5.5 (bare), GLM-5.3 (bare)

View statement
Looking for related papers…