# How can neural networks approximate any continuous function but have $\mathcal{VC}$ dimension only proportional to their number of parameters?

Neural networks typically have $$\mathcal{VC}$$ dimension that is proportional to their number of parameters and inputs. For example, see the papers Vapnik-Chervonenkis dimension of recurrent neural networks (1998) by Pascal Koirana and Eduardo D. Sontag and VC Dimension of Neural Networks (1998) by Eduardo D. Sontag for more details.

On the other hand, the universal approximation theorem (UAT) tells us that neural networks can approximate any continuous function. See Approximation by Superpositions of a Sigmoidal Function (1989) by G. Cybenko for more details.

Although I realize that the typical UAT only applies to continuous functions, the UAT and the results about the $$\mathcal{VC}$$ dimension of neural networks seem to be a little bit contradictory, but this is only if you don't know the definition of $$\mathcal{VC}$$ dimension and the implications of the UAT.

So, how come that neural networks approximate any continuous function, but, at the same time, they usually have a $$\mathcal{VC}$$ dimension that is only proportional to their number of parameters? What is the relationship between the two?

• So the definition is that for every $\epsilon$ there exists $N$ width neural network which can approximate to the $\epsilon$ accuracy. It is pretty obvious if $\epsilon = 0$ the width will be infinite. Even definite mathematical series require infinite number of term summations to converege to a function.
– user9947
Apr 13 '20 at 0:56

VC Dimension of Neural Networks establishes VC bounds depending on the number of weights, whereas the UAT refers to a class of neural networks in which the number of weights a particular network can have is not bounded, although it needs to be finite.

I think that we can show, from theorem 2 and the observations below theorem 3 in Approximation by Superpositions of a Sigmoidal Function, that the VC dimension of

$$S=\left\{\sum_{i=1}^N \alpha_i\sigma(y_i^T x + \theta_i) : N\in\mathbb N, \alpha_i, \theta_i \in\mathbb R, y_i\in\mathbb{R}^n \right\}$$

is infinite.

Let $$\{(x_i, y_i)\}_{i=1}^k$$ be a sample of arbitrary size $$k\in\mathbb N$$, and let us see that there is a function in $$S$$ which can correctly classify it, i.e., $$S$$ shatters $$\{x_i\}_{i=1}^k$$.

We note $$B(x, \varepsilon) := \{ y\in\mathbb{R}^n : d(x,y) < \varepsilon \}$$ (this is just standard notation to denote a ball).

First, let $$\varepsilon > 0$$ be such that $$B(x_i, \varepsilon)\cap B(x_j, \varepsilon) = \emptyset$$ every time that $$i \ne j$$.

Now define $$D = \cup_{y_i=1} B(x_i, \varepsilon)$$. Define $$f_{\varepsilon}(x)$$ as in the observations below theorem 3 of Cybenko's paper, and use theorem 2 to find a function $$G(x)$$ in $$S$$ that classifies correctly all points at least $$\varepsilon$$ away from the boundary of $$D$$, i.e., all points in the sample.

• If you look at Cybenko's paper, you will see that the number of weights isn't really unbounded or infinite. The theorem holds for a finite but arbitrary $N$, where $N$ is the number of units in the hidden layer. The question is: in the limit, i.e. as $N \to \infty$, will the neural network have VC dimension $\infty$? Can you prove this from Cybenko's theorem?
– nbro
Apr 19 '20 at 12:41
• Sorry, I can't see that it holds for a fixed $N$. In particular, proof of theorem 1 requires that $S$ is a subspace of $\mathcal C(I_n)$, which I don't think holds if $N$ is fixed. However, defining $S$ to be the set of (finite but arbitrarily large) linear combinations of that form, it is trivially a subspace.
– Dani
Apr 20 '20 at 18:34
• I didn't say "fixed", I said "arbitrary".
– nbro
Apr 20 '20 at 18:38
• Maybe we aren't understanding each other. Originally, I meant that the class of functions for which the UAT applies is $\{ \sum_{i=1}^N \alpha_i \sigma(y_i^T x + \theta_i) : N\in \mathbb{N}, \alpha_i, \theta_i \in \mathbb{R}, y_i\in \mathbb{R}^n \}$.
– Dani
Apr 20 '20 at 18:45
• Ok. But then why do you say that "the UAT refers to a class of neural networks with unbounded number of weights."?
– nbro
Apr 20 '20 at 18:48