Bounds on the Reconstruction Error of Kernel PCA with Interpolation Spaces Norms

W

We appreciate the reviewer's thorough reading and approval of our work. For your first concern about the limited empirical validation, We have offered a simple empirical experiment in Section 4 in order to exemplify our result. However, due to the computation difficulty of experiments of kernel methods, especially under the large dimension setting, we haven't found a suitable dataset under which the experiment can be done within days.

For your second concern about the choosing of parameter such as $s$, we introduced the interpolation space to bridge the gap between the two previously used norms: the RKHS norm and the $L_2(P)$ norm. The norm in the interpolation space also highlights some theoretical insights, such as the limitations of the RKHS norm in high-dimensional contexts and the periodic plateau phenomenon, which might be difficult to detect using only the RKHS norm. Hence, the adoption of interpolation space is more from the theoretical side.

For your third concern about the choosing of $n$, we totally agree with you that a tighter bound of n rather than the bound $n \geq \mathcal{C}_3\ell^{2\beta}$ we give here may exist when there are some underlying properties of data. Investigating how to determine a data-driven n remains a complex issue that requires further exploration, and we may consider addressing this problem in the future. We appreciate your insightful suggestion on pursuing a data-driven approach rather than relying solely on a global bound.

Q1

Thank you for your requirement of elaborating more on the paper of Rosasco L, Belkin M, De Vito E. In fact, we utilized Proposition 10 from their paper as a lemma to support our proof of Proposition 3.4 (see Lemma B.2). Their work enabled us to verify Assumption (C) under the polynomial eigenvalue decay assumption. We have also revised our manuscript to include a citation of this literature in Section 2.2, where the properties of the integral operators are discussed.

Q2

Thank you for your insightful question on whether the current result can be extended to the manifold setting. To the best of our knowledge, the properties of specific kernels on manifolds are generally limited to a fixed-dimension context. Therefore, it might be feasible to extend the current results in Section 3.2 to manifolds. For the large dimension setting, an important lemma in our work is Lemma A.5, which shows that $\mu_k = \Theta_d(d^{-k})$ and $N(d, k) = \Theta_d(d^{k})$ for $k \leq p+3$. Such structure in the spectrum allows us to describe reconstruction error, and can only be proved in the hypersphere setting to the best of our understanding. On the other hand, few results about the spectrum of kernels in the general domain can be found under large dimension settings (see, e.g., Remark 3.6). However, despite the difficulties of extending the large dimension results to the manifold setting, we believe that similar results shall exist, and the idea you point out is promising.

Q3

Thank you for your insightful question regarding the potential extension of our results to MDS. To the best of our knowledge, MDS typically involves a dissimilarity matrix of the samples, with elements often based on distances. The method diagonalizes this matrix and selects the subspace spanned by the leading eigenvectors. However, MDS relies heavily on the specific samples chosen, and we have not come across literature addressing MDS in a population setting, which might make the analysis more challenging than in the case of kernel PCA. Additionally, defining the interpolation space in an MDS context could be problematic. Nevertheless, we do believe that MDS might yield similar or related results due to its parallels with empirical kernel PCA, and it is of great interest and importance to derive the similar results in MDS. Please let us know if there are any misunderstandings on our part regarding MDS.

W

We are sorry for not making our presentation clearer. We will aim to improve clarity in the revision. However, due to the complexity of kernel PCA and the limited number of pages in an ICLR manuscript, the use of some common notations might be unavoidable. To reduce potential miscommunication, please allow us to provide a more readable summary below:

Why $[\mathcal{H}]^{s}$ norm

Reconstruction error is often used to evaluate the performance of PCA and KPCA. For PCA, the definition is

For KPCA, the definition is

where

Since kernel PCA operates in the RKHS (a function space derived by a kernel function) rather than $\mathbb{R}^d$, various norms can be used to define the reconstruction error of KPCA. Previous works consider the $\mathcal{H}$ norm (which is the original norm of RKHS) and the $L_2(P)$ norm. Recent studies in RKHS regression strongly suggest that measuring the reconstruction error through $[\mathcal{H}]^{s}$-norm would provide new insights, linking the two norms used in previous literature ($s=0$ refers to the $L_2(P)$ norm; $s=1$ refers to the $\mathcal{H}$ norm).

Existing results:

