  We show that a collection of Gaussian mixture models (GMMs) in $R^{n}$ can be
optimally classified using $O(n)$ neurons in a neural network with two hidden
layers (deep neural network), whereas in contrast, a neural network with a
single hidden layer (shallow neural network) would require at least
$O(\exp(n))$ neurons or possibly exponentially large coefficients. Given the
universality of the Gaussian distribution in the feature spaces of data, e.g.,
in speech, image and text, our result sheds light on the observed efficiency of
deep neural networks in practical classification problems.
