Skip to content
nonconvexcard

Derive the margin generalisation bound

ProofGraduate⏱ 1 hourLearning Theorymargin boundcontractionramp losssvm

Problem

Let FB\Fcal_B be the norm-bounded linear class with ∥xi∥2≤R\|x_i\|_2\le R, and fix γ>0\gamma>0. Prove that with probability at least 1−δ1-\delta, for all f∈FBf\in\Fcal_B,

P(Yf(X)≤0)≤1n∑i1{yif(xi)≤γ}+2BRγn+log⁡(1/δ)2n.\P\big(Yf(X)\le0\big) \le \frac1n\sum_i\one\{y_if(x_i)\le\gamma\} + \frac{2BR}{\gamma\sqrt n} + \sqrt{\frac{\log(1/\delta)}{2n}} .

Identify the surrogate loss, its Lipschitz constant, and the role of the contraction lemma.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
The geometric marginClassical MLProofFoundation15 min
Solve a two-point SVM by handClassical MLNumericalBeginner30 min
The soft-margin SVM is regularised hinge-loss minimisationClassical MLProofIntermediate30 min
VC dimension of halfspacesLearning TheoryProofIntermediate30 min
A one-parameter class with infinite VC dimensionLearning TheoryProofAdvanced1 hour