# Convergence of Empirical Risk Minimizer and True Risk Minimizer

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

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

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

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

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

Now we also have the minimizer of the true risk

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

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?

• There is a standard general argument for ii), but to be clear, are you restricting yourself only to the case of linear regression i.e. $\mathcal{F} = \{f_{\theta}(x) = \theta^Tx, \space \theta \in \mathbb{R}^d \}$ or are you interested in the general case? And are you familiar with concentration inequalities? IMO using concentration inequalities is the most conventional way (in the statistical learning theory literature) of revealing the subtlety in point ii) concerning the dependence of the ERM $\hat{f}$ on data. Jul 9, 2021 at 9:51
• @luco00. Can you please elaborate why (ii) doesn't hold in general? You mentioned $\hat f$ depends on the data set. As a result, $l(y_i, \hat f(x_i)), i=1, 2, ..., n$ are no longer independent, so the law of large numbers doesn't apply. Did I miss the point? Feb 19, 2023 at 17:45

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.

• +1. For authoritative references and lucid, clear summary of the arguments. Jul 9, 2021 at 10:18
• Did you mean$$\hat R_D(\hat f) \to_p R_D(f^*)$$ This is different from ii) $$\hat{R}_D(\hat{f}) \to_p R_D(\hat{f}).$$ I am curious if (ii) holds under certain conditions. Feb 21, 2023 at 20:21
• Yes, I meant that. This is the usual convergence you are interested in, and under uniform convergence, if you think carefully, the two convergences you wrote should converge to the same thing. In the book from Vapnik I cited above, the example in section 3.2.1 is illuminating. The example shows how the dependency of $\hat{f}$ on data may prevent convergence to the true risk. Summarizing it, the data being a countable set, you can always choose particular functions that fit the data better than they ever could on the population. Feb 22, 2023 at 11:40
• My point is: under uniform convergence, $\hat{f}$ is the empirical risk minimizer ($\hat{R}$), so it minimizes a quantity that is also converging to something as $n \to \infty$ ($R$), so that, in the limit, $\hat{R}(\hat{f})=R(\hat{f})=R(f^*)$. I do not know of examples where $\hat{f} \nrightarrow f^*$, and $\hat{R}(g) \rightarrow R(g)$ (for $g \in \mathcal{G}$, say a specific class of functions containing $\hat{f}$, for any $n$), so that $\hat{R}(\hat{f}) \to R(\hat{f})$ and $\hat{R}(\hat{f}) \nrightarrow R(f^*)$. Feb 23, 2023 at 9:57
• The reference for the claim is: "under uniform convergence". Most of Vapnik's book is literally about that. My intention was only to summarize the basic arguments that are typically used in empirical risk minimization, and its consistency (as per my intuition goes). If you have a reference for statement (ii) in the original question, I would be happy to read it; I've never seen one, nor a counterexample. That is why I keep saying that either I am missing something, or it may need to be better contextualized. Feb 23, 2023 at 10:03