While asymptotic convergence provides intuition for how test error behaves as the dataset size approaches infinity, practical machine learning relies on finite datasets. Because the classification error is a bounded random variable (between $$0$$ and $$1$$), valid finite sample bounds can be established using Hoeffding's inequality. It guarantees that the probability of the empirical error $$\epsilon_\mathcal{D}(f)$$ exceeding the true error $$\epsilon(f)$$ by a margin of $$t$$ or more is exponentially bounded:
$$P(\epsilon_\mathcal{D}(f) - \epsilon(f) \geq t) < \exp\left( - 2n t^2 \right)$$

Finite Sample Bounds for Test Error via Hoeffding's Inequality

By the central limit theorem, as the size $$n$$ of a test dataset grows toward infinity, the empirical test error $$\epsilon_\mathcal{D}(f)$$ approaches the true population error $$\epsilon(f)$$ at an asymptotic convergence rate of $$\mathcal{O}(1/\sqrt{n})$$. This $$\mathcal{O}(1/\sqrt{n})$$ rate reveals that improving the precision of the error estimate is computationally expensive; for instance, estimating the test error twice as precisely requires collecting four times as many samples.

Claude

Because the true population error $$\epsilon(f)$$ of a classifier cannot be observed directly in most practical scenarios, it must be estimated using samples. When a test dataset $$\mathcal{D}$$ is statistically representative of the underlying population, the empirical error $$\epsilon_\mathcal{D}(f)$$ serves as a statistical estimator for the population error $$\epsilon(f)$$. Since the empirical error is a sample average and the population error is its expectation, this reduces to a classical mean estimation problem.

Estimation of Population Error via Empirical Error

The Central Limit Theorem is a foundational mathematical principle in probability theory stating that the average of $$n$$ independent random samples drawn from any distribution (with mean $$\mu$$ and standard deviation $$\sigma$$) will approximately follow a normal distribution centered at the true mean $$\mu$$ with a standard deviation of $$\sigma/\sqrt{n}$$, as the sample size $$n$$ grows large. In machine learning, this theorem explains why the empirical error of a classifier evaluated on a test set converges to its true population error at an asymptotic rate of $$\mathcal{O}(1/\sqrt{n})$$.

Central Limit Theorem

Dive into Deep Learning

In the context of estimating classification error, the event of a classifier $$f$$ making an error on a single instance, $$\mathbf{1}(f(X) 
eq Y)$$, can be modeled as a Bernoulli random variable. It takes the value $$1$$ (error) with probability equal to the true population error rate $$\epsilon(f)$$, and $$0$$ (correct) otherwise. Consequently, its variance is $$\epsilon(f)(1-\epsilon(f))$$, which reaches its maximum when the true error rate is exactly $$0.5$$ and decreases as the error approaches $$0$$ or $$1$$. This implies that the asymptotic standard deviation of the empirical error estimate cannot exceed $$\sqrt{0.25/n}$$ for a sample size $$n$$.

Classification Error as a Bernoulli Random Variable

Asymptotic Convergence Rate of Test Error

Statistical learning theory is the mathematical subfield of machine learning that aims to elucidate the fundamental principles explaining why and when models trained on empirical data can generalize to unseen data. A primary objective is to bound the generalization gap by relating the properties of the chosen model class to the dataset size.

Statistical Learning Theory

When evaluating a machine learning model, the empirical error measured on a test dataset provides an unbiased estimate of the underlying population error. To formally quantify the uncertainty of this point estimate, researchers construct confidence intervals around the test error. These boundaries can be formulated as approximate confidence intervals based on exact asymptotic distributions—such as the central limit theorem—or as strictly valid, albeit more conservative, finite sample confidence intervals derived from finite sample guarantees like Hoeffding's inequality.

Learn Before

Related

Learn After