A rule learned from examples is judged by its error on cases it has not seen, but the only errors it can count are those on the cases it was trained on. A threshold on HbA1c chosen to separate 100 adults with and without diagnosed diabetes can make 6 mistakes among them and still err on more than a tenth of the population they came from. Statistical learning theory asks when the training error can be trusted, how far the learned rule can be from the best one available, and how many examples a guarantee of a given strength requires. Its answers are inequalities that hold at every sample size and for every distribution of the data, not approximations that hold in a limit.
The library meets the subject in practice in several places. Training, Validation, and Test Sets measures how noisy a held-out estimate is and how much choosing a model by it flatters the winner, The Bias-Variance Tradeoff splits the squared error of a fitted function, Support Vector Machines maximizes a margin, and Superposition, Memorization, and Double Descent reports test loss falling again after it rose. The units Prediction Error and Model Choice and Probability Theory supply the optimism of a fit and the inequalities behind the laws of large numbers. This unit supplies the theory that connects them: why the gap between training and test error exists, what controls it, and where the classical answers stop.
What it assumes. Probability Theory, in particular Probability Inequalities (Markov's inequality and the Chernoff bound), Moment Generating and Characteristic Functions and Conditional Expectation; the martingales of Random Walks and Martingales for one proof; and, for comparison, the optimism and cross-validation results of Prediction Error and Model Choice.
What is proved and what is cited. The unit proves its finite-sample results in full and cites the deepest of the infinite-class results. Proved: the unbiasedness of a fixed rule's training error and the optimism of empirical risk minimization; the risk of a rule that memorizes its sample; the optimality of the Bayes classifier, with the excess risk of any rule as an expected margin; the decomposition into approximation and estimation error and the reduction of the estimation error to a uniform deviation; the pointwise minimizers of the common surrogate losses; Hoeffding's lemma and inequality, the bound with the Kullback–Leibler exponent, Bennett's and Bernstein's inequalities, and McDiarmid's bounded-differences inequality; the sample complexity of finite classes in the realizable and agnostic cases by the union bound, the Occam bound and the no-free-lunch theorem of learning; shattering, the VC dimensions of thresholds, intervals, rectangles and half-spaces, and the Sauer–Shelah–Perles lemma; symmetrization, Massart's lemma, the uniform convergence bound with the VC dimension that follows from them, the contraction lemma and the margin bound for linear classifiers; the Rademacher complexity of a class that fits every labeling, and the lower bound of one half on any bound that depends only on the class and the distribution of the inputs, not on the labels, when the class can fit random labels; and the exact risk of minimum-norm least squares in a Gaussian model, whose infinite peak is a double descent. Cited: the characterization of calibrated surrogate losses; sampling without replacement; the logarithm-free rates of the fundamental theorem, which need chaining, and its lower bounds; the argument of Nagarajan and Kolter against uniform convergence; and the margin, PAC-Bayes, compression and stability bounds proposed for large networks.
Notation. Examples $z = (x, y)$ come from an unknown distribution $\mathcal{D}$ on an instance space $\mathcal{X}$ and a label space $\mathcal{Y}$, here $\{0, 1\}$; where signs are needed the labels are written $\tilde y = 2y - 1$. A training sample $S$ holds $m$ independent examples, written $S \sim \mathcal{D}^m$, and a held-out test set holds $n$. A classifier (hypothesis) $h$ belongs to a class $\mathcal{H}$; its loss on $z$ is $\ell(h, z)$, usually the 0-1 loss $\mathbf{1}\{h(x) \ne y\}$; its risk is $L_{\mathcal{D}}(h) = E[\ell(h, z)]$ and its empirical risk $L_S(h) = \frac1m\sum_i \ell(h, z_i)$. Empirical risk minimization returns $h_S \in \operatorname{argmin}_{h \in \mathcal{H}} L_S(h)$, and $h^*$ is the best rule in the class. The Bayes classifier is $f_{\mathcal{D}}(x) = \mathbf{1}\{\eta(x) \ge 1/2\}$ with $\eta(x) = P(Y = 1 \mid X = x)$, and its risk is the Bayes risk $L^*_{\mathcal{D}}$. The approximation error is $\min_{\mathcal{H}} L_{\mathcal{D}} - L^*_{\mathcal{D}}$ and the estimation error $L_{\mathcal{D}}(h_S) - \min_{\mathcal{H}} L_{\mathcal{D}}$. Guarantees have an accuracy $\varepsilon$ and hold with probability at least $1 - \delta$ over the sample; $m_{\mathcal{H}}(\varepsilon, \delta)$ is the sample complexity, $\tau_{\mathcal{H}}(m)$ the growth function, $\mathrm{VCdim}(\mathcal{H})$ the VC dimension and $\mathfrak{R}_m$ the Rademacher complexity, whose random signs $\sigma_i$ are not standard deviations. The notation follows Shalev-Shwartz and Ben-David (2014).
Data. The 5,210 adults of NHANES 2017–2018 who had an HbA1c test and answered the question about diagnosed diabetes (pregnant women excluded), of whom 806 said yes. The unit treats them as the whole population: $\mathcal{D}$ is a draw of one adult at random, so that every risk is an exact fraction, and samples are drawn with replacement, which makes them exactly independent. The rules are thresholds and intervals on HbA1c, a class whose VC dimension can be seen. The best threshold, 6.7%, errs on 437 adults, and the Bayes classifier on 427. NHANES sampling weights are not used, so the numbers describe these adults, not the U.S. population. Every number is computed by a script in tools/experiments/statistics/, and simulations use 30 seeds, reported as medians and interquartile ranges.
Articles
Risk and concentration
- Empirical Risk Minimization: why the training error of a learned rule understates its error on new data, and what the best possible error is. The training error of a rule fixed in advance proved unbiased with the binomial variance, and that of the empirical risk minimizer proved optimistic on average; a rule that memorizes its sample proved to have zero training error and the risk of a guess; the Bayes classifier proved optimal, with the excess risk of any rule as an expected margin and a bound for plug-in rules; the excess risk split into approximation, estimation and optimization error, with the estimation error at most twice the largest deviation over the class; and the hinge, logistic, exponential and squared surrogate losses shown to have minimizers with the Bayes classifier's sign. On the NHANES thresholds the training error of the chosen rule understates its risk by 0.0616 with 20 examples and 0.0024 with 2,000, and the thresholds come within 0.0019 of the Bayes risk.
- Concentration Inequalities: Hoeffding and Bernstein: bounds on how far an average of independent bounded variables, or any function that no single variable can move much, strays from its expectation, at every sample size. Hoeffding's lemma and inequality proved from the Chernoff bound, the sharper Kullback–Leibler exponent, Bennett's and Bernstein's inequalities, which use the variance, and McDiarmid's bounded-differences inequality, proved through a martingale of conditional expectations; sampling without replacement cited. For the 6.7% threshold rule a test set of 4,612 cases guarantees its error rate within $\pm 0.02$ with 95% confidence by Hoeffding's inequality, and 1,530 by Bernstein's with the variance known, where the exact binomial needs 771; Hoeffding's interval is about 2.5 times as wide as the exact one at every size.
Learnability and the size of a class
- PAC Learning and Finite Hypothesis Classes: how many examples a learner needs before it can promise, for every distribution, that its rule is probably nearly the best available. Probably approximately correct learning defined in the realizable and agnostic cases; every finite class proved learnable with $\ln(\lvert\mathcal{H}\rvert/\delta)/\varepsilon$ examples when some rule is perfect and $2\ln(2\lvert\mathcal{H}\rvert/\delta)/\varepsilon^2$ in general, by a union bound; the discretization trick, Kraft's inequality and the Occam bound; and the no-free-lunch theorem of learning, contrasted with that of optimization. With labels set by the American Diabetes Association's 6.5% cutoff, so that one of the 201 thresholds of the NHANES grid is perfect, the realizable bound at $\varepsilon = 0.01$ and $\delta = 0.05$ asks for 830 examples where 229 suffice.
- The VC Dimension: what decides whether an infinite class can be learned, and from how many examples. Restrictions, shattering and the Vapnik–Chervonenkis dimension; a class that shatters arbitrarily large sets proved not learnable; the VC dimensions of thresholds, intervals, axis-aligned rectangles and half-spaces proved, the last by Radon's theorem; the Sauer–Shelah–Perles lemma and the polynomial bound on the growth function proved; and the fundamental theorem of statistical learning proved in its qualitative form through links, its uniform convergence bound proved in Rademacher Complexity and its sharp rates and lower bounds cited. On the NHANES thresholds and intervals the VC bound stands 6 to 11 times above the largest deviation observed, falling at the same rate.
- Rademacher Complexity: how well a class can fit random signs on the sample, and why that number controls the gap between risk and empirical risk uniformly over the class. Symmetrization and its reverse, high-probability and data-dependent bounds through McDiarmid's inequality, Massart's lemma and the VC-dimension uniform convergence bound that follows from it, Talagrand's contraction lemma, and the margin bound for linear classifiers, all proved; the complexity of thresholds and intervals on the NHANES adults computed by Monte Carlo against Massart's and Sauer's bounds.
Where the classical bounds stop
- Why Classical Bounds Do Not Explain Deep Networks: what uniform convergence bounds say about models with more parameters than training examples, and why they cannot account for how well such models predict. A class able to fit every labeling proved to have Rademacher complexity 1, so its bounds are vacuous, and any bound that depends only on the class and the distribution of the inputs, not on the labels, proved to be at least one half when the class can fit random labels; the randomization test of Zhang and colleagues reproduced with a small network on digit images; the exact risk of minimum-norm least squares in the Gaussian weak-features model of Belkin, Hsu and Xu derived, whose infinite peak where parameters equal examples is a double descent; and the Nagarajan–Kolter argument and the margin, PAC-Bayes, compression and stability bounds proposed instead stated with their limits.
Where the unit leads
The guarantees here are worst cases over every distribution of the data, and on the NHANES thresholds they stand several times above what is observed. They answer a question the earlier units leave open, why a fitted model's training error must be discounted and by how much, and they show which properties of a class, its size, its VC dimension or its Rademacher complexity, set the discount. What they do not explain is the behavior of models with far more parameters than examples, which fit their training data exactly and still predict well; the last article of the unit weighs the evidence. The methods that estimate the discount from the data rather than bound it are those of What Cross-Validation Estimates and Optimism and Effective Degrees of Freedom.
This is the last unit of the plan for the Statistics collection. It began from the applied course in biostatistics and ends at the question of how much a learned rule can be trusted, which is where the collection meets the library's work on language models and the information retrieval course.
References
- Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13–30. https://doi.org/10.1080/01621459.1963.10500830 record · 2 pages
- Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2018). Foundations of Machine Learning (2nd ed.). MIT Press. record · 5 pages
- Nagarajan, V., and Kolter, J. Z. (2019). Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems 32. arXiv:1902.04742. record · 2 pages
- National Center for Health Statistics (2020). National Health and Nutrition Examination Survey 2017–2018: Demographic Variables and Sample Weights (DEMO_J), Glycohemoglobin (GHB_J) and Diabetes (DIQ_J) data files. Centers for Disease Control and Prevention. https://wwwn.cdc.gov/nchs/nhanes/continuousnhanes/default.aspx?BeginYear=2017 record · 106 pages
- Shalev-Shwartz, S., and Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press. record · 6 pages
- Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. International Conference on Learning Representations. arXiv:1611.03530. record · 2 pages