Minimax Lower Bounds for Realizable Transductive Classification
This addresses a foundational question in machine learning theory about the difficulty of transduction versus induction, with implications for semi-supervised learning, though it is incremental in providing lower bounds.
The paper tackles the problem of determining whether transductive learning is easier than inductive learning by proving the first minimax lower bounds for realizable transductive binary classification, showing that m must be at least Ω(d/ε + log(1/δ)/ε) for learning a concept class with VC-dimension d.
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 $Ω(d/ε+ \log(1/δ)/ε)$ when $ε$-learning a concept class $\mathcal{H}$ of finite VC-dimension $d<\infty$ with confidence $1-δ$, for all $m \leq u$. This result draws three important conclusions. First, general transduction is as hard as general induction, since both problems have $Ω(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.