arXiv preprint ·
A general condition for fast rates in multi-group learning
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In multi-group learning, a single predictor must control its excess risk simultaneously over overlapping groups. Tosh and Hsu (2022) obtained $1/\sqrt{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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning (Statistics)
Corrected Block Sparse Spectral Optimization: Exact Models, Finite Identification, and Local Dynamics
A Bayesian machine learning approach to direct and spillover effects in cluster-randomized trials with noncompliance
Detection Augmented Learning In Non-Stationary Bandit Environments
Beyond Scalar Leaderboards: Adaptive Sampling for Pareto Frontier Identification in Multi-Objective LLM Arenas
Fair Regression under Approximate Demographic Parity
Get the few papers worth your time in Machine Learning (Statistics) every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.