0.4 An example of the use of sieves for complexity regularization

Consider the following setting. Let

where X is a random variable (r.v.) on $\mathcal{X}=[0,1]$ , $W$ is a r.v. on $\mathcal{Y}=\mathbf{R},$ independent of $X$ and satisfying

Finally let $f^{*}:[0,1]\to \mathbf{R}$ be a function satisfying

where $L>0$ is a constant. A function satisfying condition [link] is said to be Lipschitz on $[0,1]$ . Notice that such a function must be continuous, but it is not necessarilydifferentiable. An example of such a function is depicted in [link] (a).

Note that

Consider our usual setup: Estimate $f^{*}$ using $n$ training examples

where $\stackrel{i.i.d.}{\sim }$ means independently and identically distributed . [link] (a) illustrates this setup.

In many applications we can sample $\mathcal{X}=[0,1]$ as we like, and not necessarily at random. For example we can take $n$ samples uniformly on [0,1]

We will proceed with this setup (as in [link] (b)) in the rest of the lecture.

Our goal is to find ${\widehat{f}}_n$ such that $E[\parallel f^{*}-{\widehat{f}}_n{\parallel }^2]\to 0,\text{as}n\to 0$ (here $\parallel ·\parallel$ is the usual $L_2$ -norm; i.e., $\parallel f^{*}-{\widehat{f}}_n{\parallel }^2={\int }_0^1{|f^{*}\left(t\right)-{\widehat{f}}_n\left(t\right)|}^{2}dt$ ).

Let

The Riskis defined as

The Expected Risk (recall that ourestimator ${\widehat{f}}_n$ is based on $\{x_i,Y_i\}$ and hence is a r.v.) is defined as

Finally the Empirical Riskis defined as

Let $0<m_1\le m_2\le m_3\le \cdots$ be a sequence of integers satisfying $m_n\to \infty$ as $n\to \infty$ , and $k_n{m}_n=n$ for some integer $k_n>0$ . That is, for each value of $n$ there is an associated integer value $m_n$ . Define the Sieve ${\mathcal{F}}_1,{\mathcal{F}}_2,{\mathcal{F}}_3,...,$

${\mathcal{F}}_n$ is the space of functions that are constant on intervals

From here on we will use $m$ and $k$ instead of $m_n$ and $k_n$ (dropping the subscript $n$ ) for notational ease. Define

Note that $f_n\in {\mathcal{F}}_n$ .

The above implies that $\parallel f^{*}-f_n{\parallel }^2\to 0\text{as}n\to \infty ,$ since $m=m_n\to \infty \text{as}n\to \infty$ . In words, with $n$ sufficiently large we can approximate $f^{*}$ to arbitrary accuracy using models in ${\mathcal{F}}_n$ (even if the functions we are using to approximate $f^{*}$ are not Lipschitz!).

For any $f\in {\mathcal{F}}_n,$ $f={\sum }_{j=1}^m{c}_j{\mathbf{1}}_{\{t\in I_{j,m}\}},$ we have

Let ${\widehat{f}}_n=arg{min}_{f\in {\mathcal{F}}_n}{\widehat{R}}_n\left(f\right).$ Then

Exercise 2

Show [link] .

Note that $E\left[{\widehat{c}}_j\right]=c_j^{*}$ and therefore $E\left[{\widehat{f}}_n\left(t\right)\right]=f_n\left(t\right)$ . Lets analyze now the expected risk of ${\widehat{f}}_n$ :

where the final step follows from the fact that $E\left[{\widehat{f}}_n\left(t\right)\right]=f_n\left(t\right)$ . A couple of important remarks pertaining the right-hand-side of equation [link] : The first term, $\parallel f^{*}-f_n{\parallel }^2$ , corresponds to the approximation error, and indicates how well can we approximate the function $f^{*}$ with a function from ${\mathcal{F}}_n$ . Clearly, the larger the class ${\mathcal{F}}_n$ is, the smallest we can make this term. This term is precisely the squared bias of the estimator ${\widehat{f}}_n$ . The second term, $E[\parallel f_n-{\widehat{f}}_n{\parallel }^2]$ , is the estimation error, the variance of our estimator. We will see that the estimation erroris small if the class of possible estimators ${\mathcal{F}}_n$ is also small.

The behavior of the first term in [link] was already studied. Consider the other term:

Combining all the facts derived we have

This equation used Big-O notation.

What is the best choice of $m$ ? If $m$ is small then the approximation error ( i.e., $O(1/m^2)$ ) is going to be large, but the estimation error ( i.e., $O(m/n)$ ) is going to be small, and vice-versa. This two conflicting goals provide a tradeoff that directs our choice of $m$ (as a function of $n$ ). In [link] we depict this tradeoff. In [link] (a) we considered a large $m_n$ value, and we see that the approximation of $f^{*}$ by a function in the class ${\mathcal{F}}_n$ can be very accurate (that is, our estimate will have a small bias), but when we use the measured dataour estimate looks very bad (high variance). On the other hand, as illustrated in [link] (b), using a very small $m_n$ allows our estimator to get very close to the best approximating function in the class ${\mathcal{F}}_n$ , so we have a low variance estimator, but the bias of our estimator ( i.e., the difference between $f_n$ and $f^{*}$ ) is quite considerable.

We need to balance the two terms in the right-hand-side of [link] in order to maximize the rate of decay (with $n$ ) of the expected risk. This implies that $\frac{1}{m^2}=\frac{m}{n}$ therefore $m_n=n^{1/3}$ and the Mean Squared Error (MSE) is

So the sieve ${\mathcal{F}}_1,{\mathcal{F}}_2,\cdots$ with

produces a $\mathcal{F}$ -consistent estimator for $f^{*}=E\left[Y\right|X+x]\in \mathcal{F}$ .

It is interesting to note that the rate of decay of the MSE we obtainwith this strategy cannot be further improved by using more sophisticated estimation techniques (that is, $n^{-2/3}$ is the minimax MSE rate for this problem). Also, rather surprisingly, we are considering classes of models ${\mathcal{F}}_n$ that are actually not Lipschitz, therefore our estimator of $f^{*}$ is not a Lipschitz function, unlike $f^{*}$ itself.