Effects of model complexity

Think of a model family with an associated measure of complexity, such as number of trainable parameters. Suppose that for each setting of the complexity measure, we can solve the empirical risk minimization problem. We can then plot what happens to risk and empirical risk as we vary model complexity.

A traditional view of generalization posits that as we increase model complexity initially both empirical risk and risk decrease. However, past a certain point the risk begins to increase again, while empirical risk decreases.

The graphic shown in many textbooks is a u-shaped risk curve. The complexity range below the minimum of the curve is called underfitting. The range above is called overfitting.

This picture is often justified using the bias-variance trade-off, motivated by a least squares regression analysis. However, it does not seem to bear much resemblance to what is observed in practice.

We have already discussed the example of the Perceptron which achieves zero training loss and still generalizes well in theory. Numerous practitioners have observed that other complex models also can simultaneously achieve close to zero training loss and still generalize well. Moreover, in many cases risk continues to decreases as model complexity grows and training data are interpolated exactly down to (nearly) zero training loss. This empirical relationship between overparameterization and risk appears to be robust and manifests in numerous model classes, including overparameterized linear models, ensemble methods, and neural networks.

In the absence of regularization and for certain model families, the empirical relationship between model complexity and risk is more accurately captured by the double descent curve in the figure above. There is an interpolation threshold at which a model of the given complexity can fit the training data exactly. The complexity range below the threshold is the underparameterized regime, while the one above is the overparameterized regime. Increasing model complexity in the overparameterized regime continues to decrease risk indefinitely, albeit at decreasing marginal returns, toward some convergence point.

The double descent curve is not universal. In many cases, in practice we observe a single descent curve throughout the entire complexity range. In other cases, we can see multiple bumps as we increase model complexity.Liang, Rakhlin, and Zhai, “On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels,” in Conference on Learning Theory, 2020. However, the general point remains. There is no evidence that highly overparameterized models do not generalize. Indeed, empirical evidence suggests larger models not only generalize, but that larger models make better out-of-sample predictors than smaller ones.He et al., “Deep Residual Learning for Image Recognition,” in Computer Vision and Pattern Recognition, 2016; Huang et al., “Gpipe: Efficient Training of Giant Neural Networks Using Pipeline Parallelism,” Advances in Neural Information Processing Systems 32 (2019): 103–12.

Optimization versus generalization

Training neural networks with stochastic gradient descent, as is commonly done in practice, attempts to solve a non-convex optimization problem. Reasoning about non-convex optimization is known to be difficult. Theoreticians see a worthy goal in trying to prove mathematically that stochastic gradient methods successfully minimize the training objective of large artificial neural networks. The previous chapter discussed some of the progress that has been made toward this goal.

It is widely believed that what makes optimization easy crucially depends on the fact that models in practice have many more parameters than there are training points. While making optimization tractable, overparameterization puts burden on generalization.

We can force a disconnect between optimization and generalization in a simple experiment that we will see next. One consequence is that even if a mathematical proof established the convergence guarantees of stochastic gradient descent for training some class of large neural networks, it would not necessarily on its own tell us much about why the resulting model generalizes well to the test objective.

Indeed, consider the following experiment. Fix training data (x_1,y_1),\dots, (x_n, y_n) and fix a training algorithm A that achieves zero training loss on these data and achieves good test loss as well.

Now replace all the labels y_1,\dots,y_n by randomly and independently drawn labels \tilde y_1,\dots, \tilde y_n\,. What happens if we run the same algorithm on the training data with noisy labels (x_1,\tilde y_1),\dots, (x_n, \tilde y_n))?

One thing is clear. If we choose from k discrete classes, we expect the model trained on the random labels to have no more than 1/k test accuracy, that is, the accuracy achieved by random guessing. After all, there is no statistical relationship between the training labels and the test labels that the model could learn.

What is more interesting is what happens to optimization. The left panel of the figure shows the outcome of this kind of randomization test on the popular CIFAR-10 image classification benchmark for a standard neural network architecture. What we can see is that the training algorithm continues to drive the training loss to zero even if the labels are randomized. The right panel shows that we can vary the amount of randomization to obtain a smooth degradation of the test error. At full randomization, the test error degrades to 90\%, as good as guessing one of the 10 classes. The figure shows what happens to a specific model architecture, called Inception, but similar observations hold for most, if not all, overparameterized architectures that have been proposed.

