Margins And Interpolating Classifiers

Why Margins Matter for Interpolating Classifiers

For binary classification, a linear classifier separates observations by placing them on opposite sides of a hyperplane. If the training data are separable, many different hyperplanes may classify every training point correctly. The resulting classifiers all interpolate the labels in the sense of having zero training classification error, but their geometry can differ substantially.

A margin measures how far a classified point lies from the decision boundary, with distance measured relative to the classifier’s direction and scale. Margins help distinguish a classifier that barely separates its training data from one that separates them with room to spare. They also give a precise way to connect two geometric viewpoints: maximizing the minimum margin among unit-length classifiers and finding the smallest-norm vector that achieves a specified margin.

Neither viewpoint, by itself, says that the classifier will work well on new observations. Population classification risk depends on the joint distribution of features and labels, including regions the training sample may not represent. This distinction is essential: interpolation is a statement about the observed sample; generalization is a statement about the data-generating distribution.

Functional and Geometric Margins

Let the training data be $(x_i,y_i)$, $i=1,\ldots,n$, where $x_i\in\mathbb{R}^d$ and $y_i\in\{-1,+1\}$. A linear classifier with vector $w\ne 0$ predicts $+1$ when $w^\top x\geq 0$ and $-1$ otherwise. We count a point on the decision boundary as an error. The signed functional margin of observation $i$ is $y_i w^\top x_i$: a positive value indicates correct classification, and a negative value indicates incorrect classification.

Definition: The functional margin of $w$ on the training sample is $\min_{1\leq i\leq n} y_i w^\top x_i$. For $w\ne 0$, the geometric margin of observation $i$ is $y_i w^\top x_i/\|w\|_2$, and the geometric margin of the sample is $$ \gamma_S(w)=\min_{1\leq i\leq n}\frac{y_i w^\top x_i}{\|w\|_2}. $$ The data are strictly linearly separable if some $w\ne 0$ gives $y_i w^\top x_i>0$ for every training observation.

The functional margin depends on the scale of $w$. Replacing $w$ by $cw$ for $c>0$ multiplies every functional margin by $c$, without changing any predictions. The geometric margin removes this arbitrary scale: $\gamma_S(cw)=\gamma_S(w)$. Thus the geometric margin describes the location of the decision boundary relative to the data, not the length chosen to represent the classifier.

The set of all strictly separating vectors is $$ \mathcal{C}=\{w\in\mathbb{R}^d:y_i w^\top x_i>0\text{ for every }i\}. $$ It is an intersection of open half-spaces, so it is convex; if $w\in\mathcal{C}$, every positive multiple of $w$ is also in $\mathcal{C}$. This cone-like geometry explains why zero training error does not identify a unique vector or a unique margin.

Worked Example: Finding a Maximum-Margin Direction

Consider three labeled points in $\mathbb{R}^2$: $x_1=(1,0)$, $y_1=+1$; $x_2=(0,1)$, $y_2=+1$; and $x_3=(-1,-1)$, $y_3=-1$. For $w=(w_1,w_2)$, their signed functional margins are $w_1$, $w_2$, and $w_1+w_2$, respectively.

Strict separation requires $w_1>0$, $w_2>0$, and $w_1+w_2>0$. The third condition follows from the first two. Since geometric margin is unchanged by positive rescaling, restrict attention to $\|w\|_2=1$. In the first quadrant, the sample margin is $\min(w_1,w_2)$, because $w_1+w_2$ is at least as large as either coordinate.

Under $w_1^2+w_2^2=1$, the smaller coordinate is at most $1/\sqrt{2}$: if both coordinates exceeded $1/\sqrt{2}$, their squares would sum to more than 1. Equality is achieved at $w_1=w_2=1/\sqrt{2}$. Hence this direction maximizes the geometric margin, which is $1/\sqrt{2}$. The third point’s geometric margin is $2/\sqrt{2}=\sqrt{2}$, so the two positive points determine the minimum.

Maximum Margin and Minimum Norm

A convenient way to remove the positive scaling freedom is to require every signed functional margin to be at least 1. Among vectors satisfying those inequalities, choose one of minimum Euclidean norm. The normalization at 1 is a convention: changing the required margin to a different positive constant changes the scale of the solution, not its direction.

