Let's consider the separable problem in Support Vector Machine fitting as a special case of the non-separable problem. My terminology will be consistent with Mohri et al (2018), so I use 'risk' for 'error' or 'loss', and 'hypothesis' for 'solution' or 'model'.

I will not go into detailed formulas, since there are different ways to specify bounds on true risk based on empirical risk and complexity. However, in general, we have that with a given probability, the true risk associated with a given hypothesis is bounded by the sum of empirical risk and a term monotonic in the complexity of the hypothesis set, among potential others.

Why does the hypothesis with zero empirical risk provide the best generalisation bound? In other words, why is it not possible that the reduced complexity brought about by a larger margin outweighs a slight increase in empirical risk? (Equivalently, why is a cost of $+\infty$ optimal if the problem is solved in the general setting?)

PS For reference, Vapnik bounds the VC dimension of an SVM hypothesis by $$min\bigg(\bigg[\frac{R^2}{\rho^2}\bigg],n\bigg) + 1$$ where $R$ is the radius of the data points, $\rho$ the margin and $n$ the dimension of the space. Rademacher complexity will follow the same pattern.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.