A classifier's sign, its geometric distance to a boundary and the objective used to fit it are related but distinct. A kernel can describe an inner product in a feature space only when every finite Gram matrix is symmetric positive semidefinite.
Scores have a scale; distance does not
An affine classifier has score , with , and predicts by its sign. Replacing by for leaves the boundary and signs unchanged, but multiplies every functional score by . The signed geometric distance is : dividing by the norm removes this arbitrary positive scale. For label , the signed margin is .
Definition 11.1.1
(Functional margin and geometric margin)
For an affine score with and a labeled observation , , the functional margin is and the geometric margin is . An observation is classified correctly exactly when its functional margin is positive.
When the data are strictly linearly separable, one can rescale so that the smallest signed functional score is 1. A hard-margin SVM minimizes subject to . The closest observations then lie at distance from the boundary, and the two supporting planes are apart. These numerical formulas rely on the stated normalization. If constraints are infeasible, the hard-margin problem has no feasible solution; an optimization method cannot make contradictory labels at identical features separable.
Common mistake
(Reading a functional margin of 1 as a distance of 1)
The constraint fixes the functional margin, not the distance. A point on the margin lies at distance from the boundary, which changes whenever changes. Scaling by multiplies every functional margin by and leaves every geometric margin unchanged, so a large functional margin alone says nothing about how far a point is from the boundary.
Worked problem: two observations and a certificate
Worked example 11.1.2
(Two observations and a dual certificate)
In one dimension take a negative observation at and a positive observation at . Constraints are and . Adding them yields , so every feasible . The feasible choice , reaches this lower bound and minimizes . Its boundary is ; each observation is distance 2 from it, and the supporting-plane separation is 4.
A dual certificate makes the lower-bound argument visible in another form. Choose multipliers . They are nonnegative; and . Both constraints are equalities, so complementary slackness holds. The dual objective is , equal to the feasible primal objective. This certifies optimality. It does not require claiming that every data point has a positive multiplier in every problem.
Hinge loss changes the optimization question
For a score and label, hinge loss is . It is zero at and beyond the required functional margin, positive inside it, and at least 1 for an incorrect or zero score. A common soft-margin objective is
Here losses are summed. Using a mean instead changes the numerical meaning of , so a comparison must state the convention. The regularizer rewards a smaller norm while the loss penalizes margin violations. A lower value for one candidate proves only that another candidate is not optimal at that ; it does not, on its own, prove the first candidate is globally optimal.
Concept lensAlgebraic
Hinge loss as the optimal slack
Introduce slack variables with and minimize . For fixed , the smallest admissible is , because must be at least both and . Minimizing over the slacks therefore returns exactly the objective above, so the constrained slack form and the unconstrained hinge form describe the same problem. In the slack form each is the amount by which observation violates its margin; in the hinge form the same number is a loss on the score.
Worked problem: compare two feasible parameter choices
Worked example 11.1.3
(Comparing two feasible parameter choices)
Use the two observations above. The hard-margin solution has zero hinge loss and objective . For , each signed score is and each hinge loss is . Its objective is . It is strictly smaller than exactly when ; equality holds at . The comparison says the hard-margin parameters are not optimal for that soft objective in the strict range. It does not determine the global soft-margin minimizer.
If the same feature vector appears once with label +1 and once with label -1, their common score would need both and for hard margin, which is impossible. Their hinge losses sum to : the sum is 2 for and larger outside. A soft formulation can assign finite loss to the contradiction; no deterministic classifier using only that feature vector can assign both labels correctly.
A kernel is a structured similarity
Definition 11.1.4
(Kernel and Gram matrix)
A function is a kernel if there are a real inner-product space and a map with for all . For points the Gram matrix is .
Proposition 11.1.5
(Gram matrices of a kernel are positive semidefinite)
If is a kernel, then for every finite choice the Gram matrix is symmetric and for every .
Proof
(A Gram quadratic form is a squared norm)
Symmetry holds because , so . For real coefficients ,
Every finite Gram matrix of a kernel is thus symmetric positive semidefinite (PSD). This requirement concerns all finite input choices, not just one sampled matrix. A single Gram matrix with a negative quadratic form disproves a proposed kernel; checking one positive matrix does not prove the universal property. Numerical approximations also need care near zero eigenvalues.
Worked problem: prove one kernel and disprove another
Worked example 11.1.6
(Proving one kernel and disproving another)
For real inputs let . The feature map gives . Equivalently, any finite Gram quadratic form equals . Therefore the PSD condition holds for every finite sample.
By contrast, propose . At inputs 0 and 2 its Gram matrix is . With , , so this matrix is not PSD and cannot be a real inner-product kernel on a domain containing those inputs. The negative diagonal already supplies the counterexample: a feature vector's squared norm cannot be negative. “Similarity” as an informal label is not sufficient to justify the kernel trick.
Common mistake
(Validating a kernel with one positive Gram matrix)
A single PSD Gram matrix does not make a function a kernel. For , the one-point Gram matrix at is , which is PSD, yet the two-point matrix at inputs and above is not. A proposed kernel must pass for every finite set of inputs, or be exhibited as an inner product of feature vectors.
Why a perceptron update bound needs a margin
A perceptron update is not the same operation as minimizing the SVM objective. Augment each input with a bias coordinate: and . Starting at zero, update whenever . The equality convention matters: it determines whether a zero-score observation causes an update.
Theorem 11.1.7
(Perceptron mistake bound)
Let with for every in a finite training set, and suppose some unit vector satisfies for every . Start at and update whenever . In any order of presentation, the perceptron makes at most updates in total.
Proof
(Progress along u against growth of the norm)
After updates, the projection of the parameter on is at least , since each update increases it by at least . On an update, the squared norm changes by
The middle term is nonpositive by the update condition. Starting at zero gives . By Cauchy–Schwarz, , so for . The argument requires the separator and radius hypotheses; it is not a universal guarantee for contradictory or nonseparable data. It bounds total updates over a run, not the number needed in every single pass.
Proof X-ray
Linear progress against square-root growth
The proof sets two quantities against each other. The margin hypothesis makes the projection grow by at least per update, so it is at least linear, . The update condition makes the cross term nonpositive, so the squared norm grows by at most per update and . Cauchy–Schwarz, with of unit length, links the two: a projection cannot exceed the norm. A linear lower bound cannot stay below a square-root upper bound for long, and that forces .
Each hypothesis has its own job. Taking to be a unit vector is what lets be compared with ; rescaling would rescale without changing the data. The sign of the cross term is where "update only on a mistake" is used. The existence of is the separability assumption: without it no exists and the argument has nothing to close.
Worked problem: a bound and an actual trace
Worked example 11.1.8
(The mistake bound and an actual trace)
Take one-dimensional positive point and negative point . The augmented separator has signed score 1 on each observation and norm ; its unit normalization therefore has margin . Augmented input norms are and 1, so take . The theorem allows at most updates.
Process positive then negative repeatedly. From the positive point has score zero, so update to . The negative point has score 1, so update by to . On the next pass the positive score is 4, requiring no update; the negative score is zero, so update to . Both signed scores are then positive: 3 at the positive point and 1 at the negative point. This run has three updates, well below the upper bound. If the algorithm did not update at zero, this exact trace would differ; the convention is part of the problem.
The separability hypothesis cannot be dropped.
Counterexample mode
A mistake bound with no separator
One might hope that the perceptron stops on any finite training set. Take the single input , augmented to , appearing once with label and once with label . No separator exists. Start at and present the copy first: its score is , so the rule updates to . The copy has , so the rule updates to . After one pass the parameter is back at , so the same two updates repeat forever. The bound does not apply because no exists. The repair is the separability hypothesis, or a different algorithm or loss, such as a soft-margin objective, that tolerates contradictory labels.
Where the dual certificate comes from
A certificate is useful only if its inequality is clear. For the hard-margin constraints, take multipliers and form
At any feasible , each bracket is nonpositive, so . Its infimum over all is therefore a lower bound on every feasible primal objective. The coefficient of is ; unless that sum is zero, the infimum over is unbounded below. Under the zero-sum constraint, minimizing the quadratic over gives and dual value
Thus any nonnegative multipliers satisfying the zero-sum condition give a valid lower bound. If an explicitly feasible primal point attains the same value, no feasible point can do better: weak duality alone certifies optimality. In the two-observation example, both values equal . Complementary slackness explains which constraints can have positive multipliers at an optimum, but an observation on the margin can still have zero multiplier in a degenerate solution. The bias is not included in in this formulation; a different model that regularizes bias has a different dual.
Proposition 11.1.9
(Dual lower bound for the hard-margin problem)
Let with , and let . Every feasible of the hard-margin problem satisfies . If a feasible attains , it is optimal.
Proof
(Completing the square)
Write . For feasible each bracket is nonpositive, so . Expanding and using to remove ,
If a feasible point attains , every feasible point has objective at least that value, so it is optimal.
Concept lensGeometric
Maximum margin as the closest pair of points between the classes
For strictly separable data, the optimal gap between the supporting planes equals the Euclidean distance between the convex hulls of the two classes, and the boundary is the perpendicular bisector of a closest pair of hull points. The dual multipliers are the weights of those two points: makes the positive and negative weights equal, and is proportional to their difference. In the two-observation example the hulls are the points and , at distance .
Expanding the dual norm produces terms . Replacing those terms with a valid kernel corresponds to the same construction using feature vectors . This does not mean every symmetric-looking formula is valid, or that a finite Gram check on one training set proves validity on a whole domain. It also does not choose the feature scale or hyperparameter automatically. A model selection procedure should fit any learned preprocessing on training data, choose its settings without consulting the final test labels, and evaluate the selected pipeline on held-out data. A perfect fit on training observations is evidence about those observations, not by itself a guarantee of generalization.
A margin score should also not be read automatically as a calibrated probability. Its sign provides the decision under the chosen threshold, and its magnitude measures a normalized or unnormalized distance according to the convention; neither statement says that a score of 2 means an 88% chance of the positive class. If probabilities are needed, a separately specified calibration procedure and appropriate validation are necessary. The regularization parameter influences the trade-off between norm and training loss, but its useful value depends on the loss convention, feature scale and task. Doubling every feature without adjusting the model changes the meaning of a fixed and can change the fitted optimum.
For the linear example, multiplying by 2 gives the same boundary at and the same signs. Its functional margins become 2, but the geometric margins remain 2 because the norm also doubles. The rescaled pair remains feasible, yet its regularizer increases from to , so it is not the hard-margin minimizer. This short check ties the normalization, geometry and optimization together without treating a score as a probability.
Exercises
Quick check
(In one dimension, the observation with is scored by . Find its functional and geometric margins, and the same two margins for .)
Use and divide by for the geometric margin.
Solution · Answer
For : , so the functional margin is and the geometric margin is . For : , functional margin , geometric margin . Rescaling changes the functional margin but not the geometric one.
Quick check
(A score is . Compute the hinge loss when and when .)
Use .
Solution · Answer
For : . For : , so the loss is . A small positive score is inside the margin for the correct label and costs ; with the wrong label it costs more than .
Quick check
(Decide whether and are valid kernels on .)
Look for a feature map for one, and a one-point Gram matrix for the other.
Solution · Answer
is a kernel, with feature map . For , the one-point Gram matrix at is , and with , so is not a kernel.
Quick check
(Observations: with and with . Find the hard-margin solution, and show that certifies its optimality.)
Add the two constraints to bound , then evaluate .
Solution · Answer
The constraints are and . Adding gives , so , and is feasible with objective . For : , and , so . This equals the primal objective, so is optimal.