Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the problem of feature mapping for reproducing kernels. The focus is when the data size is too large, the SVD for the kernel Gram matrix would be prohibitively difficult. This paper proposes to use the least-squares loss to achieve a low-rank approximation to the Gram matrix, to use Legendre transformation to disentangle quadratic terms in the least-squares loss, and to use a two-phase Hebbian parameter update rule to achieve the approximating feature map.
main_review: strength: the idea is nice. After training, the obtained function maps data points directly to their images in the feature space with low computational complexity.

My concerns:
1. The one-dimension approximation (4) may lose precision. The introduced error could be significant. Users of the algorithm may not be able to estimate the introduced error. Users may end up having a totally different reproducing kernel if they shift to using the feature images.
2. The feature map is obviously not unique. For example, for any such map x--> y=F(x), and any orthogonal matrix Q, QF(x) is exactly another feature map as good as F(x). Consequently, you can not expect that W, q, or L in (8) would converge in the first phase of training.
3. Some minor mistakes in using the Legendre transformation: the sum in t on the right-hand side of (4) does not cover (1/2)q^2f(w,w). However, we see that the author(s) made it cover this term in (5) and (6). We see that it is easy to fix this problem by scaling the term (1/2)q^2f(w,w) by 1/T.
4. The optimization problem (8) is far from convex (especially in terms of W). Compared with matured randomized matrix decomposition techniques many with convergence guarantee and designed for reducing space and time complexity (e.g. Halko, N.; Martinsson, P. G.; Tropp, J. A. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53 (2011), no. 2, 217--288.) (these algorithms could be plugged into kernel-based empirical feature maps to achieve the same purpose as claimed in this paper), the convergence and precision of the proposed algorithm are both difficult to verify.

========================== after reading the authors feedback
Most of my points are well addressed. I am happy to raise the score to 8. I believe that combined with some regularity assumption on kernels, good theoretical results can be derived for the proposed algorithm as future work.
summary_of_the_review: This is a nice paper with a good idea. However, we believe that the introduced methodology is not fully developed.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the linear similarity matching problem, which represents input $x_t$ by a high dimensional vector $y_t$ such that $y_s \cdot y_t \sim f(x_s, x_t)$ for a kernel function $f$. 

Main contributions of the paper:
- The authors propose an online algorithm for linear similarity matching, which can be interpreted as a neural network with Hebbian and anti-Hebbian connections.
- The authors provide experiments to demonstrate that the proposed method can aid unsupervised learning tasks.
main_review: I like the authors' idea to use an online neural algorithm to approximate nonlinear kernel similarity. However some concerns are:

- I feel the authors need to argue more the contribution and importance of the proposed algorithm. Is there other online algorithms for similarity matching, and why one should choose this algorithms over others?
- In the experiments there is no comparison to demonstrate the advantages of the proposed algorithm over other algorithms. There is a comparison with the kernel PCA on the Half-Moon dataset, but the finding is that the proposed method's performance is not much worse compared to the kernel PCA.


Some Typos:
- page 2, 'which are defined by more a general nonlinear kernel similarity' -> 'which are defined by a general nonlinear kernel similarity'?
- Page 2, 'OUr work' -> 'Our work'.

---------------------- Score after revision -----------------------

Thanks the authors for adding the performance comparisons with other methods. I think the revised version is better than the previous one. However, I want to keep my original score, since there is some strange behavior of the proposed method in Fig 5 (as also mentioned by the authors): the error turns to increases with the dimensionality when the dimension is large. I think this behavior deserves more study and analysis.
summary_of_the_review: I feel the importance of the work is not well argued in the paper, and hope the authors could address that.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper describes an online stochastic optimization of a neural network to learn an embedding such that the inner-product between embedded points approximates a non-linear kernel based similarity. This can be a radial basis function network that approximates the embedding of a Gaussian kernel. It can also use a homogeneous kernel to approximate cosine-similarities. The network approach can be seen as a sort of Nyström approximation where each output dimension is associated with a different Nyström support point (landmark). The approximation cost is in terms of minimizing an upper bound on the squared error of the similarities. Experimental results show that the method is able to learn meaningful representations. 
main_review: Strengths: 

The problem is interesting and follows a long line of kernel methods and scalable approximations. 

The paper's approach is well motivated. 

The paper is mostly clear and well-written. 

The results are illustrative and capture some of the nature of approximating non-linear similarities in low-dimensional space.

Weaknesses:
This approximation yields something like the Nyström method. Yet no comparisons are made to baseline the approach in terms of Nyström landmark selection algorithms such as Musco and Musco's approach "Recursive Sampling for the Nyström Method" NIPS 2017. 

