Support Vector Machines and Maximum Margin

A linear classifier partitions input space $\mathbb{R}^d$ with a hyperplane $\{x : w^\top x + b = 0\}$, predicting $\hat{y} = \text{sign}(w^\top x + b)$. For linearly separable training data $\{(x_i, y_i)\}_{i=1}^n$ with $y_i \in \{-1, +1\}$, infinitely many hyperplanes achieve zero training error. The geometric margin of a hyperplane with respect to a point $x_i$ is the signed perpendicular distance from $x_i$ to the hyperplane,

The margin of the hyperplane with respect to the whole dataset is $\gamma = \min_i \gamma_i$, the distance to the closest point of either class. The maximum margin classifier is the hyperplane $(w, b)$ that maximizes $\gamma$ subject to every point being correctly classified, i.e. $\gamma_i \ge \gamma$ for all $i$. This optimization has a scaling redundancy: multiplying $w$ and $b$ by any positive constant leaves the hyperplane and every $\gamma_i$ unchanged, since both numerator and denominator scale together. We remove this redundancy with a canonical scaling: choose the scale of $(w, b)$ so that the closest points satisfy $y_i(w^\top x_i + b) = 1$ exactly. Under this normalization the margin is simply $\gamma = 1/\|w\|$, and the constraint "every point classified correctly with margin at least $\gamma$" becomes the clean linear constraint

Maximizing $1/\|w\|$ is the same as minimizing $\|w\|$, or more conveniently for calculus, minimizing $\frac{1}{2}\|w\|^2$. This is the hard-margin SVM primal problem:

It is called "hard margin" because it requires perfect linear separability, zero tolerance for violation. The objective is a convex quadratic function and the constraints are linear (affine) in $(w, b)$, so this is a convex quadratic program: a well-understood class of problems with a unique global minimum whenever the feasible region is nonempty, and efficient polynomial-time algorithms to solve it.

Step 1 — formalize as a QP. As derived above, the primal is a convex QP in $d+1$ variables ($w \in \mathbb{R}^d$, $b \in \mathbb{R}$) with $n$ linear inequality constraints. Any general-purpose QP solver can, in principle, solve this directly.

Step 2 — form the Lagrangian. Introduce one multiplier $\alpha_i \ge 0$ per constraint:

Step 3 — derive the dual by stationarity. At the optimum, the gradient of $L$ with respect to the primal variables vanishes:

Substituting these back into $L$ eliminates $w$ and $b$, giving the dual problem, a QP purely in $\alpha$:

The dual depends on the data only through inner products $x_i^\top x_j$ — the observation that later enables the kernel trick.

Step 4 — solve the dual, identify support vectors. The dual has $n$ variables and box-type nonnegativity constraints, which is often easier to solve numerically than the primal, especially via decomposition methods (e.g. SMO) that update a small subset of $\alpha_i$ at a time. At the solution, KKT complementary slackness requires

So either $\alpha_i = 0$, or the constraint is tight: $y_i(w^\top x_i + b) = 1$, meaning $x_i$ sits exactly on the margin boundary. Points with $\alpha_i = 0$ contribute nothing to $w = \sum_i \alpha_i y_i x_i$. The points with $\alpha_i > 0$ are the support vectors — they alone determine the separating hyperplane.

Step 5 — recover $w$ and $b$. Compute $w$ from the formula above, then recover $b$ using any support vector $x_s$ (or averaging over all of them for numerical stability):

Step 6 — classify new points. For a new input $x$, predict

