cs.LGNov 9, 2026

Exact Natarajan Dimension of Homogeneous Multiclass Linear Predictors

Authors: Jiahua Liu, Benchong Li

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 n(k−1)−1n(k-1)-1, where nn is the dimension of the feature space and kk is the number of classes, for n,k≥3n,k\ge3, n,k∈Nn,k\in\mathbb N.

Explore similar work

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.
Apr 14, 2026

An Optimal Sauer Lemma Over kk-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 kk-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 k>2k>2. 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 kk, list size ℓ\ell, and dimension value, replacing the exponential dependence on ℓ\ell in the Natarajan-based bound by the optimal polynomial dependence, and improving the dependence on kk 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).
Aug 26, 2026

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 H\mathcal H with DS dimension dDSd_{DS} and Natarajan dimension dNd_{\mathrm N}, the optimal agnostic transductive excess error satisfies Θ~(dDSn+dNn).\widetildeΘ\left(\frac{d_{DS}}{n}+\sqrt{\frac{d_{\mathrm N}}{n}}\right). The result holds for arbitrary label spaces. The two terms are both necessary. A DS pseudo-cube gives the realizable dDS/nd_{DS}/n obstruction, while a Natarajan cube with repeated points and fair labels gives the agnostic dN/n\sqrt{d_{\mathrm N}/n} 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 dDS/nd_{DS}/n term. Consequently, agnostic multiclass PAC and transductive learning obey the same two-dimension law up to logarithmic factors.