The experimental results are limited but clear. Nonetheless, I'd like to see results of the performance metrics (similarity and downstream tasks) across different choices of neurons.

While the method concentrated on proper kernel methods (yielding positive semidefinite kernel matrices), it is not clear if the the PSD assumption is necessary. For example stochastic neighbor embedding (SNE) can use different kernel sizes for different input points, which doesn't maintain PSD nature.  The restriction of $f$ and their implications could be elaborated on. 

In the conclusion the wording about the discussion of the relationship to Nyström is somewhat confusing. In particular, the statement "we start with a different objective" doesn't make it clear that this paper uses the same cost as the Nyström approach, but that Fu (2014) used a different objective, which is functional approximation in the RKHS. 

Minor points: 

page 2, " OUr work" 
page 3, Aspects of the proof of Lemma 1 could be incorporated into the text.
 What is meant precisely by "nearly" convex-concave, and is it due to the nature of the Legendre transform?
page 3, comma after 2 will help the reader parse the double verbs in "is derived as an upper bound to Eq. 2 is thus" 
Figure 2 could have the variables from the paper $M,N, T$. Their choice makes them a bit hard to remember.
page 4, "gaurantee"
page 5, "Hebbian rules are been defined" 
page 5, the number of training iterations could be converted to epochs? (how many times the training data set has been seen)


summary_of_the_review: The paper is a solid approach to show feasible online update rules for learning representations that capture non-linear similarity.  Not all aspects of the theory or results are explored.  Key comparisons versus other scalable techniques Nyström are not made, perhaps to focus on the online nature. Nonetheless, some more comparisons and elaborations on the nature of similarities could make this approach more useful in practice.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of finding a low-rank approximation to a kernel matrix. In the low-rank approximation problem, one would want to find a low-rank matrix such that the Frobenius distance between the low-rank matrix and the original matrix is minimized. The paper shows that this optimization problem can be upper bounded by the cost function of a Hebbian neural network with a recurrent layer. Using some experiments the paper shows that this neural network can produce accurate low-rank approximations to some synthetic datasets as well as the MNIST dataset for the Gaussian and Arc-cosine kernels.
main_review: The paper sells the result as an online algorithm for finding a low-rank approximation to a kernel matrix which is not quite the right term for their algorithm. In online algorithms, one typically can only have a single pass over the input dataset while the presented algorithm needs many passes over the input until the neural network converges. 
Moreover, even though the expression of the low-rank approximation problem in terms of a neural network is novel and interesting, it would be much more compelling if the paper presented some convergence analysis for the training of the neural net. In particular, it is not clear if SGD on this network would find the optimal solution or how many epochs are needed for training the model. Basically, the paper presents an algorithm but it does not analyze the algorithm in terms of convergence, generalization, or runtime.


Minor issue:
It seems to me that you need a factor T in the term -1/2 q_i^2 f(w_i,w_i) in Eq(5).


---------------------- Score after revision -----------------------

The revised version of the paper looks better than the initial submission and it has addressed my concerns. Therefore, I raise my score to 6.
summary_of_the_review: I generally like the idea of the paper and think it is novel to express the low-rank approximation problem in terms of a neural network but I have the following concerns about the presentation and contributions of this work. 

The paper sells the result as an online algorithm, while the presented algorithm needs many passes over the input until the neural network converges. It should be stated clearly that your algorithm requires multiple passes.
Moreover, I think it would be much more compelling if the paper presented some convergence analysis for the training of the neural net. In particular, it is not clear if SGD on this network would find the optimal solution or how many epochs are needed for training the model. Basically, the paper presents an algorithm but it does not analyze the algorithm in terms of convergence, generalization, or runtime.
review_title: null

Meta-review: This paper studies the problem of kernel similarity matching using Hebbian neural networks. Specifically, the authors propose to compute the approximate feature map for the kernel using the least square loss function, Legendre transformation, and Hebbian parameter update rules.

Reviewers generally agree that the proposed method is interesting. However, there are major issues with the current manuscript, both theoretically and empirically. Theoretically, there is no guarantee for the convergence of the method. In fact, the non-convergence of the approximation error, when the dimensionality (number of features) increases, indicates that the proposed method is not consistent, in contrast with other methods such as Kernel PCA or Nystrom approximation-based methods. As observed by the authors, this may be related to the unstable convergence of the stochastic gradient descent ascent optimization procedure. For consistency,
the approximation error needs to approach zero as the number of features becomes large. 
Overall, empirical results compared with existing methods are not  satisfactory. As the authors themselves point out in their discussion, "this method does not provide the same sorts of theoretically guarantees or empirically observed robustness of sampling based methods".

The authors are encouraged to take  reviewers' comments and suggestions into account to improve their current work.
Decision: Reject