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

CardsList
  1. Optimistic Rates for Multiclass PAC Learning

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

  2. An Optimal Sauer Lemma Over kk-ary Alphabets

    Apr 14, 2026Steve Hanneke, Qinglin Meng, Shay Moran +1Multiclass ClassificationGeneralization Bounds