RKHS regularization, kernels, and support-vector machines

Set $V:=\mathrm{span}(M\cup \{f\})$. Since $M$ is finite-dimensional and adjoining one vector increases dimension by at most one, $V$ is a finite-dimensional real inner-product space with the inherited inner product; $M$ is a subspace of $V$ and $f\in V$. Apply [F1] inside $V$ and set $p:=P_{M}f$.

By [F2], $p\in M$ and $f-p\in M^{\perp }$.

Since $p\in M$ and $f-p\in M^{\perp }$, Pythagoras [F3] gives $\mathrm{\parallel }f{\mathrm{\parallel }}^2=\mathrm{\parallel }p{\mathrm{\parallel }}^2+\mathrm{\parallel }f-p{\mathrm{\parallel }}^2\ge \mathrm{\parallel }p{\mathrm{\parallel }}^2$, so $\mathrm{\parallel }p\mathrm{\parallel }\le \mathrm{\parallel }f\mathrm{\parallel }$. If $q\in M$ also has $f-q\in M^{\perp }$, then for every $r\in M$, [F3] gives $\mathrm{\parallel }f-r{\mathrm{\parallel }}^2=\mathrm{\parallel }f-q{\mathrm{\parallel }}^2+\mathrm{\parallel }q-r{\mathrm{\parallel }}^2\ge \mathrm{\parallel }f-q{\mathrm{\parallel }}^2$. Thus $q$ is a nearest point to $f$, and [F1] forces $q=p$.

Let $E_0$ be the finitely supported functions on $X$ and define $B(a,b)={\sum }_{x,z}a(x)b(z)k(x,z)$, where each sum is over the finite supports. Symmetry and bilinearity follow from symmetry of $k$ and finite-sum algebra. For any $a$, listing its finite support gives $B(a,a)\ge 0$ by [F1].

For $a,b\in E_0$ and $t\in \mathbb{R}$, $0\le B(a+tb,a+tb)=B(a,a)+2tB(a,b)+t^{2}B(b,b)$. If $B(b,b)>0$, nonnegativity of this quadratic for all $t$ gives $B(a,b{)}^2\le B(a,a)B(b,b)$; if $B(b,b)=0$, its linear coefficient must vanish, so $B(a,b)=0$.

It follows that every $a\in N:=\{a:B(a,a)=0\}$ satisfies $B(a,b)=0$ for every $b\in E_0$. Hence $N$ is a subspace and the form descends to a well-defined positive definite inner product on $Q:=E_0\mathrm{/}N$: changing a representative by an element of $N$ does not change any pairing, and a quotient class has zero squared norm exactly when it is the zero class.

The induced inner product makes $Q$ a real inner-product space. By [F2] and [A1], its norm metric has a metric completion with compatible Banach structure, hence a norm completion; the inner product extends uniquely and makes the completion $\widehat{Q}$ a real Hilbert space.

For each $x\in X$, the image $k_x$ of $[{\delta }_x]\in Q$ satisfies $\mathrm{\parallel }{k}_x{\mathrm{\parallel }}^2=B({\delta }_x,{\delta }_x)=k(x,x)\ge 0$. Thus the finite kernel sections are elements of $\widehat{Q}$, and their span is dense because the image of $Q$ is dense in its completion.

For $a\in E_0$, the quotient pairing gives $⟨[a],k_x⟩={\sum }_{z\in \mathrm{supp}(a)}a(z)k(z,x)$, independently of the representative by [step 3.1]. Given $h\in \widehat{Q}$, density in [step 4.1] provides an approximating sequence $[a_m]\to h$. By [F3], the real sequence $⟨[a_m],k_x⟩$ is Cauchy, and if $[b_m]\to h$ is another such sequence then $\mathrm{\mid }⟨[a_m-b_m],k_x⟩\mathrm{\mid }\le \mathrm{\parallel }[a_m-b_m]\mathrm{\parallel }\mathrm{\parallel }{k}_x\mathrm{\parallel }\to 0$, so its limit is independent of the approximants. The extended inner product also satisfies [F3], hence this limit equals $⟨h,k_x⟩$.

Define the associated function of $h\in \widehat{Q}$ by $h(x):=⟨h,k_x⟩$. Applying the extended pairing to $k_z$ gives $k_z(x)=⟨k_z,k_x⟩=B({\delta }_z,{\delta }_x)=k(z,x)=k(x,z)$, so $k_x$ is exactly the section $k(\cdot ,x)$ and $⟨h,k_x⟩=h(x)$ for every $h$.

