Deep Learning with Kernels through RKHM and the Perron–Frobenius Operator

$C^{*}$-algebra, which is denoted by $\mathcal{A}$ in the following, is a Banach space equipped with a product and an involution satisfying the $C^{*}$ identity (condition 3 below).

We now define RKHM. Let $\mathcal{X}$ be a non-empty set for data.

Let $\phi:\mathcal{X}\to\mathcal{A}^{\mathcal{X}}$ be the feature map associated with $k$, defined as $\phi(x)=k(\cdot,x)$ for $x\in\mathcal{X}$ and let $\mathcal{M}_{k,0}=\{\sum_{i=1}^{n}\phi(x_{i})c_{i}|\ n\in\mathbb{N},\ c_{i}\in\mathcal{A},\ x_{i}\in\mathcal{X}\ {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(i=1,\ldots,n)}\}$. We can define an $\mathcal{A}$-valued map $\left\langle\cdot,\cdot\right\rangle_{\mathcal{M}_{k}}:\mathcal{M}_{k,0}\times\mathcal{M}_{k,0}\to\mathcal{A}$ as

which enjoys the reproducing property $\left\langle\phi(x),f\right\rangle_{\mathcal{M}_{k}}=f(x)$ for $f\in\mathcal{M}_{k,0}$ and $x\in\mathcal{X}$. The reproducing kernel Hilbert $\mathcal{A}$-module (RKHM) $\mathcal{M}_{k}$ associated with $k$ is defined as the completion of $\mathcal{M}_{k,0}$. See, for example, the references [33, 34, 26] for more details about $C^{*}$-algebra and RKHM.

We introduce Perron–Frobenius operator on RKHM [35]. Let $\mathcal{X}_{1}$ and $\mathcal{X}_{2}$ be nonempty sets and let $k_{1}$ and $k_{2}$ be $\mathcal{A}$-valued positive definite kernels. Let $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ be RKHMs associated with $k_{1}$ and $k_{2}$, respectively. Let $\phi_{1}$ and $\phi_{2}$ be the feature maps of $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$, respectively. We begin with the standard notion of linearity in RKHMs.

Note that a Perron–Frobenius operator is not always well-defined since $ac=bc$ for $a,b\in\mathcal{A}$ and nonzero $c\in\mathcal{A}$ does not always mean $a=b$.

The following lemma gives a sufficient condition for $\mathcal{A}$-linearly independence.

Note that separable kernels are widely used in existing literature of vvRKHS (see e.g. [36]). Lemma 2.8 guarantees the validity of the analysis with Perron–Frobenius operators, at least in the separable case. This provides a condition for "good kernels" by means of the well-definedness of the Perron–Frobenius operator.

We use the operator norm to derive a bound, whose dependency on output dimension is milder than existing bounds. Availability of the operator norm is one of the advantages of considering $C^{*}$-algebras (RKHMs) instead of vectors (vvRKHSs). Note that although we can also use the Hilbert–Schmidt norm for matrices, it tends to be large as the dimension $d$ becomes large. On the other hand, the operator norm is defined independently of the dimension $d$. Indeed, the Hilbert–Schmidt norm of a matrix $a\in\mathbb{C}^{d\times d}$ is calculated as $(\sum_{i=1}^{d}s_{i}^{2})^{1/2}$, where $s_{i}$ is the $i$th singular value of $a$. The operator norm of $a$ is the largest singular value of $a$.

To see the derivation of the bound, we first focus on the case of $L=1$, i.e., the network is shallow. Let $E>0$. For a space $\mathcal{F}$ of $\mathcal{A}$-valued functions on $\mathcal{A}_{0}$, let $\mathcal{G}(\mathcal{F})=\{(x,y)\mapsto f(x)-y\,\mid\,f\in\mathcal{F},\|y\|_{\mathcal{A}}\leq E\}$. The following theorem shows a bound for RKHMs with the operator norm.

Theorem 4.1 is derived by the following lemmas. We first fix a vector $p\in\mathbb{R}^{d}$ and consider the operator-valued loss function acting on $p$. We first show a relation between the generalization error and the Rademacher complexity of vector-valued functions. Then, we bound the Rademacher complexity. Since the bound does not depend on $p$, we can finally remove the dependency on $p$.

We now generalize Theorem 4.1 to the deep setting ($L\geq 2$) using the Perron–Frobenius operators.

We use the following proposition and Lemmas 4.2 and 4.3 to show Theorem 4.5. The key idea of the proof is that by the reproducing property and the definition of the Perron–Frobenius operator, we get $f_{L}\circ\cdots\circ f_{1}(x)=\left\langle\phi_{L}(f_{L-1}\circ\cdots\circ f_{1}(x)),f_{L}\right\rangle_{\tilde{\mathcal{M}}_{L}}\!\!=\left\langle P_{f_{L-1}}\cdots P_{f_{1}}\phi(x),f_{L}\right\rangle_{\tilde{\mathcal{M}}_{L}}$.

