0.12 Complexity regularization for squared error loss

Complexity regularization in regression

Recall the classification problem. In Lecture 6 , where we assumed that ${min}_{f\in \mathcal{F}}R\left(f\right)=0$ , we obtained the PAC bound $\forall f\in \mathcal{F}$

From Corrolary 1 in Lecture 6 ,

In Lectures 7 and 8 , we dropped the assumption that ${min}_{f\in \mathcal{F}}R\left(f\right)=0$ and obtained, $\forall f\in \mathcal{F}$

This led to

Hoeffding's inequality was central to our analysis of learning under bounded loss functions. In many regression and signal estimationproblems it is natural to consider squared error loss functions (rather than $0/1$ or absolute error). In such cases, we will need to derive bounds using different techniques.

To illustrate the distinction between classification andregression, consider a simple, scalar signal plus noise problem. Consider $Y_i=\theta +W_i$ , $i=1,\cdots ,n$ , where $\theta$ is a fixed unknown scalar parameter and the $W_i$ are independent, zero-mean, unit variance random variables. Let $\overline{Y}=1/n{\sum }_{i=1}^n{Y}_i$ . Then, according to the Central Limit Theorem, $\overline{Y}$ is distributed approximately $N(\theta ,1/n)$ . A simple tail-bound on the Gaussian distribution gives us

which implies that

This is a bound on the deviations of the squared error ${\text{err}}^2={|\overline{Y}-\theta |}^2$ . Notice that the exponential decay rate is a function of $ϵ$ rather than ${ϵ}^2$ , as in Hoeffding's inequality. The squared error concentration inequality implies that $E\left[\right|\overline{Y}-\theta {|}^2]=O\left(\frac{1}{n}\right)$ (just write $E\left[{\text{err}}^2\right]={\int }_0^{\infty }P({\text{err}}^2>t)dt$ ). Therefore, in regression with a squared error loss, we can hope to get a rate of convergence as fastas $n^{-1}$ instead of $n^{-1/2}$ . The reason is simply because we are using an squared error loss instead of the $0/1$ or absolute error loss.

To begin our investigation into regression and function estimation, let us consider the following. Let $\mathcal{X}={\mathbf{R}}^d$ and $\mathcal{Y}=\mathbf{R}$ . Take $\mathcal{F}$ such that $f\in \mathcal{F}$ is a map $f:{\mathbf{R}}^d\mapsto \mathbf{R}$ . We have training data ${\{X_i,Y_i\}}_{i=1}^n\stackrel{i.i.d.}{\sim }{P}_{XY}$ . As our loss function, we take the squared error, i.e.,

The risk is then the MSE:

We know that the function $f^{*}$ that minimizes the MSE is just the conditional expectation of Y given X:

Now let $R^{*}=R\left(f^{*}\right).$ We would like to select an ${\widehat{f}}_n\in \mathcal{F}$ using the training data ${\{X_i,Y_i\}}_{i=1}^n$ such that the excess risk

is small. Let's consider the difference between the empirical risks:

Note that $E[\widehat{R}\left(f\right)-\widehat{R}\left(f^{*}\right)]=R\left(f\right)-R\left(f^{*}\right).$ Hence, by the Strong Law of Large Numbers (SLLN), we know that

as $n\to \infty .$ But how fast is this convergence?

We will derive a PAC style bound for the difference $\widehat{R}\left(f\right)-\widehat{R}\left(f^{*}\right)-(R\left(f\right)-R\left(f^{*}\right)).$ The following derivation is from Barron 1991. The excess risk and it empirical counterpart will be denoted by

Note that $\widehat{r}(f,f^{*})$ is the sum of independent random variables:

where $U_i=-{(Y_i-f\left(X_i\right))}^2+{(Y_i-f^{*}\left(X_i\right))}^2.$ Therefore, $r(f,f^{*})-\widehat{r}(f,f^{*})=\frac{1}{n}{\sum }_{i=1}^n(U_i-E\left[U_i\right]).$

We are looking for a PAC bound of the form

If the variables $U_i$ are bounded, then we can apply Hoeffding's inequality. However, a more useful bound for our regression problem can be derivedif the the variables $U_i$ satisfy the following moment condition: