# Difference between generalisation error (Vapnik risk) and frequentist (statistical) risk

http://www.iro.umontreal.ca/~slacoste/teaching/ift6269/A19/notes/lecture5.pdf

I always learned: "risk is the expected loss". In these lecture notes I see two different definitions of risk: the generalisation error, also called Vapnik risk by the lecturer, defined as:

$$L(P, f) = \mathbb{E}_{P_0} [ \ell (Y, f(X)) ]$$,

where $$\ell$$ is the loss function (for predicting Y), $$f(X)$$ is the prediction of $$Y$$ on the basis of $$X$$, and $$(X_i, Y_i) \overset{i.i.d.}{\sim} P_0$$.

Now, one page further, the "frequentists risk" is defined as follows:

$$R(P, \delta) = \mathbb{E}_{D \sim P} [ L(P, \delta(D) ]$$,

where we have a decision function $$\delta$$ - in case of prediction some $$Y$$ from some $$X$$, this would just be a function $$f$$ of $$X$$, so just as in the Vapnik risk. The expectation is taken to be over some distribution $$P$$ - maybe here is the difference? What is the point of using the joint $$P$$ here, and the point $$P_0$$ in the Vapnik risk (what is the difference?)?

The frequentist risk is a function with the same variables as the Vapnik risk; is the difference in which quantities are treated as random?

I really fail to see the difference: to me it seems it's the same expected loss function, only the Vapnik risk is instantiated to prediction (could as well be classification), and the frequentist risk is formulated slightly more general (i.e. $$\delta$$ could also be an estimator in an estimation problem; or an hypothesis test). Or is that the difference?

Thanks!

You are right to raise this question - I have no idea what your instructor was trying to say there, because it is difficult to understand what he means by $$P_0$$.

The expectation is taken to be over some distribution $$P$$ - maybe here is the difference? What is the point of using the joint $$P$$ here, and the point $$P_0$$ in the Vapnik risk (what is the difference?)?

The short answer is that the framework of risk minimization for supervised learning and frequentist parametric point estimation is the same, in the sense that you would ideally like to minimise some expectation of a loss function with respect to a 'true' underlying joint density function which you do not know, but only have indirect access to through training examples drawn i.i.d. from this distribution.

The difference is that for supervised learning, the unknown density over which expectations are computed is a joint distribution $$P(X, Y)$$, whereas in parametric point estimation it's $$P(X)$$.

The frequentist risk is a function with the same variables as the Vapnik risk; is the difference in which quantities are treated as random?

See the comparison below.

I really fail to see the difference: to me it seems it's the same expected loss function, only the Vapnik risk is instantiated to prediction (could as well be classification), and the frequentist risk is formulated slightly more general (i.e. $$\delta$$ could also be an estimator in an estimation problem; or an hypothesis test). Or is that the difference?

It is exactly the same framework of taking an expectation with respect to some unknown distribution $$P$$, just contextual differences between the tasks. Have a look at the short paper by Vapnik (1999).

Risk minimization in supervised learning.

Here is an extract from Vapnik (1999):

Problem of Risk Minimization. In order to choose the best available approximation to the supervisor's response, one measures the loss or discrepancy $$L(y, f(x, \alpha))$$ between the response $$y$$ of the supervisor to a given input $$x$$ and the response $$f(x, \alpha)$$ provided by the learning machine. Consider the expected value of the loss, $$R(\alpha) = \int L(y, f(x, \alpha)) dP(x,y).$$ The goal is to find the function $$f(x, \alpha_0)$$ which minimizes the risk functional $$R(\alpha)$$ (over the class of functions $$f(x, \alpha), \alpha \in \Lambda)$$ in the situation where the joint probability distribution $$P(x,y)$$ is unknown and the only available information is contained in the training set $$(1)$$.

The supervised learning setting requires that you postulate some restricted class of functions $$\mathcal{F}$$, from which you can choose a function $$f$$, typically by some algorithmic procedure e.g. empirical risk minimisation.

As an example, you might choose $$\mathcal{F}$$ to be the space of all linear classifiers of the following form,

$$f_\alpha(x) = \begin{cases} 1 &\text{if} \quad \alpha^Tx \geq 0 \\ 0 &\text{if} \quad \alpha^Tx < 0. \\\end{cases}$$

You also specify a loss function $$L$$, whose functional form depends on whether you are doing regression, classification, or density estimation.

If you now look at the loss function in the integral, you will note it depends on three things, the unknown, random input $$X$$, and so the unknown random supervisor response $$Y$$, and also the choice of function $$f \in \mathcal{F}$$. It encodes the 'correctness' of prediction through a deviation between $$y$$ and $$f(x)$$.

The risk $$R$$ is the expectation of the loss function with respect to the true unknown joint distribution $$P$$. It is a functional $$R(\cdot) : \mathcal{F} \rightarrow \mathbb{R}$$ because it takes a function $$f$$ and returns a fixed number.

If you choose to index each function $$f \in \mathcal{F}$$ with a parameter $$\alpha$$ in some parameter space $$\Lambda$$, then the risk just reduces to a function $$R: \Lambda \rightarrow \mathbb{R}$$.

However, the risk is a theoretical construct in the sense that you cannot compute this fixed number, because even though you've integrated out the input $$X$$ and supervisor label $$Y$$, you do not have knowledge of $$P$$ to carry out this integration.

Risk minimization in parametric point estimation.

In the setting of density estimation, the framework is the same, just a difference in context.

You postulate a parametric family of density functions $$\mathcal{P} = \{f(x; \theta) : \theta \in \Theta \}$$ indexed by some unknown parameter(s) $$\theta \in \Theta$$.

Given a sample $$X_1, \dots X_n \sim f(x, \theta)$$, you want to estimate the unknown $$\theta$$ using an estimator, which is a function of the data $$\hat{\theta} = \hat{\theta}(X_1, \dots, X_n)$$, ideally to minimise the risk (although this is not possible for the same reasons as above).

The risk is the expectation of the loss with respect to the true unknown joint density $$f(X_1, \dots, X_n ; \theta)$$.

$$R(\theta, \hat{\theta}) = \mathbb{E}_{\theta}[L(\theta, \hat{\theta})] = \int \cdots \int L(\theta, \hat{\theta}) f(x_1, \dots, x_n; \theta) \, dx_1 \cdots \,dx_n$$

However, your loss now encodes a deviation between your unknown parameter $$\theta$$ and the estimator $$\hat{\theta}$$, rather than between a supervisor response $$y$$ and prediction $$f(x)$$.

Now because you 'integrate out' $$X_1, \dots, X_n$$, $$R$$ returns a fixed number. It depends on the unknown parameter $$\theta$$ and your choice of estimator $$\hat{\theta}$$, or in decision terminology, a decision rule $$\delta$$.

In the ML/statistical learning community, e.g. in Vapnik (1999), the risk $$R$$ is treated as a functional. In frequentist theoretical statistics e.g. in Lehman & Casella (1998), they treat refer to it as a function. I suspect however that the distinction in any case is not one to worry about and you can move freely between the two without much work.

Similarly, the risk is a theoretical quantity due to unknown $$\theta$$, so typically in frequentist theoretical statistics, we look at the behaviour of one-number summaries of the risk, such as the maximum risk $$\sup_{\theta} R(\theta, \hat{\theta})$$, and how they can be used to bound the risk for a class of estimators that minimise this maximum risk, known as minimax estimators.

In some senses the distinction between machine learning and modern statistics, from the perspective of theory, becomes more artificial the deeper you go; they both share a lot of specialised mathematical machinery developed in the attempt to bound the minimax risk.

References.

Vapnik, V. N. (1999). An overview of statistical learning theory. IEEE Transactions on Neural Networks, 10(5), 988–999. https://doi.org/10.1109/72.

Lehmann, E.L. and Casella, G. (1998) Theory of Point Estimation. 2nd Edition, Springer https://doi.org/10.1007/b98854