Support vector machines combine a convex margin loss with norm regularization. Their geometry is separation by a maximum-margin hyperplane in a feature space.
Hard-margin geometry
When the data are linearly separable, the SVM chooses the separating hyperplane with largest geometric margin.
Definition. For \(y_i\in\{-1,1\}\), the hard-margin problem is \[ \min_{w,b}\frac12\|w\|_2^2 \quad\text{subject to}\quad y_i(\langle w,x_i\rangle+b)\ge1,\ i=1,\ldots,n. \] The geometric margin is \(1/\|w\|_2\).
Proposition. Minimizing \(\|w\|_2\) under the normalized constraints maximizes the minimum geometric margin.
Proof. The constraints force the functional margin to be at least \(1\). The corresponding geometric margin is at least \(1/\|w\|_2\). Rescaling \((w,b)\) changes functional margins and \(\|w\|\) by the same factor, so the normalization is harmless and minimizing \(\|w\|\) maximizes the normalized geometric margin.
Soft-margin objective
Nonseparable data require slack or, equivalently, hinge loss.
Definition. The soft-margin SVM solves \[ \min_{w,b}\frac1n\sum_{i=1}^n(1-y_i(\langle w,x_i\rangle+b))_+ +\lambda\|w\|_2^2. \]
Remark. The hinge loss is zero beyond margin \(1\), linear for margin violations, and convex. This shape makes only some observations active in the optimum.
Dual problem and support vectors
The dual reveals the kernelization and the role of support vectors.
Theorem. For the hard-margin linear SVM, the dual is \[ \max_{\alpha_i\ge0}\sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\langle x_i,x_j\rangle \quad\text{subject to}\quad \sum_i\alpha_iy_i=0. \] At optimum, \(w=\sum_i\alpha_iy_ix_i\).
Proof. Form the Lagrangian \[ L(w,b,\alpha)=\frac12\|w\|^2-\sum_i\alpha_i\{y_i(\langle w,x_i\rangle+b)-1\}. \] Stationarity in \(w\) gives \(w=\sum_i\alpha_iy_ix_i\); stationarity in \(b\) gives \(\sum_i\alpha_iy_i=0\). Substituting these conditions into the Lagrangian gives the dual objective.
Generalization through norm and margin
The SVM bound is a margin bound for a norm-bounded linear class.
Proposition. If \(\|x\|_2\le R\) and \(\|w\|_2\le B\), the Rademacher complexity of linear scores \(x\mapsto\langle w,x\rangle\) is at most \(BR/\sqrt n\).
Proof. By the linear-class formula, \[ \widehat{\mathfrak R}_n\le \frac{B}{n}\mathbb E_\varepsilon\left\|\sum_i\varepsilon_ix_i\right\|_2. \] Jensen's inequality and independence of the signs give \[ \mathbb E_\varepsilon\left\|\sum_i\varepsilon_ix_i\right\|_2 \le \left(\sum_i\|x_i\|_2^2\right)^{1/2}\le R\sqrt n. \]
Primal soft-margin formulation
Proposition. The constrained problem \[ \min_{w,b,\xi\ge0}\frac12\|w\|_2^2+C\sum_{i=1}^n\xi_i \quad\text{subject to}\quad y_i(w^\top x_i+b)\ge1-\xi_i \] is equivalent to \[ \min_{w,b}\frac12\|w\|_2^2+ C\sum_{i=1}^n(1-y_i(w^\top x_i+b))_+. \]
Proof. For fixed \(w,b\), feasibility requires \(\xi_i\ge\max\{0,1-y_i(w^\top x_i+b)\}\). Since the objective increases in every \(\xi_i\), each slack is set to this smallest value.
Soft-margin dual and KKT structure
Theorem. The soft-margin dual is \[ \max_{\alpha\in\mathbb R^n} \mathbf1^\top\alpha-\frac12\alpha^\top Q\alpha \quad\text{subject to}\quad 0\le\alpha_i\le C,\quad y^\top\alpha=0, \] where \(Q_{ij}=y_iy_jx_i^\top x_j\). At any primal-dual optimum, \[ w=\sum_i\alpha_iy_ix_i, \] and \[ \begin{cases} \alpha_i=0&\Rightarrow y_if(x_i)\ge1,\\ 0<\alpha_i<C&\Rightarrow y_if(x_i)=1,\\ \alpha_i=C&\Rightarrow y_if(x_i)\le1. \end{cases} \]
Proof. Introduce multipliers \(\alpha_i\ge0\) for the margin constraints and \(\mu_i\ge0\) for \(\xi_i\ge0\). Stationarity gives \(w=\sum_i\alpha_iy_ix_i\), \(y^\top\alpha=0\), and \(C-\alpha_i-\mu_i=0\), hence \(0\le\alpha_i\le C\). Substitution yields the dual. Complementary slackness, \(\alpha_i\{y_if(x_i)-1+\xi_i\}=0\) and \(\mu_i\xi_i=0\), gives the three cases.
Only observations with \(\alpha_i>0\) enter the fitted normal vector; these are the support vectors. Points strictly beyond margin one have \(\alpha_i=0\) and can move slightly without changing the solution.
Kernelized SVM
Corollary. Replacing \(x_i^\top x_j\) in the dual by any positive-definite kernel \(K(x_i,x_j)\) produces the RKHS classifier \[ f(x)=\sum_{i=1}^n\alpha_iy_iK(x_i,x)+b. \]
Proof. In the feature space \(K(x,x')=\langle\Phi(x),\Phi(x')\rangle\), the preceding dual derivation is unchanged with \(x_i\) replaced by \(\Phi(x_i)\). The stationarity equation becomes \(w=\sum_i\alpha_iy_i\Phi(x_i)\), and evaluation against \(\Phi(x)\) gives the formula.
Hard-margin uniqueness
Proposition. If the hard-margin problem is feasible, its normal vector \(w\) is unique, although the intercept \(b\) need not be unique.
Proof. The feasible set in \((w,b)\) is convex and the objective is strictly convex in \(w\). If two optimal solutions had distinct \(w_1,w_2\), their midpoint would be feasible and would have strictly smaller squared norm, contradicting optimality. Strict convexity does not involve \(b\), so different intercepts can occur in degenerate configurations.
Population consistency of hinge regularization
Theorem. Let \(K\) be universal on a compact \(\mathcal X\), let \(\lambda_n\downarrow0\), and suppose \(n\lambda_n\to\infty\). Under bounded-kernel and measurability conditions, an RKHS hinge-loss SVM is Bayes-risk consistent: \[ R_{01}(\widehat f_n)-R_{01}^*\xrightarrow{P}0. \]
Proof outline. Universality makes the infimum of population hinge risk over the RKHS approach the unrestricted hinge Bayes risk as the norm bound expands. The regularizer implies \(\|\widehat f_n\|_{\mathcal H_K}=O_P(\lambda_n^{-1/2})\). Rademacher complexity of that ball is \(O_P\{(n\lambda_n)^{-1/2}\}\), which tends to zero and controls estimation error. Vanishing \(\lambda_n\) removes regularization bias. Hinge calibration then converts surrogate-risk consistency to zero-one consistency.
Leave-one-out support-vector bound
Proposition. In a separable hard-margin problem with a unique classifier and no degeneracies, a training point that is not a support vector cannot become a leave-one-out error when removed. Consequently, the leave-one-out error count is at most the number of support vectors.
Proof. Removing a non-support vector leaves all active constraints and the optimum unchanged, because its constraint is strict and its dual coefficient is zero. The unchanged classifier still labels that omitted point correctly. Therefore only support vectors can contribute leave-one-out errors.
Multiclass extensions
One-versus-rest and one-versus-one schemes reduce multiclass learning to binary SVMs but can produce incompatible scores. A direct Crammer-Singer formulation solves \[ \min_{w_1,\ldots,w_K}\frac\lambda2\sum_k\|w_k\|^2+ \frac1n\sum_i \max_{k\ne y_i}\{1+w_k^\top x_i-w_{y_i}^\top x_i\}_+. \] Its loss is convex and upper-bounds multiclass zero-one error. Calibration, however, depends on the precise multiclass surrogate and cannot be inferred solely from convexity.
What the margin parameter controls
The SVM tuning constant simultaneously governs norm, empirical hinge error, and the set of support vectors. A very large \(C\) prioritizes fitting margin violations and can be unstable under label noise; a small \(C\) permits violations and shrinks the RKHS norm. Proper tuning balances approximation, estimation, and robustness rather than seeking the largest training margin in isolation.