0.12 Complexity regularization for squared error loss  (Page 2/2)

for some $h>0$ .

The moment condition can be difficult to verify in general, but it does hold, for example, for bounded random variables. If [link] holds, then the Craig-Bernstein (CB) inequality states:

for $0<ϵh\le c<1$ and $t>0.$ This shows that the tail decays exponentially in t, rather than exponentially in $t^2.$ Recall Hoeffding's inequality:

If $\frac{t}{n}\ll 1,$ then $\frac{t^2}{n}\ll t,$ which implies $e^{\frac{-2t^2}{n}}\gg e^{-t}.$ This indicates that the CB inequality may be much tighter than Hoeffding's. To use the CB inequality, we need to bound thevariance of $\frac{1}{n}{\sum }_{i=1}^n{U}_i.$ Note that

Assumption 1

Proposition 1

Proposition 2

You can write $U_i$ as

Note that the variance of $U_i$ is upper-bounded by its second moment. Also note that the covariance of the two terms above is zero:

This is evident when you recall that $f^{*}\left(X_i\right)=E\left[Y\right|X=X_i].$ Now we can bound the second moments of $T_1$ and $T_2:$

So $var\left(U_i\right)\le 5b^{2}E\left[{\left(f,\left(X_i\right),-,f^{*},\left(X_i\right)\right)}^2\right].$ The final step is to see that

Thus, $nvar\left(\frac{1}{n}{\sum }_{i=1}^n{U}_i\right)\le 5b^{2}r(f,f^{*}).$ And therefore, we can say that, with probability at least $1-e^{-t},$

In other words, with probability at least $1-\delta$ (where $\delta =e^{-t}$ ),

Now, suppose we have assigned positive numbers $c\left(f\right)$ to each $f\in \mathcal{F}$ satisfying the Kraft inequality:

Note that [link] holds $\forall \delta >0.$ In particular, we let $\delta$ be a function of f:

So we can use this $\delta$ along with the procedure introduced in Lecture 9 ( i.e., Union of events bound followed by the Kraft inequality) to obtain the following. For all $f\in \mathcal{F},$ $\forall \delta >0,$

with probability at least $1-\delta .$ Now set $c=ϵh=\frac{2b^2ϵ}{3}$ and assume $ϵ<\frac{6}{19b^2}.$ Then define

Now, after using $\alpha$ and rearranging terms, we have:

We want to choose f to minmize this upper bound. So take

So, with probability at least $1-\delta ,$

where $f_n^{*}=arg{min}_{f\in \mathcal{F}}\left\{R,\left(f\right),+,\frac{c\left(f\right)log2}{nϵ}\right\}.$

Now we use the Craig-Bernstein inequality to bound the difference between $\widehat{r}(f_n^{*},f^{*})$ and $r(f_n^{*},f^{*}):$ With probability at least $1-\delta ,$

Now we can again use the union bound to combine [link] and [link] : With probability at least $1-2\delta ,$ $\forall \delta >0,$

Now set $\delta =e^{\frac{-nϵt}{2}},$ then we have

Integrating, we get

To sum up, we have shown that for $ϵ<\frac{6}{19b^2},$

or,

since $\alpha <1.$ Or, in expanded form:

Notice that if $f^{*}\in \mathcal{F}$ and if $c\left(f^{*}\right)$ is not too large (e.g., $c\left(f^{*}\right)\approx logn$ ), then we have $E\left[R\left({\widehat{f}}_n\right)\right]-R\left(f^{*}\right)=O(n^{-1}logn)$ , within a logarithmic factor of the parametric rateof convergence!