Rademacher Bound, An Alternative to Cross Validation for Ridge?

Question

Below is a theorem from the book "Foundations of Machine Learning".

It specifies the generalization bounds for Kernel Ridge Regression by making use of the Rademacher Complexity on linear models. $R(h)$ is the generalization error, and $\hat{R}(h)$ is the empirical error. Now pretty much everything is either known to us, picked by us, or can be calculated by us. $m$ is the number of training samples.

Instead of finding the right penalty $\Lambda$ via cross validation, can we simply pick the $\Lambda$ that minimizes the right hand side of the inequality? What should be the $\delta$ value to be set in order to achieve best predictive result? How to choose $r$ as tight as possible?

Is this an alternative to Cross Validation for Kernel Ridge (or just Ridge) Regression?

Answer 1

The problem is that the second part of the upper bound on the generalisation error can be huge. That is, the bound is not very tight, so it could not give you a good indication of the generalization error.

You can't really pick the $\Lambda$ that would minimize the right hand side of the inequality (that would be $0$), because the theorem makes an assumption that $|f(x)| \leq \Lambda r$. So, if you minimze it as is you, lose expressivity basically. Or did you mean do a grid search on $\Lambda$, calibrate the model and compute the upper bound, then select the $\Lambda$ which after calibration minimizes the whole upper bound not just the second part of it?

You also can't pick $r$, it is a problem value given by the distribution of your data. It basically is the radius of the ball in which lies your data.

Finally, $\delta$ doesn't have an influence on your predictive capability. It is an indicator of "how certain" this upper bound is. Indeed the upper bound is not deterministic it is only valid with a certain probability. Written holisticly it would be: $$ \mathbb{P}( \{R(h) \leq \hat{R}(h) + \frac{8r^2\Lambda^2}{\sqrt{m}} \left(1 + 0.5 \sqrt{\frac{\log{\delta^{-1}}}{2}}\right)\}) < 1 - \delta $$ When computing you generally want a low $\delta$, like say $0.01$ but it doesn't affect the result much as it is $\log{\delta^{-1}}$.