The Optimal Sample Complexity of Multiclass and List Learning

arXiv:2604.24749 · cs.LG, stat.ML · Submitted 2026-08-18 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "The Optimal Sample Complexity of Multiclass and List Learning".

Jane: The paper was written by Chirag Pabbaraju from Stanford University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title: Tom: Welcome back to the channel, everyone. Today we're digging into a paper that just hit arXiv with a title that sounds like it could end a decade-long argument: "The Optimal Sample Complexity of Multiclass and List Learning."

Jane: And Tom, I have to say, this one genuinely feels like a closing chapter. For years, researchers knew the right answer for binary classification—two labels, yes or no—but the moment you go to multiclass, where you've got many labels, the picture got fuzzy. This paper claims to nail it down.

Tom: Right, and the authors are Chirag Pabbaraju from Stanford. Single author, which is wild for a result this big. The paper is built on a recent breakthrough by Hanneke, Meng, Moran, and Shaeiri, and it resolves a conjecture that's been sitting open since two thousand fourteen.

Jane: Let me put the stakes in plain terms. Imagine you're teaching a machine to sort photos into a hundred categories. How many labeled photos do you need to guarantee it learns well? For two categories, we've known the exact answer for decades. For a hundred categories, we had upper and lower bounds that didn't match. There was this annoying gap.

Tom: And the gap wasn't tiny. The best known upper bound scaled like the DS dimension to the power of one point five, while the lower bound was just the DS dimension. That square root gap—the difference between d and d to the one point five—was the obstacle.

Jane: Exactly. And the DS dimension, named after Daniely and Shalev-Shwartz, is the right measure of complexity for multiclass problems. It tells you how intricate your hypothesis class is. The conjecture was that the sample complexity should scale linearly with it, not with its square root.

Tom: So this paper proves that conjecture. It shows the upper bound matches the lower bound, up to constants. That's the kind of result that makes textbooks get rewritten.

Jane: And it's not just about multiclass. The paper also handles something called list learning, where instead of predicting one label, the algorithm can output a short list of labels and is correct if the true label is on that list. That's useful in medical diagnosis, for example, where you want to say "here are three possible conditions."

Tom: Right, and the list version has its own dimension, the l-DS dimension, and the paper proves the optimal bound there too. So it's a two-for-one deal.

Jane: The core insight is algebraic. The authors show that the density of a certain graph—the one-inclusion graph—is always bounded by the DS dimension. That graph density was the missing link.

Tom: And once you have that, the sample complexity results just fall out from prior machinery. It's elegant in the way the best math is—one clean structural result, and then a cascade of consequences.

Jane: I love that about this paper. It doesn't invent a dozen new tools. It finds the right way to look at the problem, and everything else follows.

Tom: So we've got the big picture. Next, let's actually walk through how the proof works, because the algebra here is genuinely clever.

Summary: Tom: So we've established the headline: this paper, "The Optimal Sample Complexity of Multiclass and List Learning," closes the gap between upper and lower bounds. But let's get into the actual machinery, because the proof is the interesting part.

Jane: Yes, and I want to bring in Lu, who's been staring at the algebra all morning. Lu, what's the key move?

Lu: The key move is to think of a hypothesis class as a vector space. Each hypothesis is a vector, and you ask: what functions on this vector space can be represented as polynomials? The recent breakthrough by Hanneke and colleagues showed that a certain set of monomials—polynomials with bounded degree and bounded support—spans the entire space.

Tom: And "bounded support" means what, exactly?

Lu: It means each monomial only depends on a limited number of coordinates. Specifically, at most the DS dimension of the class. That's the crucial constraint. If the DS dimension is d, then every function can be written as a combination of monomials that each touch at most d coordinates.

Jane: And that's where the density bound comes from. Tom and I talked about the one-inclusion graph earlier. The density of that graph is what you need to control.

Lu: Right. So here's the trick. For each coordinate, you define a subspace of functions that are "simple" along that coordinate—constant, or linear, or degree at most l−one. The dimension of that subspace is exactly the number of edges in the one-inclusion graph along that direction, capped at l.

Meng: Hold on, let me make sure I'm following. You're counting how many distinct behaviors you see when you fix all coordinates except one?

Lu: Exactly. And then you count how many basis monomials live in that subspace. Those monomials have small degree along that coordinate. The rest have degree at least l. And here's the punchline: each monomial can have large degree in at most d coordinates, because of the spanning lemma.

