$(2\text{'})$ Review lecture slides to get familiar with denotations of empirical risk function hat$($R$),$ pop$-$

ulation risk function R$,$ Bayes optimal hypothesis h$\_($Bayes $),$ in$-$class optimal hypothesis h$^(*),$ and

Empirical$-$Risk$-$Minimizer $($ERM$)$ hypothesis h$\_($ERM $).$ Let hat$($h$)$ be your hypothesis, and the risk

decomposition provides us with an excellent tool to analyze the performance of hat$($h$).$

Here is the simple proof of upper bound of E$[$R$($hat$($h$))]-$R$($h$\_($Bayes $))$ :

E$[$R$($hat$($h$))]-$R$($h$\_($Bayes$))$

$=$E$[$R$($hat$($h$))]-$E$[$hat$($R$)($hat$($h$))]+$E$[$hat$($R$)($hat$($h$))]-$E$[($hat$($R$))($h$\_($ERM$))]+$E$[($hat$($R$))($h$\_($ERM$))]-$E$[($hat$($R$))($h$^(*))]+$E$[($hat$($R$))($h$^(*))]-$R$($h$\_($Bayes $))$

$=$E$[$R$($hat$($h$))-$hat$($R$)($hat$($h$))]+$E$[($hat$($R$))(($hat$($h$)))-($hat$($R$))($h$\_($ERM$))]+$E$[($hat$($R$))($h$\_($ERM$))-($hat$($R$))($h$^(*))]+$E$[($hat$($R$))($h$^(*))]-$R$($h$\_($Bayes $))$

$=$E$[$R$($hat$($h$))-$hat$($R$)($hat$($h$))]+$E$[($hat$($R$))(($hat$($h$)))-($hat$($R$))($h$\_($ERM$))]+$E$[($hat$($R$))($h$\_($ERM$))-($hat$($R$))($h$^(*))]+$R$($h$^(*))-$R$($h$\_($Bayes $))$

ubrace$($E$[$R$(($hat$($h$)))-($hat$($R$))(($hat$($h$)))]$ubrace$)\_($generalization error $)+$ubrace$($E$[($hat$($R$))(($hat$($h$)))-($hat$($R$))($h$\_($ERM$))]$ubrace$)\_($optimization error $)+$ubrace$($R$($h$^(*))-$R$($h$\_($Bayes $))$ubrace$)\_($approximation error $).$

$($a$)(0\mathrm{.}5^(\text{'}))$ Prove that E$[($hat$($R$))($h$^(*))]=$R$($h$^(*)).$

$($b$)(0\mathrm{.}5\text{'})$ Why can we drop E$[($hat$($R$))($h$\_($ERM$))-($hat$($R$))($h$^(*))]$ to make last line be an upper bound of the

previous term?

$($c$)(1\text{'})$ Approximation error describes the ability of your hypothesis class H approximating

the Bayes optimal hypothesis h$\_($Bayes $).$ Consider a regression problem on curve fitting.

Suppose the data points are generated by a quadratic function and your hypothesis

class is the quadratic function class, what's the approximation error in this case? What

happens to approximation error if you change your hypothesis class to be the linear

function class?