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?

  • $\begingroup$ 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. $\endgroup$ – DuttaA Apr 13 '20 at 0:56

I think DuttaA is right in his comment. 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.

  • $\begingroup$ 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? $\endgroup$ – nbro Apr 19 '20 at 12:41
  • $\begingroup$ 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. $\endgroup$ – Dani Apr 20 '20 at 18:34
  • $\begingroup$ I didn't say "fixed", I said "arbitrary". $\endgroup$ – nbro Apr 20 '20 at 18:38
  • $\begingroup$ 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 \}$. $\endgroup$ – Dani Apr 20 '20 at 18:45
  • $\begingroup$ Ok. But then why do you say that "the UAT refers to a class of neural networks with unbounded number of weights."? $\endgroup$ – nbro Apr 20 '20 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.