Spectral Neural Networks: Approximation Theory and Optimization Landscape

We thank the reviewer for their interesting questions and suggestions. We are encouraged by their appreciation of our submission regarding its motivation, theoretical soundness, comprehensive literature review, and presentation. Below, we provide answers to the reviewer’s questions. We have added most of these explanatory comments and changes in the updated manuscript in blue text.

Simulations.

We thank the reviewer for suggesting further simulations exploring the optimality of our theoretical results. This is a good suggestion that can be presented within the context of the broader research inquiries suggested by Reviewer hkrF. Having said this, we want to highlight the merits of our theoretical contributions in the present paper. Indeed, we bring together, in non-trivial and novel ways, a variety of results from several subfields (manifold learning, neural network approximation, Riemannian optimization, matrix factorization problems) that, in our view, have had limited theoretical interaction. We hope this paper motivates systematic theoretical explorations of important applications of neural networks to eigenvalue problems of differential operators on (unknown) manifolds in high dimensional spaces (see, for example, some suggestions by Reviewer hkrF).

About presentation.

The updated manuscript emphasizes the theoretical nature of our inquiries when describing Q1-Q3. The existing empirical results in the literature were indeed important motivators for our work.

Constructive nature in Theorem 2.2.

We want to highlight the differences in nature of Theorems 2.1 and 2.2: it is very different from stating that an approximating NN can be found by solving an optimization problem with a clearly defined objective (as in Theorem 2.2) than to simply state the existence of an approximating NN with no indication on how even to begin the search for it (as in Theorem 2.1.). While we agree that Theorem 2.2. does not describe an explicit algorithm to find this approximating NN, it is implicit that once the clearly defined target objective has been introduced, one can use any optimization algorithm to search for its minimizers. Because of this, and given our desire to highlight the conceptual differences between Theorems 2.1 and 2.2, we used the word constructive to describe the latter. We would be happy to modify this term if the reviewer believes that there is a more suitable alternative.

Figures.

We thank the reviewer for their suggestion. In the revised manuscript, we refer to our figures after Remark 3.1 when discussing the theoretical results about the landscape of the objective $\ell$.

Highlight non-convexity of the loss function $\ell$.

We thank the reviewer for their suggestion. In the revised manuscript, we have highlighted this point in the paragraph mentioned by the reviewer.

Thank you for your thoughtful feedback on our manuscript and response.

We have taken your suggestions into consideration and made the following revisions:

1. Removed the title of Figure 3.
2. Reformatted the objective function to be presented in a single line.

We believe these changes enhance the clarity of our paper.

Regarding the simulation of neuron numbers for accuracy approximation in eigenvector calculations, we acknowledge this as an intriguing area for future research. This aspect, closely tied to the Laplace-Beltrami operator as highlighted in Corollary 1, offers a promising avenue for exploring the relationship between theoretical results and empirical findings. However, our current focus is on the theoretical foundations of Spectral Neural Networks (SNNs). Consequently, our current simulations were confined to the parameterized and ambient optimization landscapes in SNNs.

Future studies could also fruitfully compare SNNs with other neural network models for spectral embedding tasks. While incorporating a detailed discussion on approximations to Partial Differential Equation (PDE) operators would indeed be valuable, we believe it might overburden the scope of this paper. Such topics merit a thorough examination in subsequent research.

We appreciate your consideration of our revisions and suggestions for simulation results. We believe the improvements address your initial concerns, enhancing both the clarity and rigor of our work. If you find that our revisions meet your expectations and improve the overall quality of the manuscript, we would be grateful if you could reflect this in an updated assessment on rating or confidence.

We thank the reviewer for their comments and questions, which we address below. We are also encouraged by the reviewer’s appreciation for our theoretical contribution to the ML community.

Significance of approximation result.

We start by highlighting that SNNs are useful beyond SSL and the context of the work of HaoChen et al. 2021 Indeed, our results can justify the use of SNNs to solve eigenvalue problems of differential operators on manifolds. The use of SNN in this context is novel, and in particular the induced training procedure is quite different from popular approaches in the literature such as Physics Informed Neural Networks (PINNS). The use of SNN beyond standard tasks in machine learning is thus of interest to the broader scientific community. See, for example, our response to Reviewer hkrF and the Conclusions section in our paper.

On the other hand, we emphasize that studying the graph constructions in HaoChen et al. 2022 is an interesting research direction and we expect that a similar analysis to the one presented in our paper can be carried out in settings that are more useful for SSL. However, to achieve this, one would first need to generalize some of the theoretical results in Calder et al 2022. This mathematical task seems feasible, but only after a lengthy analysis. This can be explored in future work.

The proof of Theorem 2.1.

