When and Why Are Deep Networks Better than Shallow Ones? Hrushikesh Mhaskar,1,2 Qianli Liao,3 Tomaso Poggio3 1 Department of Mathematics, California Institute of Technology, Pasadena, CA, 91125 2 Institute of Mathematical Sciences, Claremont Graduate University, Claremont, CA, 91711 3 Center for Brains, Minds, and Machines, McGovern Institute for Brain Research Massachusetts Institute of Technology, Cambridge, MA, 02139 Abstract While the universal approximation property holds both for hi- erarchical and shallow networks, deep networks can approxi- mate the class of compositional functions as well as shallow networks but with exponentially lower number of training pa- rameters and sample complexity. Compositional functions are obtained as a hierarchy of local constituent functions, where “local functions” are functions with low dimensionality. This theorem proves an old conjecture by Bengio on the role of depth in networks, characterizing precisely the conditions un- de