The randomization experiment shows that optimization continues to work well even when generalization performance is no better than random guessing, i.e., 10\% accuracy in the case of the CIFAR-10 benchmark that has 10 classes. The optimization method is moreover insensitive to properties of the data, since it works even on random labels. A consequence of this simple experiment is that a proof of convergence for the optimization method may not reveal any insights into the nature of generalization.

The diminished role of explicit regularization

Regularization plays an important role in the theory of convex empirical risk minimization. The most common form of regularization used to be \ell_2-regularization corresponding to adding a scalar of the squared Euclidean norm of the parameter vector to the objective function.

A more radical form of regularization, called data augmentation, is common in the practice of deep learning. Data augmentation transforms each training point repeatedly throughout the training process by some operation, such as a random crop of the image. Training on such randomly modified data points is meant to reduce overfitting, since the model never encounters the exact same data point twice.

Regularization continues to be a component of training large neural networks in practice. However, the nature of regularization is not clear. We can see a representative empirical observation in the table below.

The table shows the performance of a common neural model architecture, called Inception, on the standard CIFAR-10 image classification benchmark. The model has more than 1.5 million trainable parameters, even though there are only 50,000 training examples spread across 10 classes. The training procedure uses two explicit forms of regularization. One is a form of data augmentation with random crops. The other is \ell_2-regularization. With both forms of regularization the fully trained model achieves close to 90\% test accuracy. But even if we turn both of them off, the model still achieves close to 86\% test accuracy (without even readjusting any hyperparameters such as learning rate of the optimizer). At the same time, the model fully interpolates the training data in the sense of making no errors whatsoever on the training data.

These findings suggest that while explicit regularization may help generalization performance, it is by no means necessary for strong generalization of heavily overparameterized models.

How should we expect the gap to scale?

Before we turn to analyzing generalization gaps, it’s worth first considering how we should expect them to scale. That is, what is the relationship between the expected size of \Delta_{\mathrm{gen}} and the number of observations, n?

First, note that we showed that for a fixed prediction function f, the expectation of the empirical risk is equal to the population risk. That is, the empirical risk of a single function is a sample average of the population risk of that function. As we discussed in Chapter 3, i.i.d. sample averages should generalize and approximate the average at the population level. Here, we now turn to describing how they might be expected to scale under different assumptions.

Quantitative central limit theorems

The central limit theorem formalizes how sample averages estimate their expectations: If Z is a random variable with bounded variance then \hat{\mu}_Z^{(n)} converges in distribution to a Gaussian random variable with mean zero and variance on the order of 1/n.

The following inequalities are useful quantitative forms of the central limit theorem. They precisely measure how close the sample average will be to the population average using limited information about the random quantity.

• Markov’s inequality: Let Z be a nonnegative random variable. Then, \mathop\mathbb{P}[Z \geq t] \leq \frac{\mathop\mathbb{E}[Z]}{t}\,.

This can be proven using the inequality I_{[Z\geq t]}(z) \leq \frac{z}{t}.

• Chebyshev’s inequality: Suppose Z is a random variable with mean \mu_Z and variance \sigma_Z^2. Then, \mathop\mathbb{P}[Z\geq t+\mu_Z] \leq \frac{\sigma_Z^2}{t^2}

Chebyshev’s inequality helps us understand why sample averages are good estimates of the mean. Suppose that X_1,\dots, X_n are independent samples we were considering above. Let \hat\mu denote the sample mean \frac1n\sum_{i=1}^n Z_i. Chebyshev’s inequality implies \mathop\mathbb{P}[\hat\mu\geq t+\mu_X] \leq \frac{\sigma_X^2}{n t^2}\,, which tends to zero as n grows. A popular form of this inequality sets t=\mu_X which gives \mathop\mathbb{P}[\hat{\mu}\geq 2\mu_X] \leq \frac{\sigma_X^2}{n \mu_X^2}\,.

