arXiv:2611.12058 · v1

Exact Natarajan Dimension of Homogeneous Multiclass Linear Predictors

首次提交 2026-11-09 16:33

版本更新 2026-11-09 16:33

雷达观测 2026-11-10 15:22

摘要

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)-1\), where $n$ is the dimension of the feature space and $k$ is the number of classes, for \(n,k\ge3\), \(n,k\in\mathbb N\).

作者备注：9 pages