The SVM margin bound

ProofGraduate⏱ 1 hourClassical MLsvmmargin boundrademachercontractiongeneralisation

Theory: Support Vector Machines — Complete Derivation →

Problem

Prove the margin generalisation bound for norm-bounded linear classifiers, and explain in one paragraph why it justifies the SVM objective rather than merely being consistent with it. Then compute the bound numerically for $B = 1$ , $R = 1$ , $\gamma = 0.1$ , $n = 10^4$ and comment.

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

Problem	Field	Type	Difficulty	Time
The geometric margin	Classical ML	Proof	Foundation	15 min
Solve a two-point SVM by hand	Classical ML	Numerical	Beginner	30 min
The psi-2 norm of a Rademacher sign	High-Dim Probability	Numerical	Beginner	15 min
The soft-margin SVM is regularised hinge-loss minimisation	Classical ML	Proof	Intermediate	30 min
Massart's finite maximal inequality	Learning Theory	Proof	Advanced	30 min