Lower bound of reconstruction error
Existing results for the lower bound of reconstruction error mainly focus on the $\mathcal{H}$ norm and $L_2(P)$ norm. For the $\mathcal{H}$ norm, the proof can be simply derived by extending similar results of PCA to KPCA. (Note that when extending PCA to KPCA, the Frobenius norm becomes the RKHS norm.) For the $L_2(P)$ norm, there are some serious gaps in the previous proof that cannot be easily fixed. (See Remark 2.6 and Appendix C.1 for details.)

Upper bound of reconstruction error
For the $\mathcal{H}$ norm, the upper bound can be derived from the results in PCA. (See Proposition 2.2 for details.) Previous results of the upper bound under the $L_2(P)$ norm are incorrect as they wrongly claimed that assumption (C) in Proposition 3.1 holds with high probability. (See the discussion below Proposition 3.1 and Appendix C.2 for details.)

Convergence rate of reconstruction error under the polynomial eigendecay setting
Previous literature shows that under this setting, the convergence rate is $\ell^{-\beta+1}$ for the $\mathcal{H}$ norm case; $\ell^{-2\beta+1}$ for the $L_2(P)$ norm case. Here $\beta$ is the eigenvalue decay rate, see Assumption 3.3 for details.

Our contributions:

Lower bound of reconstruction error
We establish a lower bound for the reconstruction error under the interpolation space norm. The lower bound is attained by proving that the eigenfunctions of the $\ell$ leading eigenvalues minimize the reconstruction error (Theorem 2.5). To the best of our knowledge, we are the first to provide a rigorous proof of such theorems, especially in the interpolation space norm case.

Upper bound of reconstruction error
We successfully derive the upper bound of the reconstruction error under the interpolation space norm by emphasizing the importance of assumption (C) (Theorem 3.1). We also make efforts to ensure that assumption (C) can be verified in different cases. (See Remark 3.2 for details.)

Convergence rate of reconstruction error under the polynomial eigendecay setting
By applying our Theorem 3.1 to the polynomial eigendecay setting, we derive the convergence rate of $\ell^{-(2-s)\beta+1}$, consistent with previous results.

Convergence rate under the large dimension setting (hypersphere)
We consider a hypersphere inner product kernel (a commonly used kernel in high-dimensional cases). Under this setting, we derive the convergence rate of the reconstruction error (Theorem 3.8). This leads to two notable observations. First, when $s=1$, the reconstruction error does not converge, indicating that the RKHS norm is unsuitable as an error metric in high-dimensional cases. Second, we identify a periodic plateau phenomenon, where the reconstruction error rate remains constant over certain ranges of $\ell$ and decreases sharply over others (as illustrated in Figure 1(c)). A similar periodic plateau has been observed in other high-dimensional kernel methods.

We hope that the above summary convinces you of our work’s significant contribution to the community and may help you reevaluate our paper. Please let us know if you have any further questions.

Q1

Thank you for your concern about the definition. $\otimes_{H}$ is defined in the notation part in page 4. For your convenience, we represent it here again. $a\otimes_\mathcal{H}a=\langle a, \cdot\rangle_\mathcal{H} a$, where $\langle\cdot,\cdot\rangle_\mathcal{H}$ means the inner product in space $\mathcal{H}$. In this circumstance, we provided another interpretation just behind $\otimes_{H}$. We shall change $=$ to $:=$ to avoid misunderstanding. For your second request about $f(X)$, $f(X)$ is a random variable since $X$ is an element of $(\mathcal{X},P)$ (note that $X$ and $\mathbf{X}$ are different).

Q2

Thank you for your feedback. We understand your concern that the temporarily undefined terms might make it challenging to follow the paper. In response, we indicated the sections where you can find detailed definitions. We believe it is more appropriate to present the definition of the interpolation space norm in the preliminaries section rather than in the introduction, as including all the detailed definitions upfront could make the introduction overly dense and harder to follow. The purpose of the introduction is to provide an overview and to set the context and motivation for the work.

For your second concern about the significance of the interpolation space norm, as is written in our contribution and the summary above, the interpolation space norm links the two previous types of reconstruction error considered by other literature, the RKHS norm reconstruction error and the $L_2(P)$ error. Also, considering the interpolation space norm also brings us some new insights, such as the two observations found in the large dimension case, the unsuitableness of RKHS norm and the periodic plateau phenomenon.

Q3