Tom: So you sum over all coordinates, and the total number of "large degree" incidences is bounded by d times the number of monomials, which is the number of hypotheses.

Lu: Precisely. And that gives you exactly the density bound. The density—the average excess edge size—is at most the DS dimension. No logs, no extra factors, just the clean bound.

Meng: And that's the conjecture from two thousand fourteen?

Lu: That's the conjecture. Daniely and Shalev-Shwartz conjectured exactly this, and it's been open for over a decade. The proof is remarkably short once you have the spanning lemma. It's maybe two pages of algebra.

Jane: And the beauty is that the bound is tight. The paper even gives an example showing the constant is optimal—you can't do better than exactly the DS dimension.

Tom: So the algebra is clean, the bound is tight, and the consequences are immediate. But what does this mean for actually building learning algorithms? That's where I want to push next.

Improvements: Tom: We've got the structural result. Now let's talk about what this paper actually improves in practice. And for that, I want to bring in Meng, because you're the one who has to ship these algorithms.

Meng: Yeah, and honestly, the practical improvement is huge. Before this paper, if you wanted to learn a multiclass problem with DS dimension d, the best known algorithm needed on the order of d to the one point five samples. Now it's just d samples. That's not a log factor, that's a square root.

Jane: And for list learning, the improvement is even more dramatic. The old bounds had these horrible dependencies on the list size l—like l to the sixth power times d to the one point five. This paper gets it down to just d plus log of one over delta, all divided by epsilon. The list size essentially disappears from the sample complexity.

Meng: That's the part that gets me excited. In medical diagnosis, you might want a list of five possible conditions. The old theory said you'd need a huge amount of data just because of that list size. This paper says no—the list size doesn't really hurt you.

Lu: And it's worth emphasizing that the algorithm achieving these bounds is not some impractical oracle. For the multiclass case, it's a majority vote over one-inclusion graph predictors. That's a concrete, implementable procedure.

Meng: Right, and for the list case, they use randomization and a holdout validation set. It's a bit more involved, but still very practical. You train several predictors on prefixes of your data, validate them on a separate set, and pick the best one.

Jane: And the agnostic setting—where the data isn't perfectly labeled by any hypothesis—also gets improved. The paper gets a bound that's optimal up to log factors, with the DS dimension term scaling as one over epsilon and the Natarajan dimension term scaling as one over epsilon squared.

Meng: That matches the lower bound, so it's tight. And the Natarajan dimension is always at most the DS dimension, so the bound is never worse than what you'd get from the old analysis.

Lu: One subtlety I want to flag: the agnostic list learning bound still has that Natarajan dimension term divided by epsilon squared. The paper notes it's not clear whether that term is necessary for list learning when l is greater than one. The lower bound techniques from the single-label case don't directly apply.

Tom: So there's still a small open question there?

Lu: A small one, yes. But the main event—the realizable case—is completely settled. And the agnostic bound is optimal up to log factors, which is a massive improvement over what existed.

Meng: And I appreciate that the paper is honest about that gap. They don't claim more than they prove.

Jane: That's the mark of a good theory paper. It settles the big question and clearly marks what's left.

Tom: So we've got the theory, we've got the algorithms. What does this mean for the field, and for the world? Let's bring in Lalam for the big-picture take.

Conclusion: Tom: We've covered the theorem, the proof, and the algorithmic consequences. Let's wrap up "The Optimal Sample Complexity of Multiclass and List Learning" with the big question: what does this actually change?

Jane: For me, the biggest change is psychological. For over a decade, researchers knew the answer should be linear in the DS dimension, but they couldn't prove it. Now they can. That unlocks a whole line of follow-up work that was blocked.

Lu: Absolutely. Every time a conjecture like this falls, it's like a dam breaking. People will now use this density bound as a tool in other problems. I'm already thinking about how it applies to regression, to active learning, to online learning.

Meng: And on the practical side, the improvement is real. If you're building a system with limited labeled data—say, a medical imaging classifier with rare conditions—the difference between d and d to the one point five samples can be the difference between feasible and infeasible.

Lalam: And I want to push on that. This paper isn't just about making existing systems slightly more efficient. It's about making multiclass learning viable in domains where data is genuinely scarce. Think about endangered species monitoring, where you have a handful of photos per species. Or rare disease diagnosis, where each case is precious. The old bounds said you'd need an impractical amount of data. This paper says the complexity is exactly what you'd hope.

