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

enter image description here

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?


1 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}}$.

  • $\begingroup$ 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$ $\endgroup$ May 20, 2019 at 5:00
  • $\begingroup$ 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. $\endgroup$ May 20, 2019 at 8:48
  • $\begingroup$ I am not sure there are practical applications. What it is though, is a theoretical "validation" of machine learning, meaning that reducing the training error will help you reduce the generalization error because it is upper bounded by it. So it means that the generalization is not "infinitely off" if the training error isn't. $\endgroup$ May 20, 2019 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.