Regret decomposition

Regret decomposition

Suppose we have a function class \(\mathcal{F}\), which is a strict subset of all possible functions, and a risk function \(\mathscr{R}(\cdot)\) defined on functions. Suppose we define \[ \hat{f}:= \underset{f\in \mathcal{F}}{\mathrm{argmin}}\, \hat{\mathscr{R}}(f) \quad\quad \overline{f}:= \underset{f\in \mathcal{F}}{\mathrm{argmin}}\, \mathscr{R}(f) \quad\quad f^{\star}:= \underset{f}{\mathrm{argmin}}\, \mathscr{R}(f). \] The analogies for linear regression would be \(\hat{f}(\boldsymbol{x}) = \hat{\boldsymbol{\beta}}^\intercal\boldsymbol{x}\), \(\overline{f}(\boldsymbol{x}) = {\boldsymbol{\beta}^{*}}^\intercal\boldsymbol{x}\), and \(f^{\star}(\boldsymbol{x}) = \mathbb{E}_{\vphantom{}}\left[y\vert \boldsymbol{x}\right]\).

We are interested in the regret, \(\mathscr{R}(\hat{f}) - \mathscr{R}(f^{\star})\). Recall that we can decompose the regret into two terms:

\[ \textrm{Regret}(\hat{f}) = \mathscr{R}(\hat{f}) - \mathscr{R}(f^{\star}) = \underbrace{\mathscr{R}(\hat{f}) - \mathscr{R}(\overline{f})}_{\textrm{Estimation error}} + \underbrace{\mathscr{R}(\overline{f}) - \mathscr{R}(f^{\star})}_{\textrm{Representation error}}. \]

Intuitively, as our model class \(\mathcal{F}\) gets more complex (e.g. as we reduce the regularization penalty, or add more basis functions to the regression space), we make the representation error lower, but may increase the estimation error.

In an oversimplification, estimation error loosely corresponds to “variance” and representation error to “bias” in correctly specified linear regeression, though this analogy is misleading, since estimation error can be cause both by statistical bias and variance.

However, it is clear that, if there is a cost to expressive \(\mathcal{F}\), it must come from estimation error, and if it were not necessary to fit \(f\) from the data, we would simply make \(\mathcal{F}\) as expressive as possible. Therefore, for this unit, we will focus on understanding the relationship between \(\mathscr{R}(\hat{f}) - \mathscr{R}(\overline{f})\) and complexity of \(\mathcal{F}\).

Regret decomposition for linear regression and least squares loss

Let us now consider the special case of linear models and squared loss. Take \(\mathscr{L}(f(\boldsymbol{x}), y) = (f(\boldsymbol{x}) - y)^2\) and so \(\mathscr{R}(\cdot) = \mathbb{E}_{\boldsymbol{x}, y}\left[(y- f(\boldsymbol{x}))^2\right]\). Given some \(\boldsymbol{x}_\mathrm{new}\), we want to find a best guess \(f(\boldsymbol{x}_\mathrm{new})\) for the value of \(y_\mathrm{new}\): specifically, we want to find a function that minimizes the risk

\[ f^{\star}(\cdot) := \underset{f}{\mathrm{argmin}}\, \mathscr{R}(f) = \underset{f}{\mathrm{argmin}}\, \mathbb{E}_{\vphantom{}}\left[\mathscr{L}(f(\boldsymbol{x}_\mathrm{new}), y_\mathrm{new})\right] = \underset{f}{\mathrm{argmin}}\, \mathbb{E}_{\vphantom{}}\left[\left( y_\mathrm{new}- f(\boldsymbol{x}_\mathrm{new}) \right)^2\right]. \]

This is a functional optimization problem over an infinite dimensional space! You can solve this using some fancy math, but you can also prove directly that the best choice is

\[ f^{\star}(\boldsymbol{x}_\mathrm{new}) = \mathbb{E}_{\vphantom{}}\left[y_\mathrm{new}| \boldsymbol{x}_\mathrm{new}\right]. \]

