Source-linked AI summary
Multiclass learnability and the ERM principle
Amit Daniely, Sivan Sabato, Shai Ben-David, Shai Shalev-Shwartz
TL;DR
The paper asks how multiclass learnability and sample complexity depend on the learning setting and on the choice of ERM learner. It develops ERM-selection principles and dimension-based analyses, showing learner-dependent PAC behavior, tight Natarajan-dimension results in specified cases, and online and bandit characterizations. It also identifies an unresolved gap in bandit sample-complexity characterization and conjectures an extension beyond symmetric classes.
Problem
Multiclass sample complexity is less completely understood than the binary case, including whether learnability and uniform convergence coincide and how ERM choice affects guarantees.
Method
The paper analyzes PAC, online, and bandit multiclass learning using ERM-dependent growth quantities, symmetric-class structure, and new generalizations of Littlestone’s dimension.
Results
Some ERM learners can outperform others or learn when others fail; PAC sample complexity is characterized by Natarajan dimension in three specified cases, while online and bandit realizable bounds are tight.
Takeaways & Limitations
ERM design matters in multiclass learning, and symmetric classes admit tight sample-complexity guarantees based on the Natarajan dimension.
Takeaways & Limitations
Bandit upper and lower bounds can differ by Ω(ln(k) · k), and the paper states that Natarajan dimension alone cannot tightly characterize bandit sample complexity.
Abstract
from arXiv · showhide
We study the sample complexity of multiclass prediction in several learning settings. For the PAC setting our analysis reveals a surprising phenomenon: In sharp contrast to binary classification, we show that there exist multiclass hypothesis classes for which some Empirical Risk Minimizers (ERM learners) have lower sample complexity than others. Furthermore, there are classes that are learnable by some ERM learners, while other ERM learners will fail to learn them. We propose a principle for designing good ERM learners, and use this principle to prove tight bounds on the sample complexity of learning {\em symmetric} multiclass hypothesis classes---classes that are invariant under permutations of label names. We further provide a characterization of mistake and regret bounds for multiclass learning in the online setting and the bandit setting, using new generalizations of Littlestone's dimension.
1 Introduction
The paper examines why multiclass learnability is less fully characterized than binary learnability, focusing on PAC, online, and bandit settings. It shows that ERM choice can affect PAC sample complexity and gives tight results for important classes and models.
- Problem Setting: Multiclass learning theory is less complete than binary theory, motivating the study of sample complexity for hypothesis classes H.The learner maps instances from X to labels in Y and seeks an accurate predictor from H.
- PAC Learnability: Uniform convergence is not equivalent to multiclass learnability, and some multiclass problems are learnable by some ERM learners but not others.This contrasts with the established binary-classification relationship between learnability, uniform convergence, and ERM learning.
- PAC Learnability: Some classes have good and bad ERM learners whose sample complexities differ by Θ(ln(k)), while for infinite k some ERM learners learn classes that others fail to learn.The worst ERM learner’s realizable sample complexity is characterized by the graph dimension.
- PAC Learnability: Algorithm-dependent growth-function quantities are proposed to bound the sample complexity of specific ERM learners rather than all ERM learners uniformly.The motivation is that classical uniform upper-bound quantities cannot tightly characterize multiclass sample complexity.
- PAC Learnability: For three PAC scenarios, including symmetric hypothesis classes and ERMs with limited label usage, sample complexity is fully characterized by the Natarajan dimension.Symmetric classes are invariant under renaming class labels; the paper conjectures a corresponding result for non-symmetric classes.
- Online and Bandit Models: Two generalizations of Littlestone’s dimension characterize multiclass learnability in the online and bandit models, with tight bounds in the realizable case.The paper distinguishes batch versus online interaction and full-information versus bandit feedback.
2 Problem Setting and Notation
The paper formalizes multiclass prediction through domains, labels, hypotheses, empirical error, and PAC sample-complexity notions. It distinguishes optimal learning guarantees from guarantees applying to every ERM learner.
- Basic Definitions: A multiclass hypothesis class H consists of functions mapping an instance space X to a discrete label space Y, with k = |Y| possibly infinite.For a distribution D, Err_D(f) is the probability that f(x) differs from y, and Err_D(H) is the best error achievable within H.
- ERM Learners: An ERM learner returns, for every training sample, a hypothesis in H minimizing empirical error on that sample.Formally, Err_S(A(S)) = min_f∈H Err_S(f).
- PAC Setting: The PAC learning model evaluates predictors by their population error under i.i.d. samples from a distribution over X × Y.The goal is a high-probability predictor whose error is at most as large as the best hypothesis error plus the permitted excess error.
- Sample Complexity: Agnostic sample complexity concerns learning relative to the best hypothesis in H without assuming realizability, while agnostic ERM complexity guarantees performance for any ERM learner.The definitions state that m_PAC ≤ m_ERM, with analogous notation for agnostic learning.
- Sample Complexity: A distribution is realizable by H when some hypothesis in H has zero error, and realizable sample complexity measures the samples needed for the required accuracy and confidence.The definitions separately distinguish the best achievable algorithm, the class guarantee, and the guarantee over ERM learners.
- Assumptions: The presentation assumes X and Y are countable to avoid measurability issues.This is an explicit technical assumption of the formal setting.
3 Uniform Sample Complexity Bounds for ERM Learners
This section develops multiclass sample-complexity bounds using Natarajan and graph dimensions, contrasting them with binary ERM behavior. It establishes necessity and sufficiency results for learnability and presents an improved realizable-case upper bound.
- Binary ERM learners have comparable sample complexity up to a multiplicative factor of ln(1/ϵ).
- The graph and Natarajan dimensions generalize VC dimension by requiring different multiclass behaviors across every partition of a set.
- Natarajan dimension finiteness is necessary for multiclass learnability, while graph dimension finiteness is sufficient.
- For finite label sets, Natarajan dimension finiteness is both necessary and sufficient for learnability.
- Natarajan and graph dimensions characterize multiclass sample complexity up to a multiplicative factor of O(ln(k) ln(1/ϵ)).
- An improved upper bound provides tighter dependence on ϵ for the realizable case.
4 PAC Sample Complexity with ERM Learners
In multiclass PAC learning, ERM learners can have sharply different sample complexities, including learnability for some ERMs but failure for others. The paper proposes controlling the hypotheses an ERM considers and proves near-tight Natarajan-dimension bounds for several class families, especially symmetric classes.
- ERM-dependent sample complexity: Different ERM learners can have very different multiclass sample complexities, and some classes are learnable by one ERM but not another.This contrasts with the binary setting described by the paper.
- ERM-dependent sample complexity: In the constructed class H_X, d_N(H_X)=1 while d_G(H_X)=|X| for finite X and d_G(H_X)=∞ for infinite X.This dimension gap supports a correspondingly large gap between ERM learners.
- Design principle for ERMs: A good ERM considers only a small number of hypotheses for each target, unlike a bad ERM that may need to reject many hypotheses.In the example, A_good returns at most f_A or f_∅, whereas A_bad may return every function when the target is f_∅.
- Design principle for ERMs: The essential range yields improved bounds for ERMs, including algorithms that never output labels absent from the sample.For such learners, the essential range is bounded by the number of observed labels, and the example gives A(m)=2m.
- Symmetric classes: For symmetric hypothesis classes, the Natarajan dimension characterizes optimal sample complexity up to logarithmic factors.Symmetry means closure under permutations of label names; the paper constructs an ERM with realizable essential range at most 4d_N(H)+2.
- Symmetrization: With no prior label knowledge and balanced frequencies, classes with d_N(H)≤C_αk can have approximation error at least 1−α after random label symmetrization.The probability of this conclusion is at least 1−o(2^-k).
5 Other learning settings
The paper characterizes multiclass learnability in online and bandit settings using generalized Littlestone dimensions, obtaining tight realizable mistake bounds and multiclass regret guarantees while identifying remaining gaps.
- Online learning: The paper generalizes Littlestone dimension from binary to multiclass hypothesis classes through shattered trees with differently labeled outgoing edges.A tree is shattered when every root-to-leaf label sequence is realized by some function in H.
- Online learning: The multiclass Littlestone dimension characterizes worst-case realizable online mistakes: SOA makes at most L-Dim(H), matching the deterministic lower bound.Randomized algorithms still require at least L-Dim(H)/2 mistakes on the worst sequence.
- Agnostic online learning: In agnostic online multiclass learning, generalized Littlestone dimension characterizes the optimal regret bound via learning with expert advice.The construction replaces one expert per hypothesis with a more compact dimension-controlled expert set.
- Bandit learning: Bandit sample complexity is learnable exactly when the Natarajan dimension is finite, but current upper and lower bounds can differ by Ω(ln(k) · k).Classes with equal Natarajan dimension can nevertheless have bandit sample complexities differing by Ω(k), so tighter characterization remains open.
- Bandit learning: The bandit Littlestone dimension exactly characterizes realizable bandit mistakes for deterministic algorithms, with both matching lower and upper bounds of L.Bandit feedback reveals only whether the prediction was correct, so the relevant dimension can exceed the full-information dimension.
6 Discussion
The discussion places the multiclass results in the broader general learning framework and emphasizes that learnability need not coincide with uniform convergence or determine a unique ERM learner. It also identifies conjectures and open questions about extending the symmetric-class guarantees and closing ERM gaps.
- General learning framework: The general learning framework treats a problem as a hypothesis class, data domain, and loss function, with the learner minimizing expected loss from a sample.Multiclass classification is recovered by taking Z = X × Y and 0–1 loss.
- Open questions: Selecting among ERM learners remains fundamental because different ERM learners for the same multiclass problem can have large sample-complexity gaps.The discussion connects this issue to the broader question of identifying optimal learning procedures.
- General learning framework: The framework also includes regression with squared loss, k-means, and density estimation.These examples instantiate different hypothesis spaces and loss functions within the same abstract formulation.
- Learnability and uniform convergence: For binary classification and regression, uniform convergence classically implies and follows from learnability, but the paper shows this equivalence fails for multiclass classification.The discussion presents the multiclass result as another example where learnability does not imply uniform convergence.
- Open questions: The paper conjectures that the upper bound proved for symmetric classes extends to nonsymmetric classes, but existing ERM results cannot establish it.A proof would require new learning rules rather than uniform convergence alone.