Answers.Body: <p><a href="http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf" rel="nofollow noreferrer">VC Dimension of Neural Networks</a> 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.</p>
  <p>I think that we can show, from <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&amp;rep=rep1&amp;type=pdf#page=6" rel="nofollow noreferrer">theorem 2</a> and the observations below <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&amp;rep=rep1&amp;type=pdf#page=7" rel="nofollow noreferrer">theorem 3</a> in <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Approximation by Superpositions of a Sigmoidal Function</a>, that the VC dimension of</p>
  <p><span class="math-container">$$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\}$$</span></p>
  <p>is infinite.</p>
  <p>Let <span class="math-container">$\{(x_i, y_i)\}_{i=1}^k$</span> be a sample of arbitrary size <span class="math-container">$k\in\mathbb N$</span>, and let us see that there is a function in <span class="math-container">$S$</span> which can correctly classify it, i.e., <span class="math-container">$S$</span> shatters <span class="math-container">$\{x_i\}_{i=1}^k$</span>.</p>
  <p>We note <span class="math-container">$B(x, \varepsilon) := \{ y\in\mathbb{R}^n : d(x,y) &lt; \varepsilon \}$</span> (this is just <a href="https://en.wikipedia.org/wiki/Ball_(mathematics)" rel="nofollow noreferrer">standard notation to denote a ball</a>).</p>
  <p>First, let <span class="math-container">$\varepsilon &gt; 0$</span> be such that <span class="math-container">$B(x_i, \varepsilon)\cap B(x_j, \varepsilon) = \emptyset$</span> every time that <span class="math-container">$i \ne j$</span>.</p>
  <p>Now define <span class="math-container">$D = \cup_{y_i=1} B(x_i, \varepsilon)$</span>. Define <span class="math-container">$f_{\varepsilon}(x)$</span> as in <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&amp;rep=rep1&amp;type=pdf#page=7" rel="nofollow noreferrer">the observations below theorem 3 of Cybenko's paper</a>, and use <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&amp;rep=rep1&amp;type=pdf#page=6" rel="nofollow noreferrer">theorem 2</a> to find a function <span class="math-container">$G(x)$</span> in <span class="math-container">$S$</span> that classifies correctly all points at least <span class="math-container">$\varepsilon$</span> away from the boundary of <span class="math-container">$D$</span>, i.e., all points in the sample.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T12:41:02.553Z
