Regularized Empirical Objectives for Kernel Classifiers

Why the Objective Must Be Specified Precisely

A kernel classifier is not determined just by saying that it uses a hinge loss or a logistic loss. Its fitted score also depends on how the empirical loss is normalized and how the RKHS norm is penalized. In particular, the same numerical penalty parameter can describe different optimization problems when one objective uses a sum and another uses an average.

This distinction matters for both computation and interpretation. The regularization term can imply a bound on the fitted function’s RKHS norm, and that bound changes with the objective’s scaling. If the kernel is bounded on the diagonal, the norm bound also controls the score at each input. We make these dependencies explicit below.

Empirical Objectives for Binary Kernel Classifiers

Let \((x_1,y_1),\ldots,(x_n,y_n)\) be observed data, where \(x_i\) belongs to an input space \(\mathcal X\) and \(y_i\in\{-1,+1\}\). Let \(K\) be a positive semidefinite kernel with reproducing kernel Hilbert space (RKHS) \(\mathcal H\) and norm \(\|\cdot\|_{\mathcal H}\). A function \(f\in\mathcal H\) assigns the score \(f(x)\) to input \(x\); the predicted class is determined by the sign of that score, with a chosen convention for ties at zero.

Both losses below depend on the signed margin \(y f(x)\). A positive margin means the score points toward the observed label; a negative margin means it points the other way.

A common average-loss convention, used here as the reference convention, is

One can take \(\ell=\ell_{\mathrm h}\) or \(\ell=\ell_{\mathrm{log}}\). Both are nonnegative and convex as functions of the score. The factor \(1/2\) is a convention that simplifies derivatives of the squared norm; it does not change the substance of regularization, but it does affect the numerical value assigned to the penalty parameter.

Normalization and Penalty Conventions

Another standard form uses the sum of losses rather than their average:

Dividing this objective by \(n\) leaves its minimizers unchanged and gives

Thus the summed-loss objective with penalty parameter \(\rho\) has the same minimizer as the average-loss objective with parameter \(\lambda=\rho/n\). Keeping the same numerical parameter in both formulas generally does not give the same fit. More generally, multiplying an entire objective by a positive constant leaves its minimizer unchanged, but multiplying only its loss term or only its penalty term changes their relative weight.

Representer Form and Existence of a Minimizer

For finite data, minimizing either objective can be reduced to a finite-dimensional optimization. This is not an assumption that the RKHS itself is finite-dimensional; it follows because the data enter the loss only through the \(n\) evaluations \(f(x_i)\).

Proof. Let \(S=\operatorname{span}\{K(x_i,\cdot):1\leq i\leq n\}\), and let \(P_S f\) be the orthogonal projection of \(f\) onto \(S\). The reproducing property gives \(f(x_i)=\langle f,K(x_i,\cdot)\rangle_{\mathcal H}\). Since \(K(x_i,\cdot)\in S\), orthogonal projection preserves each observed evaluation:

Also, \(\|P_S f\|_{\mathcal H}\leq\|f\|_{\mathcal H}\). Thus projection leaves the empirical loss unchanged and cannot increase the penalty. It suffices to minimize over the finite-dimensional space \(S\).

On \(S\), the objective is continuous. It is coercive because the loss is nonnegative and \(\lambda\|f\|_{\mathcal H}^2/2\) tends to infinity as \(\|f\|_{\mathcal H}\) tends to infinity. A continuous coercive function on a finite-dimensional space attains its minimum. The empirical loss is convex in \(f\), and the squared Hilbert-space norm is strictly convex, so their sum is strictly convex and the minimizer is unique. The projection argument ensures that a minimizer can be taken in \(S\); uniqueness then implies the minimizer lies there. \(\square\)

If \(K_n\) is the \(n\)-by-\(n\) Gram matrix with entries \(K(x_i,x_j)\), the representation yields \(f(x_i)=(K_n\alpha)_i\) and \(\|f\|_{\mathcal H}^2=\alpha^\mathsf{T}K_n\alpha\). The coefficient vector need not be unique if the Gram matrix is singular, even though the minimizing function \(f\) is unique.

What the Penalty Implies About the Score

The zero function is a feasible competitor. Its hinge loss is \(1\) per observation, and its logistic loss is \(\log 2\) per observation. Comparing a minimizer with this competitor gives a direct norm bound.

Proof. For hinge loss, \(J_{n,\lambda}(0)=1\). Since \(\hat f\) minimizes the objective and empirical loss is nonnegative,

For logistic loss, \(J_{n,\lambda}(0)=\log 2\), and the same inequalities give \(\|\hat f\|_{\mathcal H}^2\leq2\log(2)/\lambda\). Finally, by the reproducing property and Cauchy–Schwarz,

This proves both claims. \(\square\)

Common Pitfalls and Practical Implications

The norm bound is a consequence of the stated objective, not a free-standing property of kernel classifiers. It depends on the loss at zero and on the coefficient multiplying the squared norm. For the summed-loss convention, comparison with zero instead gives \(\|\hat f\|_{\mathcal H}^2\leq2n/\rho\) for hinge loss and \(\|\hat f\|_{\mathcal H}^2\leq2n\log(2)/\rho\) for logistic loss.

• Wrong reasoning: “The average and summed objectives differ only by a constant, so the same penalty parameter gives the same classifier.” The correction is that dividing the whole summed objective by \(n\) also divides its penalty coefficient by \(n\). The minimizers match only after adjusting the parameter accordingly.
• Wrong reasoning: “A norm bound automatically gives the same score bound everywhere.” The correction is that the pointwise bound also uses \(K(x,x)\); a uniform score bound requires a uniform diagonal bound on the kernel over the inputs of interest.
• Wrong reasoning: “An unpenalized intercept is included in the RKHS norm bound.” The correction is that the proof bounds only the quantity actually penalized. If an intercept is added without a penalty, comparison with the zero function does not by itself bound that intercept or the full score.

In applied work, report the loss normalization, the exact penalty term, and whether an intercept is penalized. These details make the fitted objective interpretable and allow penalty values and bounds to be compared without ambiguity.