We first show a representer theorem to guarantee that a solution of the minimization problem (1) is represented only with given samples.

We discuss the practical computation and the role of the factor $\|P_{f_{L-1}}\cdots P_{f_{1}}|_{\tilde{\mathcal{V}}(\mathbf{x})}\|_{\operatorname{op}}$ in Eq. (1). Let $G_{j}\in\mathcal{A}^{n\times n}$ be the Gram matrix whose $(i,l)$-entry is $k_{j}(x_{i}^{j-1},x_{l}^{j-1})\in\mathcal{A}$.

The computational cost of $\|R_{L}^{*}G_{L}R_{1}\|_{\operatorname{op}}$ is expensive if $n$ is large since computing $R_{1}$ and $R_{L}$ is expensive. Thus, we consider upper bounding $\|R_{L}^{*}G_{L}R_{1}\|_{\operatorname{op}}$ by a computationally efficient value.

Since $G_{1}$ is independent of $f_{1},\ldots,f_{L}$, to make the value $\|P_{f_{L-1}}\cdots P_{f_{1}}|_{\tilde{\mathcal{V}}(\mathbf{x})}\|_{\operatorname{op}}$ small, we try to make the norm of $G_{L}$ and $G_{L}^{-1}$ small according to Proposition 5.4. For example, instead of the second term regarding the Perron–Frobenius operators in Eq. (1), we can consider the following term with $\eta>0$:

Note that the term depends on the training samples $x_{1},\ldots,x_{n}$. The situation is different from the third term in Eq. (1) since the third term does not depend on the training samples before applying the representer theorem. If we try to minimize a value depending on the training samples, the model seems to be more specific for the training samples, and it may cause overfitting. Thus, the connection between the minimization of the second term in Eq. (1) and generalization cannot be explained by the classical argument about generalization and regularization. However, as we will see in Subsection 6.2, it is related to benign overfitting and has a good effect on generalization.

The proposed deep RKHM has a duality with CNNs. Let $\mathcal{A}_{0}=\cdots=\mathcal{A}_{L}=Circ(d)$, the $C^{*}$-algebra of $d$ by $d$ circulant matrices. For $j=1,\ldots,L$, let $a_{j}\in\mathcal{A}_{j}$. Let $k_{j}$ be an $\mathcal{A}_{j}$-valued positive definite kernel defined as $k_{j}(x,y)=\tilde{k}_{j}(a_{j}x,a_{j}y)$, where $\tilde{k}_{j}$ is an $\mathcal{A}_{j}$-valued function. The $\mathcal{A}_{j}$-valued positive definite kernel makes the output of each layer become a circulant matrix, which enables us to apply the convolution as the product of the output and a parameter. Then, $f_{j}$ is represented as $f_{j}(x)=\sum_{i=1}^{n}\tilde{k}_{j}(a_{j}x,a_{j}x_{i}^{j-1})c_{i,j}$ for some $c_{i,j}\in\mathcal{A}_{j}$. Thus, at the $j$th layer, the input $x$ is multiplied by $a_{j}$ and is transformed nonlinearly by $\sigma_{j}(x)=\sum_{i=1}^{n}k_{j}(x,a_{j}x_{i}^{j-1})c_{i,j}$. Since the product of two circulant matrices corresponds to the convolution, $a_{j}$ corresponds to a filter. In addition, $\sigma_{j}$ corresponds to the activation function at the $j$th layer. Thus, the deep RKHM with the above setting corresponds to a CNN. The difference between the deep RKHM and the CNN is the parameters that we learn. Whereas for the deep RKHM, we learn the coefficients $c_{1,j},\ldots,c_{n,j}$, for the CNN, we learn the parameter $a_{j}$. In other words, whereas for the deep RKHM, we learn the activation function $\sigma_{j}$, for the CNN, we learn the filter $a_{j}$. It seems reasonable to interpret this difference as a consequence of solving the problem in the primal or in the dual. In the primal, the number of the learning parameters depends on the dimension of the data (or the filter for convolution), while in the dual, it depends on the size of the data.

Benign overfitting is a phenomenon that the model fits any amount of data yet generalizes well [20, 21]. For kernel regression, Mallinar et al. [22] showed that if the eigenvalues of the integral operator associated with the kernel function over the data distribution decay slower than any powerlaw decay, than the model exhibits benign overfitting. The Gram matrix is obtained by replacing the integral with the sum over the finite samples. The inequality (2) suggests that the generalization error becomes smaller as the smallest and the largest eigenvalues of the Gram matrix get closer, which means the eigenvalue decay is slower. Combining the observation in Remark 5.5, we can interpret that as the right-hand side of the inequality (2) becomes smaller, the outputs of noisy training data at the $L-1$th layer tend to be more separated from the other outputs. In other words, for the random variable $x$ following the data distribution, $f_{L-1}\circ\cdots\circ f_{1}$ is learned so that the distribution of $f_{L-1}\circ\cdots\circ f_{1}(x)$ generates the integral operator with more separated eigenvalues, which appreciates benign overfitting. We will also observe this phenomenon numerically in Section 7 and Appendix C.3.2. Since the generalization bound for deep vvRKHSs [5] is described by the Lipschitz constants of the feature maps and the norm of $f_{j}$ for $j=1,\ldots,L$, this type of theoretical interpretation regarding benign overfitting is not available for the existing bound for deep vvRKHSs.

