Generalization#
Some notes on generalization bounds in machine learning with an emphasis on stability
About this chapter
A short page on bounding the gap between how well a learned model \(A_S\) does on new data and how well it does on its training set \(S\). The first section defines the three quantities everything else uses: the risk \(R(A_S)\), the empirical risk \(R_{\mathrm{emp}}(A_S)\), and the generalization error, their difference.
The second section bounds that gap through uniform stability: if swapping one training point never changes the loss by more than \(\gamma\), the gap can be bounded in terms of \(\gamma\) and \(n\). The last section goes the other way, with a lower bound on how well any axis-aligned tree can fit data from an additive model.
Basics#
The three quantities the rest of the page uses. \(A_S\) is the model an algorithm \(A\) fits on the training set \(S\) of \(n\) points.
Risk: \(R\left(A_{S}\right)=\mathbb{E}_{(X, Y) \sim P} \ell\left(A_{S}(X), Y\right)\)
Empirical risk: \(R_{\mathrm{emp}}\left(A_{S}\right)=\frac{1}{n} \sum_{i=1}^{n} \ell\left(A_{S}\left(X_{i}\right), Y_{i}\right)\)
Generalization error: \(R\left(A_{S}\right)-R_{\mathrm{emp}}\left(A_{S}\right)\)
Uniform stability#
Stability bounds look at the algorithm, not the size of the model class. \(A_{S^i}\) is the model trained on \(S\) with the \(i\)-th point replaced, and \(\gamma\) caps how much that one change can move the loss anywhere. This is why the approach still gives bounds for 1-nearest-neighbor, whose training error is 0.
Sharper Bounds for Uniformly Stable Algorithms
uniformly stable with prameter \(\gamma\) if \(\left\vert \ell\left(A_{S}(x), y\right)-\ell\left(A_{S^{i}}(x), y\right)\right\vert \leq \gamma\)
where \(A_{S^i}\) can alter one point in the training data
stability approach can provide bounds even when empirical risk is 0 (e.g. 1-nearest-neighbor, devroye & wagner 1979)
\(n\underbrace{\left(R\left(A_{S}\right)-R_{\mathrm{emp}}\left(A_{S}\right)\right)}_{\text{generalization error}} \lesssim(n \sqrt{n} \gamma+L \sqrt{n}) \sqrt{\log \left(\frac{1}{\delta}\right)}\) (bousegeuet & elisseef, 2002)
Trees#
A lower bound rather than an upper bound. When \(y\) is a sum of functions of single features, trees that split on one feature at a time and predict leaf averages can’t beat the rate \(\Omega(n^{-\frac{2}{s+2}})\) in \(\ell_2\) risk, however the splits are chosen.
A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds (tan, agarwal, & yu, 2021)
(generalized) additive models: \(y = f(X_1) + f(X_2) + ... f(X_p)\) (as opposed to linear models)
main result
lower bound: can’t peform better than \(\Omega (n^{-\frac{2}{s+2}})\) in \(\ell_2\) risk (as defined above)
best tree (ALA tree) can’t do better than this bound (e.g. risk \(\geq \frac{1}{n^{s+2}}\) times some stuff)
generative assumption simplifies calculations by avoiding some of the complex dependencies be- tween splits that may accumulate during recursive splitting
ALA tree
learns axis-aligned splits
makes predictions as leaf averages
honest trees: val split is used to estimate leaf averages
Key ideas
The generalization error is the gap between the risk \(R(A_S)\) on new data and the empirical risk \(R_{\mathrm{emp}}(A_S)\) on the training set.
Uniform stability bounds this gap through the algorithm, by how much replacing one training point can change the loss, rather than through the size of the model class.
Stability still gives bounds when the training error is 0, as for 1-nearest-neighbor.
For data from an additive model, axis-aligned trees with leaf averages have a lower bound on their \(\ell_2\) risk of \(\Omega(n^{-\frac{2}{s+2}})\).