Squared, Logistic, and Hinge Losses in Representer Form

From an RKHS Problem to a Coefficient Problem

A regularized learning problem in a reproducing-kernel Hilbert space (RKHS) appears to optimize over an infinite-dimensional collection of functions. With empirical loss, however, the data enter only through finitely many evaluations. The representer theorem makes this structure explicit: under a norm penalty, a minimizer can be written using kernel sections centered at the observed inputs. Once written that way, the three common empirical losses considered here become finite-dimensional objectives in a coefficient vector.

We will use a fixed sample $(x_i,y_i)_{i=1}^n$, an RKHS $\mathcal H$ with kernel $k$, and a regularization parameter $\lambda>0$. Define the Gram matrix $K$ by $K_{ij}=k(x_i,x_j)$. For a coefficient vector $\alpha\in\mathbb R^n$, let $f_\alpha=\sum_{j=1}^n\alpha_j k(x_j,\cdot)$. The predictions on the training inputs are $K\alpha$, while the squared RKHS norm is $\alpha^\top K\alpha$. These identities hold even if $K$ is singular.

Definition: Given a loss function $\ell(y,t)$, the regularized empirical-risk objective in this tutorial is $$ J(f)=\frac{1}{n}\sum_{i=1}^n \ell(y_i,f(x_i))+\frac{\lambda}{2}\|f\|_{\mathcal H}^2. $$ The factor $1/n$ averages the losses, and the penalty is scaled by $\lambda/2$. All coefficient objectives below use this same convention.

For squared loss, responses $y_i$ are real-valued and $\ell(y,t)=(y-t)^2$. For logistic and hinge loss, labels are coded $y_i\in\{-1,+1\}$; their margins are $y_i f(x_i)$. The logistic loss is $\log(1+\exp(-y_i f(x_i)))$, and the hinge loss is $\max\{0,1-y_i f(x_i)\}$.

Why the Minimizer Has a Finite Representer

Let $S=\operatorname{span}\{k(x_1,\cdot),\ldots,k(x_n,\cdot)\}$, a finite-dimensional subspace of $\mathcal H$. Every $f\in\mathcal H$ has an orthogonal decomposition $f=f_S+f_\perp$, where $f_S\in S$ and $f_\perp$ is orthogonal to $S$. By the reproducing property, $f_\perp(x_i)=\langle f_\perp,k(x_i,\cdot)\rangle_{\mathcal H}=0$ at every observed input. Thus replacing $f$ by $f_S$ leaves every empirical loss unchanged. The norm penalty, in contrast, decreases if $f_\perp\ne0$.

Theorem: Suppose the empirical objective is $J(f)=n^{-1}\sum_{i=1}^n\ell(y_i,f(x_i))+\lambda\|f\|_{\mathcal H}^2/2$, where $\lambda>0$, each loss is nonnegative and continuous in its prediction argument, and $\mathcal H$ is an RKHS. Then $J$ attains a minimum, and every minimizer belongs to $S$. In particular, a minimizer has the form $f_\alpha=\sum_{j=1}^n\alpha_j k(x_j,\cdot)$.

Proof. Orthogonality gives $\|f\|_{\mathcal H}^2=\|f_S\|_{\mathcal H}^2+\|f_\perp\|_{\mathcal H}^2$, and the evaluations of $f$ and $f_S$ agree on the sample. Consequently,

J(f)=J(f_S)+\frac{\lambda}{2}\|f_\perp\|_{\mathcal H}^2.

If $f$ is a minimizer and $f_\perp\ne0$, then $J(f_S)<J(f)$, a contradiction. Therefore every minimizer lies in $S$. To verify attainment, it is enough to minimize over $S$. This space is finite-dimensional, and the objective is continuous there. Its loss term is nonnegative, so $J(f)\ge\lambda\|f\|_{\mathcal H}^2/2$. Hence every sublevel set in $S$ is bounded; it is also closed by continuity and therefore compact. A minimizing sequence can be restricted to a nonempty sublevel set, has a convergent subsequence, and its limit attains the minimum. The spanning definition of $S$ gives the stated coefficient representation. $\square$

For $f_\alpha$, the reproducing property gives $f_\alpha(x_i)=\sum_j\alpha_j k(x_j,x_i)=(K\alpha)_i$. Also,

\|f_\alpha\|_{\mathcal H}^2 =\sum_{i,j=1}^n\alpha_i\alpha_j k(x_i,x_j) =\alpha^\top K\alpha.

