Deep learning with kernels through RKHM and the Perron-Frobenius operator
Authors: Yuka Hashimoto
Masahiro Ikeda
Hachem Kadri
Venue: NeurIPS 2023 poster (2023)
Keywords: kernel method. generalization bound. C*-algebra. Perron-Frobenius operator and Koopman operator.
TL;DR: We propose deep RKHM and analyzed it through $C^*$-algebra and the Perron-Frobenius operators.

Abstract: Reproducing kernel Hilbert $C^*$-module (RKHM) is a generalization of reproducing kernel Hilbert space (RKHS) by means of $C^*$-algebra, and the Perron-Frobenius operator is a linear operator related to the composition of functions. Combining these two concepts, we present deep RKHM, a deep learning framework for kernel methods. We derive a new Rademacher generalization bound in this setting and provide a theoretical interpretation of benign overfitting by means of Perron-Frobenius operators. By virtue of $C^*$-algebra, the dependency of the bound on output dimension is milder than existing bounds. We show that $C^*$-algebra is a suitable tool for deep learning with kernels, enabling us to take advantage of the product structure of operators and to provide a clear connection with convolutional neural networks. Our theoretical analysis provides a new lens through which one can design and analyze deep kernel methods.

Deep Learning with Kernels through RKHM and the Perron-Frobenius Operator
Yuka Hashimoto
Masahiro Ikeda RIKEN AIP / Keio University, Tokyo, Japan masahiro.. ikedašriken.
NTT Network Service Systems Laboratories /
RIKEN AIP,
Tokyo, Japan
yuka. hashimoto@ntt.comm com
Hachem Kadri
Aix-Marseille University, CNRS, LIS, Marseille, France hachem. machem.kadrio0m saddri@lis-aat fr
Abstract
Reproducing kernel Hilbert -**-ue (RKHM) is generalization of reproducing kernel Hilbert space (RKHS) by means of C" -lleeba,,, and the PerronnFrobeeius operator is linear operator related to the composition of functions. Combining these two concepts, we present deep RKHM, deep learning framework for kernel methods. We derive a new Rademacher generalization bound in this setting and provide a theoretical interpretation of benign overfitting by means of Perron- Frobenius operators. By virtue of C*lalgebra, the dependency of the bound on output dimension is milder than existing bounds. We show that C* -alleerara a suitable tool for deep learning with kernels, enabling to take advantage of the product structure of operators and to provide a clear connection with convolutional neural networks. Our theoretical analysis provides new lens through which one can design and analyze deep kernel methods.
Introduction
Kernel methods and deep neural networks are two major topics in machine learning. Originally, they had been investigated independently. However, their interactions have been researched recently. One important perspective is deep kernel Icarning ( 3]. In this framework, we construct a function with the composition of functions in RKHSs, which is learned by given training data. Representer theorems were shown for deep kernel methods, which guarantee the representation of solutions of 5). We can combine the flexibility of deep neural networks with the representation power and solid theoretical understanding of kernel methods. Other important perspectives neural tangent kernel [6] 7 and convolutional kernel (8), which enable us to understand neural networks using the theory of kernel methods. In addition, Bietti et al. p proposed regularization of deep neural network through kernel perspective.
minimization problems only with given training data 4
The generalization properties of kernel methods and deep neural networks have been investigated. One typical technique for bounding generalization errors is For kernel methods, generalization bounds based on the Rademacher complexity can derived by the reproducing property. Bounds for deep kernel methods and vector- vecuer- RKHSs (vvRKHSs)
the Rademacher complexity [10] [I].
were also derived [5] 12 13]. Table [ shows existing Rademacher generalization bounds for kernel
methods. Generalization bounds for deep neural networks have also been actively studied [14 15 [6 Recently, analyzing the generalization property using the concept of benign overfitting
18
19
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Reproducing space
Output dimension
Shallow
Deep
RKHS
0(/1/n) 10]
O / O d/n)
vvRKHS
Ol d/n
12
RKHM (existing)
0
((yd/n)
d/n))
27
RKHM (ours)
O(d//4/vz)
O(B'd'/4
Table 1: Existing generalization bounds for kernel methods based on the Rademacher complexity and our bound (n:: sample size, A: Lipschitz constant regarding the positive definite kernel, B: The norm of the Perron-Frobenius operator)
has emerged 20 21 Unlike the classical interpretation of overfitting, which is called catastrophic overfitting, it explains the phenomenon that the model fits both training and test data. For kernel regression, it has been shown that the type of overfitting can be described by an integral operator associated with the kernel 22
In this paper, we propose deep RKHM to make the deep kernel methods more powerful. RKHM is generalization of RKHS by means C C*-algebra [23]22) 25). where C -algebraa is a generalization of the space of complex numbers, regarded as space of operators. We focus on the -allare of matrices in this paper. Applications We generalize the concept of deep kernel learning to RKHM, which constructs a map from an operator to an operator as the composition of functions in RKHMs. The product structure of operators induces interactions among elements of matrices, which enables us to capture relations between data components. Then, we derive generalization bound of the proposed deep RKHM. By virtue of C* ("-algebras, we can use the operator norm, which alleviates the dependency of the generalization bound on the output dimension.
RKHMs to kernel methods have been investigated recently 26 27
We also use functions and have been applied to analyzing dynamical systems [28] 29 30 31 to derive the bound. The compositions in the deep RKHM are effectively analyzed by the
operators, which are linear operators describing the composition of
operators.
C'-algebra and Perron-Frobeniu operator powerful tools that provide connections of the pro- posed deep RKHM with existing studies. Since the norm of the Perron FrobonnFrobenius operator is described by the Gram matrix associated with the kernel, bound shows a connection of the deep RKHM with benign overfitting. In addition, the product structure of a C*-algebra enables us to provide connection between the deep RKHMs and convolutional neural networks (CNNs).
Our main contributions are as follows.
We propose deep RKHM, which is generalization of deep kernel method by means of C* -llaerarraa We can make use of the products in C'-aaleeba to induce interactions among data components. We also show representer theorem to guarantee the representation of solutions only with given data. We derive a generalization bound for deep RKHM. The dependency of the bound on the output dimension is milder than existing bounds by virtue of C* -algebras. In addition, the Perron- Frobenius operators provide a connection of our bound with benign overfitting.
We show connections of our study with existing studies such CNNs and neural tangent kernel. We emphasize that our theoretical analysis using C* algebra and Berron-Frobeniig operators gives a new and powerful lens through which one design and analyze kernel methods.
2 Preliminaries
2.1 C'-algebra and reproducing kernel -oouuee
C* C*-algebra, which is denoted by A in the following, a Banach space equipped with a product and an involution satisfying the C* identity (condition 3 below).
Definition 2.1 (C" -algebrrr)) A set A is called C'-algebra if it satisfies the following conditions:
1. A is an algebra over C and equipped with bijection (+)* A + A that satisfies the following conditions for a, 3 E C and a, b E A:
(ab)* bbaa. (a")* a. (aa + =b)* aa² +3".

---

2. A is a normed space endowed with Il. and a, a A. I|ablla s ||a|Lallblla holds. In addition, A is complete with respect to || ll.
3. For E A, the C" identity ||ata|la= |alla holds.
Example 2.2 typical example of C² -algebras the C* -algebra of d by d circulant matrices. Another example is the C -algebra of d by d block matrices with M blocks and their block sizes are m == (mi,.... .mM). We denote them by Circ(d) and Block(m, d), respectively. See 127 32 for more details about these examples.
We now define RKHM. Let X' be a non-empty set for data.
Definition 2.3 (A-valued pusitive definite kernel) An A-valued map ks X x X + A is called a positive definite kernel if it satisfies the following conditions:
b(z,y) = x)"" for x. X. L. q k(11, Mzjee is positive semi-definite for E N. E. E.
Let : X' + AR be the feature map associated with ks defined as Ø(z) k(.,x) for E X and let
M = {Ein ((z))es n N, G E A, Is E (i n.). We can define an A-valued map
(s)m.. Ma, x Ma.0 + as
(a Hyj)bby Me
G kk(xs H;)bs
which enjoys the reproducing property (6(x), f) = f(x) for f E MA,u and x E X. The
reproducing kernel Hilbert A-module (RKHM) Mr associated with k defined as the completion of Ma.o- See, for example, the references 33 34 26 for more details about C*"aalebra and RKHM.
2.2 Perron-Frobenius operator on RKHM
We introduce Perron Frobbenis operator RKHM B5 Let X₁ and X₂ be nonempty sets and let k and &2 be A-valued positive definite kernels. Let Mi and M2 RKHMs associated with k and k2, respectively. Let and 62 be the feature maps of Mi and M2, respectively. We begin with the standard notion of linearity in RKHMs.
Definition 2.4 (A-linear) A linear map A Mi - M2 is called A-linear if for any E A And w E M₁, we have A A(wa) = (Aw)).
Definition 2.5 -Feoron-Frobenius operator) Let f X1 - X2 be map. The Perron-Frobeniug operator with respect to f is an A-linear map Pf MM - M2 satisfying
Pfóı(z)= - 22 (f(x))
Note that a Perron-Frobenius operator is not always well-defined since ac = be for o, b E A and nonzero E AA does not always mean
Definition 2.6 (A-linearly independent) The set (di(z) x X} is called A-linearly indepen- dent if it satisfies the following condition: For any N, Il...., En E X, and ci,..., On A. "En d1 (z:)c; 0" is equivalent to "c, = 0 all n""
Lemma 2.7 If (z) x X} is A-linearly independent, then Py is well-defined.
The following lemma gives a sufficient condition for A-linearly independence.
Lemma 2.8 Let kn ka, i.e., l is separable, for invertible operator and complex-valued kernel k. Assume (ő(z) x E X} is linearly independent (e.g. ie is Gaussian Laplacian), where is the feature map associated with k. Then, {Ør ())( X) A-linearly independent.
Note that separable kernels are widely used existing literature of vvRKHS (see e.g. 36
Lemma 2.8 guarantees the validity of the analysis with Perron operators, at least in the separable case. This provides a condition for "good kernels" by means of the well-definedness of the
operator.

---

Input
Output
fi M
/2 E 2
f3 E M
f+ E M,
Ag
A
A3
A
Figure I: Overview of the proposed deep RKHM. The small blue squares represent matrix elements. fi f2 is the encoder, and ʃ3 f4 is the decoder.
In the case of the autoencoder (see Example 3.1
Notation We denote the Euclidean inner product and norm by (::)) and || without the subscript. For E A, let |a A the unique element in A satisfying [a|a = a a. If is a matrix, ||a||и the norm of The operator norm of linear operator A on an RKHM is denoted by ||A|lop. All the technical proofs are documented in the supplementary.
3 Deep RKHM
We now construct L-layer deep RKHM. Let = Caxd be the C*-algebra of by d matrices. Let Ag...., Ar be -'-subblgebbaa A and for j = L....,L and ky A,-1 x AJ-1 + A, be an A,-valued positive definite kernel for the jth layer. For RKHM over A, associated with ky. In addition, we denote by M, the RKHM over A associated with ky. Note that Mj a subspace of M, and for u, u .Mj, we have (u, v) M; {u, M),,, We set the function space corresponding AL-1, II } and F, {f E Mj f(x) gaxd for any E Aj-1, || B₁} for = L- 1. Here, for f E Mj with = I,...., 1, Py is the Perron-Frobenuus operator with respect to ʃ from M, to M We assume the well-definedness of these operators. Then, we the class of deep RKHM
J....,,, we denote by M2 the
each layer FL
f(x) Rddd for any
Fdoep OL...... o ʃ, E Fy L, L)}.
Figure schematically shows the structure of the deep RKHM.
5), d), the C*-algebra of block diagonal matrices. By setting M1 S .... I Mr and Mi 2 ... Z Mr for elements in Aj decreases during 1 < j I I and increases during < j < L. This construction is regarded as an autoencoder, where the 1 Ith layer corresponds to the encoder and the
Example 3.1
We can set A; = Block((m2,j....
the number of nonzero
Lth
layer corresponds to the decoder.
Advantage over existing deep kernel methods Note that deep kernel methods with RKHSs and vrRKHSs have been proposed 1
4 2]. Autoencoders using RKHSs and vvRKHSs were also proposed 3 [ We have at least three advantages of deep RKHM over deep vvRKHSs or RKHSs:
1) useful structures of matrices stated in Remark 5.2 2) availability of the operator norm in the generalization bound stated in Section 3) connection with CNNs stated in Subsection 6.1
4 Generalization Bound
We derive a generalization error for deep RKHM. To derive the bound, we bound the Rademacher complexity, which one the typical methods on deriving generalization bounds [ Let Ω be probability space equipped with probability measure P. We denote the integral Jn ((w) of a measurable function 8 on Ω by E[s]. Let I1,..., Fna and y/...., Un be input and output samples from the distributions of Ao and Ar-valued random variables and y, respectively. Let oij (i (i=10 1,...,d, d, j 1,..., n) be i.i.d. Rademacher variables. Let o, = (oij)..., oa.). (d.)). For an Rdd -vluud function class JF and x (I1,..., the empirical Rademacher complexity R, (x, defined by Rr (x, F) = E[supyez Ein (0i, f(x))\/n.
4.1 Bound for shallow RKHMs
We use the operator norm to derive a bound, whose dependency on output dimension milder than existing bounds. Availability of the operator norm is 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 be large as the dimension becomes large. On the other hand, the operator norm is defined independently of the dimension d. Indeed, the Hilbert-Schmidt norm of matrix E Cd is calculated as (E 1/2, where s; is the ith singular value of The operator norm of a is the largest singular value of a.
To see the derivation of the bound, we first focus the case of L == 1, i.e. the network is shallow. Let E 0. For a space F of A-valued functions on An, let (FF) = {(x, y) + f(x) y | Je F, llvlla I E). The following theorem shows a bound for RKHMs with the operator norm.
Theorem 4.1 Assume there exists D such that ||k x1, K- 4V2(VDB, B2 and M 6(VDB, E)². Let 8 (0, Then, for any g ((F)),
D for any E Ao- Let
where F1 is defined in Section 3 with probability at least 1 - 5, we have
+ K (<2 tr (2))
1/2
log (2/0)
[Elg(z, AllIA -
19( vi
+ M
2n
Theorem 4.1 derived by the following lemmas. We first fix vector p Rd and consider the operator-valued loss function acting on 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.
Lemma 4.2 Let F be function class of -aluud functions on Ao bounded by C (i.e., ( S C for any E Ag). Let ((F {(z,,) + (z) v'pll E F, lIvll S E} and M = 2(C + E)2. Let p E Rd satisfy ||pl| and let 5 E (0, Then, for any g (F,,)).
with probability at least 6, we have
1 n2 Σ
12/(2
9) 21 =
19(
+ (x, ((F,p)) + 3M
2n
A
Lemma 4.3 With the same notations in Lemma
4.2
let K = 2/2(C + E). Then, we have
(x, ((F.p)) I Fp), where Fp {a
f())p FE
Lemma 4.4 Lef p E Rd satisfy [|ell = 1. For Fi defined in Section 3 we have
(x, S
B1
Σ 2=1
tr(k(z,, (x))) 1/2
4.2 Bound for deep RKHMS
We now generalize Theorem 4. to the deep setting (I. 2) using the Perron-Frobenius operators.
Theorem 4.5 Assume there exists
such that | lA S D for any E Ag Let K = 4 + .... Bn and M 6(VDB, + E)2. Let E (0,1). Then, for any
E G(F with probability at least - 5, we have
1/2
log (2/))
[B]]a( v) BAllA
Ia(2,, Mi
tr ki (2i,
M
2n
We use the following proposition and Lemmas 4.2 and 4.3 to show Theorem 4.3 The key idea of the proof is that by the reproducing property and the definition of the Perron Frobennis operator, we get fr ..... fi(z)= = (fi(f ....o fi))), (Pr... ... P),
Proposition 4.6 Let pe Idd satisfy lPll| 1. Then, we have
n
tr (11, 1/2
sup R J (F,FF))
|P Pii loo llfellmm (2
Here, (xx is the submodule of M, generated by on (21), ... 2 (Ix))
5

---

Corollary 4.7 Let R satisfy l|pll = 1. Then, we have
Σ tr(ha((z, 1/2
pdeop p) S B1 BL R FL
Comparison to deep vvRKHS We can also regard Cdxd as the Hilbert space equipped with the Hilbert-Schmidt inner product, i.c. can flatten matrices and get de-dimensional Hilbert space. In this case, the corresponding operator-valued kernel is the multiplication operator k(z, y). which we denote by MR(r,y) Then, apply existing results for wRKHSSs [5 [2] which involve the term (Ei= ((MM(e..:))))? is calculated as
11
7
tr tr(Ms(an.::)
(ezt: (a),)))
ka vy )
tr (t);
+1==1
511=1
Thus, using the existing approaches, we have the factor (d (dEi tr k( x. On the other hand, we have the smaller factor (Ei=1 Ir k( ((x;,, xz)) / in Theorems 4.1 and 4.5 Using the operator norm, we can reduce the dependency on the dimension d.
5 Learning Deep RKHMs
We focus on the practical learning problem. To learn deep RKHMs, we consider the following minimization problem based on the generalization bound derived in Section
min (GEM))s
Σ Vz. o.... f1(x;) 11l3 n
Phlvvollop + -
SallfillMe-
The second term regarding the Perron FrobennFo operators comes from the bound in Proposition 4.6 We try to reduce the generalization error by reducing the magnitude of the norm of the Perron Frobenius operators.
5.1 Representer theorem
We first show a representer theorem to guarantee that a solution of the minimization problem i is represented only with given samples.
Proposition 5.1 Let h: A" x An + R4 be an error function, let 91 be an R4-valued function on the space of bounded linear operators on M,, and let g2 R+ + R+ satisfy g2(a) S 92(b) for S Assume the following minimization problem has a solution:
min (JjEMa)s
.,, e. si + gi (P ... Pfi lvx) + 92 gz((1fz.llee)
Then, there exists a solution admitting a representation of the form fj = En (15 (x) ")cs for some Pujs...,Ca.. A and for = 1...., L. Here, 2r o.... (1(x;) for 1,..., and at Ii.
An advantage of deep RKHM compared deep vvRKHS is that we can make of the structure of matrices. For example, the product of two diagonal matrices is calculated by the element- wise product of diagonal elements. Thus, when A₁ among elements in an input are induced only by the kernels, not by the product ka(a, - Ca.j- That is, the form of interactions does not depend on the learning parameter Ct.j. On the other hand, if we set Aj = Block (mj. with m;- = ".n.j....,,,,a.
Remark 5.2
At Block (1,..,,
, 1), d), interactions
# (1,...,1), then at the jth layer, we get interactions among elements in the same block through the product k,, x². -1 Ca.j. In this case, the form of interactions is learned through Cj.j- For example, the part M1 ... S Mi (the encoder) in Example 3.7 tries to gradually reduce the dependency among elements in the output of each layer and describe the imput with a small number of variables. The part Mt 2 Mr, (the decoder) tries to increase the dependency.

---

5.2 Computing the norm of the Perron-Frobenius operator
We discuss the practical computation and the role of the factor || ... Phi (xx))lo Eq. ① Let
Gj A be the Gram matrix whose (i, -eettry k5(2 _2)-1 ) E A.
Proposition 5.3 For j = 1, let ( (0) )..... (3 ) = Q2 be the QR decomposition of [2) )).... .0.....,,((888) (x), [)] Then, we have |P ... P. (ox)]lop = R Gr Rillop
The computational cost of || GL is expensive if is large since computing R₃ and Ry is expensive. Thus, we consider upper bounding G Ru llop by computationally efficient value.
Gt.
Proposition 5.4 Assume Gr. is invertible. Then, we have
PP ... P.Plieoll || 11 110p
11./2
Since 1j independent of fi...., fL. to make the value [| ... Pyi small, we try to
make the norm of GL and G7 small according to Proposition 5.4 For example, instead of the second term regarding the Froron-Frobenius operators in Eq. (T. we can consider the following term with 1) 0:
A1 GL) + || (lop))
Note that the term depends on the training samples 21,..., Tn. The situation is different from the third term in Eq. ( since the third term does not depend on the training samples before applying the representer theorem. If we try 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. (I) and generalization cannot be explained by the classical argument about generalization and regularization. However, as we will see in Subsection 6.2 is related to benign overfitting and has a good effect on generalization.
The inequality ② implies that as ( (x.--)).... dr (xh-1)) dependent, the Rademacher complexity becomes large. By the term [l + GL) in Eq. 1. the function ft-1 o...o o fi is learned so that it separates I1,.... In well.
Remark 5.5
becomes nearly linearly
Remark 5.6 To evaluate f1 o.... f (1a) for = ,,..., n, we have to construct a Gram matrix Gj Apxn, and compute the product of the Gram matrix and a vector 6j E AD for j = 1,..., The computational cost of the construction of the Gram matrices does not depend on d. The cost of computing Gyc, is O( d,). where d, is the number of nonzero elements in the matrices in Aj- Note that if A₂ is the C -algeebrra of block diagonal matrices, then we have d, < d². Regarding the cost with respect to if the positive definite kernel is separable, features 37 to replace the factor n² with mn for a small integer m < n.
can use the random Fourier
Connection and Comparison with Existing Studies
The proposed deep RKHM is deeply related to existing studies by virtue of C*-algebra and the Perron-Frobanius operators. We discuss the connection below.
6.1 Connection with CNN
The proposed deep RKHM has duality with CNNs. Let Ao =... As Circ(d), the C*-aageera of d by d circulant matrices. For = 1,..., L. let aj E Ay. Let k, be an Ay-valued positive definite kernel defined as (,, y) = ky (a,z, ajy), where k, is an Ay-valued function. The Aa-uul positive definite kernel makes the output each layer become a cireulant matrix, which enables us to apply the convolution as the product of the output and a parameter. Then, f, is represented fx) = Em= ky (ajar, " for some C.j Aj. Thus, at the jth layer, the input is multiplied by aj and transformed nonlinearly by (x) = Σn ky(s, ")),. Since the product of two circulant matrices corresponds the convolution, aj corresponds to filter. In
7

---

addition, dj corresponds to the activation function at the jth 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 ci.j..... Ca.j+ for the CNN, we learn the parameter aj- In other words, whereas for the deep RKHM, we learn the activation function j. for the CNN, we learn the filter 0z. 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.
The connection between CNNs and shallow RKHMs has already been studied 127V. However, the existing study does not provide the connection between the filter and activation function. The above investigation shows a more clear layer-wise connection of deep RKHMs with CNNs.
Remark 6.1
6.2 Connection with benign overfitting
Benign overfitting is 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 3.5 we can interpret that as the right-hane hand side of the inequality (2) becomes smaller, the outputs of noisy training data at the L 1th layer tend to be more separated from the other outputs. In other words, for the random variable following the data distribution, fL-1 ..... o fi is learned so that the distribution of fL-10 ..... o (x) generates the integral operator with more separated eigenvalues, which appreciates benign overfitting. We will also observe this phenomenon numerically in Section and Appendix [.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, for j = 1,..., T., this type of theoretical interpretation regarding benign overfitting is not available for the existing bound for deep vvRKHSs.
Remark 6.2 The above arguments about benign overfitting are valid only for deep RKHMs. i.e., the case of L 2 If L (shallow RKHM), then the Gram matrix GL [K( 2 )ss.s fixed and determined only by the training data and the kernel. On the other hand, if L 2 2 (deep RKHM), then Gr, = [f.. .... o (x:4), f fi (x
depends also on f1. fL-1. As a result, by adding the term using GL to the loss function, we can learn proper f1....; fL-1 so that they make the right-hand side of Eq. ( small, and the whole network overfits benignly. As becomes large. the function fi-1 .... fi changes more flexibly to attain smaller value of the term. This is an advantage of considering a large L.
6.3 Connection with neural tangent kernel
Neural tangent kernel has been investigated to understand neural networks using the theory of kernel methods (6 77. Generalizing neural networks to C* -lgebba,,, which is called the C'-aalgebra network, also investigated [32 38). We define a neural tangent kernel for the O algebba 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 No - A over A with A-valued weight matrices W,, E N NN and element-wise activation functions σ,: f(x) = WLOL-I(WL- (WW (W(x)))...) The (i.j)-entry of f(x) is f((x,) W LL.0L-1WW-11-
on (Wix)) ...),, ), where x, is the jth column of æ regarded as æ E CdNgxd xd and W is the ith row of Wz regarded as Wr E CdxdNz-1 Thus, the (i. (entryy of fxx corresponds neural tangent kernel for each ft. Chen and Xu (2] 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 ith row of f() is described by the shallow RKHS associated with the neural tangent kernel KNT, Let NN the A-valued positive definite kernel whose (i. je)-rtryy is LNT for = j and O for i * j. Then, for any function E MANN, the elements in the ith row of g are in the RKHS associated with 1.N, i.e., associated with the Laplacian kernel. Thus, f is described by this shallow RKHM.
the output of the network fx()) We can consider the
8

---

Remark 6.3 We can combine the deep RKHM and existing neural networks by replacing some f3 in our model with an existing neural network. The above observation enables us to apply our results in Section to the combined network.
6.4 Comparison to bounds for classical neural networks
Existing bounds for classical neural networks typically depend on the product or sum of matrix (p, q) norm of all the weight matrices Wj [4] 13
16 17.. Typical bound is I/vI/n IT== [Wr]lss). Note that the Hilbert-Schmidt norm is the matrix (, 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 K1 Kjaj and kz ky,0, for some complex-value valued kernels b and k2, 01 E A1, and az E AL. Then by Proposition 5.3 the factor aLL) = [| Pf. 1o llop is written as [12 @ Bazall I| op = G & Ru llop || ai lla for some R2, GL, R1 E Cax". Thus, is independent of d. The only part depending on d is tr k1 (I,, 24). which results in the bound O(a( / dd/). Note that the width of the jih layer corresponds to the number of nonzero elements in matrix in Aj. We also discuss in Appendix [ the connection of our bound with the bound by Koopman operators, the adjoints of the Froben-s operators [18].
7 Numerical Results
We numerically confirm our theory and the validity of the proposed deep RKHM.
We compared the generalization property of the deep RKHM to the deep wRKKHS with the same positive definite kernel. For d = 10 and n 10, we set 2; (o.2) c; as input samples, where a E IR R000010 and z; E IR: 10 are randomly generated by (V 0.1). the normal distribution of mean 0 and standard deviation 0.1, (-)² is the elementwise product, and e; is the random noise drawn from (0, le - 3). We reshaped r; to a 10 by 10 matrix. We set L 3 and kj = kl for j = 2, 3, where io is the Laplacian kernel. For RKHMs, we set A1 = Block((1,....... 1). d). A = (2, 2), d), and A3 = Cdxd This is the autoencoder mentioned Example For vvRKHSs, we set the corresponding Hilbert spaces with the Hilbert-Schmidt inner product. We set the loss function as 1 1/n|| Di= [f(x))
Comparison to vyRKHS
xx|22lla for the deep RKHM and as 1/n > [xf x; llis for the deep vvRKHS. Here. f = f3 a f2 o fi. We did not add any terms to the loss function to see how the loss function with the operator norm affects the generalization performance. We computed the same value [[E][((=) x13llla- 1/nl| Σn (x;) x; la for both RKHM and vvRKHS. Figure 2 (a) shows the results. We can see that the deep RKHM generalizes better than the deep vvRKHS, only with the loss function and without any additional terms.
Observation about benign overfitting We analyzed the overfitting numerically. For d = 10 and n 1000, we randomly sampled by d diagonal matrices xi,..., Iy, E Ao from the normal distribution (0, 0.1). We set y = x + c; for i = 1.... n, where is noise drawn from the normal distribution (0, 0.001). The magnitude of the noise is 10% of 2? In addition, we set L 2. A Cd A = Block((1, ...,...., 1). d), and ky as the same kernel as the above experiment. The additional term to the loss function is set as X + Gz)
[|Gz\lop) + 1 where 7 0.01 and A = 0.01 according to Subsection 5.2 We computed the generalization error for the cases of X 0 and A 10 Figure 2 (b) shows the result. We can see that the generalization error saturates without the additional term motivated by the Perron-Frobenius operator. On the other hand, with the additional term, the generalization error becomes small, which is the effect of benign overfitting.
Comparison to CNN We compared the deep RKHM to CNN on the classification task with MNIST (39. We set d = 28 and n = 20. We constructed deep RKHM combined with a neural network with dense layers. For the deep RKHM, we set (lock((7, 7), d), and Ao Block((4,.... 4)...,4),cl d). Then, two dense layers are added. See Subsection 6..3 about combining the deep RKHM with neural networks. Regarding the additional term to the loss function, we set the same term with the previous experiment with X 0.001 and
2, Ao Cdxd, Ai =

---

0.00020
Generolizationn pnteraltzatton Erro
20
0.6
Arcuracy
Generalizatin
0.00015
10-
0.5
0.00010
RKHM, =1
0.00005
10
0.4
RKHM A -0
0.00000
RKHM
WRKHS
200
400
600
100
200
300
400
Epochs
Epochs
(b)
(c)
Figure 2: (a) The box plot of the generalization error of the deep RKHM and vvRKHS at the point that the training error reaches 0.05. (b) Behavior of the generalization error during the learning operators. (c) Test
process with and without the additional term regarding the accuracy of the classification task with MNIST for a deep RKHM and a CNN.
set A = or A = O. To compare the deep RKHM to CNNs, we also constructed a network by replacing the deep RKHM with CNN. The CNN is composed of layers with 7 x and x filters. Figure (c) shows the test accuracy of these networks. We can see that the deep RKHM outperforms the CNN. In addition, we can see that the test accuracy is higher if we add the term regarding the Perron-Frobenius operators. We discuss the memory consumption and the computational cost of each of the deep RKHM and the CNN in Appendix C.3 and we empirically show that the deep RKHM outperforms the CNN that has the same size of learning parameters as the deep RKHM. We also show additional results about benign overfitting in Appendix C,3
(c)
Conclusion and Limitations
In this paper, we proposed deep RKHM and analyzed it through C*-algebra and the operators. We derived generalization bound, whose dependency on the output dimension alleviated by the operator norm, and which is related to benign overfitting, We showed a representer theorem about the proposed deep RKHM, and connections with existing studies such as CNNs and neural tangent kernel. Our theoretical analysis shows that C"-algebra and Perron-Frobenius operators are effective tools for analyzing deep kernel methods. The main contributions of this paper are our theoretical results with Calalgebra and the are required for further progress. For example, although we numerically showed the validity of our method for the case where the number of samples is limited (the last experiment in Section 7 more experimental results for the case where the number samples is large are useful for further analysis. Also, although studying more efficient methods specific to deep RKHM remains to be investigated in future work. operators. Though separable kernels with invertible matrices, which are typical examples of kernels, satisfy the assumption, generalization of analysis to other kernels should also be studied in future work.
operators. More practical investigations
apply random Fourier features (Remark (.6) to reduce the computational costs,
As for the theoretical topic, assumed the well-definedness of the
Acknowledgements
Hachem Kadri partially supported by grant ANR-19-CE23-000 from the French National Research Agency. Masahiro Ikeda is partially supported by grant JPMJCR1913 from JST CREST.
References
[1] Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Proceedings of Advances in Neural Information Processing Systems (NIPS) 22, 2009.
[2] Sebastian W. Ober, Carl E. Rasmussen, and Mark van der Wilk. The promises and pitfalls of deep kernel learning. In Proceedings of the 37th Conference on Uncertainty Artificial Intelligence ( (UAI), 2021.
10

---

[3] Behnam Gholami and Abolfazl Hajisami. Kernel auto entoder for semi- somi-superiieed hashing. In Proceedings of 2016 IEEE Winter Conference on Applications of Computer Vision (WACV). 2016.
[4] Bastian Bohn, Michael Griebel, and Christian Rieger. A representer theorem for deep kernel learning. Journal of Machine Learning Research, 20(64): 32. 2019.
[5] Pierre Laforgue, Stéphan Clémençon, and Florence d' Alche Buc. Autoencoding any data through kernel autoencoders. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
[6] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In In proceedings of Advances in Neural Information Processing Systems (NeurIPS) 31, 2018.
[7] Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same RKHS.
In Proceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
[8] Julien Mairal, Piotr Koniusz, Zaid Harchaoui, and Cordelia Schmid. Convolutional kernel networks. In Proceedings of the Advances in Neural Information Processing Systems (NIPS) 27, 2014.
[9] Alberto Bietti, Grégoire Mialon, Dexiong Chen, and Julien Mairal. A kernel perspective for regularizing deep neural networks. In Proceedings of the 36th International Conference Machine Learning (ICML), 2019.
[10] Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 1:463-482, 2002.
[11] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning. MIT press, 2018
[12] Vikas Sindhwani, Ha Quang Minh, and Aurélie C. Lozano. Scalable matrix-valued kernel learning for high-dimensional nonlinear multivariate regression and granger causality. In Proceedings of the 29th Conference on Uncertainty Artificial Intelligence (UAI), 2013.
[13] Riikka Huusari and Hachem Kadri. Entangled kernels beyond separability. Journal of Machine Learning Research, 22(24): 2021.
[14] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Proceedings of the 2015 Conference on Learning Theory (COLT), 2015.
[15] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Proceedings of the 2018 Conference On Learning Theory (COLT), 2018.
[16] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. normalizz margin bounds for neural networks. In Proceedings of Advances in Neural Information Processing Systems (NIPS) 31, 2017.
[17] Haotian Ju, Dongyue Li, and Hongyang R Zhang. Robust fine-tuning of deep neural net- works with Hessian- generalization guarantees. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
[18] Yuka Hashimoto, Sho Sonoda, Isao Ishikawa, Atsushi Nitanda, and Taiji Suzuki. Koopman- based bound for generalization: New aspect of neural networks regarding nonlinear noise filtering. arXiv: 2302.05825, 2023.
[19] Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura. Compression based bound for non- compressed network: unified generalization error analysis of large compressible deep neural network. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
[20] Mikhail Belkin, Alexander Rakhlin, and Alexandre B. Tsybakov. Does data interpolation contradict statistical optimality? In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.

---

[21] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30033-3077 2020.
[22] Neil Rohit Mallinar, James B Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: Toward refined taxonomy of overfitting. In Proceedings of Advances in Neural Information Processing Systems (NeurlPS) 37, 2022.
[23] Jaeseong Heo. Reproducing kemnel Hilbert C* -modules and kernels associated with cocycles. Journal of Mathematical Physics, 49110)103307, 2008.
[24] Shigeru Itoh. Reproducing kemels in modules over -aleebraass and their applications. Journal of Mathematics in Nature Science, pages 1-20, 1990.
[25] Mohammad S. Moslehian. Vector-valued reproducing kernel Hilbert C* C'-modules. Complex Analysis and Operator Theory, 16(1):Paper No. 2, 2022.
[26] Yuka Hashimoto, Isao Ishikawa, Masahiro Ikeda, Fuyuta Komura, Takeshi Katsura, and Yoshi- nobu Kawahara. Reproducing kernel Hilbert -modue and kernel mean embeddings. Journal of Machine Learning Research, 22(267):1 1-6,, 2021.
[27] Yuka Hashimoto, Masahiro Ikeda, and Hachem Kadri. Learning in RKHM: -'l-algebraic twist for kernel machines. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
[28] Yoshinobu Kawahara. Dynamic mode decomposition with reproducing kernels for Koopman spectral analysis. In Advances in Neural Information Processing Systems (NIPS) 29, pages 911-919, 2016.
[29] Isao Ishikawa, Keisuke Fujii, Masahiro Ikeda, Yuka Hashimoto, and Yoshinobu Kawahara. Metric on nonlinear dynamical systems with Perron- Frobenius operators. Advances in Neural Information Processing Systems (NeurIPS) 31, pages
2018.
[30] Dimitrios Giannakis and Suddhasattwa Das. Extraction and prediction of coherent patterns in incompressible flows through space-time Koopman analysis. Physica D; Nonlinear Phenomena, 402:132211, 2020.
[31] Yuka Hashimoto, Isao Ishikawa, Masahiro Ikeda, Yoichi Matsuo, and Yoshinobu Kawahara. Krylov subspace method for nonlinear dynamical systems with random noise. Journal of Machine Learning Research, 21(172):1-29, 2020.
[32] Ryuichiro Hataya and Yuka Hashimoto. Noncommutative C*-algebra net: Leamingg neural networks with powerful product structure in C* -algebaa.. arXiv: 2302.01191,200 2023.
[33] E. Christopher Lance. Hilbert C* -moouullss a Toolkit for Operator Algebraists. London Mathematical Society Lecture Note Series, vol. 210. Cambridge University Press, 1995.
[34] Gerard J. Murphy. C"-Algebras and Operator Theory. Academic Press, 1990.
[35] Yuka Hashimoto, Isao Ishikawa, Masahiro Ikeda, Fuyuta Komura, Takeshi Katsura, and Yoshi- nobu Kawahara. Analysis via orthonormal systems in reproducing kernel hilbert e² c"-modules and applications. arXiv: 2003.00738, 2020.
[36] Mauricio A Álvarez, Lorenzo Rosasco, Neil D Lawrence, et al. Kernels for vector vector-valued functions: A review, Foundations and Trends@ in Machine Learning, 4(3):195-266, 2012.
[37] Ali Rahimi and Benjamin Recht. Random features for large-scale kemel machines. In Proceed- ings of the Advances in Neural Information Processing Systems 20 (NIPS), 2007.
[38] Yuka Hashimoto, Zhao Wang, and Tomoko Matsui. C' algebra net: new approach generalizing neural network parameters to -algeba... In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
[39] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11):2278-233 1998.
12

---

[40] Andreas Maurer. A vector-contraction inequality for rademacher complexities. In Proceedings of the 27th International Conference on Algorithmic Learning Theory (ALT), 2016.
13

---

A Proofs
We provide the proofs of the theorems, propositions, and lemmas in the main paper.
Lemma 2.7 (f) x E E is A-linearly independent, then Pj is well-defined.
Proof Assume Σi= (1:)) = Ei=1 on (x:)d; for E N, Gi, E A. Since (δ1(2) x } is A-linearly independent, we have G = d, for i = n. Thus, Ps Zimi 01 (z:)e E <1(((x)))c = Di= o1 (f(x:)) = Py Ei= (x;)d,
n.
Let kj ka, i.e., k is separable, for an invertible operator and a complex-valued kernel k. Assume (d(()) x E X3 is linearly independent (e.g. k is Gaussian or Laplacian), where is the feature map associated with k. Then, {01(z) | |x E E) A-linearly independent.
Lemma 2.8
Proof If Ei= (11))e = O, we have
0=
Σ (1)))
= (=Gc=(GV/2))(C))) Mr
where G is the -vluuvd Gram matrix whose (int)-entry is k( 2z)) E A and c= (c.,..,,cl) Cn). Thus, we obtain G1/2c = 0. Let G be the standard Gram matrix whose (i,j))entry is k( mz). Since G G @ and G is invertible, the inverse of G G- 2-1@a"" @a- Thus, /1/2 is invertible and we have =
Lemma 4.2
Let F be a function class of Rddd functions on Ao bounded by C (i.e. [If(=)]lA for any E Ag). Let G(F {(z(((])))) y) - [l(f(x) -y)p! f f F, llvll S E} and M 2(C + E)2. Let p E Rd satisfy ||ll| and let 8 E (0, 1). Then, for any g ( p).
with probability at least 6, we have
12g(2/6)
p11 S
Σ la( v:
+ 22 (R, ((F + 3M
2n
A
Proof For (x, v). (2), E A Rdd we have
[K(((=) y)pl [1(f(x') - v')pl12
= =1]f(=)p|| - (f(x) up) + |1sp|2 11f(('))) - 11lp < 2(C++E).
In addition, we have
|[[[g(z,))) (1 pl1 -1
L0(0,, vill p p|² Elgg(z v)(l))))
1/2
x2
p. 19(2,, 31 1ap
1 Σ 1g(2,, wipl?
= Ep,, 10(2, v) [an) (p, lo( w11 E[llg(z, E|llo(2)))1111)
Since (x, v) + [1 y|ll is a real-valued map, by Theorem 3.3 by Mohri et al.
we have
( m Σ 10 vi)
1/2
log (2/()
(El10<,,)) 12
p (2,,(xx p)) + 3M
2n
The inequality || 19(2,, u4) ) 1/2
211 < I 19(2,, 9) Ball completes the proof.
14

---

Lemma 4.3
With the same notations in Lemma 4.2 let K = 22/(CC + E). Then, we have
(x, (F p)) S K R. (x.FF) Fp), where Fp = - + f(r)p F)
Proof Let (2) = || yppll for & E {f(z)p f E S R and = 1,..., n. The Lipschitz constant of hi is calculated follows: We have
h₂(2) h₂(2²) ||=|| - 2 - 2', ypp) ||2111
(I|=1l + |= ||=' + 2/ z z' |||ppp||
I (II=11 + - - | - | + 2|| 2' |1lappl
I (2C 22E)ll=-
Thus, we have [++(2) (x())) & 2(C E)]l= - z/11. By Corollary 4 by Maurer 40 the statement proved.
Lemma
4.4
Let p E Id satisfy ||pl| 1. For Fi defined in Section we have
B1 a
1/2
(xp)
(((());2)))
Proof We have
sup
1
n
t (p)
Σ ((o (o)(s)) sup
1 n
EEfi
n
n Σ (pot) (0i (Ix), fi p)
1
n
= E
sup
p.
JEF
1
P. Σ [1(E)\(r'"))1 in p)
E
sup
SEJ:
Σ si (1:))
sup JEF, TI
Mar
1
12
E
sup JEF, n
Φ (xx)))
Min
1
2
1/2
E
sup
p.
Σ (o:)(('p))))
p
l1fllln.
(4)
JEF n
Mr
B1 E
1/2
p" po ki (2r (zir
B
1/2
<
E
of k1 (2,,)
(5)
B
1/2
B1 n
1/2
E
of ki (21,
Σ trki
i=1
where for p E Cd and f.g E M1. (f,9) Mi.p is the semi-inner product defined by (ʃ, Ma. ( (p, (J, p) and [fy,, (f, In addition, the inequality ( by the Cauchy-Schwand inequality and the inequality (5) is by the Jensen's inequality. Note that the Sauchy-Schwartz incquality is still valid for semi-innee products. The incquality (4) is derived by the inequality
[e E (p. (Jr. Se),, p) s |Pll (fz, (JI, ll S l|
15

---

Theorem 4.1
Assume there exists such that [x, x) S D for any x Ag.
K 4 + B and M = 6(v DB + Ey?. Let 8 E (0.1). Then, for any E ((Fi),
where F1 is defined in Section 3 with probability at least 1 - 6, we have
K
1/2 + MM
log log(2/0g (2
[F([((,))) Blll -
lo( vi)1
Σ
trih(
A
2n
Proof For f E Mi and x E Ao, we have
[If()))a== (1 Ila -
(x, x)
1/2
Iflla S VDB1.
Thus, we set C as vDB, and apply Lemmas 4.2
4.3 and 4.4
Then, for p E Rdd satisfy |p|| = 1,
with probability at least - 8, we have
K
1/2
1og(2/0)
[|[[a((,, v) 1 pl1 =
10(2; U1
+
Σ
ha (I,,
+ M
2n
Therefore, we obtain
[[[[g((, AlllA = [F]](( 1)1311/2112
K
1/2
log (2/8)
(a 31)13
+
Σ
tr k2 (25,
+ M
2n
which completes the proof.
Proposition 4.6 We have
(x, F p) S
sup (FEFF)s
[Prz 1 ". Pa Palvoollop Melallme
Σ
tr(ki (11,
1/2
Here, (x) is the submodule of Mi generated by di (21)... Φ1 (2r)).
The following lemma by Lance 33 Proposition 1.2] used in proving Proposition 4.6 Here, for a, b E A. S b means b is Hermitian positive definite.
Lemma A.1 Let M and N be Hilbert A-modules and let A be an A-linear operator from M to N. Then, we have [Aw S [| || [2
Proof
E
sup
(at ((x)))
= =
sup ((GEF))
((a )p, (o f1..)) ... )m)
fErdon
1=1
1=1
(os)")p((Llff-iil f(x)) ... fe)me p)
E
sup
(ffET,)s
1=1
E
sup
Σ
(p. ( feh
((gEF,)
t=1
1 p.
Σ (t fi(x)) Mow")
Me 2)
sup L(SEF,))
16

---

E
sup
Σ dn. (1 (o.o)))
MowD))
(BEPs
Men
i=1
E
sup
Σ Φr (f (..)))))))))))))))
(6)
(FEF))
MuD
i=1
S
sup (1EE,,,,
Pre Ph. Σ
vi (1.))()))'))
n
2
)
1/2
p. Phi-i" ... Ps Σ 2 (m:)(()))))
Mr P\ lIfellann
sup (1GEF)), n
1/2
$ E
sup
p. |1 Py Pnllvp)lle ((()))())))
p)
llfellbeee
(7)
(IEEFy) n
Mn.
1 sup n (JzET));
1P ... Polvooolop IIlellme B {(p=
Σ oi (x:)(o,pp))
1/2
P/
Me
1/2
1 sup n (gEES)))
|P ... " llfellme p
Σ
+==1
1 sup
Σ
(tkss 1/2
$ n (FEEF));
[P ... Pre 18collop Melllm
where the inequality (6 is by the Schwartz inequality and the inequality (7) by Lemma A.1
Proposition 5.1
Let h A x A" - -E be an error function, let 91 be an R4-valued function
on the space of bounded linear operators on M1, and let 92 : [R.4 - TR. satisfy ge g2(a) S a & b. Assume the following mininization problem has a solution:
min (1GEM;)s
c. .... fi(w)) + gi (P ... Pfi lix) + 92 (2((
Then, there exists solution admitting representation of the form f, Ei=1 6x )c for some Cijj...., for =1..... L. Here, xa f3 ... fI())) 1,..., Lnd aa Tzz-
Proof Let (x) be the submodule of Mj generated by و5 (5 ... (5 Let S3 = 11) + It.
where /!! (x) and / (x Then, for 1..... L - 1, we have
fa(= (0) "edT")))s))))
(,)(=))),,,)),m (
(8)
In addition, we have
1-1 II P/, 12,
Pii-1 Pf. Pyili00
j=1
where (x) is the submodule of My generated by (- )... (x In the same manner as Eq. (8). we obtain
Σ
B
)a.
Σ و )ecs Σ
دج 25 (o) ))ss
Σ
17

---

Thus, we have (x) = p 12
Furthermore, we have
[1llll, 1KS + JE S + SEt Me - + (Lt. (E) Me mella IKS Malaa
where the last inequality is derived from the fact that (5L), M. + (Jt:st),. - (t) My positive and Theorem 2.2.5 (3) by Murphy [34]. As result, the statement proved.
Proposition 5.3
For j = 1, let (5y (x = Q2 be the QR decomposition of (3) Then, we have |P ... Plloo Gr Ry llp
(x)
Proof The result derived by the identities
| Pf. P/ llop -|QiP ... Pf. 1i = =1Qii - (x())))).....))))))
- (1
= [| Grllllop
Proposition 5.4
Assume GL is invertible. Then, we have
[P ... Priiocoloo S lIG | /11/2.
Proof Since GL is invertible, by Proposition 5.3
[Rt llop bounded as
[|Pr-- ... Pa (i) llap = Gr & R [z Ra olop = ||GZ | Gollop|[GTT 1lop
where the last equality derived by the identity [R llép = [R R2 = llopp
B Connection with Generalization Bound with Koopman Operators
Hashimoto et al. [8 derived generalization bound for the classical neural network composed of linear transformations and activation functions using Koopman operators. The Koopman operator the adjoint of the Aarron-Frobenius operator. In their analysis, they set the final transformation fr in an RKHS and observed that the transformation of each layer is injective, the noise is separated through the linear transformations and cut off by fi- Since the final transformation fr in our case is in an RKHM, the same interpretation about noise is valid for deep RKHM, too. Indeed, if fi o......, o1 not injective, then Gz is not invertible, which results in the right-hand side of the inequality ( going to infinity. The bound derived by Hashimoto et al. also goes to infinity if the network is not injective.
C Experimental Details and Additional Results
We provide details for the experiments in Section All the experiments are executed with Python 3.9 and TensorFlow 2.6 on Intel(R) Core(TM) i9 CPU and NVIDIA Quadro RTX 5000 GPU with CUDA 11.7.
C.1 Comparison with vyRKHS
We set (,, v) k(x, / for j = 1,...,3 3 with k(x,, = positive definite kernels.
(ecy- and 0.001 for optimizer, we used SGD. The learning rate is set 1e-4 both for the deep RKHM and deep vvRKHS. The initial value of c.j is set as (i.j eijs where dzj Aj the block matrix all of whose elements are 0.1 and Ej,j is randomly drawn from (0, 0.05). The result in Figure 2 is obtained by 5 independent runs.
= =<
18

---

C.2
Observation about benign overfitting
We set the same positive definite kernel as Subsection C.1 for j = 1,2. For the optimizer, we used SGD. The learning rate is set as 3 x le= The initial value of Ct.j is the same as Subsection C.1
The result in Figure ii obtained by independent runs.
C.3 Comparison CNN
We set (2, y) = k(zaa, (azaa.yay)2yy yay)zy" for 1, where a1 and d2 are block matrices whose block sizes are 2 and 4, for positive definite kernels. All the nonzero elements of aj are set as 1. We set a and 02 induce interactions in the block elements (see Remark 5.2)) For the optimizer, Adam with learning rate 1e-3 for both the deep RKHM and the CNN. The initial value of cajj is set as C.j. where G is randomly drawn from (00 0.1).
used
We combined the deep RKHM and CNN with 2 dense layers. Their activation functions are sigmoid and softmax, respectively. For the CNN layers, we also used the sigmoid activation functions. The loss function set as the categorical cross-entropy for the CNN. The result in Figure is obtained by 5 independent runs.
C.3.1 Memory consumption and computational cost
Memory consumption We used a CNN with (7 x 7) and (4 x 4)-fitters. On the other hand, for the deep RKHM, we learned the coefficients C.j in Proposition 5.1 for 1, and i = 1..... n. That is, we learned the following coefficients:
n( 20) block diagonal matrices each of whom has four (7 x 7)-blocks (for the first layer)
* n block diagonal matrices each of whom has seven (4 x 4)-blocks (for the second layer)
Thus, the size of the parameters we have learn for the deep RKHM is larger than the CNN. Since the memory consumption depends on the size of learning parameters, the memory consumption is larger for the deep RKHM than for the CNN.
Computational cost In each iteration, we compute f(x;) ) for i ......... and the derivative of with respect to the learning parameters. Here, f fi o fa the network. For the deep RKHM, we compute the product of a Gram matrix (composed of n x n block diagonal matrices) and a vector (composed of n block diagonal matrices) for computing f (a:)) for all = 1..... n. Thus, the computational cost for computing (xx; for all = ...... is Onndd(m; + m2)), where m. and m2 = 4 are the sizes of the block diagonal matrices. For the CNN, the computational cost for computing (xx)) for all i .n is (nd (4 + (2)). where 4 = 7 and l2 x 4 are the number of clements in the filters. Since we set = 20 and d = 28, the computational cost of the deep RKHM for computing f (xx)) for = ... n is smaller than that of the CNN. However, since the size of the learning parameters of the deep RKHM is large, the computational cost for computing the derivative of (I;)) is larger than that of the CNN.
To compare the deep RKHM to a CNN with the same size of learning parameters (the same memory consumption), we conducted the same experiment as the last experiment in the main text, excepting for the structure of the CNN, We constructed CNN with (28 x 7 20) and (28 4- 2f)-filters (The size of learning parameters is the same as the deep RKHM) and replaced the CNN used in the experiment in the main text. Figure shows the result. The result is similar to that in Figure (c), and the deep RKHM also outperforms the CNN with the same learning parameter size. Since the size of the learning parameter is the same in this case, the computational cost for one iteration for learning the deep RKHM is the same or smaller than that for learning the CNN.
Additional results
C.3.2 Additional results for benign ovefitting
We also observed benign overfitting for the deep RKHM We compared the train and test losses for the deep RKHM with X to those with X; = The results are illustrated Figure we set λ = 0 in Eq. @ i.e., do not minimize the term in Eq. (2). then whereas the training loss becomes small as the learning process proceeds, the test loss becomes large after sufficient iterations. On the other hand, if we set x i.c., minimize the term in Eq. 22, then the training loss becomes
19

---

0.6
Test Accuracy
RKHM, A 1
0.4
RKHM, Å₃ 0
CNN
100
200
300
400
Epochs
Figure 3: Comparison of deep RKHM to CNN with the same size of learning parameter.
\ =1 1
A 1
10-1
0.3
Train Loss
A 0
Test Loss
d 0
10-2
10-3
10
100
200
300
400
100
200
300
400
Epochs
Epochs
Figure 4: Train loss and test loss for the MNIST classification task with (A 1) and without (A 0) the minimization the second term in Eq. I regarding the Perron-Frobenius operators.
smaller than the case of A O, and the test loss does not become large even the learning process proceeds. The result implies that the term regarding the Perron-Fruet Frobenius operators in Eq. causes overfitting, but it is benign overfitting.
20


Reviews:
[{"review_id": "rmmeX8FLXz", "reviewer": "Reviewer_eQG4", "summary": "The paper establishes properties on the composition of functions belonging to a RKHM, a generaliztion of RKHSs. The authors compute the Rademacher complexity of this function class and establish a representer theorem. ", "questions": "- What exactly is being done when writing \"Thus\" in the proof of Lemma 2.7 ? What does well defined mean? Are you showing existence of such a map ? It is unclear.\n- How is Corollary 4.7 derived ? Can you give more details. In particular, how do you control the operator norm of the Perron-Frobenius operator without assuming that the intermediate $\\phi_i$ are bounded ?", "limitations": "Limitations are discussed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The objects studied in the paper are well introduced. The writing is generally clear.\n- The paper adds another way formalizing the composition of linear models.", "weaknesses": "- The derivations of both the results of the paper are standard : the computation of Rademacher complexity using Cauchy-Schwartz + Jensen is essentially the same for all linear models. It is reproduced here with more terminology and higher dimensions but the steps are the same. The representer theorem which relies simply on the fact that the orthogonal component doesn't affect the objective is the same standard proof for kernels.\n- It is unclear what is gained from this additional abstraction. The paragraph on the connection to CNNs is unconvincing: CNNs learn the filters, whereas (composition) of linear models have fixed filters but learn the coefficients of the terms in the sum. It is difficult to argue that this much abstraction is necessary to derive this observation.\n\n    *The additional abstraction leads to doubts over existence of the objects*:  the existence of a \"well defined\" Perron-Frobenius operator is only established for a very specific case in Lemma 2.8, which appears to be artificial as it is a regular complex valued kernel multiplied by a matrix to create a multi-output kernel. \n\n- The term benign overfitting does not seem appropriate as it is discussed in section 6.2 of the paper :  The term benign overfitting refers to the phenomenon observed that *complex function classes* can fit training data noise without loosing performance on the test set. In section 6.2 the discussion is on the *complexity of the function class*. The authors say that *regularization*  in eq(2) with the operator norm of the Perron-Frobenius operator composition decreases the function class complexity and therefore leads to better generalization, which is normal and expected. This goes completely against the unusual empirical observations that led to the study of benign overfitting - which is that *complex function classes generalize without regularization*. How can benign overfitting be discussed by analyzing a **uniform** generalization bound ?\n\n- The general motivation of this work can be further developed (i.e slightly longer first paragraph) : Why should we formalize compositions of linear models ? The representer theorem is good to have but we have no convexity, so why use a composition of linear models instead of simply learning the feature embeddings as well if convexity is already lost ? Why are \"deep\" kernels worthy of study ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Derivations of the results\nOur Rademacher complexity analysis and representer theorem for RKHM use Cauchy-Schwarz, Jensen inequalities, and orthogonality arguments, as most of the results in the RKHS case. However, it is important to be precise that there are specificities and technical difficulties peculiar to RKHM that we adequately addressed. This is why we improved the bound.\nOur main idea is to use the operator norm to reduce the dependency of the generalization bound on the output dimension.\nIn the existing study of RKHM, the trace of operators is considered instead of the operator norm.\nAvailability of the operator norm is by virtue of the application of $C^*$-algebra, and whether we can combine the standard approaches, such as Cauchy-Schwartz and Jensen, with the operator norm or not is nontrivial.\nFor example, in the proofs of Lem. 4.4 and Prop. 4.6, we used a semi-inner product.\nAlso, in the proof of Prop. 4.6, we need another lemma (Lem. A.1) to split the operator norm of the Perron-Frobenius (P-F) operator $P_{f_{L-1}}\\cdots P_{f_1}$ and the absolute value of $\\sum_{i=1}^n\\phi_1(x_i)(\\sigma_ip^*)$.\nApplying P-F operators is also our main idea and not a standard approach.\n\n### Connection with CNN and well-definedness of the Perron-Frobenius (P-F) operators\nOur idea to connect kernel methods and CNN is based on the concepts of $C^*$-algebra and deep RKHM. Our connection relies on the observation that by considering the $C^*$-algebra $\\mathcal{A}$ of circulant matrices, we can represent the convolution as the product of elements in the $C^*$-algebra.\nIndeed, $\\mathcal{A}$-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.\nWe mentioned in the paper that for deep RKHM, we learn the coefficients $c_i$, while for CNN we learn the filters $a_j$ (line 244-245). 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.\n\nMoreover, separable kernels ($\\mathcal{A}$-valued kernel defined by a complex-valued kernel and an operator) are widely used in existing literature of vvRKHS; please see e.g. [1].\nWe might well say that it is the most used class of operator-valued kernels in the ML literature. It includes all scalar-valued kernels as a special case.\nLem. 2.8 guarantees the validity of the analysis with Perron-Frobenius operators, at least in the separable case.\nThis paper is the first paper that combines deep kernel methods with $C^*$-algebra.\nOur study provides a condition for \"good kernels\" by means of the well-definedness of the P-F operator.\nAs we already mentioned in Conclusion of our paper, more detailed analysis for other kernels is future work.\n\n### Benign overfitting\nWe are sorry the term \"regularization\" may be misleading since the operator norm of the P-F composition depends on the training data.\nThe 2nd term in Eq. (1) and the right hand side of Eq. (2) are expected to cause overfitting since these terms depend on the training data. (The Gram matrix $G_L$ depends on the data.)\nStandard existing regularizations, such as the one for kernel ridge regression (the 3rd term in Eq. (1)) and $l_p$ regularization of weight matrices for neural networks, do not depend on the data.\nPlease note the 3rd term in Eq. (1) does not depend on the training data before applying the representer theorem.\nThe term in Eq. (2) is different from these standard regularizations.\n\nIf we try to minimize a value depending on the training data, the model seems to be more specific for the training data, and it may cause overfitting.\nThus, the connection between the minimization of the 2nd term in Eq. (1) and generalization cannot be explained by the classical argument about generalization and regularization, and we need the argument of benign overfitting.\nIn the 3rd experiment in Sec. 7, we can also observe benign overfitting.\nPlease see Fig. 1 in the PDF file attached at the top of the review part.\nIf $\\lambda_1=0$ in Eq. (1) (do not minimize the term in Eq. (2)), then whereas the training loss becomes small as the learning process proceeds, the test loss becomes large after sufficient iterations.\nOn the other hand, if $\\lambda_1=1$ (minimize the term in Eq. (2)), then the training loss becomes smaller than the case of $\\lambda_1=0$, and the test loss does not become large even the learning process proceeds.\n\n### Motivation\nLet us first note the models we are considering are nonlinear.\nAll of the functions $f_1,\\ldots,f_L$ introduced in Sec. 3 are nonlinear functions.\nBy virtue of the composition, the model $f=f_L\\circ \\cdots\\circ f_1$ is also nonlinear with respect to the coefficients $c_{i,j}$ introduced in the representer thm (Prop. 5.1).\n\nThe motivation for studying deep kernel methods is that we try to combine the flexibility of deep neural networks with the representation power and solid theoretical understanding of kernel methods.\nWe cannot guarantee the convexity of the loss functions, but the situation is the same as the case of neural networks.\nWe don't have the convexity of the loss functions for neural networks.\nOur motivation for studying deep RKHM is that we apply the novel perspective of RKHM to deep kernel methods in order to make the deep kernel methods more powerful.\n\n### Answer of the Questions\n- Well-definedness of $P_f$ means \"if $u=v$ for $u,v\\in M_{k,0}$, then $P_fu=P_fv$\". We are sorry the last formula in the proof of Lem. 2.7 should be $P_f\\sum_{i=1}^n\\phi_1(x_i)d_i$ (it is a typo).\n- Cor. 4.7 is derived by applying the inequalities $\\Vert P_{f_j}\\Vert\\le B_j$ ($j=1,\\ldots,L-1$) and $\\Vert f_L\\Vert\\le B_L$ to the result in Prop. 4.6. These inequalities for intermediate layers are by the definition of $\\mathcal{F}_j$."}, {"review_id": "IrG0yfpePS", "reviewer": "Reviewer_Hurc", "summary": "This paper proposes deep Reproducing kernel Hilbert $\\mathcal{C}^*$-module (RKHM), a deep learning framework for kernel methods， which generalizes RKHS by means of $\\mathcal{C}^*$-algebra. In this setting, a map as the composition of functions in RKHMs is constructed. Theoretically, the authors develop a new Rademacher generalization bound of deep RKHM using Perron-Frobenious norm. The dependency of the bound on the output dimension is milder than existing bounds. Moreover, they show a representer theorem to guarantee that the solution of a given practical minimization problem is represented only with given data. In addition, they show connections of deep RKHM with existing studies such as CNNs, benign overfitting and neural tangent kernel. Furthermore, this paper presents a series of numerical experiments to support their theory and show the practical performance of deep RKHM.\n", "questions": "Can you explain how the generalization bounds in Theorem 4.1 and Theorem 4.5 depend on the input dimension?", "limitations": "The authors have clearly addressed the limitations of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper provides a new approach to analyze and understand deep kernel methods. In particular, the authors derives a generalization bound for deep RKHMs, while existing work focuses on shallow RKHMs. This bound also relaxes the dependence on the output dimension by using Perron-Frobenious norm. It is also interesting how this bound relates to benign overfitting.\n\nMoreover, this paper provides some experiments to support their theoretical findings.\n \nThe paper is technically sound and the contents are very relevant to the community of NeurIPS.", "weaknesses": "The paper is well-organized and well-written.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Dependency on the input dimension\nThe input dimension depends on the generalization bound through the $\\mathcal{A}$-valued kernel $k$.\nIn Thms. 4.1 and 4.5, the bound depends on $\\mathrm{tr}(k(x_i,x_i))$.\nTherefore, the dependency of the input dimension on the bound is determined by the dependency of the input dimension on the $\\mathcal{A}$-valued kernel $k$."}, {"review_id": "jq2bWCzvDF", "reviewer": "Reviewer_HsSA", "summary": "The authors introduce a generalization of RKHS for $C^*$ algebra valued kernels, called RKHM; they build networks by composing sequentially elements taken from a collection of RKHMs, one RKHM per layer. They prove generalization bounds for those networks. These networks output matrices at each layer.", "questions": "In 'Connection with neural tangent kernel', is the aim of this paragraph to define a neural tangent kernel for deep RKHM? \n\nIn 'Comparison to CNN', how long does the training take and what is the memory consumption of RKHM and CNN?", "limitations": "In Conclusion and Limitations, I feel that the statement 'connections with existing studies such as CNNs and neural tangent kernel' is a bit of a strong statement as the authors explain in section 6.1 that CNN and RKHM do not really relate to one another and it is unclear to me how deep the connection to neural tangent kernel is.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I believe that a strength of the paper is that the generalization bound obtained in this paper for RKHM is better than the known ones for vvRKHS. It is unclear to me if RKHMs generalize vvRKHSs: maybe considering RKHM in the commutative $C^*$ of diagonal matrices is a way to represent a vvRKHS as an RKHM. If it is the case then the result of this paper is a better generalization bound for vvRKHS.", "weaknesses": "I feel that the paper is sometimes difficult to read. For example the name '$\\mathcal{A}$-valued positive definite kernel' does not refer to the space $\\mathcal{X}$ that characterizes the domain of the kernel; when defining deep RKHM knowing this information could help make explicit what the domain of $k_j$ as being $A_{j-1}\\times A_{j-1}$.\nTwo remarks in this direction are on some notations: \n- line 83:  shouldn't the content of the brace in the definition of $M_{k,0}$ be $\\sum_{i=1}^{n} \\phi(x_i) c_i \\vert n\\in \\mathbb{N}, (c_i\\in A, i\\leq n), (x_i\\in \\mathcal{X}, i\\leq n) $\n\n- equation line 195, maybe the notation: $(f_j\\in \\mathcal{M}_j)_j$, could recall that the optimization is over all the RKHMs that define the networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Relation between RKHM and vvRKHS\nRKHM is a generalization of vvRKHS in the sense that we can reconstruct vvRKHS using RKHM (Please refer Thm. 4.13 of [2]).\nSince the output space of the functions in a vvRKHS is not necessarily a $C^*$-algebra, the connection between RKHM and vvRKHS is a little complicated.\nAn important advantage of RKHM over vvRKHS is that we can incorporate the flexibility of $C^*$-algebra into kernel methods.\nIndeed, the idea of using the operator norm to improve the bound proposed in this paper comes from the perspective of RKHM, and cannot be obtained from the perspective of vvRKHS.\n\nAs for the generalization bound, if the kernel has the form $k=\\tilde{k}I$ for a complex-valued kernel $\\tilde{k}$ and the $D\\times D$ identity matrix $I$, then our result reduces the dependency on the output dimension of the vvRKHS.\nThis is achieved by putting $D$ elements in a $D$-dimensional vector $v$ in a $\\lceil \\sqrt{D}\\rceil\\times \\lceil \\sqrt{D}\\rceil$ matrix.\nThen, instead of considering $D\\times D$ matrix-valued kernel for the vvRKHS, we only need $\\lceil \\sqrt{D}\\rceil\\times \\lceil \\sqrt{D}\\rceil$ matrix-valued kernel for the RKHM.\nAs a result, the dependency reduces from $D$ to $\\lceil \\sqrt{D}\\rceil$.\nSince the action of the above kernel to a vector is described by the elementwise multiplication of the complex-valued kernel $\\tilde{k}$ to the vector, the construction of the matrix-valued kernel is trivial.\nWe can generalize the above argument to the case of $k=\\tilde{k}a$ for general $a\\in\\mathbb{C}^{D\\times D}$ by considering $av$ instead of $v$ to construct the $\\lceil \\sqrt{D}\\rceil\\times \\lceil \\sqrt{D}\\rceil$ matrix.\nSince separable kernels are widely used, our result is valid in many cases.\nIn more general cases, the relationship between RKHMs and vvRKHSs is more complicated, and investigating how we can apply this type of argument to vvRKHS with more general kernels is future work.\n\n### Readability\nWe will improve readability based on your comments.\n\n### Connection with neural tangent kernel\nThe aim of this paragraph is to define a neural tangent kernel for $C^*$-algebra network (a generalization of neural networks by means of $C^*$-algebra, please see [3]) and developing a theory for combining neural networks and deep RKHMs.\nExisting studies investigate the connection between neural networks and kernel methods through neural tangent kernels.\nWe show the analogy of the existing connection for $C^*$-algebra networks and RKHMs.\nAs we stated in Rem. 6.2, by virtue of the arguments in this paragraph, we can regard deep neural networks as one-layer (shallow) RKHM, which enables us to analyze the combination of neural networks and deep RKHMs.\n\n### Comparison to CNN\n**Memory consumption**  \nIn the experiment of the comparison to CNNs in the paper, we used a CNN with $(7\\times 7)$ and $(4\\times 4)$-filters.\nOn the other hand, for the deep RKHM we used in this experiment, we learned the coefficients $c_{i,j}$ in Prop. 5.1 for $j=1,2$ and $i=1,\\ldots,n$.\nThat is, we learned the following coefficient:\n\n- $n(=20)$ block diagonal matrices each of whom has four $(7\\times 7)$-blocks (for the 1st layer)\n\n- $n$ block diagonal matrices each of whom has seven $(4\\times 4)$-blocks (for the 2nd layer)\n\nThus, the size of the parameters we have to learn for the deep RKHM is larger than the CNN.\nSince the memory consumption depends on the size of learning parameters, the memory consumption is larger for the deep RKHM than for the CNN.\n\n**Computational cost**  \nIn each iteration, we compute $f(x_i)$ for $i=1,\\ldots,n$ and the derivative of $f$ with respect to the learning parameters.\nHere, $f=f_1\\circ f_2$ is the network.\nFor the deep RKHM, we compute the product of a Gram matrix (composed of $n\\times n$ block diagonal matrices) and a vector (composed of $n$ block diagonal matrices) for computing $f_j(x_i)$ for all $i=1,\\ldots,n$. \nThus, the computational cost for computing $f(x_i)$ for all $i=1,\\ldots,n$ is $O(n^2d(m_1+m_2))$, where $m_1=7$ and $m_2=4$ are the sizes of the block diagonal matrices.\nFor the CNN, the computational cost for computing $f(x_i)$ for all $i=1,\\ldots,n$ is $O(nd^2(l_1+l_2))$, where $l_1=7\\times 7$ and $l_2=4\\times 4$ are the number of elements in the filters.\nSince we set $n=20$ and $d=28$, the computational cost of the deep RKHM for computing $f(x_i)$ for $i=1,\\ldots,n$ is smaller than that of the CNN.\nHowever, since the size of the learning parameters of the deep RKHM is large, the computational cost for computing the derivative of $f(x_i)$ is larger than that of the CNN.\n\n**Additional experiment**  \nTo compare the deep RKHM to a CNN with the same size of learning parameters (the same memory consumption), we did an additional experiment.\nWe constructed a CNN with $(28\\times 7\\cdot 20)$ and $(28\\times 4\\cdot 20)$-filters (The size of learning parameters is the same as the deep RKHM) and replaced the CNN used in the paper with this CNN.\nPlease see Fig. 2 in the PDF file attached at the top of the review part.\nThe result is similar to that in the paper, and the deep RKHM also outperforms the CNN with the same learning parameter size.\nSince the size of the learning parameter is the same in this case, the computational cost for one iteration for learning the deep RKHM is the same or smaller than that for learning the CNN.\n\n### Connection with existing studies\nIn our paper, the term \"connection\" does not mean that the two objects are the same.\nIn Sec. 6.1, we showed that whereas CNNs learn filters, deep RKHMs learn activation functions.\nAs for the neural tangent kernel, as we also stated in the response of the first question, the arguments in Sec. 6.3 enable us to analyze the combination of neural and kernel networks.\nThis makes our analysis more flexible.\nThis paper is the first paper on deep kernel methods with RKHM, and we provide new features for deep kernel methods.\nWe will investigate connections with existing methods deeper in future work."}, {"review_id": "To6xLlAopx", "reviewer": "Reviewer_gE5P", "summary": "The authors combines RKHM and Perron-Frobenious Operator to deep RKHM, a deep learning framework for kernel methods. By virtue of $C^*$-algebra, they manage to get a better bound on Rademacher generalization error and provide a clear connection with CNNs. Their theoretical analysis provides a new lens for deep kernel theory.", "questions": "Any theoretical understanding of why deep RKHMs might be better than nondeep ones?", "limitations": "The authors very adequately addressed the limitations. Very impressive.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Clear writing\n2. Very solid results\n3. Novel tools\n4. Their work can be inspiring.\n5. Experiments support their theories", "weaknesses": "As the authors say, more efficient methods specific to deep RKHM remains to be investigated in future work. It remains a problem to scale up to at least ImageNet to be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### More efficient methods specific to deep RKHM\nAs we stated in Rem. 5.6, we can apply random Fourier features to reduce the computational cost, but as you point out, methods specific to deep RKHM should be investigated as future work.\nWe will study more about this topic and conduct some experiments with ImageNet to check the computational efficiency.\n\n### Advantage of deep RKHM over shallow RKHM\nThe motivation for studying deep kernel methods is that we try to combine the flexibility of deep neural networks with the representation power and solid theoretical understanding of kernel methods.\nFrom the theoretical point of view, the arguments in Subsection 6.2 about benign overfitting are valid only for deep RKHMs (i.e., $L\\ge 2$).\nIf $L=1$ (shallow RKHM), then the Gram matrix $G_L=[k(x_i,x_j)]$ is fixed and determined only by the training data and the kernel.\nOn the other hand, if $L\\ge 2$ (deep RKHM), then $G_L=[k_L(f_{L-1} \\circ \\cdots \\circ f_1(x_i),f_{L-1} \\circ \\cdots \\circ f_1(x_j))]$ depends also on $f_{1},\\ldots,f_{L-1}$.\nAs a result, by adopting the regularization using $G_L$, we can learn proper $f_1,\\ldots,f_{L-1}$ so that they make the regularization term small and the whole network overfits benignly.\nAs $L$ becomes large, the function $f_{L-1}\\circ\\cdots\\circ f_1$ changes more flexibly to attain a smaller value of the regularization term.\n"}]

Author rebuttal:
## To all the reviewers
Thank you very much for your constructive comments. We address your questions and concerns below. We will revise our paper based on your comments and the response below for the camera-ready version.

We attached a PDF file to support some of our responses here. Also, we provide references for our responses here.

[1] Mauricio A.  Alvarez, Lorenzo Rosasco, Neil D. Lawrence, et al. Kernels for vector-valued functions: A review. Foundations and Trends in Machine Learning, 4(3):195–266, 2012.

[2] Yuka Hashimoto, Isao Ishikawa, Masahiro Ikeda, Fuyuta Komura, Takeshi Katsura, and Yoshinobu Kawahara. Reproducing kernel Hilbert $C^*$-module and kernel mean embeddings. JMLR, 22(267):1–56, 2021.

[3] Ryuichiro Hataya and Yuka Hashimoto. Noncommutative $C^*$-algebra net: Learning neural networks with powerful product structure in $C^*$-algebra. arXiv: 2302.01191.

Meta-review: This paper proposes deep Reproducing kernel Hilbert-module (RKHM), a deep learning framework for kernel methods, which generalizes RKHSs. The authors compute the Rademacher complexity of this function class and establish a representer theorem.

All reviewers liked the paper and therefore my recommendation is to accept it.
Decision: Accept (poster)