Hinge Loss, Maximum Margin, and the Points That Decide the Boundary

The hinge loss is the smallest change to the perceptron that produces a unique solution with a stated geometric guarantee. It achieves this by penalising not just misclassification but insufficiency of confidence, and the result is a decision boundary that depends on a subset of the training data, typically a small one, and on nothing else. The sparsity is not an implementation trick bolted on for efficiency; it falls out of the first-order optimality conditions of a convex problem whose loss is exactly zero on an interval.

Margin as a scaled distance

For a linear classifier $f(x) = w^\top x + b$ with labels in ${-1, +1}$, the functional margin of an observation is $y_i(w^\top x_i + b)$, which is positive when the classification is correct and grows with confidence, but is not a distance: scaling $w$ and $b$ by any positive constant multiplies every margin without changing the decision boundary. The geometric distance from the point to the hyperplane is $y_i(w^\top x_i + b)/\lVert w\rVert$, which is scale-invariant.

The maximum-margin problem fixes the scale by requiring the functional margin of the closest points to be at least 1, then minimising $\lVert w\rVert$:

$$\min_{w,b} \tfrac12 \lVert w \rVert^2 \quad \text{subject to} \quad y_i(w^\top x_i + b) \ge 1 \ \text{ for all } i .$$

The constraint is a normalisation, not a modelling assumption. Any separating $(w, b)$ can be rescaled so that the minimum functional margin equals 1, so the constraint removes exactly the scale freedom and leaves the direction and offset as the only degrees of freedom. The geometric margin is then $2/\lVert w \rVert$, and minimising $\lVert w\rVert$ maximises it. The choice of 1 is arbitrary except that it makes the algebra clean; the constraint could be $c$ for any $c > 0$, with $\lVert w\rVert$ rescaled accordingly.

The constraint set is a polyhedron and the objective is strictly convex, so the solution exists and is unique in $w$ whenever a separating hyperplane exists. That is already a qualitative improvement over the perceptron, which converges to some separating hyperplane and the choice depends on the order of the data.

Slack, C, and where the hinge comes from

When the data is not separable the constraints are impossible, so each observation gets a slack $\xi_i \ge 0$ measuring how far it falls inside the margin or on the wrong side:

$$\min_{w,b,\xi} \tfrac12\lVert w\rVert^2 + C\sum_i \xi_i \quad \text{subject to} \quad y_i(w^\top x_i + b) \ge 1 - \xi_i, \ \xi_i \ge 0 .$$

Eliminating $\xi$ by substituting its optimal value, which is $\max(0, 1 - y_i f(x_i))$, gives the unconstrained form

$$\min_{w,b} \ \tfrac12\lVert w\rVert^2 + C \sum_i \max\big(0, 1 - y_i(w^\top x_i + b)\big).$$

The second term is the hinge loss. It is zero for any observation correctly classified with functional margin at least 1, meaning any point outside the margin band, and grows linearly for observations inside the band or misclassified. The flat region is the whole point: observations far from the boundary contribute nothing to the objective at all, neither to the loss nor to its gradient, so they cannot affect the solution. Compare the logistic loss, which is strictly positive everywhere and decays only asymptotically, so every observation has some influence. The comparison of losses by their derivative behaviour is in squared, absolute, and quantile loss, and the hinge’s derivative has the same clipped shape as the Huber loss’s tail, but at a fixed threshold rather than an adaptive one.

The constant $C$ is the inverse of a regularisation strength. Large $C$ makes violating the margin expensive, so the optimiser accepts a narrow margin to fit more points; the limit $C \to \infty$ recovers the hard-margin problem when the data is separable. Small $C$ accepts violations in exchange for a wider margin, and in the limit of very small $C$ the solution is dominated by the norm term and approaches a boundary that ignores the data.

import numpy as np

def hinge_objective(X, y, w, b, C):
    margin = y * (X @ w + b)                 # y in {-1, +1}
    loss = np.maximum(0.0, 1.0 - margin)
    return 0.5 * w @ w + C * loss.sum(), loss

def hinge_subgradient(X, y, w, b, C):
    margin = y * (X @ w + b)
    active = (1.0 - margin) > 0              # inside margin or misclassified
    coef = -C * y * active                   # d/d(margin), zero outside the band
    gw = w + X.T @ coef
    gb = coef.sum()
    return gw, gb

