OPTIMAL MISTAKE BOUND LEARNING IS HARD

This paper provides evidence that there is no polynomial-time optimal mistake bound learning algorithm. This conclusion is reached via sever al reductions as follows. Littlestone (1988, Math. Learning 2, 285-318 ) has introduced a combinatorial function K from classes to integers a nd has shown that if a subroutine computing K is given, one can constr uct a polynomial-time optimal MB learning algorithm. We establish the reverse reduction. That is, given an optimal MB learning algorithm as a subroutine, one can compute K in polynomial time. Our result combine s with Littlestone's to establish that the two tasks above have the sa me time complexity up to a polynomial. Next, we show that the VC-dimen sion decision problem is polynomially reducible to the K-decision prob lem. Papadimitriou and Yannakakis [PY93] have provided a strong eviden ce that the VC-dimension decision problem is not in P. Therefore, it i s very unlikely that there is a polynomial-time optimal mistake bound learning algorithm. (C) 1998 Academic Press.