``` Algorithm HardMarginSVM(X, y): Input: data points X = {x_1, ..., x_n}, labels y_i in {-1, +1} Output: weight vector w, bias b, support vector set SV

# Step 1: build and solve the dual QP maximize sum_i alpha_i

• 0.5 sum_i sum_j alpha_i alpha_j y_i y_j * dot(x_i, x_j)

subject to alpha_i >= 0 for all i sum_i alpha_i * y_i == 0 alpha = SolveQP(...) # e.g. via SMO or an interior-point QP solver

# Step 2: recover primal solution w = sum_i alpha_i y_i x_i SV = { i : alpha_i > tolerance } # support vectors

# Step 3: recover bias using any (or all) support vectors b = average over i in SV of ( y_i - dot(w, x_i) ) return w, b, SV Function Predict(x, w, b): return sign( dot(w, x) + b ) ``` The pseudocode's key correctness point is in the recovery step: because complementary slackness forces $y_i(w^\top x_i + b) = 1$ exactly for every support vector, any support vector gives the same $b$ up to solver numerical error, and averaging over all of them reduces that error.

Space complexity. Storing the data is $O(nd)$. The dual QP requires the Gram matrix $K_{ij} = x_i^\top x_j$, an $n \times n$ matrix, costing $O(n^2)$ space if materialized in full (many practical solvers avoid storing it fully, computing entries on demand or caching a working subset).

Time complexity. Computing the full Gram matrix costs $O(n^2 d)$. Solving a general QP with $n$ variables via interior-point methods costs roughly $O(n^3)$ in the worst case (dominated by linear algebra on an $n \times n$ system per iteration, with $O(\log(1/\epsilon))$ iterations for $\epsilon$-accuracy). In practice, specialized decomposition algorithms like Sequential Minimal Optimization (SMO) update two $\alpha_i$ at a time in closed form, avoiding any large matrix factorization; empirically this scales closer to $O(n^2)$ to $O(n^3)$ depending on how many points end up as support vectors and how tightly the classes are packed, but no better worst-case polynomial bound is generally guaranteed for QP solvers on adversarial inputs. Prediction, after training, costs $O(|SV| \cdot d)$ per test point, where $|SV| \le n$ is the number of support vectors — often much smaller than $n$, which is why sparsity matters.

Why the QP is the right formulation (correctness of the reduction). We must justify that "maximize the margin subject to correct classification" really is equivalent to the QP written above. Fix any hyperplane through the origin's normal direction $w/\|w\|$. Rescaling $(w,b)$ by a positive constant does not change the hyperplane or the margin $\gamma_i = y_i(w^\top x_i + b)/\|w\|$, since both numerator and denominator scale identically — this is precisely the freedom used to fix the canonical scale $\min_i y_i(w^\top x_i+b) = 1$. Once that scale is fixed, $\gamma = \min_i \gamma_i = 1/\|w\|$ exactly, so maximizing $\gamma$ is equivalent to minimizing $\|w\|$, subject to the constraint that no point violates the unit-margin condition. This establishes the primal QP is not an approximation of the margin-maximization problem — it is the margin-maximization problem, after a valid reparametrization.

