Minimax Lower Bounds for Realizable Transductive Classification
Ilya Tolstikhin, David López-Paz · arXiv (Cornell University) · 2016
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