cs.LGNov 9, 2026
SaveExact Natarajan Dimension of Homogeneous Multiclass Linear Predictors
Organizations: School of Mathematics and Statistics, Xidian University, Xi’an, China
Abstract
The Natarajan dimension is a fundamental measure of the capacity of multiclass hypothesis classes and plays an important role in analyzing their generalization ability. In this paper, by establishing lower and upper bounds, we show that the exact Natarajan dimension of homogeneous multiclass linear predictors with pairwise distinct class weights is , where is the dimension of the feature space and is the number of classes, for , .
More in this topic
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 papersWorst-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 and Daniely-Shalev-Shwartz dimension , the optimal excess risk is known at the two endpoints ( realizable, agnostic [HMZ24, CEH+26, Pab26]) and open in between. We close the gap: at every fixed oracle risk , the optimal excess risk is , uniformly in the alphabet size, attained by a learner that knows neither 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- compression rule that empirically dominates a comparator has population risk at most with , 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 , by a pair-Assouad scheme calibrated to 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 -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 from the known realizable list lower bound.
An Optimal Sauer Lemma Over -ary Alphabets
The Sauer-Shelah-Perles Lemma is a cornerstone of combinatorics and learning theory, bounding the size of a binary hypothesis class in terms of its Vapnik-Chervonenkis (VC) dimension. For classes of functions over a -ary alphabet, namely the multiclass setting, the Natarajan dimension has long served as an analogue of VC dimension, yet the corresponding Sauer-type bounds are suboptimal for alphabet sizes . In this work, we establish a sharp Sauer inequality for multiclass and list prediction. Our bound is expressed in terms of the Daniely--Shalev-Shwartz (DS) dimension, and more generally with its extension, the list-DS dimension -- the combinatorial parameters that characterize multiclass and list PAC learnability. Our bound is tight for every alphabet size , list size , and dimension value, replacing the exponential dependence on in the Natarajan-based bound by the optimal polynomial dependence, and improving the dependence on as well. Our proof uses the polynomial method. In contrast to the classical VC case, where several direct combinatorial proofs are known, we are not aware of any purely combinatorial proof in the DS setting. This motivates several directions for future research, which are discussed in the paper. As consequences, we obtain improved sample complexity upper bounds for list PAC learning and for uniform convergence of list predictors, sharpening the recent results of Charikar et al.(STOC2023), Hanneke et al.(COLT2024), and Brukhim et al.(NeurIPS2024).
Two Dimensions Govern Agnostic Multiclass Transductive Learning
In transductive classification, an adversary fixes a labeled population, one label is hidden uniformly, and the learner sees all remaining labels. For binary classes, agnostic transductive and PAC learning have the same minimax rate. Whether this extends to multiclass learning was open, especially for unbounded label spaces where uniform convergence can fail. We resolve the question up to logarithmic factors. For every multiclass class with DS dimension and Natarajan dimension , the optimal agnostic transductive excess error satisfies The result holds for arbitrary label spaces. The two terms are both necessary. A DS pseudo-cube gives the realizable obstruction, while a Natarajan cube with repeated points and fair labels gives the agnostic obstruction. The upper bound uses a random-reservation principle. The learner deliberately ignores a constant fraction of the visible labels, which makes the true test point uniform in a large unseen block. We combine realizable compression, a label-space reduction, and inside-menu agnostic compression across this finite-population split. A new without-replacement multiplicative-weights lemma preserves the fast term. Consequently, agnostic multiclass PAC and transductive learning obey the same two-dimension law up to logarithmic factors.