05 Lagrange Duality and SVM Dual Formulation

Lagrange Relaxation and Duality

In many machine learning problems, we need to minimise a function $F(x)$ subject to certain inequalities constraints $f_i(x)\le 0$

The Lagrangian Function

To solve this, we define the Lagrangian $L(x,a)$:

$$L(x,a)=F(x)+\sum _{i=1}^N{a}_i{f}_i(x)$$

• $a_i$ (Lagrangian Multipliers): Must be $\ge 0$.
• The Penalty Logic: If a constraint is violated $(f_i(x)>0)$, then the term $a_i{f}_i(x)$ acts as a penalty, increasing the objective value. If the constraint is satisfied $(f_i(x)\le 0)$, the term is $\le 0$, “rewarding” the objective.

Primal and Dual Formulation

1. Minimax Primal: ${\min }_x{\max }_{a}L(x,a)$. The optimiser tries to find the best $x$ while the “adversary” $a$ tries to penalise any constraint violation.
2. Maxmin Dual: ${\max }_a{\min }_{x}L(x,a)$. This formulation is often easier to solve because we can sometime eliminate the inner minimisation using calculus.

Tip

Strong Duality (where Min-Max = Max-Min) holds for most ML problems because they are convex and have a feasible region where $f_i(x)<0$ for all $i$.

Karush-Kuhn-Tucker (KKT) Conditions

For a convex optimisation problem, a solution $(x^{\star },a^{\star })$ is optimal if and only if it satisfies the following KKT conditions:

1. Stationarity: The gradient of the Lagrangian with respect to the primal variables must be zero.

$${\nabla }_{x}L(x,a)=\nabla F(x)+\sum a_i\nabla f_i(x)=0$$

2. Complementary Slackness: $a_i{f}_i(x)=0$ for all $i$. This implies that either the multiplier $a_i$ is zero or the constraint is “active” $(f_i(x)=0)$.
3. Feasibility: The original primal constraints $(f_i(x)\le 0)$ and the dual constraints $(a_i\ge 0)$ must be satisfied.

Deriving the SVM Dual Formulation

The original SVM Primal Problem aims to minimise the weights $w$ while ensuring all points are outside the margin.

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2\text{subject to: }{y}_n(w^T\varphi (x_n)+b)\ge 1$$

Step-by-Step Derivation

1. Rewrite Constraints: Transform to $1-y_n(w^T\varphi (x_n)+b)\le 0$
2. Form the Lagrangian:

$$L(w,b,a)=\frac{1}{2}\Vert w{\Vert }^2+\sum _{n=1}^N{a}_n[1-y_n(w^T\varphi (x_n)+b)]$$

3. Apply Stationarity (KKT):
   • Set ${\nabla }_{w}L=0$**: $w-\sum a_n{y}_n\varphi (x_n)=0⟹\mathbf{w}={\sum }_{\mathbf{n}=1}^{\mathbf{N}}{\mathbf{a}}_{\mathbf{n}}{\mathbf{y}}_{\mathbf{n}}\varphi ({\mathbf{x}}_{\mathbf{n}})$
   • Set $\partial L/\partial b=0$: ${\sum }_{\mathbf{n}=1}^{\mathbf{N}}{\mathbf{a}}_{\mathbf{n}}{\mathbf{y}}_{\mathbf{n}}=0$
4. Substitute back into the Lagrangian: This yields the Dual Objective $(\tilde{L})$, which only depends on the multiplier $a$.

Final SVM Dual Representation

$${\text{argmax}}_a\sum _{n=1}^N{a}_n-\frac{1}{2}\sum _{n=1}^N\sum _{m=1}^N{a}_n{a}_m{y}_n{y}_{m}k(x_n,x_m)$$

Subject to: $\sum a_n{y}_n=0$ and $a_n\ge 0$

The Kernel Trick

The dual formulation highlights that the optimisation only depends on the inner product of the feature vectors: $k(x_n,x_m)=\varphi (x_n{)}^T\varphi (x_m)$

• Intuition: Instead of mapping data to a massive $d$-dimensional space $\varphi (x)$ (which is expensive), we use a Kernel Function to compute the inner product directly in the original space.
• Example (polynomial Kernel): For a $2D$ input $x$, a $2nd$-degree mapping $\varphi (x)$ leads to:

$$k(x,z)=(1+x^{T}z{)}^2$$

This is much faster than calculating the $6$-dimensional vector $\varphi (x)$ for every point.

Efficiency Comparison

• Primal: Complexity depends on the dimensionality of the feature space ($d+1$ variables).
• Dual: Complexity depends on the number of training examples ($N$ variables).