If $h(x)=0$ for every $x\in X$, then $h$ is orthogonal to every section $k_x$ and therefore to their dense span from [step 5.1]. Continuity of the inner product gives $⟨h,h⟩=0$, so positive definiteness gives $h=0$. Thus the associated-function map is injective and identifies $\widehat{Q}$ with a Hilbert space of functions having reproducing kernel $k$.

Regard $K$ as an endomorphism of ${\mathbb{R}}^n$ with its usual dot product. By [A1], $K$ is symmetric, hence self-adjoint. By [F1], there are an orthonormal eigenbasis $q_1,\dots ,q_n$ and real eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$ with $K{q}_{\mathrm{\ell }}={\lambda }_{\mathrm{\ell }}{q}_{\mathrm{\ell }}$.

Since $\mathrm{\parallel }{q}_{\mathrm{\ell }}{\mathrm{\parallel }}_2=1$, [A1] gives ${\lambda }_{\mathrm{\ell }}=q_{\mathrm{\ell }}^{T}K{q}_{\mathrm{\ell }}\ge 0$ for each $\mathrm{\ell }$. Thus each $\sqrt{{\lambda }_{\mathrm{\ell }}}$ is a real number, including when ${\lambda }_{\mathrm{\ell }}=0$.

For $1\le i\le n$, define $z_i=(\sqrt{{\lambda }_1}(q_1{)}_i,\dots ,\sqrt{{\lambda }_n}(q_n{)}_i)\in {\mathbb{R}}^n$. The spectral decomposition $K={\sum }_{\mathrm{\ell }=1}^n{\lambda }_{\mathrm{\ell }}{q}_{\mathrm{\ell }}{q}_{\mathrm{\ell }}^T$ then gives $z_i^T{z}_j={\sum }_{\mathrm{\ell }=1}^n{\lambda }_{\mathrm{\ell }}(q_{\mathrm{\ell }}{)}_i(q_{\mathrm{\ell }}{)}_j=K_{ij}=k(x_i,x_j)$ for all $i,j$.

Let $M:=\mathrm{span}\{k_{x_i}:1\le i\le n\}$. It is finite-dimensional. Apply [F2] to $f$ and $M$, and write $f=p+h$ with $p\in M$ and $h\perp M$.

For every $i$, [F1] gives $h(x_i)=⟨h,k_{x_i}⟩=0$, so $p(x_i)=f(x_i)$. Hence the loss terms in $J(p)$ and $J(f)$ agree.

The norm-contraction clause of [F2] gives $\mathrm{\parallel }p{\mathrm{\parallel }}_{\mathcal{H}}\le \mathrm{\parallel }f{\mathrm{\parallel }}_{\mathcal{H}}$. Monotonicity of $\mathrm{\Omega }$ therefore gives $J(p)\le J(f)$.

Since $f$ is a minimizer, $J(f)\le J(p)$. Thus $J(p)=J(f)$ and $p$ is also a minimizer; by its definition $p$ is a finite linear combination of the sample kernel sections.

The tuple $w=0$, $b=0$, and ${\xi }_i=1$ is feasible and has objective $Cn$. Every feasible objective is nonnegative, so the primal infimum lies in $[0,Cn]$.

Let $M=\mathrm{span}\{\varphi (x_i):1\le i\le n\}$. For any feasible tuple, project $w$ onto $M$ using [F1]. The residual is orthogonal to every $\varphi (x_i)$, so all sample scores and constraints are unchanged, while the norm does not increase. Thus minimizing over $M\times \mathbb{R}\times {\mathbb{R}}^n$ has the same infimum as minimizing over the full feature space.

If all labels are $+1$, then $w=0$, $b=1$, and $\xi =0$ is feasible with objective $0$, which is globally minimal by step 1.1. If all labels are $-1$, then $w=0$, $b=-1$, and $\xi =0$ gives the same conclusion.

