2016/02/09 by Tolstikhin, Ilya, Lopez-Paz, David
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.1602.03027
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 H of finite VC-dimension d