Support Vector Machines and Support Vector Regression

A classifier can fit every training label correctly and still fail to minimize the SVM objective. That happens in the toy example below: our fixed-step implementation agrees with the reference SVC on all training labels, while the reference fit has a lower value of the same hinge-loss objective. The scratch algorithm uses a fixed learning rate and a finite update budget without a convergence certificate. The Support Vector Machine (SVM) gives us an objective for assessing that optimization gap. For linearly separable data, its hard-margin form chooses the separating hyperplane with the widest buffer to the nearest training points. Its soft-margin form allows violations of that buffer in exchange for a penalty. We will derive both formulations and use the dual coefficients to identify which training points contribute to the fitted decision function.

The dual formulation gives a precise notion of sparsity. In a soft-margin SVM, training examples with zero dual coefficient do not contribute to the decision function. Only points on or inside the margin can have nonzero coefficients, although some such coefficients may also be zero. This differs from Lasso's sparsity in input-feature coefficients, and it can be useful computationally when the support set is small. A single formula, hinge loss plus an L2 penalty, connects the geometric story of maximum margins to regularized empirical risk minimization.

The same machinery extends to regression. Support Vector Regression (SVR) uses an $\varepsilon$-insensitive loss. Residuals with magnitude at most $\varepsilon$ incur no data-fit loss, while excess residual magnitude is penalized linearly. Points strictly inside the tube have zero dual coefficients, which can produce a sparse model. Compared with squared loss, linear growth limits the influence of large response residuals, although it does not protect against every outlier or guarantee a small support set.

We work through margins, support vectors, the hinge loss, and the soft-margin Lagrangian, then connect valid kernels and ε-insensitive regression to executable examples. The margin and dual derivations spell out the Lagrangian steps.

The maximum-margin principle gives SVMs a clean, geometric objective. With a valid positive-semidefinite kernel, the standard SVM objective is convex: every local minimum is global. Suitable solvers can approach a global optimum, but their stopping tolerances, update rules, and convergence conditions still matter. Support vectors identify the examples that contribute to the decision function, which can make the fit compact and useful to inspect. The support set can also contain most or all of the training data, and convexity alone does not make every fitted parameter unique.

The kernel trick extends the same dual optimization framework to nonlinear boundaries by replacing inner products with a valid kernel. A real-valued kernel must be symmetric and produce a positive-semidefinite Gram matrix for every finite collection of inputs; it then corresponds to inner products in a feature space. Support Vector Regression uses the same representation with an $\varepsilon$-insensitive loss. That loss ignores residuals within the tube and grows linearly outside it, reducing the influence of large response residuals relative to squared loss. Its support set need not be small, and whether it predicts better than OLS depends on the data and must be checked on validation data.

Exact nonlinear kernel SVMs can become expensive as the training set grows. Materializing the full Gram matrix requires $O(n^2)$ storage, while decomposition solvers can compute entries on demand and keep a bounded cache. Training time depends on the kernel, feature dimension, data, cache, solver, and stopping tolerance; a single quadratic or cubic rate does not describe every SVM. Large linear problems can instead be fitted without a Gram matrix. Feature scales also affect the regularization and kernel geometry, so choose a meaningful scale for the inputs; standardization is a useful default when units differ, as discussed in Standardization.

SVM decision scores are not calibrated probabilities. In a binary model the score is $f(\mathbf{x})$; with a nonzero normal vector, divide by its feature-space norm to obtain signed distance to the hyperplane. Procedures such as Platt scaling or isotonic regression can estimate probabilities from scores, adding estimation work whose quality must be checked. Kernel settings and the penalty $C$ affect the fit, so compare relevant choices through hyperparameter search. With imbalanced classes, unweighted summed loss gives more total weight to the more numerous class; class weights or resampling within training folds can change that tradeoff.

We start with a question that is more subtle than it first appears: among all hyperplanes that separate two classes, which one should we trust? A hyperplane is specified by a normal vector $\mathbf{w} \in \mathbb{R}^p$ and a bias $b \in \mathbb{R}$, and the signed decision value is

