Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 38 · Applications in Machine Learning

Support Vector Machines and Duality

Train a linear SVM two ways: subgradient descent on the hinge loss and the dual QP. Verify strong duality numerically and identify the support vectors.

A support vector machine (SVM) is a classifier that separates two classes with the widest possible "street". It is a showcase of nearly everything in this track: a convex QP, a non-smooth loss, a Lagrangian dual, KKT conditions and complementary slackness. The idea is simple. Among all separating lines, pick the one with the largest margin, the gap between the line and the nearest points.

The soft-margin primal

Labels are y_i ∈ {−1, +1}. The classifier is sign(wᵀx + b). The distance from the boundary to the nearest points on each side is 1/‖w‖ when the margin constraints are y_i(wᵀx_i + b) ≥ 1. Maximizing the margin means minimizing ½‖w‖². Real data often overlap, so we allow violations with slack ξ_i ≥ 0 and charge a price C for them:

Text
minimize    ½ ‖w‖² + C Σ ξ_i
subject to  y_i (wᵀx_i + b) ≥ 1 − ξ_i,    ξ_i ≥ 0

This is a convex QP. Eliminating ξ_i = max(0, 1 − y_i(wᵀx_i + b)) gives an unconstrained form with the hinge loss:

Text
minimize    ½ ‖w‖² + C Σ max(0, 1 − y_i (wᵀx_i + b))

The hinge loss is zero for points that are correct with margin at least 1, and grows linearly otherwise. It is convex but has a kink at 1, so we use subgradients: at a kink, any slope between the two sides is a valid subgradient.

Training with subgradient descent

A subgradient of the objective is: w − C Σ_{i : margin_i < 1} y_i x_i for w, and −C Σ_{i : margin_i < 1} y_i for b. With a decaying step η_k = η₀ / √k, subgradient descent approaches the optimum slowly. This is a basic approach; dedicated solvers (such as Pegasos or dual coordinate descent) are faster.

Python Subgradient descent on the hinge loss

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The dual and support vectors

Introduce multipliers α_i ≥ 0 for the margin constraints and μ_i ≥ 0 for ξ_i ≥ 0. Setting derivatives of the Lagrangian to zero gives:

Text
w = Σ α_i y_i x_i        Σ α_i y_i = 0        0 ≤ α_i ≤ C

Substituting back yields the dual problem, a QP in α only:

Text
maximize    Σ α_i − ½ Σ_i Σ_j α_i α_j y_i y_j (x_iᵀ x_j)
subject to  0 ≤ α_i ≤ C,    Σ α_i y_i = 0

Complementary slackness gives the geometry:

α_i Meaning of point i
α_i = 0 Correct with margin more than 1: does not affect the solution
0 < α_i < C Exactly on the margin (y_i(wᵀx_i + b) = 1)
α_i = C Inside the margin or misclassified (ξ_i > 0)

The points with α_i > 0 are the support vectors: the solution w is a combination of them alone. Also, the dual depends on the data only through inner products x_iᵀx_j. Replace them by a kernel function k(x_i, x_j) and you get nonlinear classifiers without changing the algorithm.

Verifying strong duality numerically

We solve the dual with SLSQP on the same data, recover w and b, and compare the dual value with the primal value. Slater's condition holds (the problem is a QP with feasible affine constraints), so the two values should be equal.

Python Solve the dual QP and compare with the primal

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two values agree up to numerical error, which is strong duality at work. The counts show that most points have α = 0: only the support vectors determine the classifier. If the gap you see is slightly above zero, the solver stopped a little early; tighter tolerances shrink it.

The subgradient solution from the first example should land close to this dual solution but not exactly on it, since subgradient methods converge slowly. This is the usual trade-off: simple first-order methods are easy to write; exact QP solvers are accurate.

Choosing C

  • Large C: violations are expensive, the margin is narrow and the model fits the training data tightly. Risk: overfitting.
  • Small C: violations are cheap, the margin is wide, the model is simpler. Risk: underfitting.
  • Pick C by cross-validation, like λ in ridge or lasso (here C plays the role of 1/λ).

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the hinge loss of a point with margin y(wᵀx + b) = 0.3?

    max(0, 1 − 0.3) = 0.7. The point is correct but inside the margin, so it is penalized.
  2. 2. Which points are support vectors?

    Complementary slackness gives α_i = 0 for points strictly outside the margin, so they do not affect w.
  3. 3. Why is strong duality guaranteed for the SVM QP?

    For convex problems with affine inequality constraints, feasibility is enough, so the primal and dual optima are equal.
  4. 4. What does a larger C do?

    C multiplies the slack cost, so large C makes the model fit training points more strictly.

Summary

  • The soft-margin SVM minimizes ½‖w‖² + C Σ max(0, 1 − y_i(wᵀx_i + b)), a convex QP with a non-smooth hinge loss.
  • The dual is a QP in α with box constraints and one equality; w = Σ α_i y_i x_i.
  • Complementary slackness identifies support vectors (α_i > 0); the dual uses only inner products, which enables kernels.
  • Primal and dual values coincide (strong duality); subgradient methods are simple but slow, QP solvers accurate.

Next: Practice Set: Duality and KKT