\begin{slide}{}

\begin{center}

{\Large \bf 9.520: Class 21}

{\Large \bf Approximation Error and Approximation Theory}

{\em Federico Girosi}

\end{center}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf Plan of the class}
\end{center}

\begin{enumerate}

\item Learning and generalization error;

\item Approximation problem and rates of convergence;

\item N-widths;

\item ``Dimension independent'' convergence rates.

\end{enumerate}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}

\begin{center}
{\large \bf Note}
\end{center}
\large

These slides cover more extensive material than what will be presented
in class. 


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{}

\begin{center}
{\large \bf References}
\end{center}

\tiny

The background material on generalization error (first 8 slides) is
explained at length in:

[1] P. Niyogi and F.~Girosi.
On the relationship between generalization error,
hypothesis complexity, and sample complexity for Radial Basis
Functions. {\it Neural Computation}, 8:819--842, 1996.


[2] P. Niyogi and F. Girosi. Generalization bounds for function
approximation from scattered noisy data. {\it  Advances in
Computational Mathematics}, 10:51--80, 1999.

[1] has a longer explanation and introduction, while [2] is more
mathematical and also contains a very simple probabilistic proof of a
class of ``dimension independent'' bounds, like the ones discussed at
the end of this class. 

As far as I know it is A. Barron who first clearly spelled out the
decomposition of the generalization error in two parts. Barron uses a
different framework from what we use, and he summarizes it nicely in:

[3] A.R. Barron. Approximation and estimation bounds for artificial
neural networks. {\it Machine Learning}, 14:115--133, 1994.

The paper is quite technical, and uses a framework which is different
from what we use here, but it is important to read it if you plan to
do research in this field.

The material on $n$-widths comes from:

[4] A. Pinkus. {\it N-widths in Approximation Theory},
Springer-Verlag, New York, 1980.

Although the book is very technical, the first 8 pages contain an
excellent introduction to the subject. The other great thing about
this book is that you do not need to understand every single proof to
appreciate the beauty and significance of the results, and it is a
mine of useful information. 

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf References (continued)}
\end{center}
\tiny

[5] H.N. Mhaskar. Neural networks for optimal approximation of smooth
and analytic functions. {\it Neural Computation}, 8:164--177, 1996.

[6] A.R. Barron. Universal approximation bounds for superpositions of
a sigmoidal function. {\it IEEE Transaction on Information Theory},
39:3, 930--945, 1993.

[7] F.~Girosi and G. Anzellotti.  Rates of convergence of
approximation by translates {A.I. Memo} 1288, Artificial Intelligence
Laboratory, Massachusetts Institute of Technology, 1992. 

For a curious way to prove dimension independent bounds {\it using VC
theory} see: 

