Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: 
This paper proposes a neural random Fourier feature method. Its novelty is that it considers arbitrary differentiable kernels, while the method introduced by Bahroun et al. (2017) considered kernel similarity matching.

strengths_and_weaknesses: The paper is well written and the contributions seem clear. The derivations seem novel and the experiments are interesting, illustrating the relevance of the proposed method

One issue is that this paper seems to provide an incremental contribution; This contributions is simply the extension of the neural random Fourier feature method be applicable to arbitrary differentiable kernels, while the initial method proposed by Bahroun et al. (2017) investigated kernel similarity matching. 

There are some spelling and grammatical errors that can be easily identified and corrected, such as "the neural algorithm procedes as follows”, “We compare various number of neurons“, “the cluster centers return by KMeans”, “has occured”, "where the the neurons”, “the the colors are”, “We train all configuration”, “The results are show in”, “it seemed that to yield”, “Empirically the convergence our algorithm is”… And also several errors in the appendix.
questions: The main question is about the incremental contribution of this paper, compared to the work of Bahroun et al. (2017) 
limitations: yes
review_title: null

final_score: 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.
review_content: summary: The paper proposes a way to approximate a kernel using a similarity matching objective. In particular, the method adapts the tools from linear similarity matching that formulate kernel approximations as neural network training.
strengths_and_weaknesses: ### Strengths
1. The proposed method is interesting as a biological implementation of kernel approximation, as it can work with one point at a time (and not pairs of points) to approximate the similarity matrix. 
2. This is a relatively straightforward extension of the previous work on online similarity matching, but it's still novel. 

### Weaknesses
1. Unlike Nystrom and random Fourier features method, the proposed method doesn't have theoretical guarantees for the quality of the approximation.
2. The paper is unlikely to be interesting outside of the neuroscience community, as random Fourier features (along with some improved methods) work well/fast/with guarantees for kernel approximation.