Suppose we consider any other function \(f(\cdot)\). The risk is larger, since

\[ \begin{aligned} \mathbb{E}_{\vphantom{}}\left[\left( y_\mathrm{new}- f(\boldsymbol{x}_\mathrm{new}) \right)^2\right] ={}& \mathbb{E}_{\vphantom{}}\left[ \mathbb{E}_{\vphantom{}}\left[\left( y_\mathrm{new}- f(\boldsymbol{x}_\mathrm{new}) \right)^2 | \boldsymbol{x}_\mathrm{new}\right] \right] &\textrm{(Tower property)} \\={}& \mathbb{E}_{\vphantom{}}\left[ \mathbb{E}_{\vphantom{}}\left[\left( y_\mathrm{new}- f^{\star}(\boldsymbol{x}_\mathrm{new}) + f^{\star}(\boldsymbol{x}_\mathrm{new}) - f(\boldsymbol{x}_\mathrm{new}) \right)^2 | \boldsymbol{x}_\mathrm{new}\right] \right] &\textrm{(add and subtract)} \\={}& \mathbb{E}_{\vphantom{}}\left[\left( y_\mathrm{new}- f^{\star}(\boldsymbol{x}_\mathrm{new}) \right)^2\right] + \\& \mathbb{E}_{\vphantom{}}\left[\left( f^{\star}(\boldsymbol{x}_\mathrm{new}) - f(\boldsymbol{x}_\mathrm{new}) \right)^2\right] + \\& 2 \mathbb{E}_{\vphantom{}}\left[ \mathbb{E}_{\vphantom{}}\left[y_\mathrm{new}- f^{\star}(\boldsymbol{x}_\mathrm{new}) | \boldsymbol{x}_\mathrm{new}\right] \left( f^{\star}(\boldsymbol{x}_\mathrm{new}) - f(\boldsymbol{x}_\mathrm{new}) \right) \right] &\textrm{(expand the quadratic, use conditioning)} \\={}& \mathbb{E}_{\vphantom{}}\left[\left( y_\mathrm{new}- f^{\star}(\boldsymbol{x}_\mathrm{new}) \right)^2\right] + \\& \mathbb{E}_{\vphantom{}}\left[\left( f^{\star}(\boldsymbol{x}_\mathrm{new}) - f(\boldsymbol{x}_\mathrm{new}) \right)^2\right] & \textrm{($\mathbb{E}_{\vphantom{}}\left[y_\mathrm{new}- f^{\star}(\boldsymbol{x}_\mathrm{new}) | \boldsymbol{x}_\mathrm{new}\right]=0$ by definition)} \\\ge& \mathbb{E}_{\vphantom{}}\left[\left( y_\mathrm{new}- f^{\star}(\boldsymbol{x}_\mathrm{new}) \right)^2\right]. & \textrm{(anything squared is greater than $0$)} \end{aligned} \]

Approximating the conditional expectation

We now know that the optimal regression function is given by \(f^{\star}(\boldsymbol{x}) = \mathbb{E}_{\vphantom{}}\left[y| \boldsymbol{x}\right]\). The problem is how to estimate it. Typically, we don’t know the functional form of \(\mathbb{E}_{\vphantom{}}\left[y| \boldsymbol{x}\right]\), because we don’t know the joint distribution of \(\boldsymbol{x}\) and \(y\). But suppose we approximate it with a linear function of the form \[ \mathbb{E}_{\vphantom{}}\left[y| \boldsymbol{x}\right] \approx f(\boldsymbol{x}; \boldsymbol{\beta}) := \approx \boldsymbol{\beta}^\intercal\boldsymbol{x}. \] This amounts to using the approximating function class \[ \mathcal{F}_{lin} = \{ f: f(\boldsymbol{x}) = \boldsymbol{x}^\intercal\boldsymbol{\beta}\textrm{ for some }\boldsymbol{\beta}\in \mathbb{R}^{P} \}. \]