Theorem: Suppose the finite training sample is strictly linearly separable. Let $$ \kappa=\max_{\|u\|_2=1}\min_{1\leq i\leq n}y_i u^\top x_i. $$ Then $\kappa>0$, the maximum is attained, and the unique solution to $$ \min_{w\in\mathbb{R}^d}\frac{1}{2}\|w\|_2^2 \quad\text{subject to}\quad y_i w^\top x_i\geq 1\quad\text{for all }i $$ has norm $1/\kappa$. Its direction maximizes the sample geometric margin.

Proof. Strict separability gives a vector whose signed margins are all positive. Normalizing that vector to unit length shows that the maximum defining $\kappa$ is positive. The unit sphere in $\mathbb{R}^d$ is compact, and the minimum of finitely many continuous functions is continuous, so the maximum is attained at some unit vector $u_*$.

The vector $u_*/\kappa$ is feasible, since each of its signed margins is at least $\kappa/\kappa=1$. Its norm is $1/\kappa$. Conversely, let $w$ be any feasible vector. It is nonzero, and $v=w/\|w\|_2$ has unit norm. Feasibility implies $$ \min_i y_i v^\top x_i =\frac{\min_i y_i w^\top x_i}{\|w\|_2} \geq \frac{1}{\|w\|_2}. $$ The left side is at most $\kappa$, by the definition of $\kappa$. Therefore $\|w\|_2\geq 1/\kappa$. The feasible vector $u_*/\kappa$ attains this lower bound and is a minimum-norm solution.

The feasible set is closed and convex, and the objective $\|w\|_2^2/2$ is strictly convex, so the minimum-norm solution is unique. Its direction attains the maximum sample geometric margin by construction. $\square$

In the worked example, the constraints are $w_1\geq 1$, $w_2\geq 1$, and $w_1+w_2\geq 1$. The third constraint is redundant. The minimum-norm feasible vector is therefore $(1,1)$, whose norm is $\sqrt{2}$; the corresponding maximum geometric margin is $1/\sqrt{2}$, in agreement with the direct calculation.

Worked Example: Checking the Minimum-Norm Solution

Suppose the observations are $(x_1,y_1)=((2,0),+1)$ and $(x_2,y_2)=((0,1),+1)$. The unit-margin constraints are $2w_1\geq 1$ and $w_2\geq 1$, or $w_1\geq 1/2$ and $w_2\geq 1$.

To minimize $w_1^2+w_2^2$ under these separate lower bounds, choose the smallest permitted coordinates: $w_*=(1/2,1)$. Its squared norm is $1/4+1=5/4$, so $\|w_*\|_2=\sqrt{5}/2$.

For a unit vector $u=(u_1,u_2)$ in the positive quadrant, the sample geometric margin is $\min(2u_1,u_2)$. The direction of $w_*$ is $(1/\sqrt{5},2/\sqrt{5})$, giving margins $2/\sqrt{5}$ and $2/\sqrt{5}$. Thus its geometric margin is $2/\sqrt{5}$, and its reciprocal is $\sqrt{5}/2=\|w_*\|_2$, as the theorem predicts.

Geometric Margins and Perturbations

A positive geometric margin also has a direct robustness interpretation. For a correctly classified point $x$ with label $y$, the signed distance to the hyperplane $w^\top x=0$ is $y w^\top x/\|w\|_2$. If features are perturbed, the classifier remains correct as long as the perturbation is smaller than this distance.

Result: Let $w\ne 0$, $y\in\{-1,+1\}$, and suppose $y w^\top x/\|w\|_2=m>0$. For any perturbation $\delta$ satisfying $\|\delta\|_2<m$, the perturbed point $x+\delta$ remains strictly correctly classified.

Proof. By the Cauchy–Schwarz inequality, $$ \frac{y w^\top(x+\delta)}{\|w\|_2} =\frac{y w^\top x}{\|w\|_2}+\frac{y w^\top\delta}{\|w\|_2} \geq m-\frac{|w^\top\delta|}{\|w\|_2} \geq m-\|\delta\|_2>0. $$ The perturbed signed margin is positive, so the perturbed point remains correctly classified. $\square$

