The SVM dual and support vectors

The SVM primal is a constrained QP over $w$ and $b$. The dual is a QP over one multiplier $\alpha_i$ per training example, with a structure that makes two things explicit: the solution is sparse in $\alpha$, and it depends on the data only through inner products[1]. The second fact is what kernel methods exploit.

Forming the dual

Start with the soft-margin primal:

Introduce multipliers $\alpha_i \ge 0$ for the margin constraints and $\mu_i \ge 0$ for the nonnegativity of slack. The Lagrangian is

Stationarity:

So $w = \sum_i \alpha_i y_i x_i$, $\sum_i \alpha_i y_i = 0$, and $0 \le \alpha_i \le C$ (eliminating $\mu_i = C - \alpha_i$).

Substituting back gives the dual QP:

The data enters only through the inner products $x_i^\top x_j$, which is the hook the kernel trick will exploit.

Three regimes of $\alpha_i$ (KKT)

The complementary slackness conditions classify every training example into exactly one bucket:

• $\alpha_i = 0$: the constraint $y_i(w^\top x_i + b) \ge 1$ is slack (strict inequality). The point sits outside the margin and contributes nothing to $w$.
• $0 < \alpha_i < C$: the constraint is tight, $y_i(w^\top x_i + b) = 1$. The point lies exactly on the margin boundary. These are the margin support vectors.
• $\alpha_i = C$: the constraint is tight with positive slack, so the point is inside the margin or misclassified. These are the bound support vectors, the noisy or hard-to-classify points.

Only the support vectors have $\alpha_i > 0$, and only they contribute to $w$. The classifier is sparse in examples: most training points are forgotten after fitting[2].

Recovering $w$ and $b$

The weight vector is

a linear combination of the support vectors. The bias $b$ is recovered from any margin support vector ($0 < \alpha_i < C$): such a point satisfies $y_i(w^\top x_i + b) = 1$, so $b = y_i - w^\top x_i$. In practice average across all margin support vectors for stability.

Why the dual is interesting

Three reasons:

• Sparsity: only support vectors matter at prediction time, so the model size is the number of SVs, not the dataset size.
• Kernelization: the dual depends on data only via inner products, so replacing $x_i^\top x_j$ with a kernel $k(x_i, x_j)$ lifts the SVM to any reproducing kernel Hilbert space without ever forming the lifted features.
• Algorithms: dual coordinate ascent (SMO) is the basis of LIBSVM and remains competitive on small to medium problems.

Check it on arrays

import numpy as np

rng = np.random.default_rng(0)

# Mildly nonseparable data
n_per = 40
X_pos = rng.normal([1.2, 0.5], scale=0.8, size=(n_per, 2))
X_neg = rng.normal([-1.2, -0.5], scale=0.8, size=(n_per, 2))
X = np.vstack([X_pos, X_neg])
y = np.array([1.0] * n_per + [-1.0] * n_per)

def svm_dual(X, y, C=1.0, lr=1e-3, steps=20000):
    K = X @ X.T
    Q = (y[:, None] * y[None, :]) * K
    n = len(y)
    alpha = np.zeros(n)
    for _ in range(steps):
        grad = 1 - Q @ alpha
        alpha = alpha + lr * grad
        alpha = np.clip(alpha, 0, C)
        # project onto sum(y * alpha) = 0
        s = (y @ alpha) / (y @ y)
        alpha -= s * y
        alpha = np.clip(alpha, 0, C)
    return alpha

C = 1.0
alpha = svm_dual(X, y, C=C)
w = (alpha * y) @ X
margin_sv = (alpha > 1e-4) & (alpha < C - 1e-4)
b = np.mean(y[margin_sv] - X[margin_sv] @ w)

# Classify and check the three buckets
n_zero = int(np.sum(alpha < 1e-4))
n_margin = int(np.sum(margin_sv))
n_bound = int(np.sum(alpha > C - 1e-4))
print(f"alpha = 0      : {n_zero} / {len(y)}  (outside margin)")
print(f"0 < alpha < C  : {n_margin}            (on margin)")
print(f"alpha = C      : {n_bound}            (inside margin or misclassified)")
print(f"accuracy: {np.mean(np.sign(X @ w + b) == y):.3f}")
print(f"margin = 1/||w||: {1.0 / np.linalg.norm(w):.3f}")

The training set splits cleanly into the three KKT buckets; only the support vectors (margin + bound) shape the decision boundary.

Exercises

Exercise 1. A soft-margin SVM with $C = 1$ returns multipliers $\alpha = (0, 1, 0.4, 0)$ on four training points. Classify each point into its KKT bucket and state which points contribute to $w$.

Exercise 2. Given the optimal dual solution and a margin support vector $x_k$ (with $0 < \alpha_k < C$), derive the bias $b = y_k - \sum_i \alpha_i y_i\, x_i^\top x_k$.

Exercise 3 (code). Run the dual coordinate-ascent on a mildly nonseparable dataset and verify the equality constraint $\sum_i \alpha_i y_i = 0$ holds and that the three KKT buckets partition all training points.

import numpy as np

rng = np.random.default_rng(0)
n_per = 40
X = np.vstack([rng.normal([1.2, 0.5], 0.8, (n_per, 2)),
               rng.normal([-1.2, -0.5], 0.8, (n_per, 2))])
y = np.array([1.0] * n_per + [-1.0] * n_per)

def svm_dual(X, y, C=1.0, lr=1e-3, steps=20000):
    Q = (y[:, None] * y[None, :]) * (X @ X.T)
    alpha = np.zeros(len(y))
    for _ in range(steps):
        grad = 1 - Q @ alpha
        alpha = np.clip(alpha + lr * grad, 0, C)
        alpha -= (y @ alpha) / (y @ y) * y        # project onto sum(y*alpha)=0
        alpha = np.clip(alpha, 0, C)
    return alpha

C = 1.0
alpha = svm_dual(X, y, C)

assert abs(y @ alpha) < 1e-2                       # equality constraint

n_zero = int(np.sum(alpha < 1e-4))
n_margin = int(np.sum((alpha > 1e-4) & (alpha < C - 1e-4)))
n_bound = int(np.sum(alpha > C - 1e-4))
print(f"buckets: zero={n_zero}, margin={n_margin}, bound={n_bound}")
assert n_zero + n_margin + n_bound == len(y)      # exact partition

w = (alpha * y) @ X
sv = alpha > 1e-4
b = np.mean(y[sv] - X[sv] @ w)
acc = np.mean(np.sign(X @ w + b) == y)
print(f"accuracy: {acc:.3f}")
assert acc > 0.85

The next lesson exploits the dual's inner-product structure to lift the SVM into nonlinear feature spaces via the kernel trick.