Note that we are not assuming this is true — we do not expect that \(\mathbb{E}_{\vphantom{}}\left[y| \boldsymbol{x}\right]\) is a linear function of \(\boldsymbol{x}\). Rather, we are finding the best approximation to the unknown \(\mathbb{E}_{\vphantom{}}\left[y_\mathrm{new}| \boldsymbol{x}_\mathrm{new}\right]\) amongst the class of functions of the form \(\boldsymbol{\beta}^\intercal\boldsymbol{x}_\mathrm{new}\).

The linear assumption gives us a finite–dimensional class of candidate functions, which gives us a tractable optimization problem. Under this approximation, the problem becomes \[ \begin{aligned} \beta^{*}:={}& \underset{\beta}{\mathrm{argmin}}\, \mathbb{E}_{\vphantom{}}\left[\left( y- \boldsymbol{\beta}^\intercal\boldsymbol{x}\right)^2\right] \\ ={}& \underset{\beta}{\mathrm{argmin}}\, \left(\mathbb{E}_{\vphantom{}}\left[y^2\right] - 2 \boldsymbol{\beta}^\intercal\mathbb{E}_{\vphantom{}}\left[y\boldsymbol{x}\right] + \boldsymbol{\beta}^\intercal\mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}\boldsymbol{x}^\intercal\right] \boldsymbol{\beta}\right). \end{aligned} \]

Differentiating with respect to \(\boldsymbol{\beta}\) and solving gives

\[ \boldsymbol{\beta}^{*}= \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}\boldsymbol{x}^\intercal\right] ^{-1} \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}y\right]. \]

The plug-in estimator and empirical risk

Of course, we cannot compute \(\boldsymbol{\beta}^{*}\) any more than we can compute \(\mathbb{E}_{\vphantom{}}\left[y\vert \boldsymbol{x}\right]\), since we don’t know \(p(\boldsymbol{x}, y)\). Recall that our computable estimate was

\[ \hat{\boldsymbol{\beta}}:= \underset{\boldsymbol{\beta}}{\mathrm{argmin}}\, \hat{\mathscr{R}}(\boldsymbol{\beta}) = \underset{\boldsymbol{\beta}}{\mathrm{argmin}}\, \frac{1}{N} \sum_{n=1}^N\left(y_n - \boldsymbol{\beta}^\intercal\boldsymbol{x}_n \right)^2 = \left(\frac{1}{N} \boldsymbol{X}^\intercal\boldsymbol{X}\right)^{-1} \frac{1}{N} \boldsymbol{X}^\intercal\boldsymbol{Y}. \]

By the LLN, as \(N \rightarrow \infty\), \[ \frac{1}{N} \boldsymbol{X}^\intercal\boldsymbol{X}\rightarrow \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}\boldsymbol{x}^\intercal\right] \quad\textrm{and} \frac{1}{N} \boldsymbol{X}^\intercal\boldsymbol{Y}\rightarrow \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}y\right]. \] Furthermore, in an advanced probability class, you can show that, if \(\mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}\boldsymbol{x}^\intercal\right]\) is invertible, then by the continuous mapping theorem (CMT) \[ \left(\frac{1}{N} \boldsymbol{X}^\intercal\boldsymbol{X}\right)^{-1} \rightarrow \mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}\boldsymbol{x}^\intercal\right]^{-1}. \] Another application of the CMT then gives that \[ \hat{\boldsymbol{\beta}}\rightarrow \boldsymbol{\beta}^{*}. \] We have shown that, as \(N \rightarrow \infty\), the OLS estimator converges to the best linear estimator of the risk function! That is, in fact, the best quantity you could hope for it to converge to.

This is not a coincidence, since \(\hat{\boldsymbol{\beta}}\) is minimizing an objective function that is closely related to \(\mathscr{R}(\boldsymbol{\beta})\). Note that we cannot actually compute \(\beta^{*}\) directly, since we still don’t know the joint distribution of \(\boldsymbol{x}\) and \(y\), and so cannot compute the preceding expectations. However, if we have a training set, we can approximate the expected loss:

