Research map / Learning theory and algorithms / Sample complexity
On Agnostic PAC Learning in the Small Error Regime
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.
Gives an efficient agnostic PAC learner whose error is c·τ + O(√(τ(d+log(1/δ))/m) + (d+log(1/δ))/m) with c ≤ 2.1, via majority votes of ERMs on recursively split subsamples plus a region-of-disagreement tie-breaking ERM.
Problem
Optimal sample complexity of agnostic PAC binary classification as a function of tau = err(h*), particularly in the regime tau ≈ d/m, and whether computationally efficient majority-vote learners are optimal in this tau-based framework.
Approach
Replaces Hanneke's overlapping splits with disjoint 27-way recursive splits, subsamples ERMs for efficiency, and combines two independent voting classifiers with an ERM trained on their region of disagreement as a tie-breaker, reducing the tau multiplier from 15 to 2.1.
Key results
- Achieves error 2.1·τ + O(√(τ(d+ln(1/δ))/m) + (d+ln(1/δ))/m), matching the known lower bound and resolving the τ ≈ d/m regime.
- Earlier simpler approach gives constant 15 on τ; improved scheme reduces it to 2.1 via 27-way splits and tie-breaking ERM.
- Best-of-both-worlds combination with the HLZ learner yields min of 2.1τ bound and τ + Õ(ln^5(m/d)·d/m) bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed best-of-both-worlds learner, combining the new voting learner with the earlier learner | Agnostic PAC learning · Agnostic PAC learning | error upper bound: 2.1 · τ + O (√(τ(d + ln(1/δ))/m) + (d + ln(1/δ))/m) | Helped |
| Replace the earlier learner with the proposed learner when τ = o(ln^5(m/d) · d/m) | Agnostic PAC learning · Agnostic PAC learning | error upper bound: 2.1 · τ; ln^5(m/d) | Helped |
| Use the improved 27-subsample splitting, two independent voting classifiers, and an ERM tie-breaker instead of the initial approach (ablation) | Proposed learner · Agnostic PAC learning | error upper bound: 15τ -> 2.1τ | Helped |
| Add an ERM tie-breaker trained on the voters’ region of disagreement | Two voting classifiers · Agnostic PAC learning | multiplicative factor on τ: ≈13 -> 1.1 | Helped |
| Use 27 recursive calls instead of 3 to control the low-threshold voting error | Voting classifier · Agnostic PAC learning | error upper bound: 11/243; 3160 | Helped |
| Subsample the ERM training subsequences rather than running ERM on all of them | Proposed voting learner · Agnostic PAC learning | ERM-oracle efficiency | Helped |
| Use a three-way splitting and majority-vote approach instead of the improved method (ablation) | Proposed learner · Agnostic PAC learning, τ = O(d/m) | error upper bound: 2.1τ -> 15τ | Hurt |
Limitations
- Constant 2.1 on tau does not reach the optimal constant 1, so full optimality for all tau is open.
- Relies on finite VC dimension and ERM oracle; analysis of the tie-breaker uses delicate conditioning and overlapping training samples, so the learner is not strictly stable.
- Best-of-both-worlds bound only improves the polylog regime via combination with prior learner.
Experimental setup
Metrics: expected error bound as function of tau, m, d, delta
Baselines: ERM Hanneke-Larsen-Zhivotovskiy learner
Builds on: Hanneke's recursive splitting algorithm (optimal PAC learner) Hanneke, Larsen, and Zhivotovskiy (FOCS '24) tau-dependent agnostic bounds
Closest papers by meaning
- Universal Rates of Empirical Risk Minimization (NeurIPS 2024 · similarity 0.85)
- Reliable Learning of Halfspaces under Gaussian Marginals (NeurIPS 2024 · similarity 0.85)
- Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale (NeurIPS 2026 · similarity 0.85)
- Testably Learning Polynomial Threshold Functions (NeurIPS 2024 · similarity 0.85)
- Learning via Surrogate PAC-Bayes (NeurIPS 2024 · similarity 0.85)
- Fast Rates for Bandit PAC Multiclass Classification (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.