$$f(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b.$$

where:

• $\mathbf{w}$: the normal vector of the hyperplane, which fixes its orientation
• $\mathbf{x}$: the input point being classified
• $b$: the bias term, which shifts the hyperplane away from the origin
• $f(\mathbf{x})$: the signed decision value, positive on one side of the hyperplane and negative on the other

This tells us which side of the boundary a point lies on; away from a zero score, the predicted signed label is $\operatorname{sign}(f(\mathbf{x}))$. For a nonzero normal vector, multiplying $\mathbf{w}$ and $b$ by a positive constant preserves both that prediction and the geometric boundary. Infinitely many boundaries may separate a dataset. In the separable hard-margin setting, the SVM selects the boundary with the widest empty buffer. Points with nonzero dual coefficients are called support vectors; in the hard-margin optimum they lie on the buffer's edge.

The perpendicular distance of a point $\mathbf{x}$ to the decision hyperplane $f(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b = 0$ is

$$\frac{|\mathbf{w}^\top \mathbf{x} + b|}{\|\mathbf{w}\|},$$

where:

• $\mathbf{w}$: the normal vector of the hyperplane
• $\mathbf{x}$: the query point whose distance we measure
• $b$: the bias term
• $\|\mathbf{w}\| = \sqrt{\mathbf{w}^\top \mathbf{w}}$: the Euclidean length of the normal vector

This expression exposes an important scaling issue: multiplying $\mathbf{w}$ and $b$ by the same positive constant leaves the hyperplane and every perpendicular distance unchanged, because the numerator and denominator scale together. The unnormalized decision values $f(\mathbf{x})$ and functional margins $y_i f(\mathbf{x}_i)$ do scale by that constant. The length $\|\mathbf{w}\|$ therefore becomes a measure of margin width only after we fix the functional-margin scale. Here $\|\mathbf{w}\| = \sqrt{\mathbf{w}^\top \mathbf{w}}$ is the Euclidean length of the normal vector; in the canonical hard-margin scale, the two margin hyperplanes have separation $2/\|\mathbf{w}\|$.

For a separating hyperplane, we can fix the scale so that the smallest functional margin is one. At the maximum-margin solution with both classes present, the bias centers the corridor between the nearest opposite-class projections, so the two supporting hyperplanes are $f(\mathbf{x})=1$ and $f(\mathbf{x})=-1$. Their perpendicular separation is $2/\|\mathbf{w}\|$, with each one a distance $1/\|\mathbf{w}\|$ from the decision hyperplane. Maximizing this width is equivalent to minimizing $\|\mathbf{w}\|$, or $\tfrac12\|\mathbf{w}\|^2$. The hard-margin problem therefore asks for the smallest weight norm subject to every training point lying on or beyond its class's margin hyperplane:

$$\begin{aligned} \min_{\mathbf{w},\, b} \;& \tfrac{1}{2}\|\mathbf{w}\|^2 \\ \text{s.t.} \;& y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1, \quad i = 1, \ldots, n. \end{aligned}$$

where:

• $\tfrac{1}{2}\|\mathbf{w}\|^2$: the objective being minimized, equivalent to maximizing the margin $2/\|\mathbf{w}\|$
• $y_i \in \{-1, +1\}$: the label of the $i$-th training example
• $\mathbf{x}_i$: the $i$-th training input
• $\mathbf{w}^\top \mathbf{x}_i + b$: the signed decision value of the $i$-th example
• $y_i (\mathbf{w}^\top \mathbf{x}_i + b) \geq 1$: the constraint that every point lies on or beyond its margin boundary

The quantity

$$m_i = y_i(\mathbf{w}^\top \mathbf{x}_i + b)$$

is the functional margin of the $i$-th example. In the canonical hard-margin optimum, support vectors have $m_i=1$, while points with $m_i>1$ lie beyond the corridor. In a soft-margin fit, $m_i<1$ indicates a margin violation, and support vectors can lie inside the margin or even be misclassified. The dual coefficient, rather than nearness alone, determines whether a point appears in the fitted decision function.

If the classes are linearly separable, the hard-margin constraints are feasible. If they are not, no hyperplane can keep the corridor empty, and insisting on the hard constraint makes the optimization problem infeasible. The SVM responds by turning the violation into a penalty. The hinge loss measures exactly how much a point fails the margin requirement:

$$L_\text{hinge}(m_i) = \max\bigl(0,\, 1 - m_i\bigr).$$

where:

• $m_i = y_i(\mathbf{w}^\top \mathbf{x}_i + b)$: the functional margin of the $i$-th training example
• $1 - m_i$: the amount by which the functional margin falls short of 1

The maximum with zero clamps the loss at zero, so points with $m_i \geq 1$ contribute no penalty and points that intrude into the margin or are misclassified incur a linear cost.

The hinge loss is zero once the functional margin reaches 1, and it grows linearly as points cross into the corridor or onto the wrong side. Penalizing these margin violations gives the soft-margin regularized empirical-risk objective:

$$\min_{\mathbf{w},\, b} \; \tfrac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^n \max\!\bigl(0,\, 1 - y_i(\mathbf{w}^\top \mathbf{x}_i + b)\bigr).$$

where:

• $\tfrac{1}{2}\|\mathbf{w}\|^2$: the margin term, which shrinks as the margin widens
• $C$: the penalty parameter controlling the exchange rate between margin width and training error
• $\max\!\bigl(0,\, 1 - y_i(\mathbf{w}^\top \mathbf{x}_i + b)\bigr)$: the hinge loss of the $i$-th example
• $\sum_{i=1}^n$: the sum over all training examples

The constant $C>0$ sets the exchange rate between weight norm and training hinge loss. On a fixed dataset with the same kernel and penalty convention, increasing $C$ cannot increase the optimized total hinge loss, while the optimized squared weight norm cannot decrease. Either quantity can stay unchanged over a range of $C$, and individual residuals or classification errors need not move monotonically. The hinge form needs no separate slack variables and can be optimized by subgradient methods. Because the loss has a kink at margin one, the following expressions give one valid subgradient of $J$:

$$\nabla_{\mathbf{w}} J = \mathbf{w} - C \sum_{i \in \mathcal{A}} y_i \mathbf{x}_i, \qquad \frac{\partial J}{\partial b} = - C \sum_{i \in \mathcal{A}} y_i,$$

where:

• $J(\mathbf{w}, b) = \tfrac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^n \max\!\bigl(0, 1 - y_i(\mathbf{w}^\top \mathbf{x}_i + b)\bigr)$: the regularized hinge-loss objective being minimized
• $\mathcal{A} = \{i : 1 - y_i(\mathbf{w}^\top \mathbf{x}_i + b) > 0\}$: the set of points currently violating the margin, i.e. those with active hinge loss
• $C$: the exchange rate between margin width and training error

These expressions choose the zero hinge subgradient at points with $m_i=1$. At such a kink, any multiple $-\theta_i y_i\mathbf{x}_i$ with $\theta_i\in[0,1]$ is allowed for the weight part of the hinge term, with the corresponding $-\theta_i y_i$ for the bias. Strict margin violators have the full hinge contribution, while points with $m_i>1$ have none. This current strict-violation set is not the dual support-vector set: an optimal point on the margin can have nonzero dual weight even though its hinge loss is zero.

The classical soft-margin formulation is the constrained version of the regularized empirical-risk objective above. Writing $\xi_i = \max\bigl(0, 1 - y_i(\mathbf{w}^\top \mathbf{x}_i + b)\bigr)$ as an explicit variable and minimizing $\tfrac{1}{2}\|\mathbf{w}\|^2 + C \sum_i \xi_i$ over $\mathbf{w}$, $b$, and $\xi$ subject to the relaxed margin constraints gives the same optimum as the hinge-loss problem. At the optimum, each slack records a functional-margin shortfall; a correctly classified point inside the margin can also have positive slack:

$$\begin{aligned} \min_{\mathbf{w},\, b,\, \xi} \;& \tfrac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \\ \text{s.t.} \;& y_i(\mathbf{w}^\top \mathbf{x}_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0. \end{aligned}$$

where:

• $\xi_i \geq 0$: the slack for the $i$-th example, measuring how far it violates the margin
• $\tfrac{1}{2}\|\mathbf{w}\|^2$: the margin term
• $C \sum_{i=1}^n \xi_i$: the total violation penalty, scaled by $C$
• $y_i(\mathbf{w}^\top \mathbf{x}_i + b) \geq 1 - \xi_i$: the relaxed margin constraint, allowing the $i$-th example to fall short of the margin by at most $\xi_i$

At any optimum, the slacks are pinned down by the KKT conditions:

$$\xi_i = \max\bigl(0, 1 - y_i(\mathbf{w}^\top \mathbf{x}_i + b)\bigr).$$

where:

• $\xi_i$: the optimal slack for the $i$-th example
• $m_i = y_i(\mathbf{w}^\top \mathbf{x}_i + b)$: the functional margin of the $i$-th example
• $1 - m_i$: the amount by which the functional margin falls short of 1

This is why the slack formulation and the hinge-loss formulation describe the same learning problem even though they look different. In the constrained problem the slacks are auxiliary variables, but the KKT conditions pin each one to the value the hinge loss would assign it, so eliminating the slacks recovers the regularized empirical-risk objective exactly. The slack view is valuable because it reveals the constrained optimization structure and prepares us for the Lagrangian, which is where kernels enter.

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

$$\mathcal{L}(\mathbf{w}, b, \xi, \alpha, \mu) = \tfrac{1}{2}\|\mathbf{w}\|^2 + C\sum_i \xi_i - \sum_i \alpha_i\!\left[y_i(\mathbf{w}^\top \mathbf{x}_i + b) - 1 + \xi_i\right] - \sum_i \mu_i \xi_i.$$

where:

• $\mathbf{w}, b$: the primal weight vector and bias
• $\xi_i \geq 0$: the slack for the $i$-th example, measuring how far it violates the margin
• $\alpha_i \geq 0$: the Lagrange multiplier for the $i$-th margin constraint
• $\mu_i \geq 0$: the Lagrange multiplier for the nonnegativity constraint $\xi_i \geq 0$

Setting derivatives to zero gives three structural facts. First, $\partial \mathcal{L} / \partial \mathbf{w} = 0$ yields the weight as a linear combination of training points,

$$\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i.$$

where:

• $\alpha_i \geq 0$: the Lagrange multiplier for the $i$-th margin constraint
• $y_i \in \{-1, +1\}$: the label of the $i$-th training example
• $\mathbf{x}_i$: the $i$-th training input
• $\sum_i$: the sum over all training examples

This is the first sign that the solution may be sparse: any point with $\alpha_i = 0$ contributes nothing to the weight vector. Second, $\partial \mathcal{L} / \partial b = 0$ yields the balance condition

$$\sum_i \alpha_i y_i = 0.$$

where:

• $\alpha_i \geq 0$: the Lagrange multiplier for the $i$-th margin constraint
• $y_i \in \{-1, +1\}$: the label of the $i$-th training example
• $\sum_i$: the sum over all training examples

Third, $\partial \mathcal{L} / \partial \xi_i = 0$ yields $C - \alpha_i - \mu_i = 0$, so eliminating $\mu_i$ gives the box constraint

$$0 \leq \alpha_i \leq C.$$

Substituting the three equations back into $\mathcal{L}$ leaves only $\alpha$ behind:

$$\begin{aligned} \max_{\alpha} \;& \sum_{i=1}^n \alpha_i - \tfrac{1}{2}\sum_{i,j} \alpha_i \alpha_j\, y_i y_j\, \mathbf{x}_i^\top \mathbf{x}_j \\ \text{s.t.} \;& 0 \leq \alpha_i \leq C, \quad \sum_i \alpha_i y_i = 0. \end{aligned}$$

where:

• $\alpha_i$: the dual multiplier for the $i$-th margin constraint, bounded in $[0, C]$
• $C$: the upper bound on each multiplier
• $\mathbf{x}_i^\top \mathbf{x}_j$: the pairwise inner product between training examples

The dual problem is a convex quadratic program: the objective is a concave quadratic in $\alpha$ that we maximize over the box and balance constraints, so the feasible region is convex and any local maximum is global. Apart from the box constraint $0 \leq \alpha_i \leq C$ and the balance condition $\sum_i \alpha_i y_i = 0$, its dependence on the training input vectors is only through pairwise inner products $\mathbf{x}_i^\top \mathbf{x}_j$. The decision function becomes

$$f(\mathbf{x}) = \sum_{i=1}^n \alpha_i y_i\, \mathbf{x}_i^\top \mathbf{x} + b.$$

where:

• $\mathbf{x}$: the input point whose decision value we compute
• $\alpha_i$: the dual multiplier of the $i$-th training example
• $b$: the bias recovered from the KKT conditions
• $\mathbf{x}_i^\top \mathbf{x}$: the inner product between the $i$-th training point and the query point

The KKT complementarity conditions require $\alpha_i=0$ whenever $y_i(\mathbf{w}^\top\mathbf{x}_i+b)>1$. A point with $0<\alpha_i<C$ lies exactly on its margin hyperplane; a point with a strict violation has $\alpha_i=C$. At equality $m_i=1$, the multiplier can include either endpoint, so touching the margin does not by itself prove $\alpha_i>0$. The support vectors are precisely the points with positive dual coefficient in this representation. Only those terms remain in the decision sum, but the support set need not be a small fraction of the data.

There is also a useful connection to ordinary L2 regularization. If we divide the primal objective by $nC$ and let

$$\lambda = \frac{1}{nC},$$

the soft-margin objective becomes

$$\frac{\lambda}{2}\|\mathbf{w}\|^2 + \frac{1}{n}\sum_{i=1}^n \xi_i.$$

Here the loss is averaged over the $n$ examples. Under this convention, $C = 1/(n\lambda)$: increasing $C$ reduces the relative strength of the L2 penalty. For a fixed training problem, the optimized total hinge loss cannot increase as $C$ grows, although the solution may stay unchanged over a range of values. If the loss is written as an unaveraged sum instead, the corresponding coefficient is $\lambda = 1/C$. Larger $C$ and larger Ridge-style $\lambda$ therefore move regularization in opposite directions; always check the loss normalization before comparing libraries or codebases.

The dual exposes a clean structural idea. Anywhere the algorithm touches an inner product $\mathbf{x}_i^\top \mathbf{x}_j$, we can replace it with a symmetric function $K(\mathbf{x}_i, \mathbf{x}_j)$ that corresponds to an inner product in some feature space $\varphi$, possibly infinite-dimensional:

$$K(\mathbf{x}_i, \mathbf{x}_j) = \varphi(\mathbf{x}_i)^\top \varphi(\mathbf{x}_j).$$

where:

• $K$: the kernel function, symmetric in its two arguments
• $\mathbf{x}_i, \mathbf{x}_j$: two input examples
• $\varphi$: the feature map from input space into the (possibly infinite-dimensional) feature space

The dual problem and decision function replace each inner product by the kernel. The weight representation belongs to the feature space: $\mathbf{w}_\varphi=\sum_i\alpha_i y_i\varphi(\mathbf{x}_i)$. A nonlinear kernel need not provide a weight vector in the original input coordinates. The decision function is:

$$f(\mathbf{x}) = \sum_i \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b.$$

where:

• $\alpha_i$: the dual multiplier of the $i$-th training example
• $y_i$: the label of the $i$-th training example
• $K(\mathbf{x}_i, \mathbf{x})$: the kernel similarity between the $i$-th training point and the query point
• $b$: the bias recovered from the KKT conditions

We can now fit nonlinear functions in the original input space without explicitly computing $\varphi(\mathbf{x})$. This is the kernel trick. Three useful kernel examples are:

• Linear kernel, $K(\mathbf{z}, \mathbf{z}') = \mathbf{z}^\top \mathbf{z}'$, which recovers the linear soft-margin formulation.
• Polynomial kernel, $K(\mathbf{z}, \mathbf{z}') = (\mathbf{z}^\top \mathbf{z}' + c)^d$, with positive integer $d$ and $c \geq 0$. When $c > 0$, its feature map contains scaled monomials of degrees zero through $d$; when $c = 0$ and $d > 0$, it contains only degree-$d$ monomials.
• Radial basis function (RBF) kernel, $K(\mathbf{z}, \mathbf{z}') = \exp(-\gamma\|\mathbf{z} - \mathbf{z}'\|^2)$, with $\gamma > 0$. Similarity falls to $e^{-1}$ at Euclidean separation $1/\sqrt{\gamma}$, so this is its characteristic distance scale.

A real-valued kernel is valid when it is symmetric and its Gram matrix $K_{ij}=K(\mathbf{x}_i,\mathbf{x}_j)$ is positive semidefinite for every finite input collection. This is the positive-type kernel condition that gives a Hilbert-space feature map. A PSD training matrix alone does not establish that condition on all inputs; Mercer's spectral expansion requires additional regularity assumptions. Logistic-style similarities $\sigma(\mathbf{z}^\top\mathbf{z}')$ are not valid kernels in general and can make the dual nonconcave. The linear kernel, the polynomial kernel under the conditions above, and the RBF kernel with $\gamma>0$ are valid. Nonnegative weighted sums and pointwise products of valid kernels remain valid; the latter follows from the Schur product theorem applied to their Gram matrices.

Two controls govern the RBF kernel. A larger $\gamma$ makes similarity more local, which can permit a more variable boundary when $C$ is large enough; it does not by itself force memorization. A smaller $\gamma$ makes similarities vary more slowly. For fixed $C$, taking $\gamma$ all the way to zero makes the kernel approach the constant value one, so the fitted scores can flatten toward an intercept rather than recover a linear SVM. The penalty $C$ controls the cost of violations and interacts with this locality. Choose them jointly using validation, as covered in Hyperparameter Search and Nested Cross-Validation.

Support Vector Regression extends everything above to a continuous target $y_i \in \mathbb{R}$. The idea is to build a tube of half-width $\varepsilon > 0$ along the fitted function and ignore residuals smaller than $\varepsilon$. The loss is symmetric and piecewise linear:

$$L_\varepsilon(r) = \max\bigl(0, |r| - \varepsilon\bigr),$$

where:

• $r$: the residual $y_i - f(\mathbf{x}_i)$ for a training example, i.e. the difference between the observed target and the predicted value
• $\varepsilon > 0$: the half-width of the insensitive tube
• $|r| - \varepsilon$: the amount by which the residual exceeds the tube
• $\max\bigl(0, |r| - \varepsilon\bigr)$: the loss, zero inside the tube and linear outside

Points inside the tube incur zero loss; points outside incur a linear penalty. This is the regression analogue of the margin neighborhood: small errors are treated as noise and ignored, while large errors become support vectors that shape the fit.

In QP form we introduce two slacks per point, one for errors above the tube, $\xi_i$, and one for errors below, $\xi_i^*$:

$$\begin{aligned} \min_{\mathbf{w},\, b,\, \xi,\, \xi^*} \; & \tfrac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^n (\xi_i + \xi_i^*) \\ \text{s.t.} \; & y_i - (\mathbf{w}^\top \mathbf{x}_i + b) \leq \varepsilon + \xi_i, \\ & (\mathbf{w}^\top \mathbf{x}_i + b) - y_i \leq \varepsilon + \xi_i^*, \\ & \xi_i,\, \xi_i^* \geq 0. \end{aligned}$$

where:

• $\mathbf{w}, b$: the primal weight vector and bias
• $\xi_i$: the slack for residuals above the tube ($y_i > f(\mathbf{x}_i) + \varepsilon$)
• $\xi_i^*$: the slack for residuals below the tube ($y_i < f(\mathbf{x}_i) - \varepsilon$)
• $C$: the penalty controlling how strongly residuals outside the tube are penalized
• $\varepsilon$: the half-width of the insensitive tube

The dual has two multiplier families $\alpha_i,\alpha_i^*\in[0,C]$. With $\beta_i=\alpha_i-\alpha_i^*$, stationarity in the unpenalized bias gives $\sum_i\beta_i=0$, and stationarity in the weight gives $\mathbf{w}=\sum_i\beta_i\varphi(\mathbf{x}_i)$. Its objective is

$$\max_{\alpha,\alpha^*}\; \sum_i y_i\beta_i-\varepsilon\sum_i(\alpha_i+\alpha_i^*) -\frac12\sum_{i,j}\beta_i\beta_j K(\mathbf{x}_i,\mathbf{x}_j), \quad \sum_i\beta_i=0,\quad 0\le\alpha_i,\alpha_i^*\le C.$$

Here $\beta_i$ is the signed coefficient of training example $i$, and the $\varepsilon$ term penalizes the total multiplier mass $\sum_i(\alpha_i+\alpha_i^*)$ in the dual maximization. An active tube constraint can still have zero multiplier. A PSD kernel makes this objective concave. The prediction is

$$f(\mathbf{x}) = \sum_{i=1}^n (\alpha_i - \alpha_i^*)\, K(\mathbf{x}_i, \mathbf{x}) + b.$$

where:

• $\alpha_i$: the dual multiplier for the constraint $y_i-f(\mathbf{x}_i)\le\varepsilon+\xi_i$
• $\alpha_i^*$: the dual multiplier for the constraint $f(\mathbf{x}_i)-y_i\le\varepsilon+\xi_i^*$
• $K(\mathbf{x}_i, \mathbf{x})$: the kernel similarity between the $i$-th training point and the query point
• $b$: the bias recovered from the KKT conditions

Complementarity explains where nonzero coefficients can occur. For $\varepsilon > 0$, a point strictly inside the tube has $\alpha_i = \alpha_i^* = 0$. A point on either edge may have a nonzero multiplier, while a point strictly outside has the corresponding multiplier at $C$. Thus only points on or outside the tube can contribute, but their number need not be small. The tube half-width $\varepsilon$ controls which residuals have zero loss, and $C$ controls the penalty beyond the tube. The linear growth of this loss limits sensitivity to large response residuals relative to squared error; it does not protect against every outlier or guarantee better generalization. At $\varepsilon = 0$, the loss becomes absolute error, and the prediction still uses the net coefficient $\alpha_i-\alpha_i^*$.

The practical limits depend on the formulation. Exact nonlinear kernel SVMs can be expensive on large datasets, while dedicated linear solvers avoid the full kernel matrix. Choose input scales that reflect the problem and evaluate preprocessing within the training folds. A binary classification score is $f(\mathbf{x})$; when $\mathbf{w}\ne0$, its signed geometric distance is $f(\mathbf{x})/\|\mathbf{w}\|$ in the model's feature space. Neither quantity is automatically a probability. Validate the relevant hyperparameters, including $C$, kernel settings such as $\gamma$, and $\varepsilon$ for SVR, alongside any probability calibration needed downstream.

The following cell generates a small two-dimensional toy dataset and fits a large-$C$ linear SVM, producing the decision-score field used by the margin figure below. A large penalty can recover a separating solution on this example; it is still a soft-margin SVC fit. The reference estimator uses labels 0 and 1; our signed mathematical labels are $-1$ and $+1$. We map 0 to $-1$ and 1 to $+1$ when calculating functional margins.

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.

We build the linear hinge-loss classifier from primitives first, then compare it with scikit-learn's SVC on the same data. Working from first principles helps us see where the subgradient comes from and how sensitive the solution is to feature scaling. We standardize the numerical inputs here so that both optimizers use the same feature representation.