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

Authors: Yuka Hashimoto, Ayoub Hafid, Masahiro Ikeda, Hachem Kadri
Primary area: learning theory
Keywords: kernel methods, positive definite kernel, spectral truncation

Abstract:
$C^*$-algebra-valued kernels could pave the way for the next generation of kernel machines. To further our fundamental understanding of learning with $C^*$-algebraic kernels, we propose a new class of positive definite kernels based on the spectral truncation. We focus on kernels whose inputs and outputs are vectors or functions and generalize typical kernels by introducing the noncommutativity of the products appearing in the kernels. The noncommutativity induces interactions along the data function domain. We show that it is a governing factor leading to performance enhancement: we can balance the representation power and the model complexity. We also propose a deep learning perspective to increase the representation capacity of spectral truncation kernels. The flexibility of the proposed class of kernels allows us to go beyond previous separable and commutative kernels, addressing two of the foremost issues regarding learning in vector-valued RKHSs, namely the choice of the kernel and the computational cost.

Decision: reject
Reviewer scores: 6, 3, 6, 6

Reviews and discussion:
<thread>
creation date:
1730476741602

thread_type:
official_review

<thread_object>
creator: reviewer_jz5n

<content>
summary:
In this paper, authors propose a set of positive definite spectral truncation kernels, which is a class of the $C^*$-Algebra-valued kernel. The definitions of the proposed kernels involve several concepts, including $C^*$-Algebra, function-valued kernel, spectral truncation, and the torus. The authors provide a theoretical analysis of the convergence and generalization.  In addition, the authors introduce a noncommutativity and further illustrate its effectiveness with numerical results.

strengths:
1. This paper is well written and organized.
2. Theoretical analysis is detailed, enabling the proposed method to have solid theoretical support.
3. The authors consider the deep spectral truncation kernel, sharing the advantage of both deep model and spectral truncation kernel, to improve the representation power.

weaknesses:
Please see the **Questions** section.

questions:
1. In line 156, $z \in \mathbb{T}$ be the Fourier function. Why $z$ is a function? Based on the **Example 2.2**, $\mathbb{T}$ is a set, and the elements of $\mathbb{T}$ are real numbers. This puzzled me.
2. One of the main contributions of this paper is that the authors generalize typical kernels by introducing the noncommutativity of the products appearing in the kernels and showing their advantages. This is because $\mathcal{R}_n (x)$ and $\mathcal{R}_n (y)$, based on the spectral truncation, is noncommutative. However, the benefits of introducing noncommutativity in terms of convergence and generalization were not found. The effect of the noncommutativity is just illustrated in the experiment part. Or am I missing some details?
3. **Theory 3.4** gives the theoretical result of the convergence of proposed kernels. Does this mean that the proposed $k_n^{poly,q}(x, y)(z)$, $k_n^{prod,q}(x, y)(z)$, and $k_n^{seq,q}(x, y)(z)$  can approximate $k^{poly,q}(x, y)(z)$, $k^{prod,q}(x, y)(z)$, and $k^{seq,q}(x, y)(z)$, respectively? So is there any theoretical guidance for the selection of $n$, that is, how much $n$ can be well approximated?
4. From **Theory 4.1**, we can observe that the generalization bound is related to the trace of the kernel. How is this different from the previous theoretical results?
5. $n$ is the number of orthogonal bases. Therefore, the complexity of the model is larger if $n$ is larger, and the representation power of the model is better. This phenomenon also occurs in the general learning process or kernel function approach strategies. How is this different from them?
6. To obtain $c(z)$, computing $(G(z)+\lambda I)^{-1}y(z)$. Poor scalability.
7. Some definitions are in the complex number domain, while some are in the real number domain. It is confusing for me. When to do it in the complex number domain and when to do it in the real number domain. It can include a pseudo-code to show the details.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730664249709

thread_type:
official_review

<thread_object>
creator: reviewer_xmui

<content>
summary:
This paper proposes a new class of positive definite kernels based on the spectral truncation. Detailed properties and examples have been discussed, and numerical results on both synthetic data and the MNIST dataset are presented.

strengths:
The authors have introduced the basic properties of the proposed kernels and also investigated the generalization error. The presentation is clear.

weaknesses:
Though the theoretical results are promising, two main questions remain unaddressed:
1. How can practical learning designs benefit from the new algebraic structures?
2. How can the development facilitate the kernel choices in practice? Section 6 seems to have some discussions on deep models, but a general development shall be data/task-dependent.

questions:
See Weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730733024962

thread_type:
official_review

<thread_object>
creator: reviewer_33dl