Jane: That's the cultural impact, isn't it? When theory says a problem is hard, it discourages people from even trying. When theory says it's feasible, it invites innovation.

Lalam: Exactly. And there's a deeper point. The paper shows that the right complexity measure—the DS dimension—is not just an abstract curiosity. It's the exact quantity that determines how much data you need. That's a beautiful example of theory guiding practice.

Tom: And it's worth remembering that this all came from a single structural insight. The spanning lemma, the algebraic characterization. One clean idea, and then everything else follows.

Meng: I also want to give credit where it's due. The paper builds directly on the work of Hanneke, Meng, Moran, and Shaeiri. That's how science should work—standing on shoulders.

Jane: And the author, Chirag Pabbaraju, deserves a lot of credit for seeing how to finish the job. The conjecture had resisted a decade of attempts.

Lu: I think the most exciting thing is that this won't be the end. The algebraic approach that worked here is likely to have more mileage. I'd bet we'll see it applied to other open problems in learning theory within the next year.

Tom: So to sum up: this paper proves the optimal sample complexity for multiclass and list learning, resolves a two thousand fourteen conjecture, and gives practical algorithms that match the theory. That's a complete package.

Jane: And with that, we'll say goodbye to "The Optimal Sample Complexity of Multiclass and List Learning." A truly satisfying result.

Tom: Thanks for listening, everyone. Next up on the channel, we've got a paper on efficient transformers that I think you'll all enjoy. See you then.

Chirag Pabbaraju

Stanford University

cs.LG, stat.ML

Submitted: 2026-08-18

Updated: 2026-08-19

Comments: tightened realizable list learning results

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

Key concepts

DS Dimension: The DS dimension, named after Daniely and Shalev-Shwartz, measures the complexity of multiclass problems. It indicates how intricate a hypothesis class is. The paper proves that sample complexity scales linearly with this dimension, resolving a decade-old conjecture that previously suggested a much larger gap between bounds.
List Learning: In list learning, an algorithm outputs a short list of potential labels instead of a single prediction. The algorithm is correct if the true label is included in the list. This is useful for practical applications like medical diagnosis, where providing several possible conditions is more helpful.
Sample Complexity: Sample complexity is the amount of labeled data required to guarantee a machine learning algorithm learns a task effectively. This paper establishes the optimal bounds for multiclass and list learning, proving that the required number of samples scales linearly with the DS dimension.

Terminology

Sample Complexity — 72× in this paper · explained in 15 episodes
List Learning — 43× in this paper · explained in 2 episodes
VC Dimension — 6× in this paper · explained in 2 episodes
Hypergraph — 4× in this paper · explained in 2 episodes
Core — 3× in this paper · explained in 2 episodes
Generalization — 2× in this paper · explained in 13 episodes
Loss Function — 2× in this paper · explained in 2 episodes
Accuracy — 1× in this paper · explained in 1 episode
Active Learning — 1× in this paper · explained in 6 episodes
Benchmark — 1× in this paper · explained in 2 episodes
Symposium on Foundations of Computer Science — 1× in this paper
Transformer — 1× in this paper · explained in 2 episodes

Summary

Summary

This paper resolves a longstanding open conjecture in learning theory, thereby determining the optimal sample complexity of multiclass and list learning.

Main Result

The central contribution is a positive resolution of a conjecture by Daniely and Shalev-Shwartz (2014). The paper proves that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. Formally, the main structural theorem states:

Theorem 1 (Density upper-bounded by DS). Let H ⊆ [k] X be a hypothesis class having l-DS dimension d l DS. For all integers l ≥ 1 and n > 0, ⌈µ l H(n)⌉ ≤ d l DS.

Here, µ l H(n) is the maximum l-density function and d l DS is the l-DS dimension, which are parameterized versions of the standard quantities satisfying µ 1 H(n) = µ H(n) and d 1 DS = d DS. The proof builds upon a recent algebraic characterization of multiclass hypothesis classes by Hanneke et al. (2026), specifically their Spanning Lemma which states that the set of bounded-degree, bounded-support monomials M s l(W) spans the vector space V W for any class W with l-DS dimension at most s. The paper's proof uses this spanning result to construct a basis of monomials and then analyzes direction-wise subspaces U i of functions that are constant on edges in direction i, showing that the dimension of these subspaces equals the sum of min(l, e) over edges, ultimately yielding the density bound.

