Regularized Empirical Risk in an RKHS

Why Penalize Empirical Risk?

In supervised learning, a function \(f\) is assessed by how well its predictions match the responses observed at the training inputs. An empirical loss depends only on those finitely many predictions. By itself, it may not distinguish between functions that agree on the training data but behave very differently elsewhere. A squared RKHS norm penalty adds a preference for functions with smaller norm.

The penalty serves a mathematical purpose as well as a modeling one: when the loss is lower bounded, it prevents a sequence of candidate functions from having unbounded RKHS norm while keeping the objective small. That control makes it possible to prove that a minimizer exists. The assumptions on the loss matter; merely writing down a penalty does not guarantee that every objective has a minimizer.

Definition of Regularized Empirical Risk

Let \(\mathcal H\) be a real RKHS of functions on an input set \(\mathcal X\), with reproducing kernel \(k\). The observed data are \((x_i,y_i)\), \(i=1,\ldots,n\), where \(x_i\in\mathcal X\) and \(y_i\in\mathcal Y\). For each observed response, let \(\phi_i:\mathbb R\to(-\infty,\infty]\) be a loss as a function of the prediction. For example, a common loss \(L(t,y)\) gives \(\phi_i(t)=L(t,y_i)\).

This definition separates the two parts of the objective. The empirical term uses only the \(n\) scalar values \(f(x_1),\ldots,f(x_n)\); it does not directly use all the other values of \(f\). The penalty uses the RKHS norm. By the reproducing property, \(f(x)=\langle f,k(\cdot,x)\rangle_{\mathcal H}\), so each evaluation is a continuous linear functional and satisfies \[ |f(x)|\leq \|f\|_{\mathcal H}\sqrt{k(x,x)}. \] Thus finite evaluations are well-defined and controlled by the norm.

The normalization \(1/n\) and the factor \(1/2\) are conventions, not requirements. Changing either changes the numerical scale of \(\lambda\). Here, \(\lambda\) is strictly positive: with \(\lambda=0\), the norm control used in the existence result below is absent.

Worked Objectives

Existence of a Minimizer

Here is a useful sufficient condition. It does not require convex losses. Lower semicontinuity prevents an objective value from dropping suddenly at a limit, and a lower bound on each loss ensures that the penalty controls any sequence whose objective approaches its infimum.

Proof. Since \(\phi_i(0)<\infty\), the zero function has finite objective, so the infimum \(m=\inf_{f\in\mathcal H}J_\lambda(f)\) is at most \(J_\lambda(0)<\infty\). Let \(m_i\) be a finite lower bound for \(\phi_i\). The penalty is nonnegative, so

Choose a minimizing sequence \((f_j)\) with \(J_\lambda(f_j)\to m\). Its objective values are bounded above, and the displayed inequality, together with \(\lambda>0\), implies that \((f_j)\) is bounded in \(\mathcal H\). A bounded sequence in a Hilbert space has a weakly convergent subsequence; write that subsequence as \(f_{j_r}\rightharpoonup f\).

For each observed input \(x_i\), evaluation \(g\mapsto g(x_i)=\langle g,k(\cdot,x_i)\rangle_{\mathcal H}\) is a bounded linear functional. Therefore \(f_{j_r}(x_i)\to f(x_i)\). Lower semicontinuity of \(\phi_i\) gives \[ \phi_i(f(x_i))\leq \liminf_{r\to\infty}\phi_i(f_{j_r}(x_i)). \] The squared Hilbert norm is weakly lower semicontinuous. Since there are finitely many loss terms, their sum and the penalty together are weakly lower semicontinuous, and hence \[ J_\lambda(f)\leq \liminf_{r\to\infty}J_\lambda(f_{j_r})=m. \] The definition of \(m\) also gives \(J_\lambda(f)\geq m\). Thus \(J_\lambda(f)=m\), as required. \(\square\)

The theorem gives sufficient conditions, not necessary ones. For example, the loss may take the value \(+\infty\) at some predictions, provided the stated lower semicontinuity, lower bound, and finite value at zero hold.

When Is the Minimizer Unique?

Convexity of the losses supplies a simple uniqueness guarantee. Convexity means \(\phi_i((1-t)a+tb)\leq (1-t)\phi_i(a)+t\phi_i(b)\) for \(a,b\in\mathbb R\) and \(0<t<1\). The norm penalty is strictly convex, so it distinguishes any two different functions, even if they give identical predictions at the observed inputs.

Proof. Let \(f,g\in\mathcal H\) be distinct and \(0<t<1\). Convexity of each loss and linearity of evaluation imply that the empirical term at \((1-t)f+tg\) is no greater than the corresponding weighted average of its values at \(f\) and \(g\). For the penalty, the Hilbert-space identity

shows a strict reduction, because \(f\ne g\) and \(\lambda t(1-t)>0\). Combining the two inequalities yields

Thus \(J_\lambda\) is strictly convex. If two distinct functions both minimized it, their strict convex combination would have a smaller objective, a contradiction. \(\square\)

Common Pitfall: A Penalty Alone Does Not Ensure Existence

A frequent mistake is to assume that adding a positive squared-norm penalty guarantees a minimum for any loss. Consider again the constant-function RKHS, but now use the continuous loss \(\phi(t)=-t^4\). For any \(\lambda>0\),

There is no minimizer: the objective is unbounded below. The correction is to check the loss assumptions rather than infer existence from the penalty alone. A lower bound on each loss is a convenient sufficient condition for the coercive control in the theorem. In applications, the loss and its domain should be checked explicitly.

Regularized empirical risk is a useful foundation for kernel learning because it states the fitting criterion at the observed inputs while controlling function size in the chosen RKHS. The existence and uniqueness arguments depend on distinct properties: lower semicontinuity and a lower bound support existence, while convexity combined with the squared norm penalty gives uniqueness. Neither conclusion should be assumed without its hypotheses.