Approximation Theory

Given a family of curves G, and a family of neurons F. For any curve $g\in G$, does there exist a neural net $f\in F$ such that $\xi (g,f)<ϵ$.

• Goal is to think about how deep and how wide the network should be? Why should we care about the architecture of a NN?
• One nice family: Lipschitz family of functions.

Prove a special version of universal approximation theorem for lipschitz functions and 3-layer relu networks. More details of the proof can be found here.

• To understand this, taking a special case of univariate case, and approximating the function using piecewise constant function or rectangles, and then finding the error such that $|f(x)-g(x)|<ϵ$ can be an easier first introduction.
• Let $g:[0,1{]}^d\to \mathbb{R}$ be any L-lipschitz function. Then for any error $ϵ>0$, there exists a 3-layer relu network with total number of neurons $N=4d(L/ϵ{)}^d$ such that ${\int }_{[0,1{]}^d}|f(x)-g(x)|dx<2ϵ$.
  • This can be generalised to any continuous function, i.e. when g is any continuous function. There exists a 3-layer ReLU network f with $\Omega \left(\frac{1}{{\delta }^d}\right)$ ReLU with ${\int }_{[0,1{]}^d}|f(x)-g(x)|dx\le 2ϵ$.
• We aim to approximate the function using a partition as rectangles $\mathcal{P}=\{R_1,R_2,\dots ,R_N\}$ such that each side $<\delta$. Each $R_i$ is of the form ${\prod }_{i=1}^d[a_j,b_j)$.
• Let $h={\sum }_i{\alpha }_i{1}_{R_i}$ be the piecewise constant function. This means the function will be approximated $|h-g|<ϵ$ at each partition using h when ${\alpha }_i=g(x_i)$, where each $x_i\in R_i$.
• We can represent rectangles using a linear combination of ReLU $g_1\left(x\right)=\sigma \left(\frac{x-\left(a-c\right)}{c}\right)-\sigma \left(\frac{x-a}{c}\right)-\sigma \left(\frac{x-b}{c}\right)+\sigma \left(\frac{x-\left(b+c\right)}{c}\right)$, same for other dimensions as well. $g_{i,\gamma }(x)=1$ when $x\in R_i$ and $g_{i,\gamma }(x)\in [0,1]$ when $x\in [a-\gamma ,b+\gamma ]$, and 0 otherwise.
• This can be combined to form a hyperrectangle $g_{\gamma }(x)=\sigma \left({\sum }_j{g}_{j,\gamma }(x_j)-(d-1)\right)$, (d-1) to cut the hyperrectangle at other positions. So, this is equal to 1 at only the partition $R_i$. Thus, $g_{\gamma }\approx 1_{R_i}$.
• and then linearly combined using a ReLU layer $f(x)={\sum }_i{\alpha }_i{g}_i(x)$.
• So, we’re in a 3-way approximation g → h → f, and that’s why $2ϵ$, $\Vert f-g\Vert \le \Vert f-h\Vert +\Vert h-g\Vert$
• Note the curse of dimensionality in above proof (exponential dependence on $d$), and above proof fails to generalise because we’re using rectangles to approximate a function.

Universal Approximation class A class of functions $F$ is universal approximator over a compact set S if for every continuous function g and $ϵ>0$, there exists $f\in F$ such that ${\sup }_{x\in S}|f(x)-g(x)|<ϵ$.

• Above proof can be succinctly done in 2 layers.
• This is generally proven using Stone-Weierstrass Theorem.
• TODO: read this.

Barron’s Theorem

Fourier representation is also a universal approximator - TODO: read this.

Depth Separation

Goal is to prove that to approximate a function that can be approximated with constant width deep networks, constant deep shallow network, require exponential many neurons. - Proven by taking a function $g(x)=\sigma (2\sigma (x)-4\sigma \left(x-\frac{1}{2}\right))$. This function has the property that the number of kinks scale exponentially with $g^L$. - In a L layer ReLU network or widths $(m_1,m_2,\dots ,m_L)$, number of affine pieces $N_i$ (piecewise linear regions) for layer i ⇐ $2m_i\ast N_{i-1}=2^L\prod m_j$. Thus, $N_A(g)\le 2^i{\prod }_{j<i}{m}_j$. - And total number of affine pieces = $N_A(f)\le 2^L{\prod }_{j<L}{m}_j\le {\left(\frac{m}{L}\right)}^L$. - Any univariate function f with N piecewise linear regions or affine pieces (or kinks) can be composed together. - $N_A(f+g)\le N_A(f)+N_A(g)$, $N_A(f\circ g)\le N_A(f)\cdot N_A(g)$. - Above result is used to prove that depth increases number of affine pieces multiplicatively, while width only scales it additively. - TODO: redo the proof properly.