| Efficient Learning Algorithms Yield Circuit (2008) | |||||||||||||
Abstract | |||||||||||||
| For C equal to polynomial-size, depth-two threshold circuits (i.e., neural networks with a polynomial number of hidden nodes), our result shows that efficient learning algorithms for this class would solve one of the most challenging open problems in computational complexity theory: proving the existence of a function in EXPNP or BPEXP that cannot be computed by circuits from C. We are not aware of any representationindependent hardness results for learning polynomial-size neural networks. Our approach uses the framework of the breakthrough result due to Kabanets and Impagliazzo showing that derandomizing BPP yields non-trivial circuit lower bounds. 1 Introduction Discovering the limits of efficient learnability remains an important challenge incomputational learning theory. Traditionally, computational learning theorists have reduced problems from computational complexity theory or cryptographyto learning problems in order to better understand the difficulty of various classification tasks. There are two lines of research in learning theory in this direction. First, severalresearchers have shown that properly PAC learning well-known concept classes 2 (i.e. learning with the requirement that the output hypothesis be of the sameform as the concept being learned) such as DNF formulas, finite automata, or intersections of halfspaces is NP-hard with respect to randomized reductions [1;2; 3]. | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||