Suppose both labels occur. Set $R={\max }_i\mathrm{\parallel }\varphi (x_i)\mathrm{\parallel }$ and let $S$ be the subset of $M\times \mathbb{R}\times {\mathbb{R}}^n$ consisting of feasible tuples with objective at most $Cn$. By step 1.1, $S$ is nonempty. It is closed because the constraints are continuous affine inequalities and the objective is continuous; continuity of each score follows from [F2]. Every tuple in $S$ satisfies $\mathrm{\parallel }w\mathrm{\parallel }\le \sqrt{2Cn}$ and $0\le {\xi }_i\le n$. Choose indices $i_{+}$ and $i_{-}$ with labels $+1$ and $-1$. Their constraints and [F2] give $b\ge 1-n-\sqrt{2Cn}R$ and $b\le n-1+\sqrt{2Cn}R$, so $b$ is bounded. Equip the product space with the inner product $⟨(w,b,\xi ),(w^{\mathrm{\prime }},b^{\mathrm{\prime }},{\xi }^{\mathrm{\prime }})⟩=⟨w,w^{\mathrm{\prime }}⟩+b{b}^{\mathrm{\prime }}+{\xi }^T{\xi }^{\mathrm{\prime }}$. It has finite dimension $d=\dim M+1+n\ge 1$, so [F3] gives an orthonormal basis identifying it with ${\mathbb{R}}^d$. Hence $S$ is a nonempty closed bounded subset of that Euclidean space. By [F4], the continuous objective attains a minimum on $S$. Any feasible tuple outside $S$ has objective greater than $Cn$, whereas $S$ contains a feasible tuple of objective $Cn$; therefore this minimum is also the global primal minimum. By step 1.2 it is a full-space minimizer with $w\in M$.

Let $(w_{\ast },b_{\ast },{\xi }_{\ast })$ be any primal minimizer, which exists by [F1], and let $M=\mathrm{span}\{\varphi (x_i):1\le i\le n\}$. Project $w_{\ast }$ onto $M$ using [F2]; its residual is orthogonal to every $\varphi (x_i)$, so the projection preserves all margins and slacks. If the residual were nonzero, [F3] would give a strictly smaller squared norm and hence a strictly smaller objective, contradicting minimality because the regularization coefficient is $1\mathrm{/}2>0$. Thus every primal minimizer has $w_{\ast }\in M$.

Identify $M$ with a Euclidean space using an orthonormal basis. In the finite-dimensional variable space $M\times \mathbb{R}\times {\mathbb{R}}^n$, the objective is a proper continuous convex function and the $2n$ inequality constraints are continuous affine functions with the sign convention [F7]. No inequality is removed by the domain-preserving convention in [F5]: all functions have full domain, and sending the corresponding ${\xi }_i\to -\mathrm{\infty }$ makes either constraint function positive. There are no primal equality rows, so the full-row-rank condition in [F5] holds vacuously.

The point $w=0$, $b=0$, ${\xi }_i=2$ has strict slack in every constraint: $1-{\xi }_i-y_i(⟨w,\varphi (x_i)⟩+b)=-1<0$ and $-{\xi }_i=-2<0$. The objective and all constraint domains are the whole finite-dimensional variable space, so this point lies in their relative interiors. Together with the finite attained primal value from [F1], this verifies every hypothesis of [F6].

Write the margin constraints as $g_i^{(m)}:=1-{\xi }_i-y_i(⟨w,\varphi (x_i)⟩+b)\le 0$ and the nonnegative-slack constraints as $g_i^{(s)}:=-{\xi }_i\le 0$. Give them multipliers ${\alpha }_i\ge 0$ and ${\mu }_i\ge 0$, respectively. The Lagrangian is $L=\frac{1}{2}\mathrm{\parallel }w{\mathrm{\parallel }}^2+C{\sum }_i{\xi }_i+{\sum }_i{\alpha }_i{g}_i^{(m)}+{\sum }_i{\mu }_i{g}_i^{(s)}$.

Put $v:={\sum }_i{\alpha }_i{y}_i\varphi (x_i)$. The terms of $L$ depending on $w$ are $\frac{1}{2}\mathrm{\parallel }w{\mathrm{\parallel }}^2-⟨w,v⟩=\frac{1}{2}\mathrm{\parallel }w-v{\mathrm{\parallel }}^2-\frac{1}{2}\mathrm{\parallel }v{\mathrm{\parallel }}^2$, so their infimum is $-\frac{1}{2}\mathrm{\parallel }v{\mathrm{\parallel }}^2$. The infimum over the unrestricted bias $b$ is finite exactly when ${\sum }_i{\alpha }_i{y}_i=0$, and the infimum over each unrestricted ${\xi }_i$ is finite exactly when $C-{\alpha }_i-{\mu }_i=0$. Thus the dual-feasible conditions are ${\sum }_i{\alpha }_i{y}_i=0$ and $0\le {\alpha }_i\le C$.

Apply [F6] using the verified hypotheses in [step 3.1]. It gives an attained dual optimum $(\alpha ,\mu )$ with the same value as the primal optimum and complementarity for both families $g_i^{(m)}$ and $g_i^{(s)}$. At any fixed primal minimizer, these equal values and complementarity make $L$ attain its unconstrained infimum; its derivatives in $w$, $b$, and each ${\xi }_i$ therefore vanish.

