Statistical learning theory / Open question
The Exact Sample Cost of Multiclass Learning
The quantity of data needed for learning should be measured by the correct model complexity, without avoidable logarithmic losses from the proof or algorithm.
Seed catalog · Showing the bundled record.
Problem statement
For every multiclass class with finite DS dimension and Natarajan dimension , can an agnostic learner achieve with probability using samples, for a universal independent of ? Here . Remove the polylogarithmic overhead in the known upper bound, or prove that an overhead is unavoidable.
Assumptions and scope
- Use arbitrary i.i.d. labelled distributions, 0<epsilon,delta<1/4, any finite alphabet size K, and the standard measurability/countability conditions. The output may be improper; runtime is not constrained.
- Natarajan dimension is the largest number of points with two distinct labels per point such that all binary choices are realized. DS dimension is the largest number of points whose class trace contains a finite nonempty pseudo-cube: every labeling has an alternative differing only in each prescribed single coordinate.
- Constants must be uniform over alphabet size and both dimensions. A realizable theorem, a binary theorem, or a bound hiding logarithms in a tilde-O does not settle this question.
What would settle it?
A distribution-free upper bound of the displayed form with literal universal constants, or a class/distribution family requiring an unbounded multiplicative overhead. Removing selected logs is partial progress and must identify the remaining factors.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Pabbaraju's November revision settles realizable multiclass PAC without logarithmic factors and removes the previous sqrt(d_DS) gap. Its agnostic corollary and the optimistic follow-up still retain polylogarithms; the latter explicitly asks for log-free rates. The DS/epsilon plus Natarajan/epsilon^2 structure is established, not the open contribution. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Pabbaraju — The Optimal Sample Complexity of Multiclass and List Learning ↗partial theory · source checked 2026-11-19
HTML Corollaries 1.1–1.2, definitions and results tables checked: realizable multiclass PAC is Theta((d_DS+log(1/delta))/epsilon) without hidden logs; agnostic bounds still hide polylogarithms. Do not relist the old sqrt(d_DS) or realizable logarithmic gap.
- Cohen et al. — Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back ↗partial theory · source checked 2026-11-19
Abstract and its role in Pabbaraju's Corollary 1.2 checked: the agnostic rate has separate DS/epsilon and Natarajan/epsilon^2 terms, not a single VC-like dimension. Subsequent sharp realizable rates improve the DS term.
- Li, Han, Jiang and Gao — Optimistic Rates for Multiclass PAC Learning ↗problem statement · source checked 2026-11-19
HTML Sections 2, 3 and 6 checked: DS/Natarajan definitions, optimistic rates with log^2/log^3 factors, and an explicit question about eliminating logarithmic loss. The base agnostic log-free question is retained; the paper's Lean claims and dependencies were not audited.