The active mask is the sparsity: at the optimum, only those rows appear in the gradient, and the normals $w$ is a linear combination of exactly those rows. That is the representer property, and it is why the solution is supported on a subset of the data.

The dual exposes the support vectors

Introducing multipliers $\alpha_i \ge 0$ for the margin constraints gives, after minimising over the primal variables, the dual problem

$$\max_{\alpha} \sum_i \alpha_i - \tfrac12 \sum_{i,j} \alpha_i\alpha_j y_i y_j x_i^\top x_j \quad \text{subject to} \quad 0 \le \alpha_i \le C, \ \sum_i \alpha_i y_i = 0 .$$

The primal solution is recovered as $w = \sum_i \alpha_i y_i x_i$, so the weight vector is a combination of training points with nonzero multipliers. Those points are the support vectors. The Karush–Kuhn–Tucker conditions pin their identity precisely: $\alpha_i = 0$ for points strictly outside the band, where the margin constraint is inactive; $0 < \alpha_i < C$ for points exactly on the margin at functional margin 1; and $\alpha_i = C$ for points inside the band or misclassified, where the slack constraint is active.

This three-way classification is diagnostic. A fit with many $\alpha_i$ strictly between 0 and $C$ means many points sit exactly on the margin, which in exact arithmetic should be rare and in floating point is common: the boundary is a hyperplane and points at distance one from it are a measure-zero set, so a large count usually means the solver has not converged. The count of points at $\alpha_i = C$ is the count of margin violations, and it grows with the overlap between classes.

The dual has only $n$ variables, independent of the dimensionality of the feature space. This is what makes kernelisation possible: the dual depends on the data only through the inner products $x_i^\top x_j$, and replacing the inner product with a positive semidefinite kernel $k(x_i,x_j)$ corresponds to solving the same problem in a feature space that may be infinite-dimensional. The primal weight vector may not exist explicitly in that space, but it never needs to be formed.

Choosing C without a held-out set of a useful size

The number of effective parameters of a margin classifier is not its weight count. A bound due to Vapnik relates the generalisation error to the ratio of the radius of the smallest sphere containing the data to the margin, divided by the square root of the number of observations. The practical consequence is that the leave-one-out error has a closed form in terms of the support vectors: removing a training point that is not a support vector leaves the solution unchanged, so the leave-one-out error is at most the number of support vectors above the margin divided by $n$. When that count is small, the leave-one-out estimate is tightly bounded and no separate holdout is needed; when it approaches $n$, the bound is vacuous and the model has overfit.

import numpy as np

def loo_bound(alpha, C, y, X, w, b):
    """Upper bound on LOO error: points with alpha>0 that are misclassified or inside."""
    margin = y * (X @ w + b)
    at_bound = (alpha > 1e-8) & (margin <= 1.0 + 1e-6)
    return at_bound.sum() / len(y)

The bound is an inequality rather than an estimate, so it is valid without distributional assumptions, but it is loose in the direction that matters least: it overstates the error rather than understating it. That asymmetry is the useful part.

The limits of a linear boundary

The hinge loss is unbounded below in the sense that making an already-correct point more confident yields no reward, but making a wrong point more wrong yields linear cost. That asymmetry is deliberate: it means the model does not spend capacity making easy points easier, which is where the sparsity comes from. The cost is that a handful of points with label noise and unusual features can be extremely influential if their slack is large, since their contribution to the objective is unbounded until their multiplier saturates at $C$, after which their pull is capped, which is the practical meaning of the upper bound in the dual box constraint.

Multi-class extension uses one binary problem per class, which reintroduces the normalisation question treated in softmax versus one-vs-rest probabilities: the per-class hinge scores are not probabilities and do not sum to one. The contrast with the logistic model is sharpest in the tail: the logistic loss decays geometrically for a confident correct prediction, so every observation retains a small influence, while the hinge loss is identically zero outside the band. That difference in tail behaviour, described in logistic regression as conditional likelihood, is what makes one solution dense and the other sparse, and no amount of solver tuning changes it. The whole construction then assumes the margin is the right notion of confidence. For problems where the cost of a confident error is not linear in the distance from the boundary, so that a point just inside the boundary is acceptable but one deep inside is catastrophic, a loss with a faster-growing tail is the appropriate choice, and the hinge’s linear tail is the modelling assumption that has to be justified rather than inherited.