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 mathcal H with DS dimension dDS and Natarajan dimension dmathrm N, the optimal agnostic transductive excess error satisfies widetildeThetaleft(fracdDSn+√fracdmathrm Nnright). The result holds for arbitrary label spaces. The two terms are both necessary. A DS pseudo-cube gives the realizable dDS/n obstruction, while a Natarajan cube with repeated points and fair labels gives the agnostic √dmathrm 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/n term. Consequently, agnostic multiclass PAC and transductive learning obey the same two-dimension law up to logarithmic factors.