• Hoeffding’s inequality: Let Z_1, Z_2, \ldots, Z_n be independent random variables, each taking values in the interval [a_i,b_i].Let \hat\mu denote the sample mean \frac1n\sum_{i=1}^n Z_i. Then \mathop\mathbb{P}[\hat\mu \geq \mu_Z + t] \leq \exp\left(- \frac{2n^2t^2}{\sum_{i=1}^n(b_i-a_i)^2}\right)\,.

An important special case is when the Z_i are identically distributed copies of Z and take values in [0,1]. Then we have \mathop\mathbb{P}[\hat\mu \geq \mu_Z + t] \leq \exp\left(- 2nt^2\right)\,. This shows that when random variables are bounded, sample averages concentrate around their mean value exponentially quickly. If we invoke this bound with t=C/\sqrt{n}, the point at which it gives non-trivial results, we have an error of O(1/\sqrt{n}) with exponentially high probability. We will see shortly that this relationship between error and number of samples is ubiquitous in generalization theory.

These powerful concentration inequalities let us precisely quantify how close the sample average will be to the population average. For instance, we know a person’s height is a positive number and that there are no people who are taller than nine feet. With these two facts, Hoeffding’s inequality tells us that if we sample the heights of thirty thousand individuals, our sample average will be within an inch of the true average height with probability at least 83%. This assertion is true no matter how large the population of individuals. The required sample size is dictated only by the variability of height, not by the number of total individuals.

You could replace “height” in this example with almost any attribute that you are able to measure well. The quantitative central limits tell us that for attributes with reasonable variability, a uniform sample from a general population will give a high quality estimate of the average value.

“Reasonable variability” of a random variable is necessary for quantitative central limit theorems to hold. When random variables have low variance or are tightly bounded, small experiments quickly reveal insights about the population. When variances are large or effectively unbounded, the number of samples required for high precision estimates might be impractical and our estimators and algorithms and predictions may need to be rethought.

Bounding generalization gaps for individual predictors

Let us now return to generalization of prediction, considering the example where the quantity of interest is the prediction error on individuals in a population. There are effectively two scaling regimes of interest in generalization theory. In one case when the empirical risk is large, we expect the generalization gap to decrease inversely proportional to \sqrt{n}\,. When the empirical risk is expected to be very small, on the other hand, we tend to see the generalization gap decrease inversely proportional to n\,.

Why we see these two regimes is illustrated by studying the case of a single prediction function f\,, chosen independently of the sample S\,. Our ultimate goal is to reason about the generalization gap of predictors chosen by an algorithm running on our data. The analysis we walk through next doesn’t apply to data-dependent predictors directly, but it nonetheless provides helpful intuition about what bounds we can hope to get.

For a fixed function f\,, the zero-one loss on a single randomly chosen data point is a Bernoulli random variable, equal to 1 with probability p and 1-p otherwise. The empirical risk R_S[f] is the sample average of this random variable and the risk R[f] is its expectation. To estimate the generalization gap, we can apply Hoeffding’s inequality to find
\mathop\mathbb{P}[ R[f]-R_S[f] \geq \epsilon] \leq \exp\left( -2n\epsilon^2\right)\,. Hence, we will have with probability 1-\delta on our sample that |\Delta_{\mathrm{gen}}(f)| \leq \sqrt{\frac{\log(1/\delta)}{2n}}\,. That is, the generalization gap goes to zero at a rate of 1/\sqrt{n}\,.

In the regime where we observe no empirical mistakes, a more refined analysis can be applied. Suppose that R[f]>\epsilon\,. Then the probability that we observe R_S[f]=0 cannot exceed \begin{aligned} \mathop\mathbb{P}[ \forall i\colon\operatorname{sign}(f(x_i))=y_i] &= \prod_{i=1}^n \mathop\mathbb{P}[ \operatorname{sign}(f(x_i))=y_i] \\ & \leq (1-\epsilon)^n \leq e^{-\epsilon n}\,. \end{aligned} Hence, with probability 1-\delta, |\Delta_{\mathrm{gen}}(f)| \leq \frac{\log(1/\delta)}{n}\,, which is the 1/n regime. These two rates are precisely what we observe in the more complex regime of generalization bounds in machine learning. The main trouble and difficulty in computing bounds on the generalization gap is that our prediction function f depends on the data, making the above analysis inapplicable.

