# Rademacher Bound, An Alternative to Cross Validation for Ridge?

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?

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}}$$.
• RIght hand side cannot be 0, because setting $\Lambda$ too low makes $\hat{R}(h)$ very high. Yes I am talking about choosing hypotheses with different values of $\Lambda$ May 20, 2019 at 5:00
• Ok! But my other points still stand, the second part of the upper bound might still be too large to have any valuable information on $R(h)$. And picking $r$ or $\delta$ is not really possible. May 20, 2019 at 8:48