# Is Transductive Learning Equivalent to PAC Learning?

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 42 references that are in the map.
- First posted on arXiv 8 May 2024.

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

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions](https://mlsanity.com/paper/2304.11059/) (2023)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis](https://mlsanity.com/paper/2102.05077/) (2021)
- [When are epsilon-nets small?](https://mlsanity.com/paper/1711.10414/) (2017)

## Built on by (most cited first, 4 of 4)

- [An Optimal Agnostic PAC Algorithm](https://mlsanity.com/paper/2608.06363/) (2026)
- [PAC Learning is just Bipartite Matching (Sort of)](https://mlsanity.com/paper/2502.00607/) (2025)
- [A One-Inclusion Graph Approach to Multi-Group Learning](https://mlsanity.com/paper/2603.23208/) (2026)
- [Two Dimensions Govern Agnostic Multiclass Transductive Learning](https://mlsanity.com/paper/2608.25326/) (2026)

## Abstract (arXiv)

Much of learning theory is concerned with the design and analysis of probably approximately correct (PAC) learners. The closely related transductive model of learning has recently seen more scrutiny, with its learners often used as precursors to PAC learners. Our goal in this work is to understand and quantify the exact relationship between these two models. First, we observe that modest extensions of existing results show the models to be essentially equivalent for realizable learning for most natural loss functions, up to low order terms in the error and sample complexity. The situation for agnostic learning appears less straightforward, with sample complexities potentially separated by a frac1ε factor. This is therefore where our main contributions lie. Our results are two-fold: 1. For agnostic learning with bounded losses (including, for example, multiclass classification), we show that PAC learning reduces to transductive learning at the cost of low-order terms in the error and sample complexity via an adaptation of the reduction of arXiv:2304.09167 to the agnostic setting. 2. For agnostic binary classification, we show the converse: transductive learning is essentially no more difficult than PAC learning. Together with our first result this implies that the PAC and transductive models are essentially equivalent for agnostic binary classification. This is our most technical result, and involves two steps: A symmetrization argument on the agnostic one-inclusion graph (OIG) of arXiv:2309.13692 to derive the worst-case agnostic transductive instance, and expressing the error of the agnostic OIG algorithm for this instance in terms of the empirical Rademacher complexity of the class. We leave as an intriguing open question whether our second result can be extended beyond binary classification to show the transductive and PAC models equivalent more broadly.