SOURCE-LINKED INTELLIGENCE

Two Dimensions Govern Agnostic Multiclass Transductive Learning

arXiv · AI, language, vision and robotics · article · Aug 26, 2026 · UTC

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 $\mathcal H$ with DS dimension $d_{DS}$ and Natarajan dimension $d_{\mathrm N}$, the optimal agnostic transductive excess error satisfies $\widetildeΘ\left(\fra

Read original source ↗ Open in workspace

recordType

paper

region

Global