Corollaries for Multiclass Learning

Realizable multiclass learning (Corollary 1.1): The paper establishes the optimal sample complexity of Θ((d DS + log(1/δ))/ε). Specifically, there exists a learning algorithm A such that for any distribution D realizable by H, with probability at least 1−δ over a sample S ∼ D m where m ≥ 9.64(d DS + log(2/δ))/ε, it holds that err D(f̂ S) ≤ ε. This follows by plugging Theorem 1 into Theorem 2.2 of Aden-Ali et al. (2023), which gives a bound of O((⌈µ H(n)⌉ + log(1/δ))/n). This resolves the gap between the previous upper bound of Õ(d 1.5 DS/ε) from Brukhim et al. (2022) and Hanneke et al. (2024), and the lower bound of Ω(d DS/ε) from Hanneke et al. (2024).
Agnostic multiclass learning (Corollary 1.2): The paper obtains an upper bound of Õ(d DS/ε + d Nat/ε2 + log(1/δ)/ε2), where d Nat is the Natarajan dimension. This improves upon the previous bound of Õ(d real/ε + d Nat/ε2) from Cohen et al. (2025), where d real was unknown at the time. Combined with the lower bound from Cohen et al. (2025), this gives the optimal sample complexity (up to log factors) of Θ̃(d DS/ε + d Nat/ε2 + log(1/δ)/ε2).

Corollaries for List Learning

Realizable list learning (Corollary 1.3): The paper establishes the optimal sample complexity of O((d l DS + log(1/δ))/ε) for l-list learning. This is achieved via a randomized list learner that uses a holdout validation set. The paper first shows a deterministic list learner with sample complexity O(l(d l DS + log(1/δ))/ε) by combining Theorem 1 with the one-inclusion graph list predictor framework (Corollary A.1), and then uses randomization and validation to shave the factor of l. This matches the lower bound of Ω(d l DS/ε) (proven in Appendix A.1.3, which also establishes the log(1/δ)/ε dependence under a label-richness condition).
Agnostic list learning (Corollary 1.4): The paper obtains an improved sample complexity of Õ(ld l DS/ε + l4d l Nat/ε2 + log(1/δ)/ε2), where d l Nat is the l-Natarajan dimension. This improves upon the previous best bound of Õ(l6(d l DS) 1.5/ε2) from Charikar and Pabbaraju (2023). The proof generalizes the results of Cohen et al. (2025) to the list learning setting, using a three-step approach: (1) constructing a finite list cover via compression, (2) running multiplicative weights to obtain a list hypothesis ν, and (3) learning a list-bounded classifier using a compression scheme of size O(l4d l Nat log(p) log(n)).

Key Technical Details

The proof of Theorem 1 uses the algebraic characterization of [HMMS26], which shows that the set of monomials M s l(W) spans the vector space of functions on W. The paper defines subspaces U i of functions that are univariate polynomials of degree at most l−1 in coordinate i when restricted to edges in direction i, and shows dim(U i) = Σ a min(l, e i,a). By counting basis monomials with degree < l at coordinate i versus those with degree ≥ l, the paper derives the density bound.
The paper notes that the bound in Theorem 1 is tight including the constant, as demonstrated by the example H = [k] s × [l] m−s as k → ∞, where d l DS = s and µ l H(m) → s.
The results extend to infinite label spaces (k = ∞) as noted in Remarks 2 and 4, using a compactness argument for the one-inclusion graph orientation.
The paper emphasizes that the main contribution is the structural result in Theorem 1, with the learning results following largely from generalizing pre-existing technical machinery. The paper also notes that the algebraic proof contrasts with classical combinatorial proofs for the binary case, which fail to generalize due to pathologies with the shifting operation for k > 2.

Improvements for AI systems

Based on the scientific paper, here are the specific improvements that can be made to AI systems, particularly in the context of supervised learning, model selection, and learning theory:

1. Optimal Sample Complexity for Multiclass Classification (Realizable Setting)

Improvement: Replace the existing suboptimal sample complexity bound of (d DS 1.5 + (1/delta) over epsilon) with the provably optimal O (d DS + (1/delta) over epsilon).
What the improved AI system can do: Given a multiclass hypothesis class with DS dimension d DS, the system can now achieve a target error epsilon with confidence 1-delta using strictly fewer training samples. This directly reduces the data collection cost and training time for applications like image classification, natural language processing, and speech recognition, where the label space is large. The system no longer wastes samples due to the sqrt d DS overhead.

