cs.LGNov 6, 2026

Marginal-Nonuniform Multiclass Learning

Authors: Nataly Brukhim, Steve Hanneke, Amirreza Shaeiri, Maximilian Thiessen

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

Explore similar work

CardsList
  1. Agnostic Marginal-Nonuniform Learning

    Nov 9, 2026Tanmay Devale, Steve Hanneke, Amirreza ShaeiriAgnostic Learning

  2. Optimistic Rates for Multiclass PAC Learning

    Aug 11, 2026Xiaoyu Li, Andi Han, Jiaojiao Jiang +1Sample CompressionMulticlass Classification