Epoch-wise Bias–Variance Decomposition

Bias and variance are usually studied at the end of training. Here, we instead track how they evolve during optimization, one epoch at a time.

Suppose that we are training a model parameterized by $\theta$, and let $\theta_t$ denote the parameters at step $t$ produced by the optimization algorithm of our choice. In machine learning, it is often helpful to decompose the error $E(\theta)$ as $B^2(\theta)+V(\theta)+N(\theta)$, where $B$ represents the bias, $V$ the variance, and $N$ the noise (irreducible error). In most cases, the decomposition is performed at an optimal solution $\theta^*$—for instance, $\lim_{t \to \infty}\theta_t$, or an early-stopped version—to understand how bias and variance change with model complexity, model size, and related quantities. This has helped explain phenomena such as model-wise double descentAs model capacity grows, test error may first decrease, then increase near the interpolation threshold, and finally decrease again in the overparameterized regime.. It can also be useful to visualize how $B(\theta_t)$ and $V(\theta_t)$ evolve with $t$, which can help explain epoch-wise double descentFor a fixed model, test error can decrease, rise around the time the training data are fitted, and then decrease again as training continues.. That is what we will study in this post.

Source An earlier version of these notes is available on HackMD.

Notations

• $\mathcal{X}$ : domain set (input space)
• $\mathcal{Y}$ : label set (output space)
• $\mathcal{H}$ : hypothesis class (class of possible models we can learn)

Definitions and preliminaries

Definition 1 Loss function. The loss function $\ell(t,y)$ takes two labels, produces a value between $0$ and some constant $M\in[0,\infty]$, and measures the cost of predicting $y$ when the true value is $t$.

Examples include square loss $\ell(t,y)=(t-y)^2$, absolute loss $\ell(t,y)=|t-y|$, and zero-one loss $\ell(t,y)=\mathbb{1}_{\{t\ne y\}}$.

Definition 2 Training set. Let $S$ be a set of $|S|$ observations $z_i=(x_i,t_i)\in\mathcal X\times\mathcal Y$, where $x_i\in\mathcal X$ is a feature vector and $t_i\in\mathcal Y$ is the label of the $i$-th sample. The observations are assumed to be i.i.d.i.i.d. means independent and identically distributed: every $z_i$ follows the same distribution $\mathcal D$, and observing one sample does not change the distribution of the others. draws from an unknown data distribution $\mathcal D$.

Since training-set size is an important parameter of a learning problem, we assume below that all datasets have the same size $n$.

Definition 3 Optimal prediction.

Let $x$ be random and let $t=t(x)$ be either deterministic or random conditional on $x$. The factorization $p(x,t)=p(x)p(t\mid x)$The joint distribution of an input and label equals the marginal distribution of the input multiplied by the conditional distribution of the label given that input. gives the optimal prediction at $x$ as

In the deterministic case, there exists $t\in\mathcal Y$ such that $p(t\mid x)=1$, and therefore $y^*(x)=\arg\min_y\ell(t,y)=t$.

In the nondeterministic case:

• Using square loss, we have

Thus the optimal prediction is the conditional meanAs a function of $y$, the expected square loss is a convex quadratic. Its derivative is $2(y-\mathbb E[t\mid x])$, which vanishes at $y=\mathbb E[t\mid x]$. of $p(t\mid x)$. For example, suppose that, for a fixed $x$, $(x,1)$ occurs with probability $p_x\in[0,1]$ and $(x,0)$ occurs with probability $1-p_x$:

Then, using square loss, we have $y^*(x) = p_x$.

• Using absolute loss, we have

where $F_{t\mid x}$ is the conditional CDF$F_{t\mid x}(u)=\mathbb P(t\le u\mid x)$. Its generalized inverse is $F_{t\mid x}^{-1}(q)=\inf\{u:F_{t\mid x}(u)\ge q\}$, which remains meaningful for discrete distributions.. Thus $y^*(x)$ is a median of $p(t\mid x)$.

The last line follows because $y\mapsto 2F_{t\mid x}(y)-1$ is the derivative of the function

which therefore reaches its minimum at a median, where $y=F_{t\mid x}^{-1}(1/2)$.

For the Bernoulli example above, $F_{t\mid x}(u)=(1-p_x)\mathbb{1}_{\{0\le u<1\}}+\mathbb{1}_{\{1\le u\}}$, so $y^*(x) = \mathbb{1}_{\{1-p_x<1/2\}}+\lambda\mathbb{1}_{\{1-p_x=1/2\}} = \mathbb{1}_{\{p_x>1/2\}}+\lambda\mathbb{1}_{\{p_x=1/2\}},\qquad \lambda\in[0,1].$

• Using zero-one loss, we have

That is the conditional modeA mode is any label with maximal conditional probability $p(t\mid x)$. Predicting it minimizes the probability of misclassification under zero-one loss.. For the same Bernoulli example, we have

Definition 4 Learning algorithm. A learning algorithm is a map $\mathcal A:(\mathcal X\times\mathcal Y)^n\to\mathcal H$. It takes a dataset $S\in(\mathcal X\times\mathcal Y)^n$ containing $n$ samples and returns a model $h=\mathcal A(S)\in\mathcal H$.

