Motivation
Squared loss asks a prediction to approximate a numerical label. Classification has a different immediate aim: give the correct sign while retaining a margin from the decision boundary. Hinge loss measures failure to attain a specified signed margin. It is convex but not differentiable at the margin, so a ridge-regression normal equation cannot simply be reused with the label vector changed.
The existing RKHS construction supplies the function space and its bounded evaluations. Here we use that foundation to prove a complete classification result, including existence, a finite representation, duality, and the meaning of support-vector coefficients. We will keep three unknowns separate: the regularized function, an unpenalized intercept, and the coefficients used to represent the function. They need not share the same uniqueness properties.
Soft margins also make contradictory observations mathematically admissible. The resulting optimization problem remains solvable, but no optimization theorem can make identical inputs with opposite labels distinguishable. A useful derivation should explain this limitation alongside the successful separable examples.
Definitions
Let be a real symmetric positive semidefinite kernel with RKHS , and let be a nonempty finite sample with . Write , , and . We assume the reproducing identity and Hilbert-space projection results developed in the earlier kernel-space note.
Definition 11.1.1
(Soft-margin primal with an unpenalized intercept)
The score is with and . Throughout the main derivation, the intercept is unpenalized and is optimized, while the function receives a squared RKHS-norm penalty. Predict positive when the score is nonnegative, negative otherwise; this tie convention does not alter the training objective. Define margin and hinge .
For a fixed , the soft-margin primal is
For fixed scores, the optimal slack is , since increasing it has positive cost. Thus the equivalent objective is . This loss is a sum. Multiplying the averaged objective by gives the present convention with , for .
Let . A representation has training vector and squared function norm . The latter is generally not , and a singular can make distinct coefficient vectors represent the same function.
Theorem/proposition
Theorem 11.1.2
(Hinge-loss representers and primal attainment)
The primal minimum is attained. Every minimizing function lies in , and the function is unique across all optimal triples. Neither nor a coefficient representation is necessarily unique. These claims require no strict positive definiteness of and no separability of the labels.
Theorem 11.1.3
(Soft-margin duality and a complete optimality certificate)
The dual is the attained concave maximization
Its optimum equals the primal minimum. A primal-feasible triple and a dual-feasible vector are optimal if and only if
for every . These are the stationarity and complementary-slackness parts of the KKT certificate; primal and dual feasibility are also required.
The equality constraint on dual coefficients comes from optimizing an unpenalized intercept. It is not a property of every kernel classifier. We will derive its two common alternatives after establishing the main result.
Proof sketch or proof idea
Proof
(Finite span, existence and uniqueness)
Decompose any function as with and . Evaluation gives , while . Removing a nonzero remainder leaves all margins unchanged and strictly improves the objective. This proves the representer conclusion conditional on attainment and reduces the existence question to the finite-dimensional space , even when its kernel generators are dependent.
In a fixed bounded primal sublevel, the norm of and every slack are bounded. Reproducing evaluation therefore bounds all . If both labels occur, a positive-label constraint bounds below and a negative-label constraint bounds it above. Thus a minimizing sequence has a convergent subsequence in , and closed constraints and continuity give a minimizer. If all labels equal , take ; the objective is zero, its global lower bound. Finally, if two optimal functions differed, averaging their feasible triples would strictly reduce the squared-norm term and leave the slack cost linear. This contradicts optimality and proves uniqueness of the function.
Proof
(The dual problem and strict feasibility)
Introduce nonnegative multipliers for and for . The Lagrangian is
Its infimum over occurs at . Its infimum over unrestricted is finite exactly when ; its infimum over unrestricted slack variables is finite exactly when . Eliminating gives the box constraints and the displayed dual. Positive semidefiniteness makes its quadratic term concave. The feasible box slice is compact and nonempty, so its maximum is attained.
Strict feasibility is easy after finite reduction: makes both families of inequalities strict. This is Slater's condition for this convex problem. Rather than merely citing a general strong-duality theorem, we now construct optimal multipliers directly.
Proof
(Constructing multipliers and closing the gap)
At a minimizer of , let A be the box of possible hinge weights: if , if , and if . In the finite Hilbert space , form the compact convex set
Each element is a subgradient, obtained from the supporting-line inequality for each scalar hinge. More specifically, the one-sided derivative in any direction equals . Away from a hinge kink its slope is fixed; at a kink it is the maximum of its two adjacent linear slopes. The independent intervals in A let the maxima be taken separately and then added.
If zero were not in , choose its minimum-norm point . Differentiating squared distance along every segment inside gives . In direction the maximum directional derivative is therefore at most , contradicting minimality. Thus , giving both function stationarity and . Take the optimal hinge slacks. The definition of A gives both complementarity identities, including the cases exactly at margin one.
To finish without any unproved duality exchange, expand the following identity for any feasible pair:
Every term is nonnegative. The constructed multipliers make all terms zero, proving equality of the attained optima. Conversely, any optimal feasible pair has zero gap, so each nonnegative term must vanish. This proves the full certificate and its necessity, without inverting or assuming differentiability of the hinge.
Proof X-ray
Where strong duality really enters
Three facts carry the argument. The representer step uses only the reproducing property: means , so the remainder is invisible to every margin and is pure cost. Existence needs both labels to bound the unpenalized intercept from both sides, which is why the one-label case is settled separately. The key move for strong duality is geometric: the set of hinge subgradients is compact and convex because each margin contributes its own interval of weights, and if its minimum-norm point gives a strict descent direction, contradicting optimality. Strict feasibility shows that Slater theory would apply, but the proof does not rely on it. The gap identity closes the argument: it writes as a sum of three nonnegative terms, so multipliers that make all three vanish give equal values, and any zero-gap pair must satisfy every KKT condition. A formal Lagrangian calculation alone would give only a candidate dual and weak duality.
For a chosen optimal dual vector, indices with are called support vectors. The certificate gives , , and . Conversely, a margin strictly above one forces , while a margin below one forces . Equality at margin one permits any box status. A positive margin guarantees correct classification, even below one; a negative margin guarantees an error. At margin zero, the positive tie convention is correct for a positive label and wrong for a negative label.
Worked examples
Worked example 11.1.4
(A complete two-point Gram calculation)
Take , inputs and labels . Then and is the all-ones matrix. The equality constraint gives , and the dual is on . At , its maximum is at . Recovery gives . The optimal intercept set is exactly , since its hinge sum is one precisely on that interval. Choose , giving both margins and both slacks . Primal and dual values are . With this choice, indeed for , both points are correctly classified despite their positive hinge loss and upper-box multipliers. At , the negative point ties at score zero and is misclassified under our convention.
Worked example 11.1.5
(A singular Gram matrix and nonunique support coefficients)
Use the same linear kernel with inputs and labels , and choose . Now for , and is the three-by-three all-ones matrix. Dual feasibility gives . Again the objective is , maximized at . Any nonnegative split is optimal. All these choices give , zero slacks, and value . Either duplicate may have zero multiplier while lying exactly on the margin. More generally, coefficient vectors and represent this same function, illustrating coefficient redundancy separately from dual feasibility.
Worked example 11.1.6
(A free intercept need not be unique)
With the linear kernel, put both inputs at zero and give opposite labels. Then is zero and every RKHS function has value zero at both observations. The optimal function is zero. Any minimizes , with slacks . The dual forces equal coefficients and maximizes their sum at , giving value . There is no coefficient strictly between zero and from which to recover a unique intercept. This is legitimate nonuniqueness, not a failed inverse or an infeasible training problem.
Concept lensStructural
Three choices for the intercept give three duals
Fixing removes the dual equality constraint entirely. Penalizing an optimized intercept by , , instead gives and adds to the dual objective, with no equality restriction. Only the unpenalized optimized intercept used above imposes . Treating a constant feature as an ordinary penalized RKHS coordinate therefore changes the model unless its penalty convention is adjusted explicitly.
When a free support coefficient exists, gives . Without one, use the remaining KKT inequalities to find permissible intercepts rather than dividing by a singular matrix or inventing a free support point. Coefficient redundancy and multiplier nonuniqueness also mean that a support-vector designation can depend on the selected optimal dual vector. It need not identify a uniquely essential subset of observations.
History of an idea
Allowing imperfect separation
Cortes and Vapnik's 1995 primary article explicitly extends support-vector classification to nonseparable training data. The soft-margin derivation here makes that tolerance algebraic through slacks and bounded dual coefficients; it proves optimization statements, not a generalization guarantee for every kernel and data set.
Common mistakes
The first error concerns the kernel itself: the dual derivation used positive semidefiniteness at a specific point.
Counterexample mode
A positive-looking similarity can destroy convexity
The symmetric two-point matrix has positive entries but . It cannot be an RKHS Gram matrix. With labels the feasible dual line would give , which is convex rather than concave. Inserting this similarity into the formulas does not retain the proved kernel-classification problem. Positive semidefiniteness, not merely symmetry or positive entries, is the needed repair.
Common mistake
(Canceling a singular Gram matrix)
Stationarity is the function identity . Written for a coefficient vector of , it reads , which does not give when is singular. In the three-point example, and both satisfy and represent the same .
Common mistake
(Reading box status as classification status)
A multiplier does not mean a strict margin, and does not mean a misclassification. In the three-point example, a duplicated point exactly on the margin can have ; in the first worked example, both points have yet are correctly classified for .
A quadratic-program optimum certifies training optimality under its assumptions, not population accuracy. Kernel selection, class weighting, numerical optimization tolerances, and statistical error bounds require additional analysis.
Summary
Hinge regularization has an attained finite-span solution with a unique RKHS function, even for singular kernels and contradictory labels. A carefully derived intercept convention determines the dual constraints. Compact hinge-slope geometry constructs multipliers, and a nonnegative gap identity proves strong duality and the KKT certificate. Exact Gram examples show why functions, intercepts, arbitrary coefficients, and support-vector multipliers must remain distinct.
Exercises
Quick check
(Repeat the first Gram example with . Find the dual optimum, function, intercept, slacks, and common objective value. Why are the coefficients now strictly inside the box?)
Maximize without the upper bound first.
Solution · Answer
The scalar maximum is at . Thus , the free-coefficient margin equations give , both slacks vanish, and both objective values are . The multiplier is below because the unit margin can be achieved without making the hinge active below its kink; the formal conclusion follows from the explicitly solved dual and KKT equations.
Quick check
(In the three-point example, write the full family of optimal vectors. Give two different choices and explain which observations are called support vectors for each.)
Use .
Solution · Answer
The family is for . At , indices two and three have positive multipliers; at , indices one and three do. The unique function and all margins are identical. Thus an individual duplicated boundary point may have zero multiplier, and a selected support set is not intrinsically unique.
Quick check
(Derive the additional dual term and intercept formula when is added. Show that it can be represented by replacing with in the no-intercept dual.)
Minimize over inside the Lagrangian.
Solution · Answer
Minimizing gives and minimum . No equality constraint is needed. The new quadratic is , exactly the no-intercept dual with the augmented kernel. Its constant feature is penalized, unlike the main free intercept.
Quick check
(Suppose a feasible pair has primal-dual gap at most . Prove its primal suboptimality is at most . Can that fact alone bound population classification error or the Euclidean distance between arbitrary coefficient representations?)
Combine weak duality with the gap identity.
Solution · Answer
Weak duality gives , so . Applying the gap identity with an optimal dual certificate also gives . These are optimization certificates for the specified training problem; population error needs statistical assumptions. When is singular, null coefficient directions can have arbitrarily large Euclidean length while representing the same function, so the gap alone cannot control distances between those representations. With positive definite that nullspace objection does not apply.