# Two Dimensions Govern Agnostic Multiclass Transductive Learning

arXiv: https://arxiv.org/abs/2608.25326 · HTML: https://mlsanity.com/paper/2608.25326/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 16 references that are in the map.
- First posted on arXiv 26 Aug 2026.

## Builds on (most cited first, 11 of 11)

- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023)
- [Blocks: Collaborative and Persistent Augmented Reality Experiences](https://mlsanity.com/paper/1908.02409/) (2019)
- [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026)
- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [Multiclass Transductive Online Learning](https://mlsanity.com/paper/2411.01634/) (2024)
- [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024)
- [Local Regularizers Are Not Transductive Learners](https://mlsanity.com/paper/2502.07187/) (2025)
- [Local Regularization Does Not Characterize Multiclass PAC Learnability](https://mlsanity.com/paper/2607.23449/) (2026)
- [Universal Multiclass Transductive Online Learning](https://mlsanity.com/paper/2605.30479/) (2026)

## Abstract (arXiv)

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.