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

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.

Strengths

1. Clear writing 2. Very solid results 3. Novel tools 4. Their work can be inspiring. 5. 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.

Questions

Any theoretical understanding of why deep RKHMs might be better than nondeep ones?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors very adequately addressed the limitations. Very impressive.

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.

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}$. Two remarks in this direction are on some notations: - 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) $ - 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.

Questions

In 'Connection with neural tangent kernel', is the aim of this paragraph to define a neural tangent kernel for deep RKHM? In 'Comparison to CNN', how long does the training take and what is the memory consumption of RKHM and CNN?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

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.

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.

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. Moreover, this paper provides some experiments to support their theoretical findings. The paper is technically sound and the contents are very relevant to the community of NeurIPS.

Weaknesses

The paper is well-organized and well-written.

Questions

Can you explain how the generalization bounds in Theorem 4.1 and Theorem 4.5 depend on the input dimension?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have clearly addressed the limitations of this work.

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.

Strengths

- The objects studied in the paper are well introduced. The writing is generally clear. - 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. - 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. *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. - 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 ? - 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 ?

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. - 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 ?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Limitations are discussed.