# Minimax Lower Bounds for Realizable Transductive Classification

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2016.

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

- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Non-Parametric Representation Learning with Kernels](https://mlsanity.com/paper/2309.02028/) (2023)
- [Transductive Robust Learning Guarantees](https://mlsanity.com/paper/2110.10602/) (2021)
- [Can semi-supervised learning use all the data effectively? A lower bound perspective](https://mlsanity.com/paper/2311.18557/) (2023)
- [Robust Graph Structure Learning with the Alignment of Features and Adjacency Matrix](https://mlsanity.com/paper/2307.02126/) (2023)
- [Even Sharper Bounds for Transductive Learning and Its Applications](https://mlsanity.com/paper/2609.28459/) (2026)

## Abstract (arXiv)

Transductive learning considers a training set of m labeled samples and a test set of u unlabeled samples, with the goal of best labeling that particular test set. Conversely, inductive learning considers a training set of m labeled samples drawn iid from P(X,Y), with the goal of best labeling any future samples drawn iid from P(X). This comparison suggests that transduction is a much easier type of inference than induction, but is this really the case? This paper provides a negative answer to this question, by proving the first known minimax lower bounds for transductive, realizable, binary classification. Our lower bounds show that m should be at least Omega(d/ε + log(1/δ)/ε) when ε-learning a concept class H of finite VC-dimension d<∞ with confidence 1-δ, for all m ≤ u. This result draws three important conclusions. First, general transduction is as hard as general induction, since both problems have Omega(d/m) minimax values. Second, the use of unlabeled data does not help general transduction, since supervised learning algorithms such as ERM and (Hanneke, 2015) match our transductive lower bounds while ignoring the unlabeled test set. Third, our transductive lower bounds imply lower bounds for semi-supervised learning, which add to the important discussion about the role of unlabeled data in machine learning.