Let $S$ be our set of training examples that are related using the following equation:

where $h^*$ is the best possible classifier that maps the relationship between $x$ and $y$, and $\xi^{(i)} \in \mathcal{N}(0, \sigma^2)$ is the noise in the $ith$ example.

Also, let ${h}_s$ be our best fit model for the dataset $S$. The Mean Squared Error (MSE) can be written as:

Also, let $h_{avg}(x) = \mathbb{E}\left[h_s(x)\right]$ be the "average model" - the model obtained by drawing an infinite number of datasets, training on them, and averaging their predictions on $x$.

Then, the Mean Squared Error can be further broken down into 3 components:

The Bias-Variance tradeoff tells us that as we increase the number of parameters in our neural network, the test error will decrease because the bias is decreasing. However, after a certain point the variance starts increasing faster than the bias is decreasing and therefore, the test error will start to increase.

In reality, however, we see a double descent phenomenon wherein the test error starts to decrease again at the point where the number of parameters $d$ are approximately equal to the number of training examples $d$. This is called the over-parameterization regime.

For any hypothesis $h$, the true error is given by:

However, since we have no way of determining the underlying probability distribution $\mathcal{D}$, we cannot determine the true error of the hypothesis. Instead, we estimate the empirical error of the hypothesis over our $n$ training examples.

Let $\mathcal{H}$ be the set of all possible hypotheses that we are considering. To find the hypothesis that minimizes the empirical error over our training set, we find:

Using Hoeffding inequality, we note that the true error and the estimated empirical error of our selected hypothesis follow the following inequality:

Now we want to find an inequality for our entire set of hypotheses $\mathcal{H} = \{ h_1, \dots, h_k \}$. We see that the following inequality holds:

We call this the uniform convergence result.

This means that as n increases, the probability of the true error being close to the empirical error is bounded by a bigger value. Whereas, as we increases the number of hypotheses in our set, this probability is actually bounded by a smaller value.

In the context of learning, we can say that the more complex our model, the lower our probability of minimizing the empirical error. And the more the number of training examples, the higher our probability of minimizing the empirical error.

Now let $\delta = 2k\exp\left(-2\gamma^2 n\right)$

We see that if we want the probability of "the true error being within $\gamma$ to the empirical error for all hypothesiss under our consideration" to be at least $1 - \delta$, our $n$ needs to be atleast as large as:

Similarly, we can also see that given $k$ and $n$, the difference between the true error and the empirical error (for all hypotheses is our set) will always be less than:

Next, in our set of hypothesiss $\mathcal{H}$, let $h^*$ be the hypothesis that minimizes the true error and $\hat{h}$ be the hypothesis that minimizes our empirical error.

Using our uniform convergence assumption, we can see that:

With a probability of $1 - \delta$, the true error of our selected hypothesis is less than or equal to the true error of the best hypothesis + some term that depends on the number of hypotheses and the number of training examples.

The first term on the right can be thought of as the bias. And the second term can be thought of as the variance. We see that as we increase k, the first term either stays the same or potentially decreases. Whereas, the second term increases.

This is similar to what we saw in the Bias-Variance tradeoff. As we increase the complexity of our model, variance increases and the potential for our model to overfit also increases.