Spectral Truncation Kernels: Noncommutativity in $C^*$-algebraic Kernel Machines

Thank you very much for your constructive comments. We addressed you comments and questions and revised the paper. We summarize the answers below.

[Q1] Presentation regarding the Fourier function
We are sorry for the confusion. We replaced the sentence with "Let $e_j$ be the Fourier function defined as $e_j(z)=\mathrm{e}^{\mathrm{i}jz}$ for $j\in\mathbb{Z}$".

[Q2] Benefits of introducing noncommutativity
Although benefits in the terms of convergence and generalization are also important, but the main scope of this paper is to propose kernels going beyond commutative and separable kernels with lower computational cost than existing operator-valued kernels with the framework of vvRKHSs. Separable and commutative kernels are two extreme cases regarding the dependencies between input and output variables. For separable kernels, the output is determined only by the global information of the input. On the other hand, commutative kernels only identify the pointwise (completely local) dependencies. The proposed kernel fill a gap between separable and commutative kernels with lower computational cost than existing operator-valued kernels. Indeed, the proposed kernel is indexed by the truncation parameter $n$, and we showed that the proposed kernels converge to the commutative kernels as $n$ goes to infinity. On the other hand, if $n=1$, then the proposed kernels are separable kernel. If $n$ is small, the proposed kernel focuses more on global information of input functions. If $n$ is large, the proposed kernel focuses more on local information of input functions. This feature is achieved by introducing the noncommutativity to typical commutative kernels by applying the theory of spectral truncation, and is described by the property of the Fejer kernel. We revised Sections 1 and 3 and added Appendices A and B to clarify the benefit of introducing the noncommutativity.

[Q3] Theoretical guidance for the selection of $n$, how much $n$ is suitable for well approximated
Although $k_n^{\operatorname{poly},q}$, $k_n^{\operatorname{prod},q}$, and $k_n^{\operatorname{sep},q}$ can approximate $k^{\operatorname{poly},q}$, $k^{\operatorname{prod},q}$, and $k^{\operatorname{sep},q}$, our goal is not approximating the commutative kernels $k^{\operatorname{poly},q}$, $k^{\operatorname{prod},q}$, and $k^{\operatorname{sep},q}$. As we explained above, by setting $n$ as a finite value, we can go beyond separable and commutative kernels. Indeed, the parameter $n$ controls the input and output dependencies. If $n$ is small, the proposed kernel focuses more on global information of input functions. If $n$ is large, the proposed kernel focuses more on local information of input functions. This feature is described by the property of the Fejer kernel. We can determine optimal $n$ in the sense of the dependencies by observing the Fejer function $F_n^{2q,P}$. Since the proposed kernel is defined by the convolution of the input function with the Fejer kernel, the volume of the region where the value of the Fejer kernel is sufficiently large corresponds to the range of local dependencies. Thus, if we have a information of the local dependencies, then we can choose $n$ based on the values of $F_n^{2q,P}$.

In Appendix B, we added Remark B.1 about determining $n$ discussed above. We also added Figure 2 for helping understand the property of the Fejer kernel.

[Q4,Q5] Defference from previous results of generalization bounds
The argument regarding the representation power and model complexity is common. However, since we proposed a new kernel, it is important to check this common property is also valid to the proposed kernel. This paper is the first step of proposing kernels that beyond separable and commutative kernels based on the noncommutativity and speatral truncation. More detailed analysis of what benefit is obtaind in the sense of generalization bound compared to other machine learning methods is future work.

Thank you for the additional questions.

Regarding the deep methods with kernels, they are also suited to the case where the number of samples are limited. An advantage of the deep methods with kernels is their connection with benign overfitting. As discussed in Section 6.2 in [3], we can learn models so that they overfit benignly if the number $L$ of layers is $L\ge 2$. Regarding the comparison with the theory of DNNs, not only the theoretical analysis of kernel methods is simpler, but also the deep model with kernels has an advantage on generalization bound. As discussed in Section 6.4 in [3], for the deep model with kernels, we can obtain a generalization bound whose dependency on the widths of the layers is smaller than those for DNNs. Different from obtaining the deep structure by the composition of kernels, such as [1] and [3], the deep structure in our case, discussed in Section 6, is obtained by the product of the proposed kernels, and is for improving the performance. We can extract both local and global dependencies at the same time by considering the product of the kernels. We can also apply the proposed kernels to the deep structure discussed in [1,3], and then we can have the same advantages of the deep methods discussed in [1,3], as discussed above.