We refer the reviewer to the general response to reviewers.

The decomposition of $Y_{\theta^*}$.

Recall that $\bar{U}$ is invertible. Hence, let $E = \bar{U}^{-1}Y_{\theta^*}$. We let $E^1$ be the first $r$ rows of $E$ with the rest of rows being equal to 0. Similarly, $E^2$ has the rest of the rows of $E$.

Remarks G.1 - G.3.

More than being necessary for our proofs, these remarks help convey why our results are not direct consequences of existing results and that careful analysis is needed to deduce them. This is closely connected to the discussion in our general response to reviewers.

The neural network family that we consider.

We thank the reviewer for their suggestion. The family of approximating functions was defined in detail in (C.2); this was mentioned in the statement of Theorem 2.1. We do not include its (long) definition in the main text because of space limits. Given all the other important things we needed to include in the main body of the paper, we were forced to move some details to the appendix. We also want to highlight that many remarks in the main body of the paper and in the appendix were included to help convey the relevance of our theoretical results.

We hope our explanations can help convey that our work is well motivated and that the mathematical problems we study are exciting and non-trivial.

We thank the reviewer for their comments and questions, which we address in what follows.

The approximation results in Section 2.

Please see the general response to reviewers.

Constructive approximations in Theorem 2.2.

Theorem 2.2. is not a mere existence result. It is very different to state that an approximating NN can be found by solving an optimization problem with a clearly defined objective than to simply state the existence of an approximating NN with no indication on how even to begin the search for it (as in Theorem 2.1.). That is, existence just says there are parameters such that something is true, but gives no indication on how to find these parameters. Of course, once one has a clearly defined objective, one can ask the natural follow-up question: what is the behavior of popular optimization algorithms when trying to optimize the target objective? This is what we explore in Q3.

The landscape results in Section 3.

As was discussed in paragraphs 2, 3, and 4 on page 4, the optimization landscape is non-trivial because there are two sources of “non-convexity”: 1) the non-linearity of neural networks and 2) the non-convexity of the ambient loss function. With our numerical illustration (Figures 4 and 5), we suggest that the properties of the landscape for the SNN problem are expected to resemble those of the ambient loss landscape, at least in some form of overparameterized regime. A precise mathematical statement along these lines will be explored in the future and deserves its own careful analysis. As we discussed in paragraphs 2, 3, and 4 on page 4, as well as in the last paragraph of the Conclusions section, this problem is different from other analyses in the literature of training dynamics of overparameterized neural networks because in our case, the ambient loss function $\ell$ is non-convex, not because neural networks are nonlinear functions.

Notation.

We defined $\epsilon$ in the surroundings of Equation (1.2) and defined $m$ in Assumption 2.1. It is the underlying manifold’s intrinsic dimension. $\epsilon$ in this work is always used as the length scale that determines the graph connectivity. $\delta$, on the other hand, is a tunable approximation error. Notice that the size of $\epsilon$ is implicitly controlled by the number of data points available since our error estimates are only meaningful with a likelihood that depends on $n$ and $\epsilon$.

We hope our explanations can help convey that our work is well motivated and that our mathematical contributions are novel, sound, and far from trivial.

We thank the reviewer for their thoughtful comments and their positive feedback. In particular, we thank them for their insightful comments on the use of NNs to solve eigenvalue problems for more general differential operators. Indeed, we agree with the reviewer that it is of interest to provide theoretical guarantees for the use of a SNN-like approach to find the spectrum of other differential operators such as the ones in the Schrödinger equation. As the reviewer mentions, this is of relevance for the broader scientific community.

We hope our edits improve our manuscript’s clarity and also better position our work in the landscape of existing results on similar problems. All references provided by the reviewer were incorporated in the paper. New text has been highlighted in blue. Below we provide answers to the reviewer’s questions.

Other differential operators and Generic NN-based eigensolvers.

We have added references to the papers the reviewer mentioned. In Section A.2 we have added a brief discussion on the eigensolvers mentioned by the reviewer.

On Remark 2.2.

Remark 2.2. aims at highlighting that the $\epsilon^2$ term in our error estimates in Theorem 2.1. is essential for our proof of Theorem 2.2. As discussed in our general response, this $\epsilon^2$ term could not have been obtained by directly fusing the results in Calder et al 2022 and Chen et al 2022. In order to get the term $\epsilon^2$, we needed to first obtain a stronger quantitative estimate for the regularity of the (discrete) graph Laplacian eigenvectors (stronger than the ones explicitly stated in Calder et al 2022) and then apply the results in Chen et al 2022 to find an NN approximator of a suitable extrapolation of the discrete eigenvector to the manifold (different from an associated eigenfunction!, for otherwise the error of approximation would not be $\epsilon^2$ but $\epsilon$). In order to obtain the better discrete regularity for graph Laplacian eigenvectors, we used the fact that graph Laplacian eigenvectors converge in a stronger semi-norm (almost $C^{0,1}$) toward Laplace-Beltrami eigenfunctions.

