Exercise 4.9

When $K$ increases, there are less points available to train the models, so the learned models become worse, and $E_{\mathit{val}}(g_m^{\text{−}})$ becomes larger for each model $m$. $g_{m^{\text{∗}}}^{\text{−}}$ is the model with the lowest validation error among all models, so $E_{\mathit{val}}(g_{m^{\text{∗}}}^{\text{−}})$ will also increases with $k$. The same logic applies to $E_{\mathit{out}}(g_{m^{\text{∗}}}^{\text{−}})$ as well since $E_{\mathit{val}}(g_{m^{\text{∗}}}^{\text{−}})$ is an estimate of $E_{\mathit{out}}(g_{m^{\text{∗}}}^{\text{−}})$.

When $K$ increases to certain large value, there are much less points $N-K$ available to train the models, complex models converge to simple models(TODO), so the optimistic validation error $E_{\mathit{val}}(g_{m^{\text{∗}}}^{\text{−}})$ is closer to all validation errors $E_{\mathit{val}}(g_m^{\text{−}})$ for all models. Since each single validation error $E_{\mathit{val}}(g_m^{\text{−}})$ is an unbiased estimate of the $E_{\mathit{out}}(g_m^{\text{−}})$, the optimistic validation error $E_{\mathit{val}}(g_{m^{\text{∗}}}^{\text{−}})$ converges to $E_{\mathit{out}}(g_{m^{\text{∗}}}^{\text{−}})$ as well.