[3] Yuka Hashimoto, Masahiro Ikeda, and Hachem Kadri, "Deep learning with kernels through RKHM and the Perron-Frobenius operator", NeurIPS 2023.

Thank you very much for your constructive comments. We addressed you comments and questions and revised the paper. We summarize the answers below. Please see the global comment at the top of this page for more details of the motivation of this paper.

[W1] Benefit from the new algebraic structures
An important benefit of applying the noncommutative algebraic structure is that we can go beyond separable and commutative kernels with low computational cost. By virtue of the noncommutative structure, we can generalize commutative kernels, which enables us to induce interactions along data function domain. Since the kernel is function-valued, we can apply the framework of RKHMs and can obtain the final solution with the calculation of functions, which results in lower computational cost than the vvRKHS method with existing operator-valued kernels.

[W2] Kernel choices in practice
Applying the proposed kernels, we can extract both local and global dependencies of the output function on the input function. The proposed kernel has a parameter $n$, which control how much we focus on local dependencies. The optimal choice of $n$ depends on data and tasks. If we want to focus on the global dependencies, then $n$ should be set as a small number. On the other hand, if we want to focus on local dependencies, then $n$ should be set as a large number.

Thank you very much for your constructive comments. We addressed you comments and questions and revised the paper. We summarize the answers below.

[W1] Application of approximation techniques
Although we obtain a Gram matrix $G$ with function-valued elements for the proposed kernel, we can obtain the $\mathbb{C}^{N\times N}$ Gram matrix by evaluating it at a certain point $z$. Then, we can apply low-rank approximations such as the Nystrom method to $G(z)\in\mathbb{C}^{N\times N}$. In this way, we can reduce the computational cost with respect to $N$ for the proposed kernel, too. In the last paragraph of Section 5, we tried to insist that we can apply the Nystrom method to the proposed kernel, but we are sorry that the sentences were not clear. We revised the last paragraph of Section 5 to clarify the above point.

The main goal of this paper is to propose a new class of function-valued kernels based on spectral truncation and investigate their fundamental properties. Thus, although we can apply some approximation methods to the proposed kernels, we focused more on the basic method without the approximation. In addition, we may develop approximation methods by taking advantages of the fact that the output of the kernels are functions. However, more detaild observation about the approximation methods that is specific to the proposed kernel is future work.

[W2] Analysis of the deep model
The goal of Proposietion 6.1 is not providing general analysis for deep models, but providing a certain archtecture that is effective in the sense of the deep model. For the deep model, we can construct the model by parameterizing the learnable values, and specifying the model architecture is important. The result in Proposition 6.1 provides a certain architecture of the deep model that achieves the exponential growth of the representation power with respect to the number of layers. Thus, this result is useful in constructing a model with a theoretical guarantee.

[W3] Additional experiments with more complex, real-world datasets
The motivation of this paper is to propose kernels going beyond the separable and commutative kernels with low computational cost and to theoretically investigate their fundamental properties. This work is the first attempt to achieve the above goal, and the goal of the numerical experiments in this paper is to confirm these fundamental properties, and more detailed experimental investigation is beyond the scope of this paper. Please see the global comment at the top of this page for more details of the motivation of this paper.

Dear Reviewer 33dL,

Thank you again for your comments. Regarding [W3], our main goal is to propose kernels going beyond the separable and commutative kernels with low computational cost and to theoretically investigate their fundamental properties. However, we agree that more experimental results are needed for showing the availability of the proposed kernels to pratical applications. For this purpose, we conducted an additional experiment.

One potential application of the proposed kernel is the application to operator learning. In the framework of operator learning, we obtain a solution of a partial differential equation as an output from an input function (such as initial condition or parameter of the equation). Thus, we construct a model where both of the input and output are functions. Applying kernel methods to operator learning has been proposed [1]. We can construct the model by solving a kernel ridge regression task. Please see Appendix D for more details.

We applied the proposed kernel to operator learning and obtained a higher performance than the existing method proposed in [1]. Please see Appendix D.1 (colored in blue) for more details.

Although experiments for more complex cases are future work, we believe this result adresses your point [W3], and shows the possibility of the proposed kernels for futher applications. If you have any additional comments, questions, and concerns, please let us know.

[1] Pau Batlle, Matthieu Darcy, Bamdad Hosseini, and Houman Owhadi, "Kernel methods are competitive for operator learning", Journal of Computational Physics, 496(1):112549, 2024.

Thank you for your response.

