New Theory Unifies Multiclass Transductive and PAC Learning Rates

In transductive classification, a learner is given a labeled population where one label is hidden, and they must predict that hidden label using all other visible labels. While it was known that binary class transductive and PAC learning have the same minimax rate, whether this extended to multiclass learning, especially with unbounded label spaces, remained an open question. This research resolves the question, demonstrating that for any multiclass class, the optimal agnostic transductive excess error is governed by two key dimensions: the DS dimension ($d_{DS}$) and the Natarajan dimension ($d_N$). The optimal error rate is shown to be approximately $\widetilde\Theta\left(\frac{d_{DS}}{n}+\sqrt{\frac{d_{\mathrm N}}{n}}\right)$, where 'n' is the number of samples. Both terms are proven to be necessary. The upper bound of this result is achieved using a "random-reservation principle," where the learner strategically ignores a fraction of visible labels. This, combined with techniques like realizable compression and a new multiplicative-weights lemma, ensures the preservation of the fast $d_{DS}/n$ term. Consequently, agnostic multiclass PAC and transductive learning are shown to obey the same two-dimension law, up to logarithmic factors.