Convergence of Empirical Risk Minimizer and True Risk Minimizer

Question

Let $D:= \{ (x_1, y_1), \dots, (x_n, y_n) | x_i \in \mathbb{R}^d, y\in\mathbb{R}\}$ be our dataset.

Let $F$ be some function class and $f\in F$.

Furthermore, $l$ is some loss function. E.g. the squared loss.

Def: True/Population Risk

\begin{equation} R_D(f) = \mathbb{E}_{(x,y)\sim P_{xy}} l(y, f(x)) \tag{1} \end{equation}

Def: Training/Empirical Risk \begin{equation} \hat{R}_D(f) = \frac{1}{n}\sum_{i=1}^n l(y_i, f(x_i)) \tag{2} \end{equation}

Now in my lecture we used empirical risk minimization for linear regression:

\begin{equation} \hat{f} := \underset{f\in F}{\arg\min} \ \hat{R}_D(f) \tag{3} \end{equation}

Now we also have the minimizer of the true risk

\begin{equation} f^{*} := \underset{f\in F}{\arg\min} \ R_D(f) \tag{4} \end{equation}

Now I'm wondering: For $n \to \infty$ can we say that:

i) $\hat{f} \to f^{*}$?

ii) $\hat{R}_D(\hat{f}) \to R_D(\hat{f})$?

For i) I'd say that yes, the minimizer of the empirical risk will converge to the minimizer of the true risk.

Now in ii) it was said that this doesn't hold because $\hat{f}$ depends on the data set but what confuses me is: If we increase $n$, don't we increase the data set as well and thus our data set "converges" to the true population. And if we then minimize, we'd of course get equality simply because the empirical risk is now equivalent to the true risk.

Can someone elaborate on i and ii but especially ii?

Answer 1

Since $\hat f$ and $f^*$ are defined as risk minimisers, points i. and ii. are intimately connected. I think that this amount to a problem of uniform convergence of the risks over the class $F$. Moreover, you should be careful when defining the convergence type "$\to$" and what you are exactly looking for.

A reference you may want to look at is chapter 3 in Vapnik (1998) "Statistical Learning Theory", or for easier access Vapnik' Principles of Risk Minimization.

In brief, my understanding is: if you have uniform convergence, that is if as $n\to\infty$, for any $\epsilon >0$, you have $$P_{xy}\left\{\sup _{f \in F}\left|R_D(f)-\hat R_D(f)\right|>\varepsilon\right\} \to 0$$

you also have $$R_D(\hat f) \to_p R_D(f^*).$$

To elaborate a bit, under certain conditions, you have a well behaved problem, where as the size of the sample gets large, you get closer and closer to the ground truth and the empirical risk minimization principle is consistent. Thus, you are able to "retrieve correctly" both the minimising function and the corresponding value of the risk.

The problem now is to show whether the condition above is satisfied for the problem at hand. There are several ways to do this (as @microhaus suggested in the comment). For sure, there are cases where this condition is satisfied.

(EDIT: for example, in the case of linear regression, with squared-loss function and $F = \{f_\theta(x)=X^\top \theta, \theta \in\Theta\}$, with $\Theta$ closed and bounded (you can get rid of closedness), you have uniform convergence (e.g. see Bierens (1991) Topics in Advanced Econometrics, Ch. 4))

Might be that what they told you in class needs to be contextualized in a class of problems or the professor meant something slightly different. If you can, you should definitely ask her/him clarifications; it's an excellent question.