PaperlayerView exact revision on arXiv

Source-linked AI summary

The Optimal Sample Complexity of Multiclass and List Learning

Chirag Pabbaraju

arXiv:2604.24749v4cs.LGstat.ML

TL;DR

Multiclass sample complexity remained unresolved because prior DS-dimension bounds retained a √dDS gap. Building on an algebraic characterization, the paper proves density is bounded by DS dimension, establishing the conjecture and optimal multiclass and list-learning dependence.

  • Problem

    The optimal sample complexity for multiclass learning in terms of the DS dimension remained open, with a persistent √dDS gap between bounds.

  • Method

    The paper builds on an algebraic characterization of multiclass hypothesis classes to prove a structural density upper bound by the corresponding DS dimension.

  • Results

    Theorem 1 proves that maximum ℓ-density is bounded by ℓ-DS dimension, yielding optimal sample-complexity results for multiclass and list learning.

  • Takeaways & Limitations

    The structural result resolves the longstanding Daniely–Shalev-Shwartz conjecture and removes the DS-dimension barrier in multiclass learning.

  • Takeaways & Limitations

    The paper identifies exploring further consequences of algebraic methods in multiclass and list learning as future work.

Abstract

from arXiv · show

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{\text{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.

1 Introduction

Multiclass sample complexity is governed by the DS dimension, but prior bounds left an extraneous √dDS gap. The paper resolves the underlying density conjecture and derives optimal multiclass-learning consequences.

  • 1 Introduction: Multiclass learning lacks the fully characterized sample complexity known for binary classification, where the VC dimension is optimal.
  • 1 Introduction: Prior multiclass bounds left a dDS^1.5 dependence on the upper-bound side and a corresponding √dDS gap from the lower bound.
  • 1 Introduction: The maximum density function µH(n) provides an alternative sample-complexity bound without logarithmic factors, motivating the conjecture µH(n) ≤ c · dDS.
  • 1 Introduction: The conjecture had remained open despite the binary-case bound and an existing c · dDS · log(k) upper bound.
  • 1.1 Results: Building on a recent structural breakthrough, the paper proves the conjecture and thereby bypasses the dDS^1.5 barrier.
  • 1.1 Results: The structural theorem yields optimal sample-complexity results for realizable multiclass learning and further corollaries for multiclass and list learning.

2 Preliminaries

The preliminaries define PAC and agnostic learning, parameterized DS and Natarajan dimensions, and the one-inclusion graph and density quantities used in the paper’s structural analysis.

  • Learning definitions: PAC learning requires an algorithm to achieve error at most ε with probability at least 1 − δ on realizable distributions.
  • Learning definitions: Agnostic PAC learning instead compares the algorithm’s error with infh∈H errD(h) plus ε for arbitrary distributions.
  • Combinatorial dimensions: The paper parameterizes DS and Natarajan dimensions by list size ℓ, with the ordinary DS dimension obtained when ℓ = 1.
  • One-inclusion graph: The one-inclusion graph represents hypotheses as vertices and groups hypotheses differing only in coordinate i into hyperedges.
  • Density: The maximum ℓ-density function is defined from ℓ-density of finite restrictions of the one-inclusion graph.
  • Terminology: The literature uses differing names and definitions for related density quantities, with discrepancies that can amount to factors of 2 and ℓ + 1.

3 Main Structural Result

The paper uses an algebraic characterization of multiclass hypothesis classes to show that maximum ℓ-hypergraph density is bounded by the ℓ-DS dimension, with the bound tight in its constant. This structural theorem yields density bounds for finite and infinite label spaces and supports optimal learning consequences.

  • Algebraic characterization: The proof builds on a spanning lemma stating that bounded-degree monomials span the function space associated with a multiclass hypothesis class.This algebraic characterization is the key technical input from prior work.
  • Proof strategy: Summing active-coordinate contributions over the monomial basis gives the bound Dens_ℓ(W) ≤ d^ℓ_DS.Each basis monomial has at most d^ℓ_DS active coordinates, which controls the total density.
  • Theorem 1: Theorem 1 establishes that every restricted multiclass hypothesis class W has ℓ-density at most its ℓ-DS dimension.The result applies to every sample restriction and completes the structural bound used later for learning guarantees.
  • Proof strategy: The argument defines direction-wise subspaces whose dimensions are controlled by edge sizes through Vandermonde-matrix ranks.For an edge of size t, the relevant dimension is min(ℓ, t), enabling the density calculation.
  • Extensions: The density upper bound remains valid when the label space is infinite after replacing the finite-label degree restriction with the appropriate coordinate-wise condition.The proof otherwise proceeds unchanged, and an additional compactness argument supplies the required orientation for infinite graphs.
  • Tightness: The constant in Theorem 1 is tight for the class H = [k]^s × [ℓ]^(m−s) as k grows large.This construction shows that the bound cannot be improved even in its leading constant.

4 Concluding Thoughts

The paper highlights that its algebraic route contrasts with classical combinatorial proofs in the binary case and completes a puzzle suggested by prior work. It points to further exploration of algebraic methods in multiclass and list learning.

  • Discussion: The paper’s DS-dimension argument is algebraic, unlike classical binary proofs based on combinatorial techniques such as shifting.In the binary case, DS dimension coincides with VC dimension, but the proof styles differ.
  • Discussion: Prior work speculated that more combinatorial proofs might improve multiclass sample complexity, whereas this paper uses the existing algebraic characterization to complete the result.The paper presents the algebraic characterization itself as the route that resolves the outstanding issue.
  • Future directions: The authors identify further exploration of algebraic methods in multiclass and list learning as a future direction.This is presented as an open avenue rather than a result established by the paper.

A List Learning Results

The list-learning implications rely largely on technical machinery already available in the literature, with the paper supplying the details in a condensed appendix treatment.

  • List-learning implications: Most machinery needed to derive the list-learning implications of Theorem 1 already exists in prior work.The appendix provides the necessary details, but describes them as condensed.

A.1.1 Deterministic List Learner

The deterministic list learner uses one-inclusion graph orientations with bounded leave-one-out error to obtain realizable list-learning guarantees. The construction extends to infinite label spaces with an additional compactness argument.

  • Guarantee: Corollary A.1 gives a deterministic algorithm for any class with ℓ-DS dimension d^ℓ_DS under realizable distributions.The guarantee holds with probability at least 1 − δ and returns a list whose error is at most ε.
  • Deterministic list learner: The deterministic learner constructs a one-inclusion graph on the class projected onto the training and test points, then chooses an orientation minimizing maximum ℓ-outdegree.Each edge is oriented to a subset of at most ℓ hypotheses, whose test-point labels form the prediction list.
  • Generalization argument: The density bound from Theorem 1 controls the predictor’s leave-one-out error and yields the stated learning guarantee through the prior sample-complexity theorem.The proof plugs the DS-based outdegree bound into the existing one-inclusion analysis.
  • Generalization argument: The one-inclusion graph predictor satisfies the symmetry and bounded leave-one-out-error assumptions needed to apply the prior generalization theorem.The loss treats a prediction as incorrect when the true label is absent from the output list.
  • Final predictor: A Top-ℓ vote over predictors trained on increasing sample prefixes produces the final list prediction.If the true label is absent, sufficiently many prefix predictors omit it, which leads to the leave-one-out bound.
  • Infinite label spaces: For infinite label spaces, a compactness argument supplies an ℓ-list orientation with the required outdegree bound, after which the finite-label proof applies unchanged.This is the additional justification needed for the extension.

A.1.2 Randomized List Learner

The randomized list learner samples multiple prefix-trained predictors and uses an independent validation set to select a good one. Randomization and validation amplify confidence while preserving optimal sample complexity.

  • Construction: The randomized learner is obtained by adding randomness and holdout validation to the deterministic list learner.This construction is explicitly designed to achieve optimal sample complexity.
  • Candidate generation: R = O(log(1/δ)) randomly sampled prefixes produce predictors, with at least 1 −δ/3 probability including one with error at most ε/4.The prefixes are sampled uniformly from {n/4, …, n −1}.
  • Candidate selection: An independent validation set empirically benchmarks the predictors to identify the low-error candidate.The validation set is drawn separately from the training data.
  • Candidate selection: v = O(log(R/δ)/ε) validation samples ensure every bad predictor has error greater than ε/2 while the good predictor has error smaller than ε/2, with probability 1 −δ/3.A union bound is applied over the R predictors.
  • Guarantee: The final guarantee holds with probability at least 1 −δ after combining the average-prefix, random-prefix-sampling, and empirical-validation events.The total sample requirement includes the samples used for training prefixes and validation.

A.1.3 Realizable List Learning Lower Bound

The section establishes realizable lower bounds for list learning from DS-shattered sequences, with an improved bound under a label-richness assumption. The proof uses unseen points whose labels cannot reliably fit into an ℓ-label output list.

  • Scope: With the additional label-richness property, the lower bound is strengthened by a factor of ℓ, although it does not apply to every class with ℓ-DS dimension dℓDS.The label-richness condition supplies sufficiently many distinct labels on a shattered sequence.
  • Scope: Without label-richness, the result still rules out a universal improvement of the realizable list-learning upper bound.The weaker conclusion applies to general classes covered by the theorem’s setting.
  • Lower-bound statement: Theorem 2 gives a realizable lower bound for every randomized ℓ-list learner when H has ℓ-DS dimension dℓDS and suitably shatters a sequence of that size.The theorem assumes that H (2ℓ−1)-DS shatters a sequence of size dℓDS.
  • Proof construction: The construction uses a distribution concentrating mass 1 −8ε on one point and distributing 8ε across the remaining shattered points.The same distribution governs both training and test samples.
  • Proof idea: A point absent from the training sample has its true label contained in the learner’s fixed list with probability at most ℓ/2ℓ ≤ 1/2 under (2ℓ−1)-DS shattering.This creates unavoidable prediction error on unseen shattered points.
  • Quantitative consequence: For δ ≤1/8, the resulting argument implies sample complexity at least Ω(d/ε).The bound follows after fixing a hypothesis and comparing the learner’s error on the constructed distribution.

A.2.1 Agnostic List Learning Upper Bound

The agnostic upper-bound proof builds a finite list cover, applies multiplicative weights, and then uses a fractional list learner with an agnostic transductive guarantee before conversion to a PAC learner.

  • Step 1: Approximation by Finite List Cover: A realizable sample is compressed into a subsample of size O(dℓDS log m), and reconstruction produces lists of size O(ℓlog m) covering the sample labels.This yields a finite family of list hypotheses for the first proof step.
  • Final conversion: Sampling O(log m) sequences and combining the resulting samples with validation yields an ℓ-list predictor with small agnostic error.The final construction aggregates the samples used for the fractional learner and for rounding.
  • Step 2: Multiplicative Weights: Multiplicative weights operates on the finite list cover and outputs a menu ν whose list size is O(ℓT log n1).The procedure maintains weights over the cover and updates them across fresh samples.
  • Step 3: Fractional List Learning: The proof’s third step replaces agnostic sample compression with a fractional ℓ-list learner having small agnostic transductive error, followed by conversion to a PAC learner.This is the section’s main deviation from the earlier proof strategy.
  • Fractional predictor: Thinning the version space defines a deterministic fractional ℓ-list predictor supported on ν, with Ct remaining positive and the resulting predictor well-defined.The construction assigns fractional predictions using the retained version-space structure.
  • Guarantee: The fractional predictor’s transductive error is competitive with that of every fixed h ∈H, providing an agnostic transductive guarantee.This guarantee is then used with the cited conversion result to obtain PAC learning.

A.2.2 Agnostic List Learning Lower Bound

The agnostic lower-bound section proves separate hardness terms for confidence and list learning, using hidden-label constructions and KL-based testing arguments. It also gives a class with Natarajan dimension d whose list-learning lower bound scales with ℓd.

  • Theorem statement: Theorem 5 states two agnostic list-learning lower bounds, including one for a class with DS(H) = 1 and another for a class with Nat(H) = d.The theorem allows randomized ℓ-list learners.
  • Hidden-bit construction: The first construction hides a bit in one of two disjoint label sets and uses transcript indistinguishability, with KL divergence unchanged by the learner’s independent randomness.A testing lower bound then controls the probability of estimating the hidden bit incorrectly.
  • Reduction to learning error: The learner’s prediction error is related to the hidden-bit estimator, so an estimator error yields excess error over the best hypothesis in H.The proof compares the learner against a single-label benchmark hypothesis.
  • Natarajan-dimension construction: For the second construction, the hypothesis class has Nat(H) = d, and any d+1 points include two points from one block, preventing ℓ-Natarajan shattering.The block structure enforces a global sign choice within each block.
  • Quantitative consequence: When m ≤ dℓ/32768ε^2, the construction supplies a distribution for which the learner cannot meet the agnostic guarantee.The proof’s final parameter choice also requires M = max(25 log(4)/dε^2, 100m/ε).
Loading 2604.24749v4…