Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes

Alkis Kalavasis, Grigoris Velegkas, Amin Karbasi

In the realm of machine learning theory, the Probably Approximately Correct (PAC) framework serves as the traditional gold standard. It establishes that if a hypothesis class has a finite dimension (such as the VC dimension for binary classification or the Natarajan dimension for multiclass), it can be learned with a sample complexity that scales linearly. However, standard PAC theory is inherently a "worst-case" framework—it assumes the hardest possible data distribution. In practice, algorithms frequently exhibit exponentially better performance or operate on data with specific, helpful structures like margins or low-dimensional manifolds.

This paper builds a more nuanced theoretical foundation for multiclass classification to explain these real-world behaviors. It achieves this by exploring universal learning rates (distribution-dependent learning) and partial concept classes (learning under data-dependent assumptions).

The Limitations of Standard PAC

Standard PAC learning is distribution-independent. It asks: "How many samples are needed to guarantee low error across all possible distributions?" This stringent requirement often yields pessimistic $1/n$ error bounds. However, if we fix a specific target distribution, the error rate might decay much faster. This distribution-dependent perspective is known as the "Universal Learning" setting.

Furthermore, standard theory relies on total concept classes, where every hypothesis must assign a label to every conceivable input in the domain. This rigid assumption fails to capture structured data scenarios where certain inputs might never occur or where a classifier only needs to be defined on a specific manifold. To model this, the authors utilize partial concept classes, where a hypothesis is permitted to return a "don't care" symbol (often denoted as $\star$) for certain inputs.

The central challenge addressed by this work is twofold: Can we precisely characterize when a multiclass problem allows for exponentially fast learning rates? And does introducing "partial" concepts fundamentally alter the requirements for learnability?

Methodology & Complexity Measures

To tackle these questions, the authors employ sophisticated tools bridging combinatorial geometry and game theory:

  1. Gale-Stewart (GS) Games: The learning process is framed as an infinite game between a "Learner" and an "Adversary." If the Learner possesses a winning strategy in this game, it guarantees the existence of an algorithm that eventually stops making mistakes on any realizable data sequence.
  2. Tree-Based Complexity Measures: The authors introduce and extend tree-based dimensions to map out learning rates.
  3. Multiclass Littlestone Trees: These structures are used to characterize the threshold between exponential and linear learning rates.
Illustration of a Littlestone tree structure.
  • Natarajan-Littlestone (NL) Trees: A novel structural measure combining the Natarajan dimension (standard for multiclass) with the Littlestone tree (standard for online learning). The NL tree characterizes the jump from linear to "arbitrarily slow" rates.
Illustration of a Natarajan-Littlestone (NL) tree.
  1. One-Inclusion Hypergraph Algorithm: A standard tool for multiclass learning that the authors successfully adapt to function with partial concepts.
  2. Majority Voting: To achieve optimal exponential rates, the authors split data into batches, train multiple "eventually correct" predictors, and aggregate them via majority vote to sharply accelerate error decay.

Key Findings

The Trichotomy of Universal Rates

The paper establishes a complete characterization of multiclass learning rates for fixed distributions, revealing a strict "trichotomy." For any multiclass concept class, there are only three possible universal regimes:

  • Exponential Rate ($e^{-n}$): Achieved if and only if there is no infinite multiclass Littlestone tree.
  • Linear Rate ($1/n$): Achieved if there is an infinite Littlestone tree, but no infinite NL tree.
  • Arbitrarily Slow Rates: Occurs if and only if there is an infinite NL tree.

Crucially, there is no middle ground between these regimes. A key insight here is the distinction between a class having an unbounded dimension (where for every depth $d$ there exists a tree) versus containing a single infinite tree. Universal learning depends strictly on the latter.

Learnability of Partial Concepts

The authors prove that a partial multiclass concept class is PAC learnable if and only if its Natarajan dimension is finite. While this mirrors the classic result for total classes, the proof is significantly more complex because standard uniform convergence arguments fail for partial classes.

Furthermore, they demonstrate that partial concepts are fundamentally distinct from total concepts. They prove a disambiguation theorem: there exist partial classes with a small, finite Natarajan dimension that cannot be extended to any total class with a finite Natarajan dimension. You cannot simply "fill in the blanks" of a partial concept without potentially blowing up its complexity to infinity.

Algorithm Design Implications

Interestingly, the paper highlights that Empirical Risk Minimization (ERM) is not always optimal in these nuanced settings. Hitting the optimal rates—particularly the exponential ones—requires specialized algorithms derived from game theory and one-inclusion graphs rather than standard ERM.

Limitations and Future Directions

While this work significantly advances multiclass learning theory, it operates entirely within the realizable setting (assuming a perfect hypothesis exists in the class). Extending these universal rate characterizations to the agnostic (noisy) setting remains a major open challenge.

Additionally, the algorithms derived via Gale-Stewart games serve primarily as theoretical existence proofs; they are generally not computationally efficient for high-dimensional, real-world applications. Finally, while the paper bridges much of the gap between binary and multiclass universal learning, some lower bounds for linear rates in the multiclass setting remain slightly less tight than their binary equivalents, suggesting the NL-tree measure may still have room for refinement.

Summary updated

Abstract

In this paper we study the problem of multiclass classification with a bounded number of different labels $k$, in the realizable setting. We extend the traditional PAC model to a) distribution-dependent learning rates, and b) learning rates under data-dependent assumptions. First, we consider the universal learning setting (Bousquet, Hanneke, Moran, van Handel and Yehudayoff, STOC'21), for which we provide a complete characterization of the achievable learning rates that holds for every fixed distribution. In particular, we show the following trichotomy: for any concept class, the optimal learning rate is either exponential, linear or arbitrarily slow. Additionally, we provide complexity measures of the underlying hypothesis class that characterize when these rates occur. Second, we consider the problem of multiclass classification with structured data (such as data lying on a low dimensional manifold or satisfying margin conditions), a setting which is captured by partial concept classes (Alon, Hanneke, Holzman and Moran, FOCS'21). Partial concepts are functions that can be undefined in certain parts of the input space. We extend the traditional PAC learnability of total concept classes to partial concept classes in the multiclass setting and investigate differences between partial and total concepts.
BibTeX
@inproceedings{kalavasis2022multiclass,
  author = {Alkis Kalavasis and Grigoris Velegkas and Amin Karbasi},
  title = {{Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=BDZNGxO_Qy},
}
Figure