Neural tangent kernel has been investigated to understand neural networks using the theory of kernel methods [6, 7]. Generalizing neural networks to $C^{*}$-algebra, which is called the $C^{*}$-algebra network, is also investigated [32, 38]. We define a neural tangent kernel for the $C^{*}$-algebra network and develop a theory for combining neural networks and deep RKHMs as an analogy of the existing studies. Consider the $C^{*}$-algebra network $f:\mathcal{A}^{N_{0}}\to\mathcal{A}$ over $\mathcal{A}$ with $\mathcal{A}$-valued weight matrices $W_{j}\in\mathcal{A}^{N_{j}\times N_{j-1}}$ and element-wise activation functions $\sigma_{j}$: $f(x)=W_{L}\sigma_{L-1}(W_{L-1}\cdots\sigma_{1}(W_{1}x)\cdots)$. The $(i,j)$-entry of $f(x)$ is $f_{i}(\mathbf{x}_{j})=\mathbf{W}_{L,i}\sigma_{L-1}(W_{L-1}\cdots\sigma_{1}(W_{1}\mathbf{x}_{j})\cdots)$, where $\mathbf{x}_{j}$ is the $j$th column of $x$ regarded as $x\in\mathbb{C}^{dN_{0}\times d}$ and $\mathbf{W}_{L,i}$ is the $i$th row of $W_{L}$ regarded as $W_{L}\in\mathbb{C}^{d\times dN_{L-1}}$. Thus, the $(i,j)$-entry of $f(x)$ corresponds to the output of the network $f_{i}(\mathbf{x}_{j})$. We can consider the neural tangent kernel for each $f_{i}$. Chen and Xu [7] showed that the RKHS associated with the neural tangent kernel restricted to the sphere is the same set as that associated with the Laplacian kernel. Therefore, the $i$th row of $f(x)$ is described by the shallow RKHS associated with the neural tangent kernel $k_{i}^{\operatorname{NT}}$. Let $k^{\operatorname{NN}}$ be the $\mathcal{A}$-valued positive definite kernel whose $(i,j)$-entry is $k_{i}^{\operatorname{NT}}$ for $i=j$ and $0$ for $i\neq j$. Then, for any function $g\in\mathcal{M}_{k^{\operatorname{NN}}}$, the elements in the $i$th row of $g$ are in the RKHS associated with $k_{i}^{\operatorname{NT}}$, i.e., associated with the Laplacian kernel. Thus, $f$ is described by this shallow RKHM.

Existing bounds for classical neural networks typically depend on the product or sum of matrix $(p,q)$ norm of all the weight matrices $W_{j}$ [14, 15, 16, 17]. Typical bound is $O(\sqrt{1/n}\prod_{j=1}^{L}\|W_{j}\|_{\operatorname{HS}})$. Note that the Hilbert–Schmidt norm is the matrix $(2,2)$ norm. Unlike the operator norm, the matrix $(p,q)$ norm tends to be large as the width of the layers becomes large. On the other hand, the dependency of our bound on the width of the layer is not affected by the number of layers in the case where the kernels are separable. Indeed, assume we set $k_{1}=\tilde{k}_{1}a_{1}$ and $k_{L}=\tilde{k}_{L}a_{L}$ for some complex-valued kernels $\tilde{k}_{1}$ and $\tilde{k}_{2}$, $a_{1}\in\mathcal{A}_{1}$, and $a_{L}\in\mathcal{A}_{L}$. Then by Proposition 5.3, the factor $\alpha(L):=\|P_{f_{L-1}}\cdots P_{f_{1}}|_{\tilde{\mathcal{V}}(\mathbf{x})}\|_{\operatorname{op}}$ is written as $\|\tilde{R}_{L}^{*}\tilde{G}_{L}\tilde{R}_{1}\otimes a_{L}^{2}a_{1}\|_{\operatorname{op}}=\|\tilde{R}_{L}^{*}\tilde{G}_{L}\tilde{R}_{1}\|_{\operatorname{op}}\;\|a_{L}^{2}a_{1}\|_{\mathcal{A}}$ for some $\tilde{R}_{L},\tilde{G}_{L},\tilde{R}_{1}\in\mathbb{C}^{n\times n}$. Thus, it is independent of $d$. The only part depending on $d$ is $\operatorname{tr}k_{1}(x_{i},x_{i})$, which results in the bound $O(\alpha(L)\sqrt{d/n})$. Note that the width of the $j$th layer corresponds to the number of nonzero elements in a matrix in $\mathcal{A}_{j}$. We also discuss in Appendix B the connection of our bound with the bound by Koopman operators, the adjoints of the Perron–Frobenius operators [18].