We thank the reviewer for their questions and comments, which we address below. We are encouraged by the reviewer’s appreciation of our presentation and theoretical analysis. We have added most of these explanatory comments and changes in the updated manuscript in blue text.

Only recovering eigenvectors up to rotation.

We do not believe this is a limitation. First, notice that for many important downstream tasks, such as spectral clustering and spectral contrastive learning, it is sufficient to generate unions of eigenspaces, and thus, recovering individual eigenvectors may not be necessary for those tasks. On the other hand, if one indeed desires to generate the first K individual eigenvectors of $A_n$, it suffices to simply run the SNN algorithm for $r=1, \ldots , K$ and carry out a Gram-Schmidt like procedure with the outcomes. This pipeline would indeed avoid the use of eigensolvers, as claimed.

Assumption on $\eta$.

The non-increasing assumption on $\eta$ appears in multiple results in the manifold learning literature. We used some of these results in the proofs of our theorems. Notice that most $\eta$ used in practice (e.g., Gaussian, 0-1) satisfy this assumption.

The definition of $D_G$.

$D_G$ is the diagonal matrix whose $i$-th diagonal entry is the degree of the point $x_i$. $D_G$ was defined in the Appendix in the paragraph below (A.5). In the updated manuscript, we have added an explicit reference to its definition.

Notations in Theorem 3.2.

There is a typo in Theorem 3.2. We had not defined $\Lambda$. We thank the reviewer for pointing this out. We have now incorporated it in the updated manuscript.

About the related work and novelty.

First, we want to point out that the work Luo & Garcia Trillos 2022 that the reviewer mentions makes very different assumptions on the matrix $A_n$ than the ones we make in our paper. The implications of the different assumptions are indicated at multiple points in the paper: in Remark 3.2, the discussion below Theorem 3.2, and Remarks H.1 and H.2.

Our paper studies SNNs comprehensively and combines multiple results from several subfields (such as manifold learning, neural network approximation theory, and Riemannian optimization) in a way that is original and far from trivial. Indeed, as we explain in our general response to reviewers (see also the response to Reviewer hkrF), we had to tackle multiple technical difficulties to bring together existing results in the literature. The paper Chen et al. 2022 that the reviewer mentions is indeed a useful auxiliary result for our work, but by no means are our Theorems 2.1 and 2.2 corollaries of it.

Thank you for reviewing our manuscript and providing your feedback. We have now incorporated a brief discussion on the global optimization landscape from Luo & Garcia Trillos 2022 into the related work section of our paper. Please see our revised manuscript, where this is highlighted in blue.

In response to your concerns we would like to highlight the following:

1. The reviewer’s main concern is that our paper is very much like Luo and García Trillos, yet the reviewer has focused entirely on one single aspect of our paper (more on this below) and did not discuss more than half of our paper, which has little to no overlap with the mentioned paper. In particular, there is no mention of the motivation for our problem, nor to the approximation theory results Theorems 2.1 and 2.2, nor to the connection with learning solutions of PDEs, nor to the prospect of using our ideas to provide a theoretical basis for the use of SNNs in other problems in the sciences (as other reviewers have highlighted). In fact, there is not even a mention to our numerical simulations, which try to convey why studying the landscape of the ambient problem may be relevant for the SNN training problem, which is what motivated some of the open problems we formulated in the paper.

2. We do mention the extent of the similarities between our section 3 and the paper of Luo and Garcia Trillos. Please see our Remark 3.1 in the main text and the multiple remarks and comments in section H.

3. The concepts of benign landscape and the Riemannian approach are very broad ideas in the optimization literature, not just ours or Luo & Garcia Trillos 2022’s. A quick online search reveals this.

4. R1, R2, R3 are indeed similarly defined as in Luo & Garcia Trillos, but, as explained extensively in the paper and in our previous replies to all reviewers, the challenge is in showing that those regions indeed satisfy the desired properties to describe the landscape of our ambient problem as benign: local strong convexity around global minimizer, escape direction for saddles, large gradient in all other regions. In other words, R1, R2, R3 are ansatz, which are naturally inspired by previous work, but this doesn’t imply the ansatz is trivially correct in our case. There is an enormous difference between 1) guessing what a good answer could be and 2) proving that this guess is indeed a good answer. We thus invite the reviewer to compare the papers in more detail, and not focus exclusively on their superficial similarities. On this last point, we reiterate our discussion in 1. above.