In this chapter, we will focus mostly on 1/\sqrt{n} rates. These rates are more general as they make no assumptions about the expected empirical risk. With a few notable exceptions, the derivation of 1/\sqrt{n} rates tends to be easier than the 1/n counterparts. However, we note that every one of our approaches to generalization bounds have analyses for the “low empirical risk” or “large margin” regimes. We provide references at the end of this chapter to these more refined analyses.

Uniform stability

While average stability gave us an exact characterization of generalization error, it can be hard to work with the expectation over S and S'. Uniform stability replaces the averages by suprema, leading to a stronger but useful notion.

In this definition, it is important to note that the z has nothing to do with S and S'\,. Uniform stability is effectively computing the worst-case difference in the predictions of the learning algorithm run on two arbitrary datasets that differ in exactly one point.

Uniform stability upper bounds average stability, and hence uniform stability upper bounds generalization gap (in expectation). Thus, we have the corollary \mathop\mathbb{E}[\Delta_{\mathrm{gen}}(A(S))] \leq \Delta_{\mathrm{sup}} (A)

This corollary turns out to be surprisingly useful since many algorithms are uniformly stable. For example, strong convexity of the loss function is sufficient for the uniform stability of empirical risk minimization, as we will see next.

Stability of empirical risk minimization

We now show that empirical risk minimization is uniformly stable provided under strong assumptions on the loss function. One important assumption we need is that the loss function \mathit{loss}(w, z) is differentiable and strongly convex in the model parameters w for every example z. What this means is that for every example z and for all w,w'\in\Omega, \mathit{loss}(w',z)\ge \mathit{loss}(w,z) + \langle\nabla \mathit{loss}(w,z), w' - w\rangle + \frac{\mu}2\|w-w'\|^2\,. There’s only one property of strong convexity we’ll need. Namely, if \Phi\colon\mathbb{R}^d\to\mathbb{R} is \mu-strongly convex and w^* is a stationary point (and hence global minimum) of the function \Phi, then we have \Phi(w) - \Phi(w^*) \geq \frac{\mu}{2} \| w - w^* \|^2\,. The second assumption we need is that \mathit{loss}(w, z) is L-Lipschitz in w for every z, i.e., \|\nabla \mathit{loss}(w, z)\|\le L\,. Equivalently, this means |\mathit{loss}(w, z)-\mathit{loss}(w',z)|\le L\|w-w'\|.

An interesting point about this result is that there is no explicit reference to the complexity of the model class referenced by \Omega.

Stability of regularized empirical risk minimization

Some empirical risk minimization problems, such as the Perceptron (ERM with hinge loss) we saw earlier, are convex but not strictly convex. We can turn convex problems into strongly convex problems by adding an \ell_2-regularization term to the loss function: r(w, z) = \mathit{loss}(w, z) + \frac{\mu}{2} \| w \|^2\,. The last term is named \ell_2-regularization, weight decay, or Tikhonov regularization depending on field and context.

By construction, if the loss is convex, then the regularized loss r(w, z) is \mu-strongly convex. Hence, our previous theorem applies. However, by adding regularization we changed the objective function. The optimizer of the regularized objective is in general not the same as the optimizer of the unregularized objective.

Fortunately, A simple argument shows that solving the regularized objective also solves the unregularized objective. The idea is that assuming \|w\|\le B we can set the regularization parameter \mu = \frac{L}{B\sqrt{n}}\,. This ensures that the regularization term \mu\|w\|^2 is at most O(\frac{LB}{\sqrt{n}}) and therefore the minimizer of the regularized risk also minimizes the unregularized risk up to error O(\frac{LB}{\sqrt{n}})\,. Plugging this choice of \mu into the ERM stability theorem, the generalization gap will also be O(\frac{LB}{\sqrt{n}})\,.

The case of regularized hinge loss

Let’s relate the generalization theory we just saw to the familiar case of the perceptron algorithm from Chapter 3. This corresponds to the special case of minimizing the regularized hinge loss r(w, (x,y)) = \max\{1-y\langle w,x\rangle,0\} + \frac{\mu}{2} \| w \|^2\,. Moreover, we assume that the data are are linearly separable with margin \gamma.

Denoting by \hat w_S the empirical risk minimizer on a random sample S of size n, we know that \frac\mu2\|\hat w_S\|^2 \le R_S(\hat w_S) \le R_S(0) = 1\,. Hence, \|\hat w_S\|\le B for B=\sqrt{2/\mu}. We can therefore restrict our domain to the Euclidean ball of radius B. If the data are also bounded, say \Vert x \Vert \leq D, we further get that \Vert \nabla_w r(w,z) \Vert \le \|x\| + \mu\|w\| = D + \mu B\,. Hence, the regularized hinge loss is L-Lipschitz with L=D+\mu B=D+\sqrt{2\mu}\,.

Let w_\gamma be a maximum margin hyperplane for the sample S. We know that the empirical loss will satisfy R_S[\hat w_S] \leq R_S[w_\gamma] = \frac{\mu}{2}\| w_\gamma \|^2 = \frac{\mu }{2\gamma^2}\,. Hence, by Theorem 1, \mathop\mathbb{E}[R[\hat w_S]] \le \mathop\mathbb{E}[R_S[\hat w_S]] + \Delta_{\mathrm{sup}}(\mathrm{ERM}) \le \frac{\mu }{2\gamma^2}+ \frac{4(D+\sqrt{2\mu})^2}{\mu n} Setting \mu=\frac{2\gamma D}{\sqrt{n}} and noting that \gamma\le D gives that \mathop\mathbb{E}[R[\hat w_S]] \le O\left(\frac{D}{\gamma \sqrt{n}}\right)\,. Finally, since the regularized hinge loss upper bounds the zero-one loss, we can conclude that \mathop\mathbb{P}[Y \hat w_S^T X < 0] \leq O\left(\frac{D}{\gamma \sqrt{n}}\right)\,, where the probability is taken over both sample S and test point (X, Y). Applying Markov’s inequality to the sample, we can conclude the same bound holds for a typical sample up to constant factors.

This bound is proportional to the square root of the bound we saw for the perceptron in Chapter 3. As we discussed earlier, this rate is slower than the perceptron rate as it does not explicitly take into account the fact that the empirical risk is zero. However, it is worth noting that the relationship between the variables in question—diameter, margin, and number of samples—is precisely the same as for the perceptron. This kind of bound is common and we will derive it a few more times in this chapter.

Stability analysis combined with explicit regularization and convexity thus give an appealing conceptual and mathematical approach to reasoning about generalization. However, empirical risk minimization involving non-linear models is increasingly successful in practice and generally leads to non-convex optimization problems.

VC dimension

Bounding the generalization gap from above for all functions in a function class is called uniform convergence. A classical tool to reason about uniform convergence is the Vapnik-Chervonenkis dimension (VC dimension) of a function class \mathcal{F}\subseteq X\rightarrow Y, denoted \mathrm{VC}(\mathcal{F})\,. It’s defined as the size of the largest set Q\subseteq X such that for any Boolean function h\colon Q \to \{-1,1\}, there is a predictor f\in\mathcal{F} such that f(x)= h(x) for all x\in Q\,. In other words, if there is a size-d sample Q such that the functions of \mathcal{F} induce all 2^d possible binary labelings of Q, then the VC-dimension of \mathcal{F} is at least d\,.

The VC-dimension measures the ability of the model class to conform to an arbitrary labeling of a set of points. The so-called VC inequality implies that with probability 1-\delta, we have for all functions f\in\mathcal{F} \Delta_{\mathrm{gen}}(f)\le \sqrt{\frac{\mathrm{VC}(\mathcal{F})\ln n+\ln(1/\delta)}{n}}\,.\quad\quad(2)

We can see that the complexity term \mathrm{VC}(\mathcal{F}) refines our earlier cardinality bound since \mathrm{VC}(\mathcal{F})\le\log|\mathcal{F}|+1. However VC-dimension also applies to infinite model classes. Linear models over \mathbb{R}^d have VC-dimension d, corresponding to the number of model parameters. Generally speaking, VC dimension tends to grow with the number of model parameters for many model families of interest. In such cases, the bound in Equation 2 becomes useless once the number of model parameters exceeds the size of the sample.

However, the picture changes significantly if we consider notions of model complexity different than raw counts of parameters. Consider two sets of vectors X_0 and X_1 all having Euclidean norm bounded by D. Let \mathcal{F} be the set of all linear functions f such that f(x)=w^T x with ||w||\leq \gamma{^-1}, f(x)\leq -1 if x\in X_0, and f(x)\geq 1 if x \in X_1. Vapnik showedVapnik, Statistical Larning Theory (Wiley, 1998). that the VC dimension of this set of hyperplanes was \frac{D^2}{\gamma^2}\,. As described in a survey of support vector machines by Burges, the worst case arrangement of n data points is a simplex in n-2 dimensions.Burges, “A Tutorial on Support Vector Machines for Pattern Recognition,” Data Mining and Knowledge Discovery 2, no. 2 (1998): 121–67. Plugging this VC-dimension into our generalization bound yields \Delta_{\mathrm{gen}}(f)\le \sqrt{\frac{D^2\ln n+\gamma^2\ln(1/\delta)}{\gamma^2 n}}\,. We again see our Perceptron style generalization bound! This bound again holds when the empirical risk is nonzero. And the dimension of the data, d does not appear at all in this bound. The difference between the parametric model and the margin-like bound is that we considered properties of the data. In the worst case bound which counts parameters, it appears that high-dimensional prediction is impossible. It is only by considering data-specific properties that we can find a reasonable generalization bound.

Rademacher complexity

An alternative to VC-dimension is Rademacher complexity, a flexible tool that often is more amenable to calculations that incorporate problem-specific aspects such as restrictions on the distribution family or properties of the loss function. To get a generalization bound in terms of Rademacher complexity, we typically apply the definition not the model class \mathcal{F} itself but to the class of functions \mathcal{L} of the form h(z) = \mathit{loss}(f, z) for some f\in\mathcal{F} and a loss function \mathit{loss}\,. By varying the loss function, we can derive different generalization bounds.

Fix a function class \mathcal{L}\subseteq Z\to\mathbb{R}, which will later correspond to the composition of a predictor with a loss function, which is why we chose the symbol \mathcal{L}\,. Think of the domain Z as the space of labeled examples z=(x,y)\,. Fix a distribution P over the space Z\,.

The empirical Rademacher complexity of a function class \mathcal{L}\subseteq Z\to\mathbb{R} with respect to a sample \{z_1,\dots,z_n\}\subseteq Z drawn i.i.d. from the distribution P is defined as: \widehat{\mathfrak{R}}_n(\mathcal{L}) =\mathop\mathbb{E}_{\sigma\in\{-1,1\}^n} \left[ \frac 1n \sup_{h\in\mathcal{L}} \left| \sum_{i=1}^n \sigma_i h(z_i) \right| \right]\,.

We obtain the Rademacher complexity \mathfrak{R}_n(\mathcal{L})=\mathop\mathbb{E}\left[\widehat{\mathfrak{R}}_n(\mathcal{L})\right] by taking the expectation of the empirical Rademacher complexity with respect to the sample. Rademacher complexity measures the ability of a function class to interpolate a random sign pattern assigned to a point set.

One application of Rademacher complexity applies when the loss function is L-Lipschitz in the parameterization of the model class for every example z\,. This bound shows that with probability 1-\delta for all functions f\in\mathcal{F}, we have \Delta_{\mathrm{gen}}(f)\le 2L{\mathfrak{R}}_n(\mathcal{F}) + 3\sqrt{\frac{\log(1/\delta)}{n}}\,. When applied to the hinge loss with the function class being hyperplanes of norm less than \gamma^{-1}, this bound again recovers the perceptron generalization bound \Delta_{\mathrm{gen}}(f)\le 2 \frac{D}{\gamma \sqrt{n}} + 3\sqrt{\frac{\log(1/\delta)}{n}}\,.

Margin bounds for ensemble methods

Ensemble methods work by combining many weak predictors into one strong predictor. The combination step usually involves taking a weighted average or majority vote of the weak predictors. Boosting and random forests are two ensemble methods that continue to be highly popular and competitive in various settings. Both methods train a sequence of small decision trees, each on its own achieving modest accuracy on the training task. However, so long as different trees make errors that aren’t too correlated, we can obtain a higher accuracy model by taking, say, a majority vote over the individual predictions of the trees.

Researchers in the 1990s already observed that boosting often continues to improve test accuracy as more weak predictors are added to the ensemble. The complexity of the entire ensemble was thus often far too large to apply standard uniform convergence bounds.

A proffered explanation was that boosting, while growing the complexity of the ensemble, also improved the margin of the ensemble predictor. Assuming that the final predictor f\colon X\to \{-1,1\} is binary, its margin on an example (x,y) is defined as the value yf(x)\,. The larger the margin the more “confident” the predictor is about its prediction. A margin yf(x) just above 0 shows that the weak predictors in the ensemble were nearly split evenly in their weighted votes.

An elegant generalization bound relates the risk of any predictor f to the fraction of correctly labeled training examples at a given margin \theta. Below let R[f] be the risk of f w.r.t. zero-one loss. However, let R^\theta_S(f) be the empirical risk with respect to margin errors at level \theta, i.e., the loss \mathbf{1}(yf(x)\le\theta) that penalizes errors where the predictor is within an additive \theta margin of making a mistake.

The theorem can be proved using Rademacher complexity. Crucially, the bound only depends on the VC dimension of the base class \mathcal{H} but not the complexity of ensemble. Moreover, the bound holds for all \theta>0 and so we can choose \theta after knowing the margin that manifested during training.

Margin bounds for linear models

Margins also play a fundamental role for linear prediction. We saw one margin bound for linear models in our chapter on the Perceptron algorithm. Similar bounds hold for other variants of linear prediction. We’ll state the result here for a simple least squares problem: w^* = \arg\min_{w\colon\|w\|\le B} \frac1n\sum_{i=1}^n\left(\langle x_i, w\rangle - y\right)^2

In other words, we minimize the empirical risk w.r.t. the squared loss over norm bounded linear separators, call this class \mathcal{W}_B\,. Further assume that all data points satisfy \|x_i\|\le 1 and y\in\{-1,1\}. Analogous to the margin bound in Theorem 2, it can be shown that with probability 1-\delta for every linear predictor f specified by weights in \mathcal{W}_B we have R[f] - R_S^\theta[f] \le 4\frac{{\mathfrak{R}}(\mathcal{W}_B)}{\theta} + O\left(\frac{\log(1/\delta)}{\sqrt{n}}\right)\,.

Moreover, given the assumptions on the data and model class we made, the Rademacher complexity satisfies {\mathfrak{R}}(\mathcal{W})\le B/\sqrt{n}. What we can learn from this bound is that the relevant quantity for generalization is the ratio of complexity to margin B/\theta\,.

It’s important to understand that margin is a scale-sensitive notion; it only makes sense to talk about it after suitable normalization of the parameter vector. If the norm didn’t appear in the bound we could scale up the parameter vector to achieve any margin we want. For linear predictors the Euclidean norm provides a natural and often suitable normalization.

One pass optimization of stochastic gradient descent

As we briefly discussed in the optimization chapter, we can interpret the convergence analysis of stochastic gradient descent as directly providing a generalization bound for a particular variant of SGD. Here we give the argument in full detail. Suppose that we choose a loss function that upper bounds the number of mistakes. That is \mathit{loss}(\hat{y},y) \geq \mathbb{1}\{y\hat{y}<0\}\,. The hinge loss would be such an example. Choose the function R to be the risk (not empirical risk!) with respect to this loss function: R[w] = \mathop\mathbb{E}[ \mathit{loss}(w^T x, y) ] At each iteration, suppose we gain access to an example pair (x_i, y_i) sampled i.i.d. from the a data generating distribution. Then when we run the stochastic gradient method, the iterates are w_{t+1} = w_t - \alpha_t e(w_t^Tx_t,y_t) x_t\,,\quad \text{where}\quad e(z,y) = \frac{\partial \mathit{loss}(z,y)}{\partial z}\,. Suppose that for all x, \Vert x \Vert \leq D\,. Also suppose that |e(z,y)|\leq C\,. Then the SGD convergence theorem tells us that after n steps, starting at w_0=0 and using an appropriately chosen constant step size, the average of our iterates \bar{w}_n will satisfy \mathop\mathbb{P}[\operatorname{sign}(\bar{w}_n^T x ) \neq y ] \leq \mathbb{E}[R[\bar{w}_n]] \leq R[w_\star] + \frac{C D \Vert w_\star \Vert }{\sqrt{n}}\,. This inequality tells us that we will find a distribution boundary that has low population risk after seeing n samples. And the population risk itself lets us upper bound the probability of our model making an error on new data. That is, this inequality is a generalization bound.

We note here that this importantly does not measure our empirical risk. By running stochastic gradient descent, we can find a low-risk model without ever computing the empirical risk.

Let us further assume that the population can be separated with large margin. As we showed when we discussed the Perceptron, the margin is equal to the inverse of the norm of the corresponding hyperplane. Suppose we ran the stochastic gradient method using a hinge loss. In this case, C=1, so, letting \gamma denote the maximum margin, we get the simplified bound \mathop\mathbb{P}[\operatorname{sign}(\bar{w}_n^T x ) \neq y ] \leq \frac{D}{\gamma\sqrt{n}}\,. Note that the Perceptron analysis did not have a step size parameter that depended on the problem instance. But, on the other hand, this analysis of SGD holds regardless of whether the data is separable or whether zero empirical risk is achieved after one pass over the data. The stochastic gradient analysis is more general but generality comes at the cost of a looser bound on the probability of error on new examples.

Uniform stability of stochastic gradient descent

Above we showed that empirical risk minimization is stable no matter what optimization method we use to solve the objective. One weakness is that the analysis applied to the exact solution of the optimization problem and only applies for strongly convex loss function. In practice, we might only be able to compute an approximate empirical risk minimizer and may be interested in losses that are not strongly convex. Fortunately, we can also show that some optimization methods are stable even if they don’t end up computing a minimizer of a strongly convex empirical risk. Specifically, this is true for the stochastic gradient method under suitable assumptions. Below we state one such result which requires the assumption that the loss function is smooth. A continuously differentiable function f\colon\mathbb{R}^d\to\mathbb{R} is \beta-smooth if \|\nabla f(y)-\nabla f(x)\|\le \beta\|y-x\|.

The theorem allows for SGD to sample the same data points multiple times, as is common practice in machine learning. The stability approach also extends to the non-convex case albeit with a much weaker quantitative bound.

What solutions does stochastic gradient descent favor?

We reviewed empirical evidence that explicit regularization is not necessary for generalization. Researchers therefore believe that a combination of data generating distribution and optimization algorithm perform implicit regularization. Implicit regularization describes the tendency of an algorithm to seek out solutions that generalize well on their own on a given a dataset without the need for explicit correction. Since the empirical phenomena we reviewed are all based on gradient methods, it makes sense to study implicit regularization of gradient descent. While a general theory for non-convex problems remains elusive, the situation for linear models is instructive.

Consider again the linear case of gradient descent or stochastic gradient descent: w_{t+1} = w_t - \alpha e_t x_t where e_t is the gradient of the loss at the current prediction. As we showed in the optimization chapter, if we run this algorithm to convergence, we must have the resulting \hat{w} lies in the span of the data, and that it interpolates the data. These two facts imply that the optimal \hat{w} is the minimum Euclidean norm solution of Xw=y\,. That is, w solves the optimization problem \begin{array}{ll} \text{minimize} & \|w\|^2\\ \text{subject to} & y_i w^Tx_i = 1\,. \end{array} Moreover, a closed form solution of this problem is given by \hat{w}=X^T(XX^T)^{-1}y\,. That is, when we run stochastic gradient descent we converge to a very specific solution. Now what can we say about the generalization properties of this minimum norm interpolating solution?

The key to analyzing the generalization of the minimum norm solution will be a stability-like argument. We aim to control the error of the model trained on the first m data points on the next data point in the sequence, x_{m+1}\,. To do so, we use a simple identity that follows from linear algebra.

We hold off on proving this lemma and first prove our generalization result with the help of this lemma.

This proof reveals that the minimum norm solution, the one found by running stochastic gradient descent to convergence, achieves a nearly identical generalization bound as the Perceptron, even with the fast 1/n rate. Here, nothing is assumed about margin, but instead we assume that the complexity of the interpolating solution does not grow rapidly as we increase the amount of data we collect. This proof combines ideas from stability, optimization, and model complexity to find yet another explanation for why gradient methods find high-quality solutions to machine learning problems.

Proof of Lemma 1

We conclude with the deferred proof of Lemma 1.