Generalization and uniform laws
\[ % Generalization error \def\err{\textrm{Error}} \]
Goals
- Introduce generalization error, a complexity cost for generic loss functions
- Express complexity as the expressiveness of a function class
- Present uniform bounds as one (conservative) way to control complexity cost
- Prove a ULLN for sufficiently smooth parametric function classes
- Introduce a covering argument to do so
Reading
This is a simplified exposition of Van der Vaart (2000) Example 19.7. One can find a different perspective on the same class of problems in Keener (2010) Chapter 9. A more advanced approach that is finite-sample but limited to bounded functions can be found in Wainwright (2019) Chapter 4.
A generic complexity cost
Recall our decomposition of estimation error, \[ \begin{aligned} \mathscr{R}(\hat{f}) - \mathscr{R}(\overline{f}) ={}& \underbrace{\mathscr{R}(\hat{f}) - \hat{\mathscr{R}}(\hat{f})}_{\textrm{Generalization error}} + \underbrace{\hat{\mathscr{R}}(\hat{f}) - \hat{\mathscr{R}}(\overline{f})}_{\le 0} + \underbrace{\hat{\mathscr{R}}(\overline{f}) - \mathscr{R}(\overline{f})}_{\rightarrow 0 \textrm{ by the LLN}} \ge 0. \end{aligned} \]
The reason the final term goes to zero by a LLN is that \(\overline{f}\) is fixed, and does not depend on the data. In contrast, we choose \(\hat{f}\) to minimize \(\hat{\mathscr{R}}(\cdot)\), and so might expect that \(\hat{\mathscr{R}}(\hat{f})\) is an unduly optimistic estimate of our true risk — namely that \(\hat{\mathscr{R}}(\hat{f}) \le \mathscr{R}(\hat{f})\). The difference \(\mathscr{R}(\hat{f}) - \hat{\mathscr{R}}(\hat{f})\) is sometimes called the “generalization error,” because it refers to the fact that the risk on your observed data may not “generalize” to future, unseen data. The above decomposition shows that a complexity cost must, asymptotically, come from generliazation error.
As with the bias–variance tradeoff, we argued that complexity may — but does not necessarily — increase variance. However, we argued that, if the variance is controlled (e.g. by not having too many parameters), then the risk was also controlled. Similarly, we will now focus on situations when we can control the generalization error, while acknowledging that this control may be too strict, and that complex functions may generalize while failing these controls.
Specifically, the generalization error is small if
\[ \begin{aligned} \left|\mathscr{R}(\hat{f}) - \hat{\mathscr{R}}(\hat{f})\right| = \left| \frac{1}{N} \sum_{n=1}^N\mathscr{R}(\hat{f}(x_n), y_n) - \mathbb{E}_{new}\left[\mathscr{R}(\hat{f}(x_\mathrm{new}), y_\mathrm{new})\right] \right| \rightarrow 0 \quad\textrm{(we want this)}\quad \end{aligned} \]
The problem is that \(\hat{f}\) depends on the data in a perhaps very complicated way, and so the observations \(\mathscr{L}(\hat{f}(x_n), y_n)\) are not independent — they are all dependent on one another through the dependence of \(\hat{f}\) on all the data. There are roughly two routes to controlling this dependence, and they correspond roughtly to the three ways of controlling generalization error in machine learning:
- By showing that the procedure that generated \(\hat{f}\) cannot depend too strongly on the data, or
- By showing that the loss function cannot depend too much on what \(\hat{f}\) is.
The former requires articulating something about how we get \(\hat{f}\), and so typically requires saying something about a particular algorithm in a particular context. The latter is more general, but may be more loose and so too conservative. We will now consider the latter, and try to give some examples of the former later in the course when discussing particular algorithms, like the perceptron algorithm and stochastic gradient descent.
Specifically, we will show the stronger statement that
\[ \begin{aligned} \left|\hat{\mathscr{R}}(\hat{f}) - \mathscr{R}(\hat{f})\right| \le{}& \sup_{f\in \mathcal{F}} \left|\hat{\mathscr{R}}(f) - \mathscr{R}(f)\right| \\={}& \sup_{f\in \mathcal{F}} \left| \frac{1}{N} \sum_{n=1}^N\mathscr{L}(f(x_n), y_n) - \mathbb{E}_{new}\left[\mathscr{L}(f(x_\mathrm{new}), y_\mathrm{new})\right] \right|. \quad\textrm{(a "uniform" law of large numbers)}\quad \end{aligned} \]
Note that this is an asymptotic statement, where the function class \(\mathcal{F}\) is fixed as \(N \rightarrow \infty\). Most modern ML actually focuses on finite–sample results that look something like
\[ \mathbb{P}_{\,}\left(\sup_{f\in \mathcal{F}} \left|\hat{\mathscr{R}}(f) - \mathscr{R}(f)\right| \ge \varepsilon\right) \le C(N, \mathcal{F}, \varepsilon), \]
for some explicit function \(C(\cdot)\). Typically one would hope that, all else fixed, \(C \rightarrow 0\) as \(N \rightarrow \infty\). Furthermore, one usually has \(C \rightarrow 1\) as \(\varepsilon \rightarrow 0\), so you cannot control arbitrarily small changes for any finite \(N\), and the dependence on \(\mathcal{F}\) is somewhat explicit, so you can imagine changing the complexity of your function class as the dataset grows. These results are more realistic but a little more complicated, and so beyond the scope of a course like this.
Howver, in at least some cases, the asymptotic results are simpler to understand, and rely on a similar style of argument to the finite–sample results. So the asymptotic results can give some intuition for the more sophisticated results that you might encounter in ML research or in further study.
Example: uniform laws of large numbers for OLS
Note that the above proof of the consistency of \(\hat{\boldsymbol{\beta}}\) used an explicit formula for \(\hat{\boldsymbol{\beta}}\). In this class, we will often discuss estimators for whom no explicit formula exists because we will find them via black–box optimization procedures. How can we reason in such cases?
Recall that we argued, for a particular \(f\), that a LLN should give
\[ \hat{\mathscr{R}}(f) \rightarrow \mathscr{R}(f). \]
For the OLS case, this expression is the same as
\[ \begin{aligned} \hat{\mathscr{R}}(\boldsymbol{\beta}) ={}& \frac{1}{N} \sum_{n=1}^N(\boldsymbol{x}_n^\intercal\boldsymbol{\beta}- y_n)^2 \\={}& \frac{1}{N} \sum_{n=1}^N\boldsymbol{\beta}^\intercal\boldsymbol{x}_n \boldsymbol{x}_n^\intercal\boldsymbol{\beta}- 2\frac{1}{N} \sum_{n=1}^N\boldsymbol{\beta}^\intercal\boldsymbol{x}_n y_n + \frac{1}{N} \sum_{n=1}^Ny_n^2 \\={}& \boldsymbol{\beta}^\intercal\left(\frac{1}{N} \sum_{n=1}^N\boldsymbol{x}_n \boldsymbol{x}_n^\intercal\right) \boldsymbol{\beta}- 2 \boldsymbol{\beta}^\intercal\left(\frac{1}{N} \sum_{n=1}^N\boldsymbol{x}_n y_n \right) + \frac{1}{N} \sum_{n=1}^Ny_n^2 \\\rightarrow{}& \boldsymbol{\beta}^\intercal\mathbb{E}_{\vphantom{}}\left[\boldsymbol{x}\boldsymbol{x}^\intercal\right] \boldsymbol{\beta}- 2 \boldsymbol{\beta}^\intercal\mathbb{E}_{\vphantom{}}\left[ \boldsymbol{x}y\right] + \mathbb{E}_{\vphantom{}}\left[y_n^2\right] \\={}& \mathbb{E}_{\vphantom{}}\left[(\boldsymbol{x}^\intercal\boldsymbol{\beta}- y)^2 \right] \\={}& \mathscr{R}(\boldsymbol{\beta}). \end{aligned} \]
Unfortunately, this does not translate directly into \(\hat{\boldsymbol{\beta}}\rightarrow \boldsymbol{\beta}^{*}\), since the preceding limit holds only for a fixed \(\boldsymbol{\beta}\). Different \(\boldsymbol{\beta}\) will lead to convergence at different rates, so in theory it may be the case that \(\underset{\boldsymbol{\beta}}{\mathrm{argmin}}\, \hat{\mathscr{R}}(\boldsymbol{\beta})\) does not converge to \(\underset{\boldsymbol{\beta}}{\mathrm{argmin}}\, \mathscr{R}(\boldsymbol{\beta})\).
In the special case of linear regression, show explicitly that \(\hat{\mathscr{R}}(\hat{\boldsymbol{\beta}}) \rightarrow \mathscr{R}(\boldsymbol{\beta}^{*})\). What special structure of the problem permits this result so easily?
Uniform laws of large numbers for smooth function classes
Recall that we want to find conditions under which a uniform law of large numbers (ULLN) holds:
\[ \begin{aligned} \left|\hat{\mathscr{L}}(\hat{f}) - \mathscr{L}(\hat{f})\right| \le{}& \sup_{f\in \mathcal{F}} \left|\hat{\mathscr{L}}(f) - \mathscr{L}(f)\right| \\={}& \sup_{f\in \mathcal{F}} \left| \frac{1}{N} \sum_{n=1}^N\mathscr{L}(f(x_n), y_n) - \mathbb{E}_{new}\left[\mathscr{L}(f(x_\mathrm{new}), y_\mathrm{new})\right] \right|. \end{aligned} \]
Note that the ULLN depends on the function \(f\) only through \(f\mapsto \mathscr{L}(f(x), y)\). Given this, we can define
\[ \begin{aligned} z_n :={}& (x_n, y_n)\\ g(z_n; f) :={}& \mathscr{L}(f(x_n), y_n)\\ \mathcal{G}:={}& \{ g: g(z) = g(z; f) \textrm{ for some }f\in \mathcal{F}\}. \end{aligned} \]
With these transformations, we can rewrite our generalization error in the following more general form:
\[ \sup_{g\in \mathcal{G}} \left|\frac{1}{N} \sum_{n=1}^Ng(z_n) - \mathbb{E}_{\vphantom{}}\left[g(z)\right]\right| =\sup_{g\in \mathcal{G}} \err(g, N) \]
where we define
\[ \err(g,N) := \left|\frac{1}{N} \sum_{n=1}^Ng(z_n) - \mathbb{E}_{\vphantom{}}\left[g(z)\right]\right|. \]
Note that \(\err(g,N)\) is random, since it depends on \(z_1, \ldots, z_N\).
A finite set of functions
We first note that the problem is easy if \(\mathcal{G}\) is finite, i.e., \(\mathcal{G}= \{ g_k \textrm{ for }k=1,\ldots,K < \infty \}\), where each \(g_k\) satisfies \(\mathbb{E}_{\vphantom{}}\left[|g_k(z)|\right] \infty\). In that case,
\[ \sup_{g\in \mathcal{G}} \err(g,N) = \max_{k=1,\ldots,K} \err(g_k, N). \]
Since \(\err(g_k, N) \rightarrow 0\) by the ordinary LLN, it follows that \(\max_{k=1,\ldots,K} \err(g_k, N) \rightarrow 0\) as well, since \(K\) is finite.
Specifically, \(\err(g_k, N) \rightarrow 0\) means that, for any \(\varepsilon > 0\) and \(\delta > 0\), there exists an \(N_k\) such that
\[ N > N_k \Rightarrow \mathbb{P}_{\,}\left(\err(g_k, N) \ge \varepsilon\right) \le \delta. \]
Take \(N > \max_{k =1,\ldots,K} N_k\). Then
\[ \begin{aligned} \mathbb{P}_{\,}\left(\max_{k=1,\ldots,K} \err(g_k, N) \ge \varepsilon \right) ={}& \mathbb{P}_{\,}\left(\bigcup_{k=1}^K \err(g_k, N) \ge \varepsilon\right) \\\le{}& \sum_{k=1}^K \mathbb{P}_{\,}\left(\err(g_k, N) \ge \varepsilon\right) \\\le{}& K \delta. \end{aligned} \]
Since we can take \(\delta = \delta' / K\) for any \(\delta'\), we have proven that \(\sup_{g\in \mathcal{G}} \err(f,N) \rightarrow 0\) in probability.
A covering
The previous trick cannot be applied when \(\mathcal{G}\) is infinite — as is the case in any of our examples, which are parameterized by a continuous parameter and so contain an infinite class of functions.
A classical approach is to finite a finite “cover” of \(\mathcal{G}\). There are many ways to do so, but here we will focus on a particular example (Van der Vaart (2000) Example 19.7). Suppose that: \(\mathcal{G}= \{ f(\cdot; \theta) \textrm{ for some }\theta \in \Omega \}\). Assume:
Assume that \(\Omega\) is compact, and assume that, for each \(z\), \[ \left|g(z; \theta) - g(z; \theta')\right| \le{} M(z) \left\Vert\theta - \theta'\right\Vert, \] where \(M(z) \ge 0\) and \(\mathbb{E}_{\vphantom{}}\left[M(z)\right] < \infty\).
This means that the depednence of \(g(z; \theta)\) can be decomposed into a smooth part depending on \(\theta\), and an integral part depending on \(z\). When this is true, for a fixed \(\gamma > 0\), we can always find a set of \(K(\gamma)\) parameters \(\theta_k\) (depending on \(\gamma\)) such that
\[ \textrm{For each }\theta \in \Omega\textrm{, there exists }\theta_k \textrm{ such that }\left\Vert\theta_k - \theta\right\Vert < \gamma. \]
The smaller \(\gamma\) is, the larger \(K(\gamma)\) must be. That there exist such \(\theta_k\) is guaranteed by the compactness of \(\Omega\), which is a crucial assumption.
Recall that if \(\Omega\) is compact, then every open cover has a finite sub–cover. Using this fact, prove that \(K(\gamma) < \infty\) for each \(\gamma > 0\).
Given this “covering,” for a given \(\theta\) and its associated \(\theta_k\) with \(\left\Vert\theta - \theta_k\right\Vert < \gamma\), we can identify \(g_k(\cdot) = g(\cdot; \theta_k)\).
Using the tiling to produce a ULLN
\[ \begin{aligned} \err(g, N) ={}& \left|\frac{1}{N} \sum_{n=1}^Ng(z_n; \theta) - \mathbb{E}_{\vphantom{}}\left[g(z; \theta)\right]\right| \\={}& \left|\frac{1}{N} \sum_{n=1}^Ng(z_n; \theta) - g(z_n; \theta_k) - \mathbb{E}_{\vphantom{}}\left[g(z; \theta) - g(z; \theta_k)\right] + g(z_n; \theta_k) - \mathbb{E}_{\vphantom{}}\left[g(z; \theta_k)\right]\right| \\ \le{}& \frac{1}{N} \sum_{n=1}^N\left|g(z_n; \theta) - g(z_n; \theta_k)\right| + \mathbb{E}_{\vphantom{}}\left[\left|g(z; \theta) - g(z; \theta_k)\right|\right] + \err(g_k, N) \\ \le{}& \left( \frac{1}{N} \sum_{n=1}^NM(z_n) + \mathbb{E}_{\vphantom{}}\left[M(z)\right] \right) \left\Vert\theta - \theta_k\right\Vert + \err(g_k, N) \\ \le{}& \left( \frac{1}{N} \sum_{n=1}^NM(z_n) + \mathbb{E}_{\vphantom{}}\left[M(z)\right] \right) \gamma + \max_{k=1,\ldots,K} \err(g_k, N). \end{aligned} \]
The right hand side now does not depend on \(g\), so
\[ \sup_{g\in \mathcal{G}} \err(g, N) \le \left( \frac{1}{N} \sum_{n=1}^NM(z_n) + \mathbb{E}_{\vphantom{}}\left[M(z)\right] \right) \gamma + \max_{k=1,\ldots,K} \err(g_k, N). \]
For any fixed \(\gamma\), \(\max_{k=1,\ldots,K} \err(g_k, N) \rightarrow 0\), as shown above. So since \(\frac{1}{N} \sum_{n=1}^NM(z_n) \rightarrow \mathbb{E}_{\vphantom{}}\left[M(z)\right]\), we have that, for any fixed \(\gamma\),
\[ \left( \frac{1}{N} \sum_{n=1}^NM(z_n) + \mathbb{E}_{\vphantom{}}\left[M(z)\right] \right) \gamma + \max_{k=1,\ldots,K} \err(g_k, N) \rightarrow 2 \mathbb{E}_{\vphantom{}}\left[M(z)\right] \gamma. \]
Since \(\gamma\) can be made arbitrarily small (at the cost of requiring even greater \(N\) to make \(\max_{k=1,\ldots,K} \err(g_k, N)\) small), for any \(\varepsilon\) and \(\delta\) we can choose \(\gamma = \varepsilon / 2 \mathbb{E}_{\vphantom{}}\left[M(z)\right]\) and find an \(N\) large enough that
\[ \mathbb{P}_{\,}\left(\sup_{g\in \mathcal{G}} \err(g, N) \ge \varepsilon\right) \le \delta. \]
It follows that \(\sup_{g\in \mathcal{G}} \err(g, N) \rightarrow 0\) in probability.
General covering arguments
Note that the above argument relied on having a covering of the parameter space to give a covering of the function space. The key idea is the covering, not the parameters! Many ULLNs for generic function classes proceed by studying the number of functions it takes to “cover” the function class \(\mathcal{G}\) using some notion of distance between functions, rather than the distance between parameters.
Proving the Integrable Lipschitz condition
It may seem mysterious how to show that a problem satisfies the IL condition directly. An easy way is to bound the derivative with respect to \(\theta\) in terms of a function of \(z\) with finite expectation. Specifically,
Assume that \(\Omega\) is compact. Assume that, for each \(z\), \[ \frac{\partial g(z; \theta)}{\partial \theta} \textrm{ exists and } \left\Vert\frac{\partial g(z; \theta)}{\partial \theta}\right\Vert_2^2 \le M(z) \] where \(M(z) \ge 0\) and \(\mathbb{E}_{\vphantom{}}\left[M(z)\right] < \infty\). Then \(g(z; \theta)\) satisfies the integrable Lipschitz condition.
The proof goes via the fundamental theroem of calculus. For any \(\theta\) and \(\theta'\) in \(\Omega\), let \(\theta(t) = \theta' t+ (1 - t) \theta\) for \(t\in [0,1]\) denote a parameterized path from \(\theta\) to \(\theta'\). Then, for any \(z\),
\[ \begin{aligned} \left|g(z; \theta') - g(z; \theta)\right| ={}& \left|g(z; \theta(1)) - g(z; \theta(0))\right| \\={}& \left|\int_{0}^1 \frac{\partial g(z; \theta(t))}{\partial t} dt\right| & \textrm{(by the fundamental theorem of calculus)} \\={}& \left|\int_{0}^1 \left. \frac{\partial g(z; \theta)}{\partial \theta^\intercal} \right|_{\theta = \theta(t)} \frac{\partial \theta(t)}{\partial t} dt\right| & \textrm{(by the chain rule)} \\={}& \left|\left( \int_{0}^1 \left. \frac{\partial g(z; \theta)}{\partial \theta^\intercal} \right|_{\theta = \theta(t)} dt\right) (\theta' - \theta)\right| & \textrm{(by the definition of $\theta(t)$)} \\\le{}& \left\Vert\sup_{t\in [0,1]} \left. \frac{\partial g(z; \theta)}{\partial \theta^\intercal} \right|_{\theta = \theta(t)} \right\Vert_2 \left\Vert\theta' - \theta\right\Vert_2 & \textrm{(by Cauchy-Schwarz)}\\\le{}& M(z) \left\Vert\theta' - \theta\right\Vert_2. & \textrm{(by assumption)} \end{aligned} \]
Often it’s easier to show that the norm of the partial derivative is bounded by a function of \(z\) (that is, of \(x\) and \(y\)) with finite expectation than to prove the stronger IL condition.
Revisiting the OLS example using the integrable Lipschitz condition
For example, taking squared loss and linear regression, we get
\[ g(z, \theta) = \mathscr{L}(f(\boldsymbol{x}), y) = (\boldsymbol{x}^\intercal\theta - y)^2 = y^2 - 2 y\boldsymbol{x}^\intercal\theta + \mathrm{trace}\left(\boldsymbol{x}\boldsymbol{x}^\intercal\theta \theta^\intercal\right). \]
Let us assume that \(\Omega\) is compact. (One can show that \(\Omega\) can be safely taken to be compact with high probability as \(N\) grows, but I will leave that as a potential homework problem.)
Recall that we can show directly in your homework that this loss obeys a ULLN. We can also the IL condition directly by the triangle inequality and Cauchy–Schwartz:
\[ \begin{aligned} g(z, \theta) - g(z, \theta') ={}& - 2 y\boldsymbol{x}^\intercal(\theta - \theta') + \mathrm{trace}\left(\boldsymbol{x}\boldsymbol{x}^\intercal(\theta \theta^\intercal- \theta' {\theta'}^\intercal)\right). \\={}& - 2 y\boldsymbol{x}^\intercal(\theta - \theta') + \mathrm{trace}\left(\boldsymbol{x}\boldsymbol{x}^\intercal(\theta + \theta') (\theta - \theta')^\intercal\right) \quad\Rightarrow\\ \left|g(z, \theta) - g(z, \theta')\right| \le{}& 2 \left|y\right| \left\Vert\boldsymbol{x}\right\Vert_2 \left\Vert\theta - \theta'\right\Vert_2 + \left\Vert\boldsymbol{x}\right\Vert^2_2 \left\Vert\theta + \theta'\right\Vert_2 \left\Vert\theta - \theta'\right\Vert_2 \\\le{}& \left( 2 \left|y\right| \left\Vert\boldsymbol{x}\right\Vert_2 + \left\Vert\boldsymbol{x}\right\Vert^2_2 \left\Vert\theta + \theta'\right\Vert_2 \right) \left\Vert\theta - \theta'\right\Vert_2 \\\le{}& 2 \left( \left|y\right| \left\Vert\boldsymbol{x}\right\Vert_2 + \left\Vert\boldsymbol{x}\right\Vert^2_2 \sup_{\theta \in \Omega} \left\Vert\theta\right\Vert_2 \right) \left\Vert\theta - \theta'\right\Vert_2 \end{aligned} \]
where \(\sup_{\theta \in \Omega} \left\Vert\theta\right\Vert\) is finite because \(\Omega\) is compact, and the operator norm of \(\boldsymbol{x}\boldsymbol{x}\intercal\) is equal to \(\left\Vert\boldsymbol{x}\right\Vert_2^2\). We can thus take
\[ M(z) = 2 \left( \left|y\right| \left\Vert\boldsymbol{x}\right\Vert_2 + \left\Vert\boldsymbol{x}\right\Vert^2_2 \sup_{\theta \in \Omega} \left\Vert\theta\right\Vert_2 \right), \]
and see that quadratic loss satisfies the IL condition, and so a ULLN, under standard conditions on the moments of \(\boldsymbol{x}\) and \(y\).
Alternatively, we can prove the IL condition by simply taking the derivative,
\[ \begin{aligned} \left\Vert\frac{\partial g(z, \theta)}{\partial \theta}\right\Vert_2 ={}& \left\Vert-2 y\boldsymbol{x}+ 2 \boldsymbol{x}\boldsymbol{x}^\intercal\theta\right\Vert_2 \\\le{}& 2 \left|y\right| \left\Vert\boldsymbol{x}\right\Vert_2 + 2 \left\Vert\boldsymbol{x}\right\Vert_2^2 \sup_{\theta \in \Omega} \left\Vert\theta\right\Vert_2, \end{aligned} \] which in this case gives the same bound as the more tedious computation above.