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

Nov 9, 2026

Agnostic Marginal-Nonuniform Learning

We study the problem of binary classification in the marginal-nonuniform learning framework in the agnostic setting. In this model, the constants in the learning rate may depend on the marginal distribution of the unlabeled data, but the guarantee must hold uniformly over all conditional distributions of the labels. We also study fine-grained rates. We consider two criteria. (1) The standard agnostic setting, where the learner competes with the best concept in the class. In this setting, an immediate consequence of standard agnostic PAC learning results gives us the optimal rate of 1n\tfrac{1}{\sqrt{n}} for every class H\mathcal{H} with finite VC(H)\mathrm{VC}(\mathcal{H}) and shows that arbitrarily slow rates are necessary otherwise. This also gives us the optimal fine-grained rate of VC(H)n\sqrt{\tfrac{\mathrm{VC}(\mathcal{H})}{n}}. Therefore, the dependence on the marginal distribution does not help, which is in contrast to the realizable setting. (2) In the relaxed agnostic setting, where the learner competes with (1+λ)(1+λ) times the error of the best concept for a fixed λ∈(0,1]λ\in (0,1], the picture from the realizable setting reappears. We obtain a trichotomy of the achievable optimal rates: exponential rates of the form e−ne^{-n} arise precisely when the class is finite; linear rates of the form 1n\tfrac{1}{n} arise when the class is infinite but VC(H)\mathrm{VC}(\mathcal{H}) is finite; and arbitrarily slow rates occur when VC(H)=∞\mathrm{VC}(\mathcal{H})=\infty. We also obtain the optimal fine-grained rate of uVCE(H)λn\tfrac{\mathrm{uVCE}(\mathcal{H})}{λn}, where uVCE(H)\mathrm{uVCE}(\mathcal{H}) is a recently introduced combinatorial complexity dimension called the uncentered VC\mathrm{VC}-eluder dimension.
Aug 11, 2026

Optimistic Rates for Multiclass PAC Learning

Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension dNd_N and Daniely-Shalev-Shwartz dimension dDSd_{DS}, the optimal excess risk is known at the two endpoints (dDS/nd_{DS}/n realizable, dN/n+dDS/n\sqrt{d_N/n}+d_{DS}/n agnostic [HMZ24, CEH+26, Pab26]) and open in between. We close the gap: at every fixed oracle risk L⋆L^\star, the optimal excess risk is Θ~(L⋆dN/n+dDS/n)\widetildeΘ(\sqrt{L^\star d_N/n}+d_{DS}/n), uniformly in the alphabet size, attained by a learner that knows neither L⋆L^\star nor the confidence level. The upper bound composes the cover-menu-compression architecture of [CEH+26], at the realizable rate of [Pab26], with a new comparator-facing relative compression theorem: a size-kk compression rule that empirically dominates a comparator hh has population risk at most L(h)+O(L(h)Γ+Γ)L(h)+O(\sqrt{L(h)Γ}+Γ) with Γ=(klog⁡n+log⁡(1/δ))/nΓ=(k\log n+\log(1/δ))/n, without stability; this transfers the comparison principle of the sharp binary theory [MQZ26] while discarding its Boolean-cube geometry, which does not lift to multiclass labels. The lower bound forces both terms using one class and one distribution at every fixed L⋆L^\star, by a pair-Assouad scheme calibrated to L⋆L^\star and a fiber argument on the pseudo-cubes underlying the Natarajan-versus-DS separation of [BCD+22]. Both theorems extend to list learning: against the best rr-tuple of hypotheses, the same architecture and the same two engines yield an optimistic rate and a lower bound of the same shape, forcing the fluctuation term that [Pab26] expected to be necessary against list comparators, and removing the factor rr from the known realizable list lower bound.
May 18, 2026

Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers

Noise-tolerant PAC learning of linear models has been of central interests in machine learning community since the last century. In recent years, many computationally-efficient algorithms have been proposed for the problem of learning linear threshold functions under multiple noise models. Yet, when the problem is considered under multiclass learning settings, i.e. when the number of classes kk is at least 33, it is unknown whether there exist computationally-efficient PAC learning algorithms when the data sets are maliciously corrupted. In this paper, we consider that the marginal distribution is a mixture of bounded variance distributions and the data sets satisfy a margin condition at the same time. We show that there exists a computationally-efficient algorithm that PAC learns multiclass linear classifiers {hw:x↦arg⁡max⁡y∈[k]wy⋅x,x∈Rd,w∈Rkd}\{h_w:x\mapsto \arg\max_{y\in[k]}w_y\cdot x, x\in \mathbb{R}^d, w\in\mathbb{R}^{kd}\} using at most O(k2⋅(dlog⁡d+log⁡k))O(k^2\cdot (d\log d+\log k)) samples even under a constant rate of nasty noise. Our algorithm consists of two main ingredients: a cluster-based pruning scheme and a standard multiclass hinge loss minimization program. Even in the special case of binary setting, i.e. k=2k=2, our result is strictly stronger than all prior works.