These formulas turn the theorem into concrete coefficient objectives. Positive semidefiniteness of $K$ ensures that the displayed penalty is nonnegative. If $K$ is singular, different coefficient vectors can represent the same function; the objective is still a valid objective for the represented function.

Three Explicit Coefficient Objectives

Write $y=(y_1,\ldots,y_n)^\top$. Substituting the predictions and norm into the objective gives the following formulas.

Coefficient objectives: For squared loss, $$ J_{\mathrm{sq}}(\alpha)=\frac{1}{n}\|y-K\alpha\|_2^2+\frac{\lambda}{2}\alpha^\top K\alpha. $$ For logistic loss with $y_i\in\{-1,+1\}$, $$ J_{\mathrm{log}}(\alpha)=\frac{1}{n}\sum_{i=1}^n\log\!\left(1+\exp\!\left[-y_i(K\alpha)_i\right]\right)+\frac{\lambda}{2}\alpha^\top K\alpha. $$ For hinge loss with $y_i\in\{-1,+1\}$, $$ J_{\mathrm{hinge}}(\alpha)=\frac{1}{n}\sum_{i=1}^n\max\!\left\{0,1-y_i(K\alpha)_i\right\}+\frac{\lambda}{2}\alpha^\top K\alpha. $$

The loss terms differ, but the RKHS penalty is always $\lambda\alpha^\top K\alpha/2$. For logistic loss the coefficient objective is smooth. Hinge loss is convex but not differentiable where a margin equals one. These differences matter to optimization, but not to the representer reduction.

Worked Example: Squared Loss and Its Coefficient Solution

Take $n=2$, $y=(1,0)^\top$, $\lambda=1/2$, and $$ K=\begin{pmatrix}1&1/2\\1/2&1\end{pmatrix}. $$ This matrix is positive definite: its eigenvalues are $3/2$ and $1/2$. For this example the coefficient objective is $$ J_{\mathrm{sq}}(\alpha)=\frac12\|y-K\alpha\|_2^2+\frac14\alpha^\top K\alpha. $$

Differentiating the objective gives $$ \nabla J_{\mathrm{sq}}(\alpha)=\frac{2}{n}K(K\alpha-y)+\lambda K\alpha =\frac{2}{n}K\left((K+n\lambda I/2)\alpha-y\right). $$ Here $K+n\lambda I/2=K+\tfrac12 I$, so the coefficient vector that makes the expression in parentheses zero is $$ \hat\alpha= \begin{pmatrix}3/2&1/2\\1/2&3/2\end{pmatrix}^{-1} \begin{pmatrix}1\\0\end{pmatrix} = \begin{pmatrix}3/4\\-1/4\end{pmatrix}. $$ Indeed, the matrix determinant is $9/4-1/4=2$, and its inverse is $\frac12\begin{pmatrix}3/2&-1/2\\-1/2&3/2\end{pmatrix}$. The fitted values are $$ K\hat\alpha= \begin{pmatrix}5/8\\1/8\end{pmatrix}, \qquad y-K\hat\alpha= \begin{pmatrix}3/8\\-1/8\end{pmatrix}. $$ The squared residual contribution is $\frac12((3/8)^2+(-1/8)^2)=5/64$. The penalty contribution is $\frac14\hat\alpha^\top K\hat\alpha=\frac14(7/16)=7/64$. Thus $J_{\mathrm{sq}}(\hat\alpha)=12/64=3/16$.

A Closed-Form Result for Squared Loss

The preceding calculation follows from a general coefficient formula. The scaling in the empirical average and the penalty must be kept consistent when differentiating.

Theorem: For squared loss under the objective convention above, with $K$ positive semidefinite and $\lambda>0$, one minimizer is $$ \hat\alpha=(K+n\lambda I/2)^{-1}y. $$ The matrix being inverted is positive definite. The represented minimizing function is unique, although its coefficient vector need not be unique when $K$ is singular.

Proof. Differentiating $n^{-1}\|y-K\alpha\|_2^2+\lambda\alpha^\top K\alpha/2$, using symmetry of $K$, yields $$ \nabla J_{\mathrm{sq}}(\alpha)=\frac{2}{n}K(K\alpha-y)+\lambda K\alpha =\frac{2}{n}K\left((K+n\lambda I/2)\alpha-y\right). $$ Since $K$ is positive semidefinite and $n\lambda/2>0$, all eigenvalues of $K+n\lambda I/2$ are strictly positive. It is therefore invertible. The stated $\hat\alpha$ satisfies $(K+n\lambda I/2)\hat\alpha=y$, so its gradient is zero. The objective is convex: the squared residual is convex in $K\alpha$, and the penalty is a positive-semidefinite quadratic form. A zero gradient of a differentiable convex function is a global minimum. Finally, on the RKHS, the squared norm is strictly convex and the empirical loss is convex, so their sum is strictly convex as a function of $f$; hence the minimizing function is unique. If $K$ is singular, coefficient vectors differing by a vector in the null space of $K$ can encode that same function. $\square$

