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

Alkis Kalavasis, Grigoris Velegkas, Amin Karbasi

Abstract

In this paper, we study the problem of multiclass classification with a bounded number of labels $k$ in the realizable setting. We extend the traditional PAC model in two significant directions: distribution-dependent universal learning rates and learning under data-dependent assumptions via partial concept classes. First, we provide a complete characterization of achievable learning rates for any fixed distribution, revealing a trichotomy: the optimal rate is either exponential, linear, or arbitrarily slow. We identify the complexity measures of the underlying hypothesis class that dictate these rates. Second, we investigate multiclass classification for structured data—such as data on low-dimensional manifolds—using partial concept classes, where functions may be undefined on parts of the input space. We extend PAC learnability to this setting and demonstrate fundamental differences between partial and total concepts.

Introduction

The Probably Approximately Correct (PAC) framework has served as the mathematical foundation for machine learning for decades. However, its standard formulation has two primary limitations: it focuses on worst-case distributions and assumes that hypotheses must be "total"—defined over the entire input space. In practice, data often possesses underlying structure (e.g., images residing on a manifold), and many real-world distributions are significantly easier to learn than the worst-case scenarios predicted by PAC theory.

This research addresses these gaps by extending multiclass learning theory. The authors provide a comprehensive characterization of distribution-dependent (universal) learning rates and establish a framework for the learnability of "partial" concept classes, which better represent structured data environments.

The Trichotomy of Universal Learning Rates

A central contribution of this work is the discovery that universal learning rates—the speed at which a learner improves when the distribution is fixed but unknown—do not exist on a continuous spectrum. Instead, for any given multiclass concept class, the optimal learning rate follows a strict trichotomy:

  1. Exponential Rate ($e^{-n}$): The fastest possible convergence.
  2. Linear Rate ($1/n$): The standard rate for many learnable classes.
  3. Arbitrarily Slow: No fixed rate can be guaranteed; convergence can be slower than any pre-specified function.

This finding is significant because it rules out intermediate rates, such as $1/\sqrt{n}$, in the universal realizable setting. The authors show that these rates are determined by the "infiniteness" of specific combinatorial tree structures within the hypothesis class.

Partial Concept Classes and Structured Data

Traditional theory utilizes total concept classes, where every hypothesis must assign a label to every possible point in the domain $\mathcal{X}$. This is often an unrealistic requirement. For instance, in a medical imaging task, a model only needs to be accurate on biologically plausible images, not on random noise.

Partial concept classes model this by allowing functions to be undefined (denoted by $\star$) on parts of the domain. This framework captures data-dependent assumptions like margin conditions or manifold constraints. A key insight from the paper is the Impossibility of Disambiguation: a partial concept class may be easy to learn (having a finite Natarajan dimension), yet any attempt to "fill in the blanks" to create a total concept class might result in infinite complexity. This proves that partial concepts are fundamentally more expressive and require their own dedicated theoretical treatment.

Methodology

The authors employ several advanced mathematical tools to derive these results:

  • Combinatorial Trees: They extend complexity measures such as Multiclass Littlestone trees and Natarajan-Littlestone (NL) trees. The finiteness of these trees characterizes the transition between exponential, linear, and slow rates.
  • Gale-Stewart Games: To establish upper bounds for universal rates, the learning process is modeled as an infinite game between a Learner and an Adversary. Using tools from descriptive set theory, they prove that if a Learner has a winning strategy, an eventually correct labeling function exists.
  • One-Inclusion Hypergraphs: For partial concepts, the authors adapt the one-inclusion graph algorithm. This transductive learning strategy is shown to be more effective than standard Empirical Risk Minimization (ERM) in these complex settings.
  • Sauer-Shelah-Perles (SSP) Lemma: The researchers prove a new version of this fundamental lemma specifically for partial multiclass concepts to bound the growth of the hypothesis class and determine sample complexity.

Key Results

Characterizing Rates (Theorems 1 & 2)

The paper formally links the universal learning rate trichotomy to tree structures:

  • No infinite Littlestone tree $\implies$ Exponential rate.
  • Infinite Littlestone but no infinite NL tree $\implies$ Linear rate.
  • Infinite NL tree $\implies$ Arbitrarily slow rate.

Learnability of Partial Classes (Theorem 3)

The authors prove that a multiclass partial concept class is PAC learnable if and only if its Natarajan dimension (Ndim) is finite. They provide tight bounds for the sample complexity $M(\epsilon, \delta)$, showing it scales as: $$\tilde{\Theta}\left(\frac{Ndim(H) + \log(1/\delta)}{\epsilon}\right)$$

Suboptimality of ERM

The research reinforces that while ERM is a standard approach, it is often suboptimal when moving beyond basic PAC models. More sophisticated, game-theoretic, or graph-based predictors are necessary to achieve optimal learning rates in universal and partial settings.

Conclusion and Future Work

This work provides a more nuanced understanding of multiclass learnability by moving beyond worst-case, total-concept assumptions. However, several avenues for future research remain. The current analysis is restricted to the realizable setting, where the true labeling function is assumed to exist within the hypothesis class. Extending these universal rates to the agnostic setting—where noise or model misspecification is present—is a critical next step. Additionally, while this paper treats the number of labels $k$ as a constant, exploring the implications of an extremely large or infinite label set remains an open challenge for modern large-scale classification tasks.

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