45 Empirical Risk Minimization and the Union Bound

The Overfitting Problem

When Models Get Big

When we’ve got a lot of curves in our model, it’s likely that some of them fit the data better than the true curve \(\mu\)—not because they’re actually better, but because they happen to align with the noise.

When we’ve more curves in our model, there’s a better chance one is in the zone.
Sometimes that’s ok.
- If the curve we choose is close to \(\mu\), it’s no big deal.
But it can be a problem.
- If the curve we choose is far from \(\mu\), we’re unhappy.

The Characters

\(\mu\) is the true curve. It’s what we’re trying to estimate. We’ll assume it’s in our model: \(\mu \in \mathcal{M}\).
\(Y_i = \mu(X_i) + \varepsilon_i\) where \(\varepsilon_i \sim N(0,\sigma^2)\) independently.
\(\hat\mu\) is our least squares estimator. It minimizes the empirical loss \(\ell(m) = \frac{1}{n}\sum_{i=1}^n \{m(X_i)-Y_i\}^2\) over \(m \in \mathcal{M}\).
\(\mathcal{M}_s = \{m \in \mathcal{M} : \|m-\mu\| < s\sqrt{n}\}\) is the neighborhood of curves close to \(\mu\).

We want to show \(\hat\mu\) is close to \(\mu\) with high probability.

The Argument

The Argument in Words

What we know is that \(\hat \mu\) beats or ties every other curve in the model. That’s what a minimizer (argmin) does.

\[ \hat \mu = \operatorname{argmin}_{m \in \mathcal{M}} \ell(m) \quad \iff \quad \ell(\hat\mu) \le \ell(m) \ \text{ for all } \ m \in \mathcal{M} \]

If our model is right, that means it beats or ties \(\mu\).

\[ \ell(\hat\mu) \le \ell(m) \ \text{ for all } \ m \in \mathcal{M} \ \textbf{ and } \ \mu \in \mathcal{M} \implies \ell(\hat\mu) \le \ell(\mu). \]

And if no curve in our neighborhood’s complement beats or ties \(\mu\), this means \(\hat\mu\) isn’t in that complement.

\[ \ell(\hat\mu) \le \ell(\mu) \ \textbf{ and } \ \ell(m) > \ell(\mu) \ \text{ for all } \ m \in \mathcal{M}\setminus \mathcal{M}_s \implies \hat\mu \not \in \mathcal{M}\setminus \mathcal{M}_s \]

And because \(\hat\mu\) is in the model, that means \(\hat\mu\) is in the neighborhood.

\[ \hat\mu \not \in \mathcal{M}\setminus \mathcal{M}_s \ \textbf{ and } \ \hat\mu \in \mathcal{M} \quad \iff \quad \hat \mu \in \mathcal{M}_s \]

When our two if clauses are true, this argument implies \(\hat\mu\) is in our neighborhood. So if they’re true with some probability, \(\hat\mu\) is in the neighborhood with that probability.

The Real Probability Question

To see how big the neighborhood needs to be, we revisit a characterization of the loss difference.

\[ \begin{aligned} \frac{\ell(m)-\ell(\mu)}{\|m-\mu\|} &= \|m-\mu\| - 2\left\langle\varepsilon, \frac{m - \mu}{\|m-\mu\|}\right\rangle \\ &= \|m-\mu\| - 2\sigma Z_m \quad \text{ where } \quad Z_m=\frac{\left\langle\varepsilon,\ \frac{m - \mu}{\|m-\mu\|}\right\rangle}{\sigma} \sim N(0,1). \end{aligned} \]

This means our loss difference exceeds zero for a curve \(m\) when the distance from \(m\) to \(\mu\) is large relative to the mean-zero normal random variable \(2\sigma Z_m\).

\[ \ell(m)-\ell(\mu) > 0 \quad \text{ if } \quad \|m-\mu\| > 2 \sigma Z_m \]

And it exceeds zero for all curves in our neighborhood’s complement if the minimum of the left side is larger than the maximum of the right.

\[ s\sqrt{n} = \min_{m \in \mathcal{M} \setminus \mathcal{M}_s} \|m-\mu\| > 2\sigma \max_{m \in \mathcal{M} \setminus \mathcal{M}_s} Z_m. \]

i.e. if our neighborhood’s radius exceeds a maximum of normals.

Finding the Right Radius

We’re after some radius satisfying this lower bound with probability \(1-\delta\).

\[ s\sqrt{n} > 2\sigma \max_{m \in \mathcal{M} \setminus \mathcal{M}_s} Z_m. \]

This is implied if \(s\) satisfies a slightly larger lower bound.

\[ s \sqrt{n} > 2\sigma \max_{m \in \mathcal{M}} Z_m. \]

If there are \(K\) functions \(m \in \mathcal{M}\), we need a bound on the maximum of \(K\) standard normals like \(Z_m\). That’s where the union bound comes in.