Worked Logistic and Hinge Examples

Worked Example: Logistic Loss with Two Opposite Labels

Let $n=2$, $K=I$, $y=(1,-1)^\top$, and $\lambda=1/(8\log 3)$. Consider $\alpha=(a,-a)^\top$. Its two signed margins are $y_1(K\alpha)_1=a$ and $y_2(K\alpha)_2=a$. The coefficient objective reduces to $$ J_{\mathrm{log}}(a,-a)=\log(1+\exp(-a))+\lambda a^2. $$ Its derivative is $-1/(1+\exp(a))+2\lambda a$. At $a=\log 3$, this derivative is $-1/4+2(1/(8\log 3))\log 3=0$. The second derivative is $\exp(a)/(1+\exp(a))^2+2\lambda>0$, so the restricted objective is strictly convex and this is its unique minimum along the stated symmetric form. In fact, because $K=I$, the full objective separates into one strictly convex term for each coefficient. Each term is minimized at the corresponding signed coefficient, so the full minimizer is $\hat\alpha=(\log 3,-\log 3)^\top$.

Worked Example: Hinge Loss and a Margin Below One

Let $n=2$, $K=I$, $y=(1,1)^\top$, and $\lambda=1$. For $\alpha=(a,a)^\top$, both margins equal $a$, and $$ J_{\mathrm{hinge}}(a,a)=\max\{0,1-a\}+a^2. $$ For $a<1$, this is $1-a+a^2$, whose derivative $-1+2a$ vanishes at $a=1/2$. For $a\ge1$, the objective is $a^2$, which is at least $1$. At $a=1/2$, the objective is $1-1/2+1/4=3/4$, less than $1$. Thus the symmetric minimizer is $a=1/2$. Since $K=I$, the full objective separates into the sum of two identical one-coordinate objectives, each with its unique minimizer $1/2$; consequently $\hat\alpha=(1/2,1/2)^\top$ minimizes the full objective. The margins are $1/2$, not one: the finite norm penalty balances the loss, so the optimizer need not reach the hinge margin threshold.

Scaling, Singular Matrices, and a Common Pitfall

The squared-loss solution depends on the exact constants in the objective. Under the convention here, differentiating the average squared loss contributes $2/n$, while differentiating the penalty $\lambda\alpha^\top K\alpha/2$ contributes $\lambda K\alpha$. Factoring gives $K+n\lambda I/2$, not $K+n\lambda I$. A different definition of the squared-loss objective can lead to a different constant, so the objective must be stated before quoting a formula.

Wrong reasoning: Copy a coefficient formula from an objective with different loss or penalty scaling, then assume it solves the displayed problem.
Correction: Differentiate the stated objective, retain its factors, and check that the proposed coefficients make the gradient zero. In the squared-loss example above, the corrected coefficients give fitted values $(5/8,1/8)^\top$ and objective $3/16$.
Another pitfall: Treat $\alpha$ as unique whenever the function minimizer is unique. If $K$ is singular, the map $\alpha\mapsto f_\alpha$ is not one-to-one. The fitted function and its predictions can be unique while coefficient representations are not.
Hinge-loss pitfall: Assume that every training margin must equal or exceed one. Hinge loss penalizes margins below one, but a finite norm penalty can make a smaller margin optimal, as the example demonstrates.

Key takeaway: For all three losses, replace each training prediction by $(K\alpha)_i$ and the squared RKHS norm by $\alpha^\top K\alpha$. The loss determines the data-fit term; the same RKHS penalty completes each finite-dimensional objective.

Check Your Understanding

Work through these questions using the objective scaling and notation established above.

Write the coefficient objective for logistic loss if $n=4$, using $K$, $\alpha$, and labels in $\{-1,+1\}$.
Explain why adding a component orthogonal to every training-point kernel section cannot improve a regularized empirical objective.
For squared loss, identify the matrix in the closed-form coefficient solution and state why it is invertible when $\lambda>0$.
If $K$ is singular, which quantity can be unique: the coefficient vector, the fitted function, or both? Explain.
In the hinge example, why is a margin of $1/2$ compatible with optimality even though the hinge loss is positive?