Marginal-Nonuniform Multiclass Learning
Organizations: Apple · Department of Computer Science, Purdue University · University of Tübingen and Tübingen AI Center · Max Planck Institute for Informatics
Abstract
We study the problem of multiclass classification within the framework of marginal-nonuniform learning, where the constants in the learning rate may depend on the unknown marginal distribution generating the unlabeled data, but not on the target concept. This notion naturally lies between classical PAC learning, where the constants are independent of both the marginal distribution and the target concept, and more recent universal learning, where the constants may depend on both. We give a complete characterization of the optimal marginal-nonuniform learning rates, establishing a fundamental trichotomy: exponential, linear, and arbitrarily slow rates. This characterization is witnessed by a new combinatorial dimension, termed the uncentered DS-eluder dimension. A key ingredient in the upper-bound proofs is a set of new distributional exhaustion lemmas that exploit the sequential nature of this dimension and may be of independent interest.
Figures & tables
Statistical Learning Theory
Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.
See all 631 papers