[8] F.~Girosi.  Approximation error bounds that use VC-bounds.  In
{\em Proc. International Conference on Artificial Neural Networks},
F. Fogelman-Souli\`{e} and P. Gallinari, editors, Vol. 1,
295--302. Paris, France, October 1995.




\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\begin{slide}{}


\begin{center}
{\large \bf Notations review}
\end{center}

\begin{itemize}

\item
$I[f] = \int_{X \times Y} V(f({\bf x}), y)p({\bf x}, y) d{\bf x} dy$

\item
$I_{\rm emp}[f] = {1 \over \ell} \sum_{\SSS i = 1}^{\SSS \ell} V(f({\bf x}_{\SSS i}),y_{\SSS i})$

\item 
$f_{\SSS 0} = \arg \min_f I[f]~~,~~~~f_{\SSS 0} \in \cal T$

\item 
$f_{\SSS H} = \arg \min_{\SSS f \in H} I[f]$

\item
$\hat f_{\SSS H, \ell}= \arg \min_{\SSS f \in H} I_{\SSS emp}[f]$

%\item 
%$I[f_{\SSS H}] \le \epsilon(n)$

%\item
%With probability $1 - \delta$ 
%$$
%|I[f] - I_{\SSS emp}[f]| \le \Omega (n,
%\ell, \delta) ~~\forall f \in H_{\SSS n}
%$$

\end{itemize}

\end{slide}
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf More notation review}
\end{center}

\begin{itemize}

\item $I[f_{\SSS 0}] = $ how well we could possibly do

\item $I[\hat f_{\SSS H, \ell}] = $ how well we do in space $H$ and $\ell$ data

\item $I[f_{\SSS H}] =$ how well we can do in space $H$

\item $|I[f] - I_{emp}[f]| \le \Omega (H, \ell, \delta) ~~\forall f
\in H$ (from VC theory)
 
%% \item $I[f_{\SSS H}] \le I[\hat f_{\SSS H, \ell}]$
%% 
%% \item $I_{\SSS emp}[\hat f_{\SSS H, \ell}] \le I_{\SSS emp}[f_{\SSS H}]$

\item $I[\hat f_{\SSS H, \ell}]$ is called {\it generalization error}

\item $I[\hat f_{\SSS H, \ell}] - I[f_{\SSS 0}]$ is also 
called {\it generalization error} ...

\end{itemize}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf A General Decomposition}
\end{center}

$$
I[\hat f_{\SSS H, \ell}] - I[f_{\SSS 0}] = (I[\hat f_{\SSS H, \ell}] -
I[f_{\SSS H}]) + (I[f_{\SSS H}] - I[f_{\SSS 0}])
$$

{\small \bf
generalization error = estimation error + approximation error}

When the cost function $V$ is quadratic:

$$
I[f] = E[(f_{\SSS 0} - f)^{\SSS 2}] + I[f_{\SSS 0}]
$$

and therefore

$$
E[(f_{\SSS 0} - f_{\SSS H, \ell})^2] = (I[\hat f_{\SSS H, \ell}] -
I[f_{\SSS H}]) + E[(f_{\SSS 0} - f_{\SSS H})^2]
$$

{\small \bf
generalization error = estimation error + approximation error}



\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% \begin{slide}{}
%% 
%% \begin{center}
%% \epsfig{figure=../figures/gen-error.ps,height=.6\linewidth}
%% \end{center}
%% 
%% \end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf A useful inequality}
\end{center}

%% \begin{center}
%% \epsfig{figure=../figures/iemp3.epsi,height=.3\linewidth}
%% \end{center}

If, with probability $1 - \delta$
$$
|I[f] - I_{\SSS emp}[f]| \le \Omega (H, \ell, \delta) ~~\forall f \in H
$$
then
$$
|I[\hat f_{\SSS H, \ell}] - I[f_{\SSS H}]| \le 2 \Omega (H, \ell, \delta)
$$

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf Bounding the Generalization Error }
\end{center}

$$
E[(f_{\SSS 0} - f_{\SSS H, \ell})^2] \le 2 \Omega (H, \ell, \delta)
 + E[(f_{\SSS 0} - f_{\SSS H})^2]
$$

Notice that:

\begin{itemize}

\item
$\Omega$ has nothing to do with the target space $\cal T$, it is
studied  mostly in statistics;

\item
$E[(f_{\SSS 0} - f_{\SSS H})^2]$ has everything to do with the target
space $\cal T$, it is studied mostly in approximation theory;

\end{itemize}





\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf Approximation Error}
\end{center}

We consider a {\it nested family} of hypothesis spaces $H_n$:
$$
H_0 \subset H_1 \subset \dots H_n \subset \dots 
$$

and define the approximation error as:
$$
\epsilon_{\cal T}(f, H_n) \equiv \inf_{h \in H_n} \|f - h\|
$$

\normalsize

$\epsilon_{\cal T}(f, H_n)$ is the smallest error that we can make if we
approximate $f \in \cal T$ with an element of $H_n$ (here $\| \cdot \|$
is the norm in $\cal T$).

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf Approximation error}
\end{center}
\large
For reasonable choices of hypothesis spaces $H_n$:
$$
\lim_{n \rightarrow \infty} \epsilon_{\cal T}(f, H_n) = 0
$$

This means that we can approximate functions of $\cal T$ arbitrarily well
with elements of $\{H_n\}_{n=1}^\infty$

\normalsize

For example: ${\cal T} = $ continuous functions on compact sets, and
$H_n = $ polynomials of degree at most $n$.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% \begin{slide}{}
%% 
%% {\bf Theorem: (Weierstrass)} The set $P_{[a, b]}$ of all polynomials
%% is dense in $C[a, b]$. In other words, given an $h \in C[a, b]$ and
%% $\epsilon > 0$, there is a polynomial $p$ for which:
%% $$
%% |p(x) - h(x)| < \epsilon ~~\mbox{\rm for all}~~ x \in [a, b]~.
%% $$
%% 
%% \end{slide}
%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf The rate of convergence}
\end{center}

\large
The interesting question is:

{\bf How fast does $\epsilon_{\cal T}(f, H_n)$ go to zero?}

The rate of convergence to zero is a measure of the relative
complexity of $\cal T$ with respect to the approximation scheme $H$.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

 In the next slides we compute explicitely the rate of
convergence of approximation of a smooth function by trigonometric
polynomials.

We are interested in studying how fast the approximation error goes to
zero when the number of parameters of our approximation scheme goes to
infinity.

The reason for this exercise is that the results are representative:
more complex and interesting cases all share the basic features of
this example.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{}

\begin{center}
{\large \bf Rates of convergence in 1 dimension}
\end{center}

Consider the set of functions 
$$
C_2[-\pi,\pi] \equiv C[-\pi,\pi] \bigcap L_2[-\pi,\pi]
$$

Functions in this set can be represented as a Fourier series:

$$
f(x) = \sum_{k = 0}^\infty c_k e^{ikx}~,~~~c_k \propto
\int_{-\pi}^{\pi}dx f(x)e^{-ikx}
$$

The $L_2$ norm satisfies the equation:

$$
\|f\|_{L_2}^2 = \sum_{k = 1}^\infty c_k^2
$$



\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{}

We consider as target space the following Sobolev space of smooth functions:
$$
W_{s,2} \equiv \left \{f \in C_2[-\pi,\pi]~|~\left \|{d^s f \over
dx^s}\right \|^2_{L_2} < + \infty \right \}
$$

The (semi)-norm in this Sobolev space is defined as: 

$$
\|f\|^2_{W_{s,2}} \equiv \left \|{d^s f \over dx^s}\right \|^2_{L_2} = 
\sum_{k = 1}^\infty k^{2s}c_k^2
$$

In order for a function to belong to the space $W_{s,2}$ its Fourier
coefficients $c_k$ must go to zero at a rate which depends on $s$.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

The set $W_{s,2}$ will be our {\it target space}. The {\it hypothesis
space} $H_n$ is the set of trigonometric polynomials of degree $n$,
that consists of functions of the form:
$$
p(x) = \sum_{k = 1}^n a_k e^{ikx}
$$

Given a funtion of the form 
$$
f(x) = \sum_{k = 0}^\infty c_k e^{ikx}
$$

It is easy to see that the trigonometric polynomial of degree $n$
which best approximates $f$ in the $L_2$ norm is given by the first
$n$ terms of its Fourier series:

$$
f_n(x) =  \sum_{k = 1}^n c_k e^{ikx}
$$


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}
\large
For a given $f \in W_{s,2}$ we want to study the approximation error:

$$
\epsilon_n \equiv \|f - f_n\|^2_{L_2}
$$

Notice that $n$, the degree of the polynomial, is also the number of
parameters that we use in the approximation.

Obviously $\epsilon_n$ goes to zero as $n \rightarrow + \infty$, but
the key question is: {\bf how fast?}


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf An easy estimate of $\epsilon_n$}
\end{center}

\begin{align}
\epsilon_n & \equiv \|f - f_n\|^2_{L_2} = \sum_{k = n+1}^\infty c_k^2
= \sum_{k = n+1}^\infty c_k^2k^{2s} {1 \over k^{2s}} < \nonumber \\ &
\nonumber \\ &
< {1 \over n^{2s}} \sum_{k = n+1}^\infty c_k^2k^{2s} < {1 \over n^{2s}}
\sum_{k = 1}^\infty c_k^2k^{2s} = {\|f\|_{W_{s,2}}^2 \over n^{2s}}
\nonumber
\end{align}
$$
\Downarrow
$$
$$
\epsilon_n < {\|f\|_{W_{s,2}}^2  \over n^{2s}}
$$

{\bf More smoothness $\Rightarrow$ faster rate of convergence}

But what happens in more than one dimension?

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf Rates of convergence in $d$ dimensions}
\end{center}

It is enough to study $d=2$ and a particular choice of Sobolev space
to understand the problem. We proceed in full analogy with the 1-d case:

$$
f(x,y) = \sum_{k,m = 1}^\infty c_{km}e^{i(kx+my)}
$$

$$
\|f\|_{W_{s,2}}^2 \equiv \left \|{d^s f \over dx^s}\right \|^2_{L_2} +
\left \|{d^s f \over dy^s}\right \|^2_{L_2} = \sum_{k,m = 1}^\infty
(k^{2s}+m^{2s})c_{km}^2
$$

Here $W_{s,2}$ is defined as the set of functions such that
$\|f\|_{W_{s,2}}^2 < +\infty$

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

As before the hypothesis space $H_n$ is the set of trigonometric
polynomials of degree $l$, which consists of functions of the form:
$$
p(x) = \sum_{k,m = 1}^l a_{km} e^{(ikx+imy)}
$$

A trigonometric polynomial of degree $l$ in $d$ variables has a number
of coefficients $n = l^d$.

We are interested in the behavior of the approximation error as a
function of $n$. The approximating function is:

$$
f_n(x,y) = \sum_{k,m = 1}^l c_{km} e^{(ikx+imy)}
$$

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{}

\begin{center}
{\large \bf An easy estimate of $\epsilon_n$}
\end{center}
\begin{align}
\epsilon_n & \equiv \|f - f_n\|^2_{L_2} = \sum_{k,m = l+1}^\infty
c_{km}^2 = \sum_{k,m = l+1}^\infty c_{km}^2(k^{2s}+m^{2s}) {1 \over
k^{2s}+m^{2s}} < \nonumber \\ & \nonumber \\ & < {1 \over 2l^{2s}}
\sum_{k,m=l+1}^\infty c_{km}^2(k^{2s}+m^{2s}) < {1 \over 2l^{2s}}
\sum_{k,m=1}^\infty c_{km}^2(k^{2s}+m^{2s}) = \nonumber \\ & \nonumber
\\ & = {\|f\|_{W_{s,2}}^2 \over 2l^{2s}} \nonumber
\end{align}

Since $n = l^d$, then $l = n^{1 \over d}$ (with $d=2$), and we obtain:
$$
\epsilon_n < {\|f\|_{W_{s,2}}^2  \over 2 n^{2s \over d}}
$$

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}

Now notice that the previous calculations carries over to the
$d$-dimensional cases in straightforward manner, and so the following
general result holds:

{\it if we approximate functions of $d$ variables with $s$ square
integrable derivatives with a trigonometric polynomial with $n$
coefficients, tha approximation error satisfies:}

$$
\epsilon_n < {C \over  n^{2s \over d}}
$$

{\bf More smoothness $\Rightarrow$ faster rate of convergence}

{\bf Higher dimension $\Rightarrow$ slower rate of convergence}



\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf Another Example: Generalized Translation Networks}
\end{center}

Consider networks of the form:

$$
f({\bf x}) = \sum_{k = 1}^n a_k \phi (A_k {\bf x} + {\bf b}_k)
$$

where ${\bf x} \in \R^d$, ${\bf b}_k \in \R^m$, $1 \le m \le d$, $A_k$
are $m \times d$ matrices, $a_k \in \R$ and $\phi$ is some given
function.

For $m=1$ this is a Multilayer Perceptron .

For $m=d$, $A_k$ diagonal and $\phi$ radial this is a Radial Basis
Functions network. 


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

{\bf Theorem (Mhaskar, 1994)}

Let $W_s^p(\R^d)$ be the space of functions whose derivatives up to
order $s$ are $p$-integrable in $\R^d$. Under very general assumptions
on $\phi$ one can prove that there exists $d \times m$ matrices
$\{A_k\}_{k=1}^n$ such that, for any $f \in W_s^p(\R^d)$,
one can find ${\bf b}_k$ and $a_k$ such that:

$$
\|f - \sum_{k = 1}^n a_k \phi (A_k {\bf x} + {\bf b}_k)\|_p \le c n^{- {s
\over d}}\|f\|_{W_s^p}
$$

Moreover, the coefficients $a_k$ are linear functionals of $f$.

{\it This rate is optimal}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf The curse of dimensionality (1)}
\end{center}

If the approximation error is 
$$
\epsilon_n \propto \left ({1 \over n} \right )^{s \over d} 
$$

that means that the number of parameters needed to achieve an error
smaller than $\epsilon$ is:
$$
n \propto \left ({1 \over \epsilon} \right )^{d \over s} 
$$

{\bf the curse of dimensionality} is the $d$ factor;


{\bf the blessing of smoothness} is the $s$ factor;


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{}

\begin{center}
{\large \bf Jackson type rates of convergence}
\end{center}

It happens ``very often'' that rates of convergence for functions in
$d$ dimensions with ``smoothness'' of order $s$ are of the {\bf Jackson
type}:
$$
O \left ( \left ( {1 \over n} \right )^{s \over d} \right )
$$

This is true for example for polynomial and spline approximation
techniques, and it is also true for many non-linear techniques.

{\bf Can we do better than this? Can we defeat the curse of
dimensionality? Have we tried hard enough to find
``good'' approximation techniques?}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf N-widths: definition {\small (from Pinkus, 1980)}}
\end{center}

Let $X$ be a normed space of functions, $A$ a subset of $X$, and $X_n$
a linear subspace of $X$, so that
$$
X_n = \{f \in X ~|~ f = \sum_{i = 1}^n c_i \phi_i,~~ \phi_i \in
{X}, c_i \in R, i = 1, \dots , n \}
$$

Define the {\bf Kolmogorov n-width} of $A$ in $X$ as 
{\large
$$
d_n(A, X) = \inf_{X_n}~~ \sup_{f \in A}~~
\inf_{y \in X_n}~~ \|f - y \|
$$
}

This is equivalent to
$$
d_n(A, X) = \inf_{\phi_1, \dots \phi_n}~~ \sup_{f \in A}~~
\inf_{c_1,  \dots c_n}~~ \|f - \sum_{i = 1}^n c_i \phi_i\|
$$


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{}

\begin{center}
{\large \bf Example (Kolmogorov, 1936)}
\end{center}

$X = L_2[0, 2 \pi]$

$\tilde W_2^s \equiv \{f ~|~ f \in C^{s-1}[0,2\pi], f^{(j)}~ 
\mbox{\rm periodic},~~j = 0, \dots , s-1 \}$

$A = \tilde B_2^s \equiv \{f~|~ f \in \tilde W_2^s~, \|f^{(s)}\|_2 \le
1\} \subset X$

Then 
$$
d_{2n-1}(\tilde B_2^s,L_2) =d_{2n}(\tilde B_2^s,L_2) = {1 \over n^s}
$$

and the following $X_n$ is optimal (in the sense that it achieves the
rate above):
$$
X_{2n-1} = \mbox{\rm span} \{1, \sin(x), \cos(x), \dots , \sin(n-1)x, \cos(n-1)x \}
$$

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{}

\begin{center}
{\large \bf Example: multivariate case}
\end{center}

$I_d \equiv [0,1]^d$

$X = L_2[I_d]$

$W_2^s[I_d] \equiv \{f~|~ f \in C^{s-1}[I_d]~,~f^{(s)} \in L_2[I_d] \} $

$B_2^s \equiv \{f~|~ f \in W_2^s[I_d]~,~\|f^{(s)}\|_2 \le 1\}$

{\bf Theorem} {\small (from Pinkus, 1980)}
$$
d_n(B_2^s,L_2) \approx \left ( {1 \over n} \right )^{s \over d}
$$



\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf Dimensionality and smoothness}
\end{center}

Classes of functions in $d$ dimensions with smoothness of order $s$
have an {\it intrinsic complexity} characterized by the ratio $s \over
d$: 

\begin{itemize}

\item
the curse of dimensionality is the $d$ factor;

\item
the blessing of smoothness is the $s$ factor;


\end{itemize}

\normalsize

We cannot expect to find an approximation technique that ``beats the
curse of dimensionality'', {\it unless we let the smoothness $s$ change
with the dimension $d$}. 

\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

{\bf Theorem (Barron, 1991)}


Let $f$ be a function such that its Fourier transform satisfies

$$
\int_{\R^d}~d{\bf \omega}~\|{\bf \omega}\| |\tilde f({\bf \omega})| < + \infty~.
$$

and let $\Omega$ be a bounded domain in $\R^d$. Then we can find a
neural network with $n$ coefficients $c_i$, $n$ weights ${\bf w}_i$
and $n$ biases $\theta_i$ such that

$$
\| f - \sum_{i = 1}^n c_i \sigma({\bf x} \cdot {\bf w}_i +
\theta_i)\|^2_{L_2(\Omega)} < {c \over n} 
$$


The rate of convergence is {\bf independent of the dimension $d$}.


\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{}

\begin{center}
{\large \bf Here is the trick...}
\end{center}

The space of functions such that 

$$
\int_{\R^d}~d{\bf \omega}~\|{\bf \omega}\| |\tilde f({\bf \omega})| < + \infty~.
$$

is the space of functions that can be written as 

$$
f = {1 \over \|{\bf x}\|^{d-1}} * \lambda
$$

where $\lambda$ is any function whose Fourier Transform is integrable.


Notice how the space becomes more constrained as the dimension
increases. 



\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

\begin{center}
{\large \bf Jones lemma (Maurey, 1981; Jones, 1990; Barron, 1991)}
\end{center}

%% \begin{center}
%% \epsfig{figure=../figures/lemma.ps,height=.2\linewidth}
%% \end{center}

Let $H$ be an Hilbert space and $G \subset H$ such that $\| g\|
\le b~~\forall g \in G$. Let $f \in \overline{\rm co G}$. \\
Then $\forall c > b^2 - \| f\|^2$ we can find $n$ numbers $\alpha_k >
0$, such that $\sum_{i = 1}^n \alpha_k = 1$, and $n$ elements $g_k \in
G$ such that 
$$
\|f - \sum_{k = 1}^n\alpha_k g_k \|^2 \le {c \over n}
$$


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

{\bf Theorem (Girosi and Anzellotti, 1992)}

Let $f \in H^{s, 1}(\R^d)$, where $H^{s, 1}(\R^d)$ is the space of
functions whose partial derivatives up to order $s$ are integrable,
and let $K_s({\bf x})$ be the Bessel-Macdonald kernel, that is the
Fourier transform of

$$
\tilde K_s({\bf \omega}) = { 1 \over
(1 + \| {\bf \omega}\|^2)^{s \over 2}}~~~~ s > 0~.
$$

If $s > d$ and $s$ is even, we can find a Radial Basis
Functions network with $n$ coefficients $c_\alpha$ and $n$ centers
${\bf t}_\alpha$ such that

$$
\| f - \sum_{\alpha = 1}^n c_\alpha K_s({\bf x} - {\bf
t}_\alpha)\|^2_{L_\infty} < {c \over n} 
$$

\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{}

{\bf Theorem (Girosi, 1992)}

Let $f \in H^{s, 1}(\R^d)$, where $H^{s, 1}(\R^d)$ is the space of
functions whose partial derivatives up to order $s$ are integrable.
If $s > d$ and $s$ is even, we can find a Gaussian basis
function network with $n$ coefficients $c_\alpha$, $n$ centers ${\bf
t}_\alpha$ and $n$ variances $\sigma_\alpha$ such that
$$
\| f - \sum_{\alpha = 1}^n c_\alpha e^{-{({\bf x} - {\bf
t}_\alpha)^2 \over 2 \sigma_\alpha^2}}\|^2_{L_\infty} < {c \over n} 
$$

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% \begin{slide}{}
%% 
%% {\bf Theorem}
%% 
%% If $k$ is a positive integer and $s > k + d/p$ then
%% $$H^{s,p}(\R^d) \subset C^k$$
%% and there exists a constant $c > 0$ such that
%% $$\Vert f \Vert_{\SSS C^k} \le \Vert f \Vert_{\SSS H^{s,p}(\R^d)}$$
%% is fulfilled.
%% 
%% (See Stein 1970, for example)
%% 
%% \end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{}

Same rate of convergence: $O({1 \over \sqrt n})$

\tiny

$$
\begin{array}{lll}
\mbox{\rm Function space} & \mbox{\rm Norm} & \mbox{\rm Approximation
scheme}\\
 & & \\
 & & \\
\int_{\R^d}~d{\bf \omega}~ |\tilde f({\bf \omega})| < + \infty  & L_2(\Omega) & 
f({\bf x}) = \sum_{i = 1}^n c_i \sin({\bf x} \cdot {\bf w}_i +
\theta_i) \\
 & & \\
\mbox{\bf (Jones)} & & \\
 & & \\
 & & \\
\int_{\R^d}~d{\bf \omega}~ \|{\bf \omega}\|
|\tilde f({\bf \omega})| < + \infty  & L_2(\Omega) & 
f({\bf x}) = \sum_{i = 1}^n c_i \sigma({\bf x} \cdot {\bf w}_i +
\theta_i) \\
 & & \\
\mbox{\bf (Barron)} & & \\
 & & \\
 & & \\
\int_{\R^d}~d{\bf \omega}~ \|{\bf \omega}\|^2
|\tilde f({\bf \omega})| < + \infty  & L_2(\Omega) & 
f({\bf x}) = \sum_{i = 1}^n c_i |{\bf x} \cdot {\bf w}_i +
\theta_i|_+ +\\
 & & \\
\mbox{\bf (Breiman)} & &  ~~~~~~~~~~+ {\bf a} \cdot {\bf x} + b \\
 & & \\
 & & \\
\tilde f({\bf \omega}) \in C_0^k, ~2k > d & L_\infty(\R^d) & f({\bf x}) =
\sum_{\alpha = 1}^n c_\alpha  e^{- \|{\bf x} - {\bf t}_\alpha\|^2 } \\
 & & \\
\mbox{\bf (Girosi and Anzellotti)} & &\\
 & & \\
H^{2s, 1}(\R^d), ~2s > d & L_\infty(\R^d) & f({\bf x}) = \sum_{\alpha = 1}^n c_\alpha
e^{- {\|{\bf x} - {\bf t}_\alpha\|^2 \over \sigma^2_\alpha}} \\
 & & \\
\mbox{\bf (Girosi)} & & \\
\end{array}
$$

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
