Derive the margin generalisation bound
ProofGraduate⏱ 1 hourLearning Theorymargin boundcontractionramp losssvm
Problem
Let be the norm-bounded linear class with , and fix . Prove that with probability at least , for all ,
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| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| The geometric margin | Classical ML | Proof | 15 min | ||
| Solve a two-point SVM by hand | Classical ML | Numerical | 30 min | ||
| The soft-margin SVM is regularised hinge-loss minimisation | Classical ML | Proof | 30 min | ||
| VC dimension of halfspaces | Learning Theory | Proof | 30 min | ||
| A one-parameter class with infinite VC dimension | Learning Theory | Proof | 1 hour |