2. Optimal Sample Complexity for Multiclass Classification (Agnostic Setting)

Improvement: Tighten the agnostic sample complexity from (d DS 1.5 + (1/delta) over epsilon squared) to (d DS over epsilon + d Nat + (1/delta) over epsilon squared), where d Nat is the Natarajan dimension.
What the improved AI system can do: In noisy, real-world datasets (where no perfect classifier exists), the system can now learn with a sample complexity that scales linearly with the DS dimension in the 1/epsilon term, rather than with a power of 1.5. This is particularly beneficial for high-dimensional label spaces, enabling the system to achieve near-optimal excess risk with fewer samples, making it more robust to label noise and distribution shift.

3. Optimal Sample Complexity for List Learning (Realizable Setting)

Improvement: Achieve the optimal sample complexity of O (d DS + (1/delta) over epsilon) for list learning, where the algorithm outputs a list of labels instead of a single label. This removes the previous (d DS) 1.5 barrier and all logarithmic factors.
What the improved AI system can do: For applications requiring high recall (e.g., medical diagnosis, recommendation systems, or drug discovery), the system can now output a shortlist of plausible labels. The improved bound means the system requires fewer labeled examples to guarantee that the correct label is in the list with high probability. This is critical in domains where labeling is expensive and missing the correct answer is costly.

4. Improved Sample Complexity for Agnostic List Learning

Improvement: Reduce the agnostic list learning sample complexity from (6 (d DS) 1.5 + (1/delta) over epsilon squared) to (d DS over epsilon + 4 d Nat + (1/delta) over epsilon squared).
What the improved AI system can do: In noisy environments where the system must output a list of labels, this improvement allows the system to handle larger label spaces and higher noise levels without a prohibitive increase in sample requirements. The system can now efficiently balance the trade-off between list size and accuracy, making it practical for large-scale multi-label prediction tasks.

5. Direct Application to One-Inclusion Graph Predictors

Improvement: The paper proves that the maximum density of the one-inclusion graph is bounded by the DS dimension (Theorem 1). This allows for the direct use of one-inclusion graph predictors with a tight, dimension-dependent error bound.
What the improved AI system can do: The system can now use a simple, deterministic majority-vote predictor over one-inclusion graphs (as described in Corollary 1.1) that is provably optimal. This eliminates the need for complex ensemble methods or computationally expensive hyperparameter tuning to achieve optimal generalization, leading to faster inference and more reliable predictions.

6. Unified Framework for Finite and Infinite Label Spaces

Improvement: The results extend to infinite label spaces (Remark 2 and 4), ensuring the bounds hold even when k = infinity.
What the improved AI system can do: The system can now be applied to open-set classification or regression-like tasks where the number of possible labels is unbounded (e.g., predicting a person's age or a continuous coordinate). The theoretical guarantees remain valid, providing a rigorous foundation for these less-constrained problems.

7. Removal of Logarithmic Factors in Sample Complexity

Improvement: The new bounds eliminate all polylogarithmic factors in the sample complexity for the realizable setting.
What the improved AI system can do: For small sample sizes (e.g., few-shot learning scenarios), the system now has a precise, non-conservative estimate of the number of samples needed. This allows for more efficient use of limited data, avoiding over-provisioning and enabling faster experimentation cycles in research and development.

Summary of System-Level Impact:

An AI system built using these improvements will require significantly less training data to achieve the same accuracy, particularly for multiclass and list learning tasks with large label spaces. It will be more sample-efficient, cost-effective, and robust in both clean (realizable) and noisy (agnostic) settings, while also providing tighter theoretical guarantees that enable more predictable and reliable deployment.

Abstract

While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classification has remained open. The appropriate complexity parameter for multiclass classification is the DS dimension, and despite significant efforts, a gap of sqrt DS has persisted between the upper and lower bounds on sample complexity. Recent work by Hanneke et al. (2026) shows a novel algebraic characterization of multiclass hypothesis classes in terms of their DS dimension. Building up on this, we show that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. This proves a longstanding conjecture of Daniely and Shalev-Shwartz (2014). As a consequence, we determine the optimal dependence of the sample complexity on the DS dimension for multiclass as well as list learning.