Support Vector Machines and Support Vector Regression › Example

Two points suffice to work the margin calculation by hand. Let

$$\mathbf{x}_1 = (1, 1), \; y_1 = +1, \qquad \mathbf{x}_2 = (-1, -1), \; y_2 = -1.$$

where:

• $\mathbf{x}_1, \mathbf{x}_2 \in \mathbb{R}^2$: the two training inputs
• $y_1, y_2 \in \{-1, +1\}$: their corresponding labels

The hard-margin problem for these two points is

$$\begin{aligned} \min_{\mathbf{w},\, b} \;& \tfrac{1}{2}(w_1^2 + w_2^2) \\ \text{s.t.} \;& w_1 + w_2 + b \geq 1, \\ & w_1 + w_2 - b \geq 1. \end{aligned}$$

We can prove the symmetry rather than assume it. Let $s=w_1+w_2$. The two constraints imply $s\ge1+|b|$, while $w_1^2+w_2^2\ge s^2/2$, with equality only when $w_1=w_2$. Hence the objective is at least $(1+|b|)^2/4\ge1/4$. Equality is attained by $b=0$ and $w_1=w_2=1/2$, proving global optimality. At this solution both margin constraints are tight:

$$\text{point 1:} \quad (+1)(w_1 + w_2) = 1, \qquad \text{point 2:} \quad (-1)(-w_1 - w_2) = 1.$$

Both equations reduce to $w_1 + w_2 = 1$. Under the symmetry assumption $w_1 = w_2$ we find $w_1 = w_2 = 0.5$, so $\mathbf{w} = (0.5, 0.5)$ and $\|\mathbf{w}\| = \sqrt{0.5^2 + 0.5^2} = \sqrt{0.5} \approx 0.707$. The margin width is

$$\begin{aligned} \frac{2}{\|\mathbf{w}\|} &= \frac{2}{\sqrt{0.5}} \\ &= \frac{2}{0.707\ldots} \\ &\approx 2.828, \end{aligned}$$

and the decision boundary is the line $x_1 + x_2 = 0$.

To connect this back to the dual, let $\alpha_1, \alpha_2 \geq 0$ be the multipliers. The KKT stationarity condition gives

$$\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i = \alpha_1 (1, 1) + \alpha_2 (-1) (-1, -1) = (\alpha_1 + \alpha_2)(1, 1).$$

Since $\mathbf{w}=(0.5,0.5)$, stationarity requires $\alpha_1+\alpha_2=0.5$. The balance condition gives $\alpha_1=\alpha_2=0.25$. These hard-margin multipliers are feasible for the soft-margin box constraints when $C\ge0.25$, so the same zero-slack solution is optimal there. For $0<C<0.25$, the dual optimum has $\alpha_1=\alpha_2=C$ and $\mathbf{w}=(2C,2C)$. Choosing $b=0$ then gives both points functional margin $4C<1$. In fact every $b\in[4C-1,\,1-4C]$ is optimal in this regime, showing that the unpenalized bias need not be unique.

Returning to the hard-margin solution, which is also the soft-margin solution for $C\geq0.25$, we can check strong duality. Its primal objective is

$$\tfrac{1}{2}\|\mathbf{w}\|^2 = \tfrac{1}{2}\bigl(0.5^2 + 0.5^2\bigr) = \tfrac{1}{2}(0.5) = 0.25.$$

Because both points sit exactly on the margin, their slack values are zero and the hinge-loss sum vanishes, so the primal objective equals the margin term alone. This is the dual echo of the geometric statement that the two closest points fully determine the boundary.

We can verify the calculation with the dual objective. Note that

$$\mathbf{x}_1^\top \mathbf{x}_1 = \mathbf{x}_2^\top \mathbf{x}_2 = 2, \qquad \mathbf{x}_1^\top \mathbf{x}_2 = -2,$$