<content>
summary:
This paper proposes a new class of C*-algebra-valued positive definite kernels called spectral truncation kernels for vvRKHS. The noncommutativity, controlled by a truncation parameter n, allows for capturing interactions along the data function domain. The paper argues this enables a balance between representation power and model complexity, potentially leading to improved performance. A generalization bound is derived, highlighting the role of n in this tradeoff.

strengths:
The paper introduces an approach to kernel design by leveraging the mathematical framework of C*-algebras and RKHM, offering a potentially powerful way to model complex data relationships. The theoretical analysis of generalization bounds provides valuable insights into the trade-off between representation power and model complexity, guided by the kernel's truncation parameter.

weaknesses:
1. While the authors claim a computational advantage over vector-valued RKHSs (vvRKHSs) due to the linear dependency on output dimension m compared to cubic dependency in vvRKHSs, this advantage is not clearly demonstrated. The computational cost analysis lacks a direct comparison with vvRKHSs employing appropriate approximation techniques. For instance, the use of Nyström methods or random Fourier features could significantly reduce the computational burden of vvRKHSs, potentially negating the claimed advantage of spectral truncation kernels.

2. The deep model extension, while promising, lacks theoretical grounding. The analysis of representation power growth is based on a very specific construction and doesn't provide general insights into the behavior of deep networks with spectral truncation kernels. 

3. The experimental results, while suggestive, are not compelling enough to validate the claimed advantages. The experiments are limited to synthetic data and a simplified MNIST task. More complex, real-world datasets with function-valued outputs are needed to assess the practical performance and demonstrate a clear advantage over existing methods.

questions:
See weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730899438930

thread_type:
official_review

<thread_object>
creator: reviewer_vkgt

<content>
summary:
This paper explores the recent subfield of positive definite kernels with values in a C*-algebra and RKHM (the correponding "RKHS" theory) . The whole work is motivated by going beyond the separable kernel widely used in vector-valued RKHS based on operator-valued kernels and benefit from with a better compute time when applying kernel “ridge” regression. The main interest of working with a C*-algebra is that it comes with a norm, a product and an involution, unifying operators and functions. In particular, the paper focuses on the C*-algebra of continuous functions and the case where inputs as well are elements of this C* algebra.  The paper is illustrated with the example of continuous functions on the 1D torus.  The authors propose a novel function-valued kernel, spectral truncation kernel, relying on the approximation of the multiplication operator with respect to x (defined in L2(T)) by leveraging a truncated spectral decomposition. The dimension of the truncated basis encodes a trade-off between the representation power and the model complexity. The resulting kernel also benefits from the noncommutativity of the approximated product and can be shown to converge. Applied on Kernel Ridge Regression in RKHM, this new kernel leads to a reduction of the complexity in time. It also comes with a generalization bound which is a direct instantiation of the result proven by Hashimoto et al. (2023). A deep architecture based on product (and not composition) of different kernel-based functions in RKHM is also presented. Experimental results study the behaviour of the approach with respect to the truncation parameter on  a toy dataset. An additional result on an inpainted image recovery problem built on MNIST data is also briefly presented.

strengths:
This paper is following an original path in the kernel theory, exploring new schemes of kernels with values in a C* algebra. The work is certainly promising and of great interest for the kernel community. based on solid mathematical work, it opens a new way to tackle vector-valued or function-valued regression.
- Of special interest on the case of input and outputs that can be considered as functional (or vectors that can be seen as values of functions like images), the spectral truncation kernel allows for a drastically reduced computation cost in Kernel Ridge Regression while offering a great expressivity. 
- It can be declined with various choices of ground kernels and its positive definiteness is studied
- Products of (function-valued)-functions based on those kernels provide a deep architecture.

weaknesses:
Even though very interesting the paper suffers from different flaws: some concern the presentation and can be considered as relatively minor, while the others are more fundamental.
Weaknesses in the content:
*The motivation of the paper remains unclear: if the authors wish to go beyond the separable kernel in the general case of vector-valued functions, they should briefly discuss the limitations (which indeed exist) of the different operator-valued kernels such as the transformable kernels, the separable kernels or combination of them.  If the motivation is to use RKHM theory in the case of function-valued functions then it is of paramount importance to highlight what cannot be done with operator-valued kernels devoted to functions with outputs in Hilbert spaces of functions. 
*Once a family of kernels is defined, in machine learning, we are interested on the ability of the machine learning algorithms to indeed take benefit from this kernel and provide a good solution to the ML task. So what is missing in this paper, is a discussion and an empirical study to determine when using those kernels are interesting compared to previous methods: does the complexity of the model make the algorithm more greedy in training data. I do not think that the actual generalization error bound really help to tell us that in precise terms.
My advice is thus to complete the paper with comparison with other (operator-valued) kernels and vv-RKHS. this has to be done  in the case of the current toy dataset but also in known functional regression data sets.
* Applicability and relevance of the methodology: a central question that is still not enough answered at the end of the paper is the following: on which family of problems, these spectral truncation kernels are relevant ?
For instance,  the use of function-valued kernels for inputs and outputs which are vectors should be discussed. I think it is important here to clarify this: images are by definition a discretisation of continuous maps (intensity of pixel in finite resomution) and then they can be seen as a set of values of a function taken on different observation points. There is a great interest at considering the functions as continuous functions.
 I do not think it is always meaningful for a vector to be encoded as a function of its coordinate index: can you comment on that ? 
