The effect of the choice of neural network depth and breadth on the size of its hypothesis space

A shallow neural network is a universal function approximator, if allowed an unlimited number of neurons in its single hidden layer (Cybenko, 1989; Hornik et al., 1989). Since in theory a shallow network can do anything, what is the advantage of going deep? For one thing, deeper architectures are capable of encoding certain types of functions far more efficiently than their shallow counterparts (Montufar et al., 2014; Szymanski and McCane, 2014; Telgarsky, 2015). The efficiency of function encoding is important for two reasons: - deep learning can tackle problems that may be computationally intractable with the shallow approach; - the fewer trainable parameters in a neural network, the lower the bound on their generalisation error (Vapnik, 1998) due to decreased generic representational power (Anthony and Bartlett, 2009; Bartlett et al., 2017), While the first point is highly relevant for practical purposes, the latter is more interesting from the theoretical point of view. An approximation that can be made to the same level of accuracy with significantly fewer parameters is likely to give better generalisation.