so the cross term carries a negative label product $y_1 y_2 = -1$, and the negative inner product $\mathbf{x}_1^\top \mathbf{x}_2 = -2$ makes the product positive. Thus

$$\begin{aligned} \sum_{i,j} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^\top \mathbf{x}_j &= \alpha_1^2 y_1^2 \mathbf{x}_1^\top \mathbf{x}_1 + 2\alpha_1\alpha_2 y_1 y_2 \mathbf{x}_1^\top \mathbf{x}_2 + \alpha_2^2 y_2^2 \mathbf{x}_2^\top \mathbf{x}_2 \\ &= 0.25^2 \cdot 2 + 2 \cdot 0.25 \cdot 0.25 \cdot (1)(-1)(-2) + 0.25^2 \cdot 2 \\ &= 0.0625 \cdot 2 + 0.125 \cdot 2 + 0.0625 \cdot 2 \\ &= 0.125 + 0.25 + 0.125 = 0.5. \end{aligned}$$

and the dual objective equals

$$\sum_i \alpha_i - \tfrac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^\top \mathbf{x}_j = (0.25 + 0.25) - \tfrac{1}{2}(0.5) = 0.5 - 0.25 = 0.25.$$

where:

• $\alpha_i$: the optimal dual multipliers $\alpha_1 = \alpha_2 = 0.25$ from the stationarity condition
• $y_i$: the labels $y_1 = +1$ and $y_2 = -1$
• $\mathbf{x}_i^\top \mathbf{x}_j$: the pairwise inner products, $\mathbf{x}_1^\top \mathbf{x}_1 = \mathbf{x}_2^\top \mathbf{x}_2 = 2$ and $\mathbf{x}_1^\top \mathbf{x}_2 = -2$
• $0.5$: the value of the double sum computed above

The dual objective value $0.25$ matches the primal value $0.25$, which is consistent with strong duality.

Now consider a slightly harder case that exercises the soft margin. Add a third point $\mathbf{x}_3 = (2, 2)$ with $y_3 = -1$. Keep the original candidate $\mathbf{w} = (0.5, 0.5)$ and $b = 0$; rescaling it would change the functional margins used by the objective. For the third point,

$$y_3 f(\mathbf{x}_3) = (-1)\bigl(0.5\cdot 2+0.5\cdot 2\bigr) = -2.$$

Its smallest feasible slack at this candidate is therefore

$$\xi_3=\max(0,1-y_3 f(\mathbf{x}_3))=3.$$

The original two points still have zero slack, so this candidate has objective $\tfrac14+3C$. This is a feasible value, not proof that the candidate is optimal.

In fact, this dataset has a useful structure: the positive point lies between two negative points on the same line. For every $C>0$, the exact soft-margin optimum is the constant classifier

$$\mathbf{w}=(0,0),\qquad b=-1,\qquad (\xi_1,\xi_2,\xi_3)=(2,0,0).$$

It predicts the negative class for all three points, pays hinge loss two for the positive point, and has objective $2C$. We can prove optimality using the dual multipliers

$$(\alpha_1,\alpha_2,\alpha_3) =\left(C,\frac C3,\frac{2C}{3}\right).$$

They satisfy the box constraints and $\alpha_1-\alpha_2-\alpha_3=0$, and they give

$$\sum_i\alpha_i y_i\mathbf{x}_i =\left(C+\frac C3-\frac{4C}{3}\right)(1,1) =(0,0).$$

The dual objective is consequently $\sum_i\alpha_i-\tfrac12\|\mathbf{w}\|^2=2C$, matching the primal value. A feasible primal value matching a feasible dual value establishes global optimality.

Here $C$ changes the objective value without changing the fitted classifier. The usual margin-versus-loss tradeoff does not promise that the boundary moves whenever $C$ changes. Since $\mathbf{w}=0$, this constant solution has no separating hyperplane with a finite margin width $2/\|\mathbf{w}\|$; the soft-margin objective is still well defined.