* Finally I do think that the paper would have sufficient content if it was restricted to function-valued functions. However, if images are tken as examples, then more convincing and complete comparison on image completion should be givne with more involved problems than weakly inpainted images. For the results given, do not say vv-RKHS comparions in the table say clearly the name of the matrix-valued kernel you used and try other kernels including more general operator-valued kernels for function-valued functions.

Weaknesses in the presentation of the paper.
The paper is in general not self content,  too much straightforward in its statements and very not enough precise in the presentation. It seems to me that an important work of re-writing is necessary, even though it is quite obvious that some efforst ahve been made here.
To give a few suggestions:
- rewrite the introduction with clear motivations and do not enter into partial details that cannot be understood at this stage (n < infty, n infty..)

- line 154 we jump into a comment about C(T) but previsously functions on the real torus were just an example. Now X = A ?
please say it !Moreover we cannot understand the sentence "however, by approximating ... by a Toeplitz matrix..;", we do not know yet that Toeplitz matrix will be involved here 


- before line 174, say a word about the works of Van Suijlekom and explain the role of the Fejer function. The reader has to consult this apper to undertstand the construction. It is important in what follows when talking about convergence.

- in general, do not give proposition under the form of the sole formula but write a sentence introducing the property and a comment on what the proposition brings.
- generalization bound : clearly state as in the appendix that this result comes directly from previous literature (Maurer, 2016... Hasimoto et al. 2023)
-  It is crucial to introduce m when describing the observations at line 364.
- experiments : 
what do you want to bring in terms of emprirical evidence: please present the experiments as an answer to the questions/motivation of the beginning of the paper

* after rebuttal: the paper has gained significant improvements and I am  increasing my score consequently.

questions:
Overall I would be happy to increase the score of the paper (around 4) if answers are brought during the rebuttal.

- Please clarify the motivation and express the pros and cons with previous competing methods
- Give at least one example to make the reader understand the issue with commutativity and the benefit of non commutativity
- Identify as much as possible the family of problems that could in principle be tackled by this method
- Complete the toy experiments with a comparison with other function-valued regression methods 
for the existing experiments, are the same curves observed when dealing with a very large data regime ?

Nearly all my questions have been answered in a satisfying way.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732070315370

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
**To all the reviewers**  
We thank all the reviewers for their constructive comments and questions. We addressed them and revised the paper based on the comments. The revised parts are colored in red. The answer of each comment and question is posted as a comment for each reviewer.

We would like to emphasize that this work is the first attempt to incorporate the noncommutativity of the product combined with spectral truncation to go beyond typical kernel choices.
The theoretical results open up a new direction of the applications of the proposed noncommutative kernels.
Here, we would like to summarize the advantages of the proposed kernels below:

1. **Control of local and global dependencies**  
For kernel methods with function- or vector-valued outputs, one big challenge is the choice of kernels.
In the existing framework of vvRKHSs, we need operator-valued kernels instead of scalar-valued kernels.
Typical choices are separable kernels and commutative kernels.
Although they are computationally efficient, they are two extreme cases in the sense of dependencies of input functions or vectors on output functions or vectors.
**Separable kernels focus only on global dependencies and commutative kernels focus only on local dependencies.
The proposed kernels fill a gap between these two kernels by virtue of the noncommutativity.**
The noncommutativity is parameterized by a natural number $n$, and we showed that this parameter controls how much amount of local dependencies are focused on.

2. **Computational efficiency**  
To fill a gap between separable and commutative kernels, other operator-valued kernels in the framework of vvRKHSs have been proposed.
The proposed kernel combined with the framework of RKHMs are **computationally more efficient than these existing kernels with vvRKHSs**.

3. **Control of the representation power and the model complexity**  
The parameter $n$ in the proposed kernel also controls the representation power and the model complexity, which leads the performance enhancement.

For more details, please see the answers of the reviewers and Appendices A, B, and D of the revised version of the paper.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper utilizes the tool of C-algebra to develop new methods of kernel machines, receiving certain recognition from the reviewers. However, the current paper suffers from obvious weaknesses that prevent me from recommending acceptance. To me specific, the experimental setup, consisting of a synthetic dataset and a simple dataset called MINIST, is too weak to be convincing.