Research map / Learning theory and algorithms / Sample complexity
Universal Rates of Empirical Risk Minimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes all possible universal (distribution-dependent) learning rates achieved by empirical risk minimization in the realizable case, proving a tetrachotomy (e^{-n}, 1/n, log(n)/n, arbitrarily slow) via eluder, star-eluder and VC-eluder sequences.
Problem
Determining which universal learning rates (learning curves) are achievable by ERM algorithms in the realizable setting, beyond the worst-case PAC uniform rates.
Approach
Shows that the universal rates achievable by ERM fall into exactly four categories (exponential, linear, log(n)/n, arbitrarily slow), characterized by the existence of infinite eluder, star-eluder, and VC-eluder sequences, and introduces fine-grained SE and VCE dimensions for constant factors.
Key results
- Tetrachotomy: universal rates of ERM are exactly e^{-n}, 1/n, log(n)/n, or arbitrarily slow, with characterization via eluder sequences for |H| finite/infinite and VC dimension.
- Exponential exact rate by ERM iff |H| finite (for |H|>=3).
- Arbitrarily slow ERM rates iff VC dimension infinite; infinite star number does not imply an infinite star-eluder sequence.
Surprising findings
- Infinite star number does not guarantee an infinite star-eluder sequence, so the star number does not characterize the 1/n vs log(n)/n gap.
- ERM can be strictly suboptimal: classes that optimal learners handle at exponential or 1/n rates can force ERM to slower rates.
Limitations
- Only the realizable (binary classification) case is considered.
- Characterization of the 1/n vs log(n)/n gap via a simple combinatorial quantity remains open.
- Only the worst-case ERM is analyzed; best-case ERM is left open.
Experimental setup
Builds on: PAC learning universal learning (Bousquet et al.) star number eluder dimension Littlestone dimension
Closest papers by meaning
- On the Asymptotic Distribution of the Minimum Empirical Risk (ICML 2024 · similarity 0.89)
- Asymptotic Theory of Iterated Empirical Risk Minimization, with Applications to Active Learning (ICML 2026 · similarity 0.88)
- On the Efficiency of ERM in Feature Learning (NeurIPS 2024 · similarity 0.87)
- Universal Rates for Active Learning (NeurIPS 2024 · similarity 0.86)
- On Agnostic PAC Learning in the Small Error Regime (NeurIPS 2025 · similarity 0.85)
- Prospective Learning: Learning for a Dynamic Future (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.