### Summary
I think it's an interesting paper with some room for improvement; 7 (accept).
questions: ### Comparison with other methods
The authors should include the standard random Fourier features (RFF), unless Bahroun et al. [2017] implementation is exact. Comparing with orthogonal random features [Yu et al, 2016] (https://proceedings.neurips.cc/paper/2016/hash/53adaf494dc89ef7196d73636eb2451b-Abstract.html) could be interesting as well, as it should improve performance of RFFs wrt dimensionality. 

I'd also like to see comparison of computational complexity of Nystrom, RFF, neural RFF and the proposed method.

On a related note, similarity matching and kernel-based objective have been used for neural network training: [Nøkland and Eidnes, 2019] https://proceedings.mlr.press/v97/nokland19a.html (similarity matching), [Pogodin and Latham, 2020] https://proceedings.neurips.cc/paper/2020/hash/517f24c02e620d5a4dac1db388664a63-Abstract.html (kernels + nearly similarity matching). These methods are not directly comparable with the presented one, but maybe still worth discussing.

### Small corrections

Appendix has to be in a separate pdf.

Appendix E refers to a bound in Eq. 6, but there's no bound. I assume it's for Eq. 3. Either way, why is it an important result? 

Fig. 3 should mention what kernel is used.

Line 83: Reference Eq. 3 explicitly to avoid confusion with Eq. 5.

Lines 4-5: unfinished sentence. “In this paper attempt” -> “This paper attempts” would fix it

Line 46: “we” tackle

Lines 256-258: “it seemed that” -> “it seemed” to fix the sentence

Line 295: descent-ascent? (add hyphen)

Line 296: convergence “of”

Line 297: theoretical (delet -ly)

limitations: The authors adequately addressed the limitations and potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Extended neural random Fourier feature method of Bahroun et al. [2017] for kernel
similarity matching being applicable to arbitrary differentiable kernels. Rather than using
random nonlinear features the features are learned with Hebbian learning rules.
More or less an online method for learning a (psd) similarity matrix.

strengths_and_weaknesses: Strength:
- given the approach is really more cost effective in balance to accuracy it is interesting
  to have an online version for the learning of similarities ~ kernel function approximation
- nice theoretical derivation which maybe of interest on its on (motivated from neuro-biology)

Weakness:
- convergence is obviously a problem - it may not be clear if the approach scales always
  so nice to a wider set of benchmark data
questions: - simple question for the beginning of the paper why is
  'neural kernel similarity matching' relevant?
- Your objective is interesting (but should be a bit more motivated and clarified already in
  sec 1
  (Side note regarding 'online' -- there is also work on online SVD / EVD and online nystroem
   see e.g https://arxiv.org/pdf/1802.07887.pdf)
- Regarding Eq 1 if T is super large your kernel matrix could be large as well
  ... given we make a SVD or EVD on the (psd) kernel matrix we can have your y simple
  by making an euclidean embedding of your kernel ... - which could be done more
  or less reasonable efficient e.g. by Nystroem approximation
  See e.g. work of Talwalkar https://www.jmlr.org/papers/v14/talwalkar13a.html
- 'This is known as the classical multidimensional scaling objective' - well yes but
  for MDS the embedding dimension is typically very low dimensional
- has the kernel function to be shift invariant (constant on the diagonal)?   
- derivations appear to be ok
- hm, convergence is obviously not easy
- Fig 3 there are dashed lines in the plot but not (?) in the legend - maybe due to scaling issues?
- little typo 'psuedo-inverse'
- please replace arxiv links by regular publications if available e.g. 
  Cameron Musco, Christopher Musco: Recursive Sampling for the Nystrom Method. NIPS 2017: 3833-3845
      
limitations: does not apply
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes an on-line kernel similarity matching algorithm.
Taking inspiration from biology, the authors wish to derive a representation learning algorithm that does not consider pairwise similarities (or kernel matrices), and that is based on online parameter updates.
They take the classical multidimensional scaling objective, and derive an upper bound that can be computed without pairwise terms, and further modify it to allow for online computation.
Learning rule examples are provided for a few kernels.
An experimental evaluation on toy data and MNIST illustrates that the method works similar to kernel PCA in low dimensional settings, but less good on more challenging settings.

EDIT AFTER REBUTTAL: I have increased my initial score from 4 to 6 after reading the other reviews and discussing a few of my questions with the authors.
strengths_and_weaknesses: Caveat: I am not very well read in the Hebbian learning literature.

A well written paper that proposes an interesting idea.
The upper bound reconstruction and modifications for online learning are clever.
The experiments are on very limited and low dimensional datasets and do not include any modern baselines for representation learning (only kernel pca / kmeans).
The main premise of the paper is that something can be learned by deriving brain-inspired learning algorithms, yet the paper does not deliver on this premise: the results are not very impressive and neither are their any take-aways from deriving this methodology.

In its current form, it does not provide enough content, or impact to be published as a conference paper at Neurips. I would suggest either a workshop submission or a resubmission with more interesting applications, results, or insights.

questions: It does not seem very clear to me what the high level goal of this paper is. A new method that performs well, a method that leads to interesting insights?
limitations: Numerical limitations (stability) are addressed.
Societal impact not applicable.
review_title: null

Meta-review: metareview: This submission is about brain-inspired learning (Hebbian rules) in the context of kernels. Particularly, given {x^t} points in R^M and a (reproducing) kernel f, the goal of the authors is to learn in a biologically plausible fashion a representation {y^t} in R^N such that f(x^s,x^t) \approx <y^s,y^t> where \approx is meant in squared sense as formulated in (1). They derive the bound (8)-(9) of (1) which is well-suited for Hebbian learning, and apply a stochastic gradient ascent-descent optimization. The practicality of the method is illustrated on the half-moons and the MNIST benchmarks; it performs comparably / favorably to existing approaches and shows sparsity.

Kernel methods are in the forefront of data science. Bringing this field together with online biological updates (Hebbian rules) and extending the neural random Fourier feature (Bahroun et al., 2017) to arbitrary differentiable kernels is a good fit to the focus of NeurIPS with sufficient novelty as it was elaborated by the reviewers.
confidence: Certain
Decision: Accept