Worked Example: A Perturbation at the Margin Boundary

Take $w=(3,4)$, so $\|w\|_2=5$, and let $x=(1,0)$ have label $+1$. Its functional margin is $3$, and its geometric margin is $3/5=0.6$. The result guarantees correct classification for every feature perturbation of Euclidean norm less than $0.6$.

To check the boundary, take $\delta=-0.6(3,4)/5=(-0.36,-0.48)$. Its norm is $\sqrt{0.36^2+0.48^2}=\sqrt{0.36}=0.6$. The perturbed point is $x+\delta=(0.64,-0.48)$, and $$ w^\top(x+\delta)=3(0.64)+4(-0.48)=1.92-1.92=0. $$ It lies exactly on the decision boundary. The strict inequality in the robustness result matters: perturbations smaller than the margin are guaranteed safe, while one at the margin can reach the boundary.

Zero Training Error Is Not Population Risk

For a classifier $w$, define its empirical classification error on the observed sample and its population classification risk under a distribution of a new pair $(X,Y)$ by $$ \widehat R_S(w)=\frac{1}{n}\sum_{i=1}^n \mathbf{1}\{y_i w^\top x_i\leq 0\}, \qquad R(w)=P(Yw^\top X\leq 0). $$ The indicator counts a point on the boundary as an error. A strictly interpolating classifier has $\widehat R_S(w)=0$, but that equality concerns only the observed points. The population risk averages over the full distribution, including feature-label combinations absent from the sample.

Worked Example: A Perfect Fit With Population Risk One-Half

Worked Example: A Perfect Fit With Population Risk One-Half

Let $X$ take the values $+1$ and $-1$, each with probability $1/2$, and let $Y=+1$ with probability 1. Suppose a training sample of size $n$ consists entirely of observations with $X=+1$. For $w=1$, every training signed margin is $y_iwx_i=1$, so the empirical error is zero and the sample geometric margin is 1.

On a new observation, the classifier predicts $-1$ when $X=-1$, even though the label is $+1$. It is correct when $X=+1$. Therefore $$ R(1)=P(X=-1)=\frac{1}{2}. $$ The event that all $n$ training features equal $+1$ has probability $(1/2)^n$, so this sample can arise from the stated population distribution. The example shows that even a positive, scale-invariant training margin does not by itself imply small population risk.

This example is deliberately simple, but the issue is general. A sample margin describes distances for the observed feature-label pairs. It does not report how much probability mass lies in regions where the classifier makes errors, or whether those regions were represented in the training data. To turn margin geometry into a generalization guarantee, additional information is needed, such as restrictions on the data distribution or a complexity analysis that accounts for how the classifier was selected.

Common Mistakes

Comparing functional margins across differently scaled vectors. A vector and any positive multiple of it give the same classifier, but the functional margin changes with that multiple. Use the geometric margin when comparing classifier geometry.
Treating every zero-error vector as equally separated. Zero training error only says all observed points are classified correctly. Their minimum geometric margins may be very different.
Calling minimum norm a population-risk guarantee. Minimum norm is equivalent to maximum sample margin under the stated separability and unit-margin constraints. It is not, by that equivalence alone, a bound on population risk.
Inferring generalization from a large training margin without assumptions. The training sample may omit regions carrying substantial probability mass. A margin is a geometric summary of observed data, not a description of the full distribution.

The useful conclusion is precise but limited: on strictly separable data, maximum sample geometric margin and minimum-norm unit-margin interpolation select the same linear direction. Margins also quantify tolerance to bounded perturbations. Whether that direction has low population risk remains a separate statistical question.

Check Your Understanding

Try these questions using the definitions and results above.

Why does multiplying a classifier vector by a positive constant change its functional margin but not its geometric margin?
For strictly separable data, explain why a unit-margin minimum-norm solution has the maximum sample geometric margin.
A training point has signed geometric margin $0.2$. What does the perturbation result guarantee, and what does it not guarantee at perturbation norm exactly $0.2$?
In the discrete example, calculate the probability that a sample of size 5 consists entirely of $X=+1$ observations.
What extra kind of information is needed before a training-margin calculation can support a claim about population classification risk?