We would like to emphasize that our proposed technique is not on the framework of vvRKHSs, but on the framework of RKHMs [1]. As we explained in the global comment, the proposed kernels fill a gap between existing operator-valued kernels: separable and commutative kernels. For the cases $n=1$ and $n=\infty$, the proposed kernels are equivalent to the existing operator-valued kernels, where $n$ is the truncation parameter. However, if $1<n<\infty$, they are different from existing operator-valued kernels, but they are function-valued kernels ($C^*$-algebra-valued kernels). We combined the proposed kernels with the framework of RKHMs. The reason why we can reduce the computational cost compared to the existing operator-valued kernels is that we proposed function-valued kernels and applied the framework of RKHMs. Please see table 1 and Section 5 for more details.

The framework of RKHMs is a newly developed framework, and this paper gives a potential power of the application of RKHMs. This is the first paper that proposed function-valued kernels in the framework of RKHMs and showed its computational efficiency over the framework of vvRKHSs.

[1] Yuka Hasimoto, Masahiro Ikeda, and Hachem Kadri, $C^*$-Algebraic Machine Learning − Moving in a New Direction, ICML 2024.

Dear Reviewer 33dL,

Apologies for our continuous messages. Since the end of the discussion period is approaching, we would appreciate if you could let us know whether the above answer and additional experiment address your comments or not and let us know if you have additional questions, comments, and concerns related to these points. Thank you for your time.

Thank you very much for your constructive comments. We addressed you comments and questions and revised the paper. We summarize the answers below.

[Q1] Motivation, pros, and cons of the proposed method
The motivation of this paper is to propose kernels going beyond the separable and commutative (defined only with the pointwise calculation of functions or vectors) kernels with low computational cost. In the framework of vvRKHSs, transformable kernels and combinations of them with separable kernels have been proposed to go beyond separable and commutative kernels. However, an important shortcoming of them is the significant computational cost. To resolve this issue, we propose a function-valued kernel combined with the framework of RKHMs. Separable and commutative kernels are two extreme cases regarding the dependencies between input and output variables. Separable kernels identify dependencies between input and output variables separately, and cannot reflect information of input variables properly to output variables. For the separable kernels, the output is determined only by the global information of the input. On the other hand, commutative kernels only identify the pointwise (completely local) dependencies. The proposed kernel fill a gap between separable and commutative kernels with lower computational cost than existing operator-valued kernels. Indeed, we show that the proposed kernels converge to the commutative kernels as the truncation parameter $n$ goes to infinity. On the other hand, if $n=1$, then the proposed kernels are separable kernels. If $n$ is small, the proposed kernel focuses more on global information of input functions. If $n$ is large, the proposed kernel focuses more on local information of input functions. This feature is achieved by introducing the noncommutativity to typical commutative kernels by applying the theory of spectral truncation, and is described by the property of the Fejer kernel. The Fejer kernel goes to the delta function as $n$ goes to infinity. Please see Figure 2 in appendix B for more details about the Fejer kernel.

As we discussed in Section 8, one limitation of the proposed kernels is that if we generalize them to those for more general functions than functions on the torus, then the theoretical analysis becomes more complicated, and the results in this paper may not valid for the generalized kernels. Although we can formally generalize the kernels, thorough theoretical analysis for the generalized kernels is future work.

We revised the introduction and Section 3 to emphasize more on this motivation. In addition, we added Sections A and B in the appendix to explain it in more detail.

[Q2] Issue with commutativity and the benefit of noncommutativity
Commutative kernels only identify completely local relationship between the input function and the output function. The value of the output function at $z$ is determined only with the value of the input function at $z$. For example, if we have a time-series input $[x_1,\ldots,x_d]\in\mathcal{A}^d$ as explanatory variables and try to obtain an output function as a response variable, the values of $x_1(z),\ldots,x_d(z)$ at time $z$ is strongly related to the value of the output at time $z$, but may also related to $y(z+t)$ for $t\in [-T,T]$ for a small number $T$. In this case, the commutative kernels are not suitable for extracting the relationship between $x_1(z),\ldots,x_d(z)$ and the values of the output around $z$, not only at $z$. We documented detailed explanations of commutative kernels in Appendix A.

Applying the theory of spectral truncation, we can induce the noncommutativity from commutative kernels and extract the relationship between $x_1(z),\ldots,x_d(z)$ and the values of the output around $z$. Moreover, we can control how much we will focus on local information by changing the value of $n$. If $n$ is large, then we can focus more on local information.

Dear Reviewer vkGt,

We just want to let you know that since the deadline of revising the paper is approaching, we updated our paper by adding additional experimental results about operator learning in Appendix D.1 (colored in blue). We think this modification is related to your comments about the practical applications. Thank you again for your time and valuable comments.