Finite-Dimensional Optimization over Gram Coefficients

From Functions to Coefficients

An RKHS optimization problem appears infinite-dimensional because its decision variable is a function. For empirical risk, however, the data enter through only finitely many evaluations, \(f(x_1),\ldots,f(x_n)\). The representer theorem says that, with a norm penalty, an optimizer can be sought in the span of the kernel sections at those observed inputs. This tutorial makes that reduction explicit: it gives the coefficient objective, its Gram-matrix penalty, and the formula for predictions away from the training inputs.

Let \(\mathcal H\) be a reproducing kernel Hilbert space with kernel \(k\), and let \((x_i,y_i)\), \(i=1,\ldots,n\), be the observed data. Consider a regularized empirical risk

Here \(\ell(y,t)\) is the loss for response \(y\) and fitted value \(t\). The factor \(1/2\) is a convention that simplifies derivatives. Define the Gram matrix \(K\) by \(K_{ij}=k(x_i,x_j)\). Since \(k\) is a positive-semidefinite kernel, \(K\) is symmetric and positive semidefinite.

The Gram-Matrix Objective

The reproducing property gives \(f(x_i)=\langle f,k(x_i,\cdot)\rangle_{\mathcal H}\). Apply it to \(f_\alpha\): the fitted value at \(x_i\) is a sum of kernel evaluations against the coefficients. In vector form, the training predictions are \(K\alpha\).

The penalty follows directly from bilinearity of the inner product. Each pair of kernel sections contributes its inner product \(k(x_i,x_j)\), so the squared RKHS norm is a quadratic form in \(\alpha\).

Consequently, the coefficient form of the regularized risk is

This is an optimization problem over \(n\) real coefficients rather than over all functions in \(\mathcal H\). Its data-fit term depends on \(\alpha\) through \(K\alpha\); its penalty is not generally \(\alpha^\mathsf{T}\alpha\). The Gram matrix is what connects the coefficient coordinates to both predictions and RKHS geometry.

Why the Finite-Dimensional Reduction Is Exact

The key fact is orthogonal projection onto the finite-dimensional subspace \(S=\operatorname{span}\{k(x_i,\cdot):i=1,\ldots,n\}\). The subspace is closed because every finite-dimensional subspace of a Hilbert space is closed, so the orthogonal projection \(P_S f\) exists for every \(f\in\mathcal H\).

Proof. Write \(f=P_Sf+(f-P_Sf)\). The second term is orthogonal to every element of \(S\), and hence to each \(k(x_i,\cdot)\). By the reproducing property,

Therefore replacing \(f\) with \(P_Sf\) leaves every loss term unchanged. Orthogonality also gives the Pythagorean identity

Since \(\lambda>0\), it follows that \(J(P_Sf)\leq J(f)\). Every function in \(S\) is already in \(\mathcal H\), so restricting the search to \(S\) cannot lower the infimum; the projection inequality shows it cannot raise the infimum either. If \(f\) is a minimizer, a nonzero \(f-P_Sf\) would make the penalty strictly larger while leaving the loss unchanged. Thus \(f=P_Sf\). \(\square\)

This argument also explains why the reduction does not require the Gram matrix to be invertible. The functions in \(S\) have coefficient representations, and their predictions and norms are given by the formulas above. Questions about whether different coefficient vectors represent the same function require separate care.

Predictions at New Inputs

Once the coefficients have been chosen, evaluating the fitted function at a new input \(z\) uses its kernel evaluations with the training inputs. Define \(k_z=(k(x_1,z),\ldots,k(x_n,z))^\mathsf{T}\). The prediction is a dot product of this vector with \(\alpha\), not a new optimization problem.

Optimization and a Stationarity Check

When \(\ell(y,t)\) is differentiable in \(t\), the coefficient objective has a convenient gradient. Let \(r\in\mathbb R^n\) have entries \(r_i=\partial_2\ell(y_i,(K\alpha)_i)\), where \(\partial_2\) denotes differentiation with respect to the fitted value. Symmetry of \(K\) and the chain rule give

Indeed, the derivative of the data-fit term is \(K^\mathsf{T}r/n=Kr/n\), and the derivative of \(\lambda\alpha^\mathsf{T}K\alpha/2\) is \(\lambda K\alpha\). A differentiable objective at an unconstrained minimum must have zero gradient. If the loss is convex in its fitted value, the objective is convex in \(\alpha\), so any stationary point is a global minimizer. The gradient equation is a useful check, but it does not by itself guarantee that a proposed point is optimal for a nonconvex loss.

Common Pitfall and Practical Significance

A frequent error is to penalize the coefficient vector by \(\|\alpha\|_2^2\) simply because the problem has been written in coordinates. The RKHS penalty is instead \(\alpha^\mathsf{T}K\alpha\), as follows from the inner products between kernel sections. Replacing it with \(\alpha^\mathsf{T}\alpha\) generally changes the optimization problem and the fitted function. The two expressions coincide only under particular conditions on the Gram matrix.

The finite-dimensional form matters because it turns function-space fitting into a calculation involving an \(n\times n\) matrix and a vector of coefficients. It also separates two tasks cleanly: optimize using the training Gram matrix, then predict using kernel evaluations between new inputs and the training inputs. The representation is exact for norm-regularized empirical risk, not an approximation obtained by selecting a small set of basis functions.