\[ \hat{\mathscr{R}}(\boldsymbol{\beta}) := % \meann \loss(\betav^\trans\xv_n, \y_n) = \frac{1}{N} \sum_{n=1}^N\left( y_n - \boldsymbol{\beta}^\intercal\boldsymbol{x}_n \right)^2. \]

For any particular \(\boldsymbol{\beta}\), \(\hat{\mathscr{R}}(\boldsymbol{\beta}) \rightarrow \mathscr{R}(\boldsymbol{\beta})\) by the LLN, so it might (tentatively) make sense to use \(\hat{\mathscr{R}}(\boldsymbol{\beta})\) as a proxy for \(\mathscr{R}(\boldsymbol{\beta})\). And of course, \(\hat{\boldsymbol{\beta}}:= \underset{\boldsymbol{\beta}}{\mathrm{argmin}}\, \hat{\mathscr{R}}(\boldsymbol{\beta})\), and since we have shown manually that \(\hat{\boldsymbol{\beta}}\rightarrow \boldsymbol{\beta}^{*}\), we see that \(\hat{\mathscr{R}}(\boldsymbol{\beta})\) is a good proxy for \(\mathscr{R}(\boldsymbol{\beta})\) in this particular case, in the sense that we learn a function, \(\hat{\boldsymbol{\beta}}^\intercal\boldsymbol{x}\), that converges, as \(N \rightarrow \infty\), to the best possible function in our function class: \(\hat{\boldsymbol{\beta}}^\intercal\boldsymbol{x}\rightarrow {\boldsymbol{\beta}^{*}}^\intercal\boldsymbol{x}\).

Basis expansions and regularization

Of course, we would like to estimate \(f^{\star}(\boldsymbol{x}) = \mathbb{E}_{\vphantom{}}\left[y\vert \boldsymbol{x}\right]\), not the best linear estimator. However, as we discussed in the regression unit, we can form new regression estimators out of old ones by regressing on non–linear transformations of \(\boldsymbol{x}\). For example, when \(x\) is a scalar, we could consider the following hierarchy of linear regressions:

\[ \begin{aligned} f_0(x; \beta) ={}& \beta_0 \\ f_1(x; \boldsymbol{\beta}) ={}& \beta_0 + \beta_1 x\\ f_2(x; \boldsymbol{\beta}) ={}& \beta_0 + \beta_1 x+ \frac{1}{2} \beta_2 x^2\\ \vdots{}&\\ f_K(x; \boldsymbol{\beta}) ={}& \sum_{k=1}^K \frac{1}{k!} \beta_k x^k. \end{aligned} \]

As \(K\) increases, \(f\) becomes arbitrarily expressive — in fact, it can express any piecewise continuous function on a compact domain! However, the corresponding \(\boldsymbol{\beta}\) become harder and harder to estimate. In fact, as long as \(x\) takes on \(N\) distinct values, when \(K > N\) the matrix \(\boldsymbol{X}\) is not full-rank, and \(\hat{\boldsymbol{\beta}}\) is not uniquely defined.

Conversely, if we have a function class that is too expressive, recall that we can restric the expressiveness by “regularization,” or restricting the norm of the coefficients Specifically, recall that L1 and L2 regression could equivalently be written as \[ \begin{aligned} \mathcal{F}_{L1} ={}& \{ f: f\in \mathcal{F}_{lin} \textrm{ with }\left\Vert\boldsymbol{\beta}\right\Vert_1 \le C \textrm{ for some }C > 0 \} \\ \mathcal{F}_{L2} ={}& \{ f: f\in \mathcal{F}_{lin} \textrm{ with }\left\Vert\boldsymbol{\beta}\right\Vert_2 \le C \textrm{ for some }C > 0 \}. \end{aligned} \] By forming flexible basis expansions, then regularizing, we can trade off complexity of our function class.

