Why do deep neural networks work well?

The universal approximation theorem, as I understand it, states that for any continuous bounded function $$f: X \rightarrow \mathbb{R}$$ with compact domain $$X$$ and any threshold $$\varepsilon$$ there is a perceptron $$N: X \rightarrow \mathbb{R}$$ with a single hidden layer that can approximate the function to the specific threshold:

$$\forall x \in X:\quad \left\| f(x) - N(x) \right\| \le \varepsilon$$

Nevertheless, there are also Taylor and Fourier series expansions. Though deep neural networks seem to work better in, for example, face recognition task.

The universal approximation theorem speaks about shallow neural networks. Also, it's general and doesn't say a lot about the nature of a function to approximate. Is there a mathematical explanation for such success of deep learning (at least, for specific tasks)?

Since you mention the universal approximation theorem, I think that the explanation that you are looking for is one in the framework of approximation theory. In that regard, there are many works, and I will list a couple of them below, that show that deep networks allow for a more efficient approximation than shallow networks.

Let me recall a couple of results and a suitable framework below and at the end I also adress polynomial and Fourier approximation.

1. Approximation theory of feed-forward networks

To understand this better, we need to give a complexity measure to neural networks. Recall that a feed-forward neural network is a function of the form $$\Phi(x) = T_L(\rho(T_{L-1}(\rho(\dots \rho(T_1(x)))))),$$ where $$\rho:\mathbb{R} \to \mathbb{R}$$ is the so-called activation function, which we apply coordinate-wise here. The maps $$T_\ell: \mathbf{R}^{N_{\ell-1}} \to \mathbf{R}^{N_\ell}$$ are affine linear maps, $$N_{\ell-1} \in \mathbb{N}$$, for all $$\ell \in \{1, \dots, L+1\}$$, and $$L$$ is the number of layers. Here $$\Phi$$ is a map from $$N_0$$ to $$N_L$$. In this notation, the number $$N_{\ell}$$ corresponds to the number of neurons in the $$\ell$$'s layer.

In most works on this topic, people now measure the complexity of a network in one of two ways:

1. Count the number of neurons: $$N(\Phi) := \sum_{\ell = 1}^L N_\ell$$.
2. Count the number of parameters: Here, one observes that $$T_\ell = A_\ell(\cdot) + b_\ell$$ for a matrix $$A_\ell$$ and a vector $$b_\ell$$. A way to measure the complexity of the full network is using the number of nonzero entries of both $$A_\ell$$ and $$b_\ell$$: $$W(\Phi) := \sum_{\ell = 1}^L \|A_\ell\|_0 + \|b_\ell\|_0$$. Here $$\|.\|_0$$ denotes the number of nonzero entries of a matrix/vector.

We have now associated a complexity measure to every network. This means we can ask a more nuanced question than the one of the universal approximation theorem.

Neural network approximation theory: Let $$f \in L^\infty(\mathbb R^d)$$ and $$\epsilon>0$$, does there exist a network $$\Phi$$ with $$L$$ layers such that $$\|f-\Phi\|_\infty \leq \epsilon,$$ and how large do $$N(\Phi), W(\Phi)$$ need to be?

2. Power of depth

The beautiful thing about the question above is that for types of functions $$f$$ if $$L$$ is allowed to be large, then for the same accuracy $$\epsilon$$ the numbers of neurons/parameters, $$N(\Phi), W(\Phi)$$, can be significantly smaller than if $$L$$ is small. Let me list a number of results in this direction. This list is certainly not complete.

In all of these papers, some functions are identified which, when approximated with shallow networks, need much higher $$N(\Phi), W(\Phi)$$ than when deep networks are used.

Now there are other advantages of deep networks over shallow networks from an approximation point of view, such as, that shallow networks do not allow for something that people call localized approximation. But I do not want to go into detail on this.

3. Convolutional networks

Let me also make a second point. You ask "Why do deep networks work so well?". Another answer to this question is that they don't. Deep feed-forward networks do not work at all. In virtually every application people use convolutional neural networks. You could, of course, try to approach this problem from an approximation theoretical perspective again. I know of three works that explain the power of depth for CNNs:

The first two works consider quite specific CNN architectures but highlight that deep CNNs yield better approximation rates for some functions than shallow networks. (In the second paper this is not explicit, but it says that every approximation rate from feed-forward networks translates to a similar one for convolutional networks and vice versa. So the aforementioned results for feedforward networks carry over.) The third result does not restrict the architecture, but only shows that for some very specific functions deep convolutional networks are better approximators than shallow ones.

Here a lot more work needs to be done especially relating to understanding the role of pooling.

There are other aspects of deep convolutional networks that potentially make them work well such as, that they introduce invariances which makes them good classifiers. Since this is not approximation theoretical I shall not go into detail here but I want to mention Mallat's original work on this: Understanding Deep Convolutional Networks.

4. Comparisson to polynomials and Fourier series

You also asked for a comparison to polynomial approximation or Fourier approximation. The approximation spaces of these function classes are well known, and one can simply check for which types of functions deep networks yield better approximation rates.

One point is that both polynomials and Fourier series are terrible at approximating functions with discontinuities. For example, in Optimal approximation of piecewise smooth functions using deep ReLU neural networks it was shown that deep networks approximate piecewise n-times differentiable functions essentially as well as n-times differentiable functions. The second point is, that deep networks are very efficient at representing polynomials as famously shown for ReLU networks in Error bounds for approximations with deep ReLU networks. Clearly, if each polynomial can be well approximated, then also sums of polynomials can be approximated, so the approximation rates carry over. Similarly, Approximation properties of a multilayered feedforward artificial neural network shows that certain neural networks are at least as good as polynomial approximation. As for Fourier approximation Deep Neural Network Approximation Theory has some results on how to reapproximate sinusoidal functions.

Many other works show that DNNs are in fact optimal in approximating certain function classes in a certain framework, e.g. Optimal Approximation with Sparsely Connected Deep Neural Networks but also Error bounds for approximations with deep ReLU networks. In this case, they are of course at least as good as polynomials or Fourier series.

In essence, deep networks are in almost all approximation tasks as good as polynomials/Fourier series and in some tasks they are way better.

I would say the key of their success is due to their huge number of parameters, which allows for the modelling of very complex phenomena. Also, neural networks don't care about relationships between the variables being linear (in general, having any predefined pattern) or not

However, I think the key is in the parameters. If you take a neural network with a number of parameters comparable to a linear regression model, it will actually suck!

• Fourier series approximation, as well as Tailor series approximation (polynomial regression), has an infinite number of parameters. All these methods (including ANNs) are designated to approximate specific families of functions, but ANNs work well in face recognition and many other problems, unlike other methods. – Charlie Mar 14 at 14:09
• Yes, those methods have infinitely many parameters, but in practice you never calculate all of them! If you use Fourier series approximation in real life, you will normally use a few parameters per function, since only the first few terms will have a relevant impact. Same goes for Taylor series. Also, both methods require regularity, which neural networks can sometimes ignore. – David Mar 14 at 14:33