Why strong duality holds (correctness of the dual). The primal is a convex QP (convex quadratic objective, affine constraints), and it is strictly feasible whenever the data is linearly separable (Slater's condition holds trivially since the constraints are affine, not just convex). Convexity plus Slater's condition guarantees zero duality gap: the primal optimum equals the dual optimum, and any point satisfying the KKT conditions is simultaneously primal- and dual-optimal. This is why solving the dual — often computationally more convenient because its constraints are simpler (nonnegativity plus one linear equality, versus $n$ general linear inequalities in the primal) — yields the exact same classifier as solving the primal directly.

Why the solution is unique. The primal objective $\frac{1}{2}\|w\|^2$ is strictly convex in $w$ (its Hessian is the identity matrix, positive definite), so if a feasible solution exists, the optimal $w^*$ is unique. The optimal $b^*$ is also uniquely pinned down by the requirement that at least one point from each class touch the margin boundary (this follows from the KKT stationarity condition $\sum_i \alpha_i y_i = 0$ forcing support vectors from both classes to be active at the optimum, assuming both classes are nonempty). This uniqueness is a genuine advantage over the perceptron, whose final hyperplane depends on initialization and the order examples are visited.

Honest tradeoffs. The hard-margin formulation is only well-defined when the data is linearly separable — if even one point cannot be separated, the feasible region is empty and the QP has no solution. This is a serious practical limitation, motivating the soft-margin relaxation. Even when separable, the hard-margin solution can be extremely sensitive to a single noisy or mislabeled point near the boundary, since that point may become the sole determinant of a razor-thin margin. Nonlinear class boundaries also cannot be captured by a linear hyperplane at all — a limitation removed by mapping into higher-dimensional feature spaces via kernels.

Consider four 2D points, a small enough dataset to solve by hand and verify against the geometric intuition.

By inspection, the classes are separated roughly along the direction $(1,1)$. Guess that the optimal boundary is orthogonal to $w \propto (1,1)$. Try the canonical form $w = (a, a)$ for some $a > 0$, $b$ to be determined. The candidate support vectors — the closest points across the gap — appear to be $x_3 = (0,0)$ (label $-1$) and $x_1=(2,2)$ (label $+1$), with $x_2, x_4$ farther from a boundary in this direction. Impose the canonical scaling equalities on the two candidate support vectors:

Solving: $4a - 1 = 1 \implies a = 0.5$. So $w = (0.5, 0.5)$, $b = -1$.

Check all four constraints $y_i(w^\top x_i + b) \ge 1$:

The initial guess was wrong: $x_4$ violates the margin constraint, so $(a=0.5, b=-1)$ is not feasible, meaning it cannot be optimal. This is instructive: $x_2$ turned out tight too, so the true support vectors likely include $x_4$ and $x_2$, not $x_1$ and $x_3$. Redo with $x_2=(3,1)$ (label $+1$) and $x_4=(1,0)$ (label $-1$) as the binding pair, again with $w=(a,a)$:

Subtracting: $3a = 2 \implies a = 2/3$, then $b = -1 - 2/3 = -5/3$. So $w = (2/3, 2/3)$, $b = -5/3$. Verify all four constraints:

All four constraints now hold with equality or slack ($\ge 1$ in every row). Both $x_1$ and $x_2$ are tight on the $+1$ side; only $x_4$ is tight on the $-1$ side — three support vectors total, and $x_3$ (with slack $1.67 > 1$) is not a support vector, correctly reflecting that it sits well inside its class region. The margin is $\gamma = 1/\|w\| = 1/(2\sqrt2/3) = 3/(2\sqrt2) \approx 1.06$. This trace shows why guessing support vectors from a picture can mislead you, and why the KKT feasibility check is not optional — it is the actual certificate of correctness for a candidate solution.

The maximum-margin idea traces back to Ronald Fisher's and Frank Rosenblatt's era of linear discriminants, but its rigorous convex-optimization formulation and the "support vector" terminology originate with Vladimir Vapnik and collaborators, developed alongside the broader statistical learning theory that explains why margin maximization improves generalization.

Support vector machines were, for roughly fifteen years, the default high-performance classifier for tabular and moderate-dimensional data before deep learning displaced them for perceptual tasks. They remain heavily used today in domains where the number of features can be large relative to the number of samples, or where interpretability and theoretical guarantees matter — bioinformatics (gene expression classification), text categorization, and any pipeline emphasizing convex, reproducible optimization over stochastic non-convex training. Production machine learning libraries such as scikit-learn's `SVC`, and specialized solvers like LIBSVM and LIBLINEAR, implement exactly the dual QP and SMO-style decomposition described here, and remain standard baselines against which newer classifiers are benchmarked. The margin-maximization principle itself resurfaces well beyond classic SVMs: margin-based generalization bounds inform the analysis of deep neural network robustness, and the geometric idea of maximizing distance to a decision boundary underlies adversarial robustness research, where practitioners explicitly try to widen the margin of a neural classifier against adversarial perturbations. The dual formulation's dependence on inner products alone is the direct ancestor of every kernel method used today, from Gaussian process regression to kernelized PCA.

Ask the tutor: How does introducing slack variables in the soft-margin SVM change the dual problem, and why does that let us handle non-separable and noisy data gracefully?