For any finite list $u_1,\dots ,u_m\in X$ and $c_1,\dots ,c_m\in \mathbb{R}$, symmetry and bilinearity of the real inner product give ${\sum }_{r,s}{c}_r{c}_{s}k(u_r,u_s)=⟨{\sum }_r{c}_r\varphi (u_r),{\sum }_s{c}_s\varphi (u_s)⟩=\mathrm{\parallel }{\sum }_r{c}_r\varphi (u_r){\mathrm{\parallel }}^2\ge 0$. Thus the feature-induced kernel $k$ is real positive semidefinite, so its sample Gram matrix satisfies the hypothesis of [F4]. Since $k(x_i,x_j)=⟨\varphi (x_i),\varphi (x_j)⟩$, $\mathrm{\parallel }v{\mathrm{\parallel }}^2={\sum }_{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_{j}k(x_i,x_j)$. By [F4], the matrix $(y_i{y}_{j}k(x_i,x_j){)}_{i,j}$ is the Gram matrix of $y_i{z}_i$, so its quadratic form is nonnegative. Hence the displayed dual objective is concave. Its equality row has coefficient vector $y\mathrm{\ne }0$, because $n\ge 1$ and each $y_i\in \{-1,+1\}$, so that row is independent.

Differentiating the Lagrangian of [step 3.2] gives $w={\sum }_i{\alpha }_i{y}_i\varphi (x_i)$, ${\sum }_i{\alpha }_i{y}_i=0$, and $C-{\alpha }_i-{\mu }_i=0$. The last equation and ${\mu }_i\ge 0$ give ${\alpha }_i\le C$; together with ${\alpha }_i\ge 0$ these are the dual box constraints. The complementarity equations supplied by [F6] are ${\alpha }_i{g}_i^{(m)}=0$ and ${\mu }_i{g}_i^{(s)}=0$, which are exactly the two equations in the Statement.

The finite-dimensional primal has differentiable convex objective and affine convex constraints on the open convex variable space identified in [step 2.1]. Thus [F8] certifies that any feasible tuple satisfying the stationarity and complementarity equations is a global primal minimizer. If $0<{\alpha }_i<C$, then ${\mu }_i=C-{\alpha }_i>0$, so ${\mu }_i{\xi }_i=0$ forces ${\xi }_i=0$; then ${\alpha }_i{g}_i^{(m)}=0$ forces the signed margin to equal $1$. Finally, for any input $x$, stationarity gives the score $s(x)={\sum }_i{\alpha }_i{y}_{i}k(x_i,x)+b$.

For each sample point put $a_i=c_i\exp (-\mathrm{\parallel }{x}_i{\mathrm{\parallel }}_2^2\mathrm{/}(2{\sigma }^2))$. The identity $\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2^2=\mathrm{\parallel }{x}_i{\mathrm{\parallel }}_2^2+\mathrm{\parallel }{x}_j{\mathrm{\parallel }}_2^2-2x_i^T{x}_j$ gives ${\sum }_{i,j}{c}_i{c}_j{k}_{\sigma }(x_i,x_j)={\sum }_{i,j}{a}_i{a}_j\exp (x_i^T{x}_j\mathrm{/}{\sigma }^2)$.

For each fixed pair $i,j$, the exponential series has the absolutely convergent multi-index expansion $\exp (x_i^T{x}_j\mathrm{/}{\sigma }^2)={\sum }_{\alpha \in {\mathbb{N}}_0^p}(x_i^{\alpha }{x}_j^{\alpha })\mathrm{/}({\sigma }^{2\mathrm{\mid }\alpha \mathrm{\mid }}\alpha !)$, since the corresponding series of absolute values is ${\prod }_{r=1}^p\exp (\mathrm{\mid }{x}_{ir}{x}_{jr}\mathrm{\mid }\mathrm{/}{\sigma }^2)<\mathrm{\infty }$. The sample sums are finite, so they can be interchanged with this absolutely convergent series.

Substitution into [step 1.1] yields ${\sum }_{i,j}{c}_i{c}_j{k}_{\sigma }(x_i,x_j)={\sum }_{\alpha \in {\mathbb{N}}_0^p}\frac{1}{{\sigma }^{2\mathrm{\mid }\alpha \mathrm{\mid }}\alpha !}({\sum }_i{a}_i{x}_i^{\alpha }{)}^2\ge 0$. Symmetry of $k_{\sigma }$ is immediate from $\mathrm{\parallel }x-z{\mathrm{\parallel }}_2=\mathrm{\parallel }z-x{\mathrm{\parallel }}_2$, so [F1] proves positive semidefiniteness; zero eigenvalues or repeated points do not affect the sum-of-squares argument.