Here’s the idea in a simple example. Suppose the truth is \(\mu(x) = 0\) and we’re picking the best of \(K\) constant predictors \(m_1 \ldots m_K\) evenly spaced between \(-1\) and \(1\). With noisy data, the constants that happen to align with the noise look better than \(\mu=0\). The more constants we offer, the more likely one of them fits the noise well. With \(K=2\) (just \(m=-1\) and \(m=1\)), the noise has to be pretty extreme. With \(K=100\), there’s almost certainly a constant near the noise average. That’s overfitting. The question is: how fast does this problem grow with \(K\)?

The Union Bound

What It Is

Think about if we had two things, \(A\) and \(B\), e.g. \(\{ g_1 \ge t \}\) and \(\{ g_2 \ge t \}\). And lets break down how \(A\) or \(B\) can happen into disjoint events, i.e., things that cannot happen simultaneously.

Event 1: \(A\) happens.
Event 2: \(B\) happens and \(A\) doesn’t.

The probability that \(A\) or \(B\) happens is the sum of the probabilities of these disjoint events. And Event 2 happens less often than \(B\).

\[ P(A \textbf{ or } B) = P(A) + P(B \textbf{ and not } A) \le P(A)+P(B) \]

The Union Bound and Maxima

The maximum of \(K\) things exceeds a threshold \(t\) if and only if at least one of them does.

\[ \max g_1 \ldots g_K \ge t \quad \text{ if and only if } \quad g_1 \ge t \ \textbf{ or } \ldots \textbf{ or } g_K \ge t \]

This means the probability that it happens is the probability that at least one thing happens.

\[ P(\max g_1 \ldots g_K \ge t) = P(g_1 \ge t \ \textbf{ or } \ldots \textbf{ or } g_K \ge t). \]

And this is no larger than the sum of probabilities that one happens.

\[ P(g_1 \ge t \ \textbf{ or } \ldots \textbf{ or } g_K \ge t) \le P(g_1 \ge t)\ +\ \ldots\ +\ P(g_K \ge t). \]

All of our probabilities are the same, so this sum is \(K\) times the probability of one.

\[ P(\max g_1 \ldots g_K \ge t) \le K \cdot P(g_1 \ge t). \]

The Union Bound with Gaussian Tails

We use a bound on Gaussian tail probabilities.

\[ P(g_1 \ge t) \le e^{-t^2/2} \qquad \text{ for } \qquad t > \frac{1}{\sqrt{2\pi}}. \]

Multiplying by \(K\), we get a simple bound on the probability that the max exceeds \(t\).

\[ \begin{aligned} K \cdot P(g_1 \ge t) &\le K e^{-t^2/2} = e^{\log(K) - t^2/2} \\ &= e^{-\log(K)} = 1/K \qquad \text{ for } \qquad t=2\sqrt{\log(K)}. \end{aligned} \]

This means that

\[ \begin{aligned} P\left\{\max g_1 \ldots g_K &\ge 2\sqrt{\log(K)} \right\} \le 1/K \qquad \text{ or equivalently } \\ \max g_1 \ldots g_K &< 2\sqrt{\log(K)} \qquad \text{ with probability } \quad 1-1/K. \end{aligned} \]

Putting It Together

The Result

Making the substitution into our radius condition, the radius \(s\) is good with probability \(1-1/K\) when

\[ s \sqrt{n} = 2\sigma \times 2\sqrt{\log(K)} = 4\sigma\sqrt{\log(K)}. \]

Summary. If \(\mu \in \mathcal{M}\), then

\[ \underset{\hat\mu \in \mathcal{M}_s}{\|\hat\mu - \mu\| < s\sqrt{n}} \quad \text{ with probability } \quad 1-1/K \quad \text{ for } \quad s= 4\sigma\sqrt{\log(K)/n}. \]

Sometimes we drop constants and say \(\hat \mu\) converges to \(\mu\) at the rate \(\sqrt{\log(K)/n}\).

What This Tells Us

With \(K\) curves in our model, the estimation error scales like \(\sqrt{\log(K)/n}\).
\(\log(K)\) grows very slowly with \(K\). Adding more curves to the model barely hurts.
But this bound only applies when \(\mu\) is actually in the model. If it isn’t, there’s also approximation error—the modeling part from earlier.
The tradeoff: bigger models have smaller modeling error but larger estimation error. The rate \(\sqrt{\log(K)/n}\) tells us how fast the estimation error grows.

Exercise. Generate \(n=100\) observations from \(Y_i = \varepsilon_i\) where \(\varepsilon_i \sim N(0,1)\). For \(K = 2, 5, 10, 50, 100, 500\), pick the best of \(K\) evenly-spaced constant predictors (from \(-2\) to \(2\)). Record how far the selected constant is from zero. Repeat 1000 times and plot the average distance against \(\log(K)\). What do you see?