Research map / Learning theory and algorithms / Sample complexity
Improved Sample Complexity for Multiclass PAC Learning
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.
Improves multiclass PAC sample complexity upper bound to d^{3/2} log(d) log(d/eps) over prior polylog gaps by reducing multiclass learning to list learning with boosting, proves an Omega((d+log(1/delta))/eps) lower bound, and proposes two open questions (bounded-size list learner; pivot shifting) that would close the gap.
Problem
Determining the optimal PAC sample complexity of multiclass learning in terms of DS dimension, where prior upper and lower bounds differ by polylog factors in the leading term.
Approach
Reduce multiclass learning to list learning (a reduction that converts a list learner's expected error into a multiclass learner's error), then boost a list learner via sampled boosting (adapted from da Cunha et al. 2024) using a list sample compression scheme whose size saves a log(d) factor; also a density/one-inclusion graph route with pivot shifting.
Key results
- Upper bound on multiclass PAC sample complexity O((d^{3/2} log(d) log(d/eps)+log(1/delta))/eps), reducing gap to a single log factor relative to the Omega((d+log(1/delta))/eps) lower bound.
- Error rate improved from O(log log(n) log^2(n)/n) to O(log(n)/n) dependence on n (treating d constant).
- Dimension-1 classes have sample complexity Theta(log(1/delta)/eps).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the list-learning reduction with the boosted list learner | Multiclass PAC learning · Realizable multiclass PAC (DS dimension d) | worst-case error rate: O((d^{3/2} log(d)+d log(log(n))) log²(n)+log(1/δ) over n) -> O((d^{3/2} log(d) log(n)+log(1/δ))/n) | Helped |
| Apply the one-inclusion graph density result for DS dimension 1 | Realizable multiclass PAC learning · Realizable multiclass PAC (DS dimension 1) | sample complexity: Θ(log(1/δ)/ε) | Helped |
Limitations
- Gap of sqrt(d) log(d) log(d/eps) remains between upper and lower bounds.
- Existence of list learners with bounded size and O(d/n) expected error (Open Question 1) is unresolved.
- Pivot shifting preserving DS dimension is unverified (Open Question 2).
Experimental setup
Metrics: PAC sample complexity expected error rate high-probability error rate
Baselines: Brukhim et al. 2022 multiclass learner Charikar and Pabbaraju 2023 list learner Daniely and Shalev-Shwartz 2014 density conjecture
Builds on: DS dimension (Daniely and Shalev-Shwartz 2014) Brukhim et al. 2022 multiclass PAC characterization da Cunha et al. 2024 sampled boosting Aden-Ali et al. 2023 transductive-to-inductive one-inclusion graph (Haussler et al. 1994)
Closest papers by meaning
- Fast Rates for Bandit PAC Multiclass Classification (NeurIPS 2024 · similarity 0.87)
- A Trichotomy for List Transductive Online Learning (ICML 2025 · similarity 0.87)
- Surprises in Proper Positive-Only Learning (NeurIPS 2026 · similarity 0.86)
- Collaborative Learning with Different Labeling Functions (ICML 2024 · similarity 0.86)
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.85)
- Representation Preserving Multiclass Agnostic to Realizable Reduction (ICML 2025 · 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.