Thank you for your question on the norm used in equation (2). As is shown in the notation part, the norm in equation (2) is the 2-norm in $R^d$. (From definitions in (2), both $X$ and $\beta_i$'s are vectors in $R^d$)

Q4

Thank you for your request for the condition mentioned in related works. We have already dded the condition in the manuscript. (All the major changes of the main manuscript have been marked blue. Typos and other minor changes are also updated in the new manuscript.) For your convenience, we display it here.

Condition For all $s\leq \ell$, the following inequality holds:

Q5

Thank you for the request for a explanation of the $\mathcal{H}$ norm in Remark 2.3. The $\mathcal{H}$ norm is the norm of the RKHS. We mention the $\mathcal{H}$ norm here before the RKHS part so as to announce that we want to compare this result with our result. We have added the explanation of $\mathcal{H}$ norm in the remark according to your advice. Also, we added a reference in the manuscript where you may find detailed properties and explanations of RKHS.

Reference:A. Caponnetto and E. De Vito. Optimal rates for regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331–368, 2007.

Q6

Thank you for pointing out the need for clarification regarding the inclusion map on page 5. The inclusion map is a standard mathematical concept defined as follows: Given a subset $A$ of $B$, the inclusion map $I$ assigns element $x$ of $A$ to $x$, the latter $x$ is treated as an element of $B$, $I:A\rightarrow B, I(x)=x.$

Q7

Thank you for your question. This is a definition of the inner product of the interpolation space, and we rewrite it in our revised manuscript as follows:

Notice that ${\phi_i}$ is a basis of the interpolation space, hence giving the definition of the inner product between $\phi_i$ and $\phi_j$ is enough to induce the inner product and norm of the whole interpolation space. The example you give is actually the inner product under the RKHS, which is a special case of the interpolation space when $s=1$.

W1: In the proof of Theorem 2.5, I don't understand why the orthonormality constraint $(\psi_1,\ldots,\psi_{\ell})\in B_{\ell}$ does not appear in the stationarity condition of $\mathcal{R}_{s}$, equation (6). In fact, I did not manage to recover equation (6) at all. This step of the proof deserves more details.

Thank you for your request for more details on the proof of Theorem 2.5. We have provided a proof that possesses higher readability. We hope that the updated version addresses your concerns about the proof of Theorem 2.5.

W2: The last sentence of the abstract is not very clear, and "$[\mathcal{H}]_1$ norm" is not defined at that stage. Perhaps a more precise statement would be that "the RKHS norm is not a relevant error metric in high dimensions".

Thank you for your advice on the last sentence of the abstract. We have already changed the expression according to your suggestion.

W3: The figures are difficult to read; the paper would greatly benefit from making them bigger. (E.g., with matplotlib, reduce figsize and increase dpi.)

Thank you for your kind suggestion. Following your advice, we have increased the font size of Figure 1 and the figure size of Figure 2 in our revised manuscript. We hope this makes the figures clearer.

W4: The paper contains many typos and unusual wordings.

Thank you for pointing out the typos and unusual wordings. We have revised our manuscript according to your suggestion.

Q1: Please address the missing step in the proof of Theorem 2.5 (see Weaknesses).

Thank you for requesting further explanation of the proof of Theorem 2.5. We have already provided a proof with higher readability. Please let us know if you have additional questions about the proof.

Q2: In Corollary 3.4, what is the dependency of the constant $\mathcal{C}_3$ on problem parameters? Is it polynomial?

Thank you for your request to explicitly express $\mathcal{C}_3$ . By Lemma B.2, we have $\sup _ {j \geq 1}|\lambda _ j-\widehat{\lambda} _ j| \leq 2\kappa \sqrt{2\tau} n^{-1/2}$, thus $\widehat {\lambda}_{\ell+1}$$\leq 2\lambda_{\ell+1}$ holds when $2\kappa \sqrt{2\tau} n^{-1/2}\leq c _ {\beta} (\ell+1)^{-\beta} \leq \lambda _ {\ell+1}$. Hence, we can choose $\mathcal{C} _ 3 = 2^{2\beta}8\kappa^2\tau c _ \beta^{-2}$.

Thank you for your answer. Regarding Q2, perhaps it could be useful to future readers to remark that $C_3$ is polynomial in the parameters (except beta, but the bound can be rewritten as $C'_3 (2\ell)^{2\beta}$), and especially in $\tau$.

I still have questions on the proof of Theorem 2.5, notably the case $0<s<1$ (which is the main case of interest):

• What is meant by "maximizing $R_s(\psi_{l+1}, ...)$" on line 859?
• Why does the equation on line 866 imply that $A$ must be block-diagonal?
• What is meant by "$A_1$ is non-zero only on $\ell$ $e_q$'s" on line 868?

By the way I noticed some typos in the updated proof:

• on lines 792-800, the summation $q=1$ (or $p=1$) should be replaced by $q \in N$ (or $p$)
• on line 802, $\sum_j a_{pj} a_{qj} = \delta_{pq}$, not $1$
• on line 840, the last two factors of the left hand side, $A_1$ and $\Lambda$, are switched. This also impacts the reasoning for the case $s=1$ start on line 842.
• on line 851, it could be helpful to explain explicitly why the space spanned by $A_1$ is invariant by the operator $\Lambda H \Lambda$ (IIUC it's as a consequence of (6)).
• on line 852, it could also be helpful to point out explicitly that this operator is symmetric, so that the space spanned by $A_2$ is invariant.

W1

Thank you for your advice that the hypersphere setting should be clarified in the introduction. We have updated the introduction according to your suggestion.

As for your second question, we consider the sphere setting for two main reasons:

• On the one hand, the spectral properties of inner product kernels for uniform data distributed on a large-dimensional sphere are clear. In Lemma A.5 we have shown that $\mu_k = \Theta_d(d^{-k})$ and $N(d, k) = \Theta_d(d^{k})$ for $k \leq p+3$. Such a strong block structure in the spectrum, as described, leads to the periodic plateau behavior of the reconstruction error, and can only be proved in the hypersphere setting to the best of our understanding.

• On the other hand, few results about the spectrum of kernels in the general domain can be found under large dimension settings (see, e.g., Remark 3.6).

We will try to generalize our results to kernels in general domains in future work.

W2

Thank you for your request on more discussion of the gaps. We shall add the following discussion in the main text. However, due to the constraint of main text length, we are unable to provide the whole Appendix C in the main text. We hope that the discussion shall relieve your concern on the more discussion of gaps.

• For Theorem 2.5 (which refers to Appendix C.1 for the gap), the previous gaps mainly focus on the wrong proof of the similar theorems, while the theorem itself remains true. The gap is mainly due to the wrong decomposition of some operators and sets. We give the correct proof of the theorem, and hence fill the gaps in the existing literature.

• For Proposition 3.1 (which refers to Appendix C.2 for the gap), they claimed that assumption (C) holds with high probability. The gap in their proof is mainly due to the wrong claim that a specific operator is positive semi-definite.

For your second concern that the arguments fail for specific cases, we guess that it is the assumption (C) that you think only fails for very specific corner cases. However, as shown in Remark 3.2, previous works consider the U-statistics, whose assumption (C) is hard to be verified. In order to overcome such difficulties, we consider a different setting so that the verification of assumption (C) becomes possible. Hence, we have made efforts so that assumption (C) can be verified in some important cases, rather than just pointing out a corner case under which the previous literature exists gaps.

W3

Thank you for your advice on the discussion of related works. After reading the literature you provided, we find that G. Santin and R. Schaback provide a link between the space spanned by the $\mathcal{H}$ eigenfunctions and the space spanned by the $L_2$ eigenfunctions. The literature you provided is closely related, and we have added the discussion in our work accordingly.

Q1

Thank you for your suggestion of adding the introduction of constants before using them in Section 1. We guess that the constants you mention are $\mathcal{N}_{\Sigma}(t)$, which is a coefficient that can be bounded by no more than $O(1/n)$. We have already added the explanation in the table. Please let us know if you have other questions about the constants used. (All the major changes of the main manuscript have been marked in blue. Typos and other minor changes are also updated in the new manuscript.)

Q2

Thank you for your request to explicitly exhibit the condition. We have already added the condition in our revised manuscript. For your convenience, we also display it here.

Condition: For all $s \leq \ell$, the following inequality holds:

Q3

Thank you for your question considering whether Figure 1 corresponds to an experiment. Figure 1 is only a graphical illustration of the theoretical results, not an experiment. The experimental part is in Section 4. We will clarify in our manuscript that Figure 1 is only an illustration according to your suggestion.