Estimation error decomposition

If there is to be any penalty for having an expressive \(\mathcal{F}\), it must come from the estimation error term \(\mathscr{R}(\hat{f}) - \mathscr{R}(\overline{f})\). To understand how estimation and complexity interact, we can further decompose the estimation error:

\[ \begin{aligned} \underbrace{\mathscr{R}(\hat{f}) - \mathscr{R}(\overline{f})}_{\textrm{Estimation error}} ={}& \underbrace{\mathscr{R}(\hat{f}) - \hat{\mathscr{R}}(\hat{f})}_{\textrm{"Generalization error"}} + \underbrace{\hat{\mathscr{R}}(\hat{f}) - \hat{\mathscr{R}}(\overline{f})}_{\textrm{"Negative term" $\le 0$}} + \underbrace{\hat{\mathscr{R}}(\overline{f}) - \mathscr{R}(\overline{f})}_{\textrm{LLN term}} \end{aligned} \]

This decomposition is useful because

• \(\mathscr{R}(\hat{f}) - \mathscr{R}(\overline{f}) \ge 0\) because \(\overline{f}\) minimizes \(\mathscr{R}(\cdot)\)
• \(\hat{\mathscr{R}}(\hat{f}) - \hat{\mathscr{R}}(\overline{f}) \le 0\) because \(\hat{f}\) minimizes \(\hat{\mathscr{R}}(\cdot)\)
• \(\hat{\mathscr{R}}(\overline{f}) - \mathscr{R}(\overline{f}) \rightarrow 0\) by the LLN because \(\overline{f}\) is fixed.

The key term that we don’t know anything about is \(\mathscr{R}(\hat{f}) - \hat{\mathscr{R}}(\hat{f})\), the generalization error. The generalization error measures how well the empirical risk approximates the true risk when evaluated at \(\hat{f}\). Intuitively, we might expect that the generalization error is positive, since we choose \(\hat{f}\) to minimize \(\hat{\mathscr{R}}(\cdot)\), and so \(\hat{\mathscr{R}}(\hat{f})\) might be an “optimistic” estimate of \(\mathscr{R}(\hat{f})\). In particular, we cannot apply the LLN to \(\hat{\mathscr{R}}(\hat{f})\) because \[ \hat{\mathscr{R}}(\hat{f}) = \frac{1}{N} \sum_{n=1}^N\underbrace{\mathscr{L}(\hat{f}(\boldsymbol{x}_n), y_n)}_{\textrm{Not IID!}}, \] and the observations are not IID, since \(\hat{f}\) depends on all the training data.

In itself, this decomposition does not tell us anything, because the genearlization error might be very positive, but canceled by a large “negative term.” However, if we are able to show that the generalization error goes to zero, then

\[ \begin{aligned} &\textrm{If generalization error $\rightarrow 0$, then }\\ &0 \le \mathscr{R}(\hat{f}) - \mathscr{R}(\overline{f}) \le \left|\mathscr{R}(\hat{f}) - \hat{\mathscr{R}}(\hat{f})\right| + \left|\hat{\mathscr{R}}(\overline{f}) - \mathscr{R}(\overline{f})\right| \rightarrow 0 \quad \Rightarrow\\ &\mathscr{R}(\hat{f}) - \mathscr{R}(\overline{f}) \rightarrow 0. \end{aligned} \]

That is, low generalization error is sufficient but not necessary for low estimation error.

This is nice, because we don’t know anything about \(\overline{f}\), and so cannot practically evaluate it. However, we do know \(\hat{f}\), \(\hat{\mathscr{R}}\), and, as we will see, can either estimate \(\mathscr{R}\) using out-of-sample data, or study it using statistical properties of \(\hat{f}\) and \(\hat{\mathscr{R}}\). This unit, then is devoted to studying the generlization error, both from a practical and theoretical point of view.