\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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%