Research map / Learning theory and algorithms / Sample complexity
Representation Preserving Multiclass Agnostic to Realizable Reduction
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 a simple, representation-preserving reduction from agnostic to realizable PAC learning in a unified framework that covers multiclass (unbounded labels), list, and multilabel learning, plus Massart and Tsybakov noise corollaries.
Problem
Whether agnostic PAC learning can be reduced to realizable PAC learning in multiclass settings with unbounded label spaces while preserving the representation (outputs remain in the realizable learner's hypothesis class); prior reductions relied on boosting-based sample compression, which does not p
Approach
Run the realizable learner on every subset of a first sample half, then perform empirical risk minimization over the resulting finite set of hypotheses on a held-out half. Because outputs are always produced by the realizable learner, the reduction is representation preserving; the approach extends to a unified PAC framework and noise models.
Key results
- Theorem 4.1 gives agnostic sample complexity O((1/eps^2) * max_mu MRE(eps/(2mu), delta/3)/mu + log(1/delta)) from any realizable learner, yielding eps^-3 for multiclass with finite DS dimension d.
- Corollary: multiclass agnostic sample complexity O~((d^{3/2}+log(1/delta))/eps^3) for finite DS dimension, and Massart and Tsybakov noise bounds improve the dependence on eps.
- Lower bound example: a Omega(1/eps^2) gap between optimal realizable and agnostic sample complexity in multiclass PAC learning.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the representation-preserving reduction from realizable to agnostic learning | Unified PAC Learning · Unified PAC Learning | agnostic PAC learnability | Helped |
| Apply the representation-preserving reduction | Multiclass PAC Learning · Multiclass PAC Learning | sample complexity: ˜O((d3/2 + log(1/δ))/ϵ3) | Helped |
| Apply the unified reduction to L-list learning | Unified PAC Learning reduction · L-list learning | sample complexity: ˜O((L6d3/2 + log(1/δ))/ϵ3) | Helped |
| Apply the unified reduction to multilabel learning | Unified PAC Learning reduction · Multilabel learning | agnostic PAC learnability | Helped |
| Use the reduction under Massart noise | Multiclass PAC Learning · Multiclass PAC Learning (Massart noise) | sample complexity: ˜O((d3/2 + log(1/δ))/(∆ϵ2)) | Helped |
| Use the reduction under Tsybakov noise | Multiclass PAC Learning · Multiclass PAC Learning (Tsybakov noise) | sample complexity: ˜O(a(d3/2 + log(1/δ))/ϵ3−α) | Helped |
| Require representation preservation rather than use the sample-compression-based approach | Agnostic-to-realizable reduction · Unified PAC Learning | sample complexity dependence on ϵ: 1/ϵ3; 1/ϵ2 | Hurt |
| Use a class of constant functions | Representation-preserving reduction · Unified PAC Learning | sample complexity gap: Ω(1/ϵ2) | Hurt |
Surprising findings
- The paper shows a Omega(1/eps^2) gap between realizable and agnostic sample complexity in a multiclass example, so the extra 1/eps factor in the reduction is sometimes unavoidable under representation preservation.
Limitations
- Sample complexity has an extra 1/eps factor compared with compression-based reductions (eps^-3 vs eps^-2).
- Requires finite DS dimension for multiclass; the reduction is a theoretical construction without experiments.
- Whether a sublinear proper sample compression scheme exists to close the gap is left open.
Experimental setup
Metrics: sample complexity true risk
Baselines: David et al. 2016 compression-based agnostic learner
Builds on: Hopkins et al. 2022 three-line reduction David et al. 2016 sample compression boosting Brukhim et al. 2022 multiclass PAC characterization
Closest papers by meaning
- Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise (ICML 2025 · similarity 0.85)
- Improved Sample Complexity for Multiclass PAC Learning (NeurIPS 2024 · similarity 0.85)
- Fast Rates for Bandit PAC Multiclass Classification (NeurIPS 2024 · similarity 0.84)
- Surprises in Proper Positive-Only Learning (NeurIPS 2026 · similarity 0.84)
- Trading off Consistency and Dimensionality of Convex Surrogates for Multiclass Classification (NeurIPS 2024 · similarity 0.83)
- On Agnostic PAC Learning in the Small Error Regime (NeurIPS 2025 · similarity 0.83)
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.