Answers.Text: 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?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T18:34:37.773Z
Answers.Text: 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.
Answers.UserDisplayName: Dani
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T18:38:27.930Z
Answers.Text: I didn't say "fixed", I said "arbitrary".
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T18:45:23.937Z
Answers.Text: 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 \}$.
Answers.UserDisplayName: Dani
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T18:48:23.793Z
Answers.Text: Ok. But then why do you say that "the UAT refers to a class of neural networks with _unbounded_ number of weights."?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T18:53:02.827Z
Answers.Text: I meant that the number of weights that a function in the class can have is not bounded, i.e., it contains functions with arbitrarily large number of weights. I will edit the answer to be more clear.
Answers.UserDisplayName: Dani
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T19:48:16.737Z
Answers.Text: Ok, but your answer still doesn't really try to clarify the relationship between the two, apart from saying that in the case of UAT the number of hidden units can be arbitrarily big and that the VC dimension depends on the number of weights. I already knew this. I wanted to understand more. I wanted to see a formal proof that relates the two. Maybe I should have been more explicit, in fact. I realise now that my question wasn't clear enough.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T16:21:56.553Z
Answers.Text: So, let me try to understand what you're trying to show here. You have $S$, which is a set of functions or, more precisely, the hypothesis class of a neural network. You have some labeled dataset of arbitrary size. You want to show that we can find a function in $S$ that approximates the function represented by the labeled dataset (which you denote, at the end of your answer, as $G(x)$, like in Cybenko's paper). So, **1.** you define some _ball_ (question 1: intuitively, why do you do this?).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T16:22:15.667Z
Answers.Text: Then **2.** you let $\epsilon$ be such that the balls of different inputs do not intersect (question 2: why do you do this?). Then **3.** you define the unions of all balls, i.e. $D$ (question 3: why do you do this? I suppose this is related to Cybenko's proof, which I don't recall anymore, but it would be nice if you can provide more details here about these choices in the proof, so that this answer self-contained; ideally, it would be nice if you recalled Cybenko's proofs or theorems, before proceeding to your theorem and proof).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T16:26:59.407Z
Answers.Text: Then **4.** you say that we should define $f_\epsilon(x)$ in some way and then find $G(x)$ in $S$ as described theorem 2. Then **5.** you **claim** that $G(x)$ can correctly classify all points $\epsilon$-away from the boundary of $D$, i.e. I suppose inside $D$, which you defined as the union of all balls.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T16:30:15.263Z
Answers.Text: However, how is this related to my original question "_how come that neural networks approximate any continuous function, but, at the same time, they usually have a VC dimension that is only proportional to their number of parameters?_"? How is your proof intuitively related to this? Is this because $k$ is arbitrary? I don't see how the VC dimension of neural networks is involved in your proof. I don't see how you're showing that the VC dimension of $S$ (the neural network) is infinite here.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T02:29:43.743Z
Answers.LastActivityDate: 2021-06-21T22:17:28.933Z
Answers.LastEditDate: 2021-06-21T22:17:28.933Z
Answers.UserDisplayName: Dani
Body: <p>Neural networks typically have <span class="math-container">$\mathcal{VC}$</span> dimension that is proportional to their number of parameters and inputs. For example, see the papers <a href="https://www.sciencedirect.com/science/article/pii/S0166218X98000146" rel="nofollow noreferrer">Vapnik-Chervonenkis dimension of recurrent neural networks</a> (1998) by Pascal Koirana and Eduardo D. Sontag and <a href="http://mathsci.kaist.ac.kr/~nipl/mas557/VCD_ANN_3.pdf" rel="nofollow noreferrer">VC Dimension of Neural Networks</a> (1998) by Eduardo D. Sontag for more details.</p>
  
  <p>On the other hand, the universal approximation theorem (UAT) tells us that neural networks can approximate <strong>any</strong> continuous function. See <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Approximation by Superpositions of a Sigmoidal Function</a> (1989) by G. Cybenko for more details. </p>
  
  <p>Although I realize that the typical UAT only applies to continuous functions, the UAT and the results about the <span class="math-container">$\mathcal{VC}$</span> dimension of neural networks seem to be a little bit contradictory, but this is only if you don't know the <a href="https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension" rel="nofollow noreferrer">definition of <span class="math-container">$\mathcal{VC}$</span> dimension</a> and the implications of the UAT.</p>
  
  <p>So, how come that neural networks approximate any continuous function, but, at the same time, they usually have a <span class="math-container">$\mathcal{VC}$</span> dimension that is only proportional to their number of parameters? What is the relationship between the two?</p>
  
Tags: <comparison><computational-learning-theory><vc-dimension><universal-approximation-theorems>
Title: How can neural networks approximate any continuous function but have $\mathcal{VC}$ dimension only proportional to their number of parameters?
UserDisplayName: nbro
ThreadText: # How can neural networks approximate any continuous function but have $\mathcal{VC}$ dimension only proportional to their number of parameters?
  
  (Asked by: username_0 on 2020-04-13)
  
  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](https://www.sciencedirect.com/science/article/pii/S0166218X98000146) (1998) by Pascal Koirana and Eduardo D. Sontag and [VC Dimension of Neural Networks](http://mathsci.kaist.ac.kr/~nipl/mas557/VCD_ANN_3.pdf) (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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&rep=rep1&type=pdf) (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](https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_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?
  
  **Tags:** comparison, computational-learning-theory, vc-dimension, universal-approximation-theorems
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-19. Score: 1
  
  [VC Dimension of Neural Networks](http://mathsci.kaist.ac.kr/%7Enipl/mas557/VCD_ANN_3.pdf) 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&rep=rep1&type=pdf#page=6) and the observations below [theorem 3](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&rep=rep1&type=pdf#page=7) in [Approximation by Superpositions of a Sigmoidal Function](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&rep=rep1&type=pdf), 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](https://en.wikipedia.org/wiki/Ball_(mathematics))).
  
  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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&rep=rep1&type=pdf#page=7), and use [theorem 2](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.7873&rep=rep1&type=pdf#page=6) 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.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_1**: 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.  
  > **username_0**: I didn't say "fixed", I said "arbitrary".  
  > **username_1**: 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 \}$.  
  > **username_0**: Ok. But then why do you say that "the UAT refers to a class of neural networks with _unbounded_ number of weights."?  
  > **username_1**: I meant that the number of weights that a function in the class can have is not bounded, i.e., it contains functions with arbitrarily large number of weights. I will edit the answer to be more clear.  
  > **username_0**: Ok, but your answer still doesn't really try to clarify the relationship between the two, apart from saying that in the case of UAT the number of hidden units can be arbitrarily big and that the VC dimension depends on the number of weights. I already knew this. I wanted to understand more. I wanted to see a formal proof that relates the two. Maybe I should have been more explicit, in fact. I realise now that my question wasn't clear enough.  
  > **username_0**: So, let me try to understand what you're trying to show here. You have $S$, which is a set of functions or, more precisely, the hypothesis class of a neural network. You have some labeled dataset of arbitrary size. You want to show that we can find a function in $S$ that approximates the function represented by the labeled dataset (which you denote, at the end of your answer, as $G(x)$, like in Cybenko's paper). So, **1.** you define some _ball_ (question 1: intuitively, why do you do this?).  
  > **username_0**: Then **2.** you let $\epsilon$ be such that the balls of different inputs do not intersect (question 2: why do you do this?). Then **3.** you define the unions of all balls, i.e. $D$ (question 3: why do you do this? I suppose this is related to Cybenko's proof, which I don't recall anymore, but it would be nice if you can provide more details here about these choices in the proof, so that this answer self-contained; ideally, it would be nice if you recalled Cybenko's proofs or theorems, before proceeding to your theorem and proof).  
  > **username_0**: Then **4.** you say that we should define $f_\epsilon(x)$ in some way and then find $G(x)$ in $S$ as described theorem 2. Then **5.** you **claim** that $G(x)$ can correctly classify all points $\epsilon$-away from the boundary of $D$, i.e. I suppose inside $D$, which you defined as the union of all balls.  
  > **username_0**: However, how is this related to my original question "_how come that neural networks approximate any continuous function, but, at the same time, they usually have a VC dimension that is only proportional to their number of parameters?_"? How is your proof intuitively related to this? Is this because $k$ is arbitrary? I don't see how the VC dimension of neural networks is involved in your proof. I don't see how you're showing that the VC dimension of $S$ (the neural network) is infinite here.  
  
  ---
  
  