The optimal model satisfies $f(x)=y^*(x)$ for every $x$. Under zero-one loss, this is the Bayes classifierThe Bayes classifier predicts a most probable class conditional on $x$. The smallest classification error it can attain is the Bayes rate; this is the irreducible classification error induced by class overlap or label noise.. In the binary example above, it is $f(x)=\mathbb{1}_{\{\mathbb P(t=1\mid x)\ge 1/2\}}$.

Definition 5 True risk. Given $h\in\mathcal H$,

Definition 6 Empirical risk. For $h\in\mathcal H$ and $S=\{(x_1,t_1),\ldots,(x_n,t_n)\}$,

The essential task of supervised learning is to obtain good performance on unseen data by adjusting $h$ using one sampled training set $S$. The two risks differTrue risk averages over the unknown population distribution $\mathcal D$; empirical risk averages over the finite observed training set. Generalization concerns how well the latter controls the former.. We recall them mainly to make the dependence $h=\mathcal A(S)$ explicit.

Definition 7 Expected loss at an input.

Since the same learner $\mathcal A$ generally produces different models $h$ for different training sets $S$, the loss $\ell(t,h(x))$ depends on $S$ through $h=\mathcal A(S)$. We expose this dependency by averaging over training sets.

Let $D_n$ be a collection of training sets of size $n$, let $\hat y_n(x)$ denote the prediction at $x$ obtained by applying the learner to a sampled training set, and let $Y_n(x)=\{\mathcal A(S)(x):S\in D_n\}$ be the multiset of predictionsA multiset keeps multiplicity: the same numerical prediction appears several times when several training sets produce it. Equivalently, one may regard $Y_n(x)$ as the empirical distribution induced by sampling $S$ from $D_n$..

The quantity of interest is the expected loss

Our objective is to decompose $E_n(x)$ into three terms: bias, variance, and noise (irreducible error). A standard decomposition exists for square loss, and several alternatives have been proposed for zero-one loss.

Definition 8 Main prediction. For a loss function $\ell$ and a collection of training sets $D_n$, the main prediction is

In words, the main prediction minimizes its average loss relative to all predictions in $Y_n(x)$. It is the prediction that “differs least” from the learner’s possible predictions according to $\ell$, and therefore describes their central tendency.

Remark The main prediction need not belong to $Y_n(x)$. For example, the mean of finitely many predictions can lie strictly between all observed values.

Theorem 1 Under square loss, the main prediction is the mean of $Y_n(x)$; under absolute loss, it is a median; and under zero-one loss, it is a mode (a most frequent prediction).

Definition 9 Bias, variance, and noise. For an input $x$, define

In words, the square bias is the loss of the main prediction relative to the optimal prediction; the variance is the average loss of individual learned predictions relative to the main prediction; and the noise is the unavoidable component, independent of the learning algorithm. In the deterministic case, $N(x)=\ell(t(x),t(x))$ for every $x$.

Bias and variance may be averaged over all examples, in which case we will refer to them as average square bias

and average variance

The average noise is

Theorem 2 For square loss $\ell(t,y)=(t-y)^2$,

Bias-variance decomposition

For a given loss function $\ell$, we seek two constants $c_1(x,\ell)$ and $c_2(x,\ell)$ such that

Theorem 3 For square loss $\ell(t,y)=(t-y)^2$, $c_1(x,\ell)=c_2(x,\ell)=1$.

Let $\mathbb{P}_{D_n}(x) = \mathbb{P}[y^*(x) \in Y_n(x)]$ be the probability over training sets in $D_n$ that the learner predicts the optimal class for $x$.

Theorem 4 For zero-one loss $\ell(t,y)=\mathbb{1}_{\{t\ne y\}}$ in binary classification, $c_1(x,\ell)=2\mathbb P_{D_n}(x)-1$ and $c_2(x,\ell)=2\mathbb{1}_{\{y^{\ell,D_n}(x)=y^*(x)\}}-1$.

The proof is given by Domingos (2000)Pedro Domingos, “A Unified Bias-Variance Decomposition for Zero-One and Squared Loss,” AAAI 2000, pp. 564–569..

The same paper treats multiclass zero-one loss and absolute loss $\ell(t,y)=|t-y|$.

Application: teacher–student setup

Work in progress The teacher–student application remains in the earlier HackMD version while I verify and format its derivation for this post.

References

• Pedro Domingos, “A Unified Bias-Variance Decomposition for Zero-One and Squared Loss”, Proceedings of the 17th National Conference on Artificial Intelligence, pp. 564–569, 2000.

• IFT 6085, Lecture 9: Stability, Generalization and the Applications of Stability.

@misc{tikengnotsawo2023biasvarianceepoch,
  author = {Tikeng Notsawo, Pascal Jr.},
  title = {{Epoch-wise Bias–Variance Decomposition}},
  year = {2023},
  month = may,
  url = {https://tikquuss.github.io/blog/bias-variance-epoch/},
  note = {Blog post}
}