Derive the soft-margin SVM dual

ProofGraduate⏱ 3 hoursClassical MLsvmsoft marginbox constraintdualflagship

Theory: Support Vector Machines — Complete Derivation →

Problem

Derive the soft-margin dual from $\min\frac12\|w\|_2^2+C\sum_i\xi_i$ subject to $y_i(\langle w,x_i\rangle+b)\ge1-\xi_i$ , $\xi_i\ge0$ . Show that the box constraint $0\le\alpha_i\le C$ is derived rather than imposed, and that the slack variables disappear identically.

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 soft-margin SVM is regularised hinge-loss minimisation	Classical ML	Proof	Intermediate	30 min
Prove the O(1/t) rate for gradient descent abyss	Optimization	Proof	Advanced	1 hour
The three regimes of a training point	Classical ML	Proof	Advanced	30 min