Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Authors present a tensor kernel ridge regression method where the covariance kernel is replaced with random Fourier features to reduce the typical O(N^3) cost down to O(NM^2) for M random frequencies. RFFs typically have slow convergence in approximating the full kernel w.r.t. to the number of random frequencies. The tensor is assumed to have a rank-R CPD decomposition to further reduce the complexity of the problem.
main_review: I think the fundamental idea is solid but I have the following questions about the implementation of the model

1.) In Section 4.2 you mention that you use a GP to learn the hyperparameters of your model, wouldn't this contradict the main point of your paper? Why not include the hyperparameter learning component as a part of the learning procedure for your model and the comparisons?
2.) In Section 4.3, why not actually learn hyperparameters in some manner that is non-naive? There is little to suggest that this strategy generalizes to a broad scenario. I think you need to discuss in detail how to learn the hyperparameters for your approach


limitations_and_societal_impact: The authors have adequately addressed their limitations. I do not see any potential negative societal impacts.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors propose a method for inference of large-scale gaussian process (GP) regressio problems with relatively high-dimensional inputs. The method achieves state of the art performance on real-world datasets using 2 innovations 1) formulation of the regression problem in the primal form with deterministic Fourier features, 2) reducing the dimensionality of the regression weights in the primal space by  defining them as a low-rank tensor. The authors describe the advantages and disadvantages of different choices for the tensor decomposition and demonstrate computational and inferential performance on both synthetic and real datasets. Of note is their ability to achieve comparable performance using a laptop computer to competing methods using clusters.
main_review: The paper is well-motivated, accessibly written, and well demonstrated. I have very little critical to say about it other than that I'm not sure how this approach helps with hyperparameter learning, which tends to be some of the highest computational overhead of GP methods. Did I miss something?

Finally, the authors mention the non-probabilistic nature of these methods. They might think of their method in the context of work by Rose Yu and colleagues, starting with their 2018 AISTATS paper. Although they rely on the Tucker decomposition, rather than CP decomposition, it might be closely-related enough to consider mentioning.

limitations_and_societal_impact: Limitations were addressed but there was no mention of societal impacts.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors propose a novel kernel approximation scheme based on deterministic Fourier features and tensor decomposition. The proposed approach improves previous efforts in the sense that (i) it deduces the (kernel) approximation error to decrease exponentially with the number of frequencies (or Fourier features); and (ii) it overcomes the ”curse of dimensionality“ with the low-rank tensor decomposition approach, the complexity of which scales linearly in the input dimension. Simulation results (on the performance of tensor kernel ridge regression) are provided to validate the proposed method, on both small and large dimensional datasets.
main_review: The article is in general well written and makes a solid contribution to the approximation of large-scale kernel matrices. A few comments:
* Only performance of kernel-based methods are compared on various datasets, e.g., MSE in the regression setting or misclassification rate in the classification setting. Unless I missed something, the proposed method is designed to (i) deduce the **approximation error** (with respect to the underlying kernel matrix) in a more efficient manner and (ii) reduce the (storage and computational) **complexity**. None of the numerical results seems to reflect this information/improvement. 
* It seems that the defining equation of G^(d) should be G^d?


================================================
After rebuttal: I thank the authors for their clarification, that helps. I believe that adding more experiments on the gain of (storage and computational) **complexity** with the proposed method will broaden the impact of this work (for the moment there are only two sentences on the time complexity). My score remains the same.
limitations_and_societal_impact: The authors have adequately addressed the possible limitations of their approach. This work is mainly theoretical and algorithmic and I do not see any possible negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes to use tensor decomposition techniques to approximate the deterministic Fourier features (DFF), in large-scale kernel learning. The main idea is that, after the DFFs are generated in the tensor form, low-rank approximation by tensor decomposition is applied, which can be formulated as a regularized convex optimization. Block coordinate descent is then used to solve the problem effectively. Experiments on kernel ridge regression and Gaussian process regression with synthetic and real datasets confirm the effeciency of the proposed approach.
main_review: The paper is written very clearly, and the organization is neat, so it's very easy to follow. 

In general, the problem studied in the work, speeding up large-scale kernel learning, is valuable and interesting to many people in the NeurIPS community. Deterministic random feature have received less attention before since it is harder to be applied in practice and suffers from the curse of dimensionality, but as the paper shows, it has its own advantages and can be competible in certain problems. Tensor dedcomposition is also a trending topic recently. The idea of combining them together is a good attempt.

Regarding the content of the paper, the first 5 pages are rather fundamental and mostly introduce existing concepts and algorithms.  The problem formulation is presented in Section 3.4, which is also quite standard and does not require novel techniques. Hence, I would say that this paper is more like an experimental/application paper, that applies existing methods in tensor analysis to deterministic Fourier features.

Questions:

1) Could please specify the dimensionality of the feature space of proposed low-rank DFF? Should it be $\hat MRD$ or $\hat MR$ (line 207 and 278)? This relates to the validity of comparison with RFF.

2) How does RFF compare with T-KRR in terms of exact running time? What is the optimization algorithm for RFF?

3) What is the relationship between Hilbert-GP, DFF and the proposed method? There are some description in e.g. sec 4.1, but I suggest to make the comparison and relation with other methods more clear, e.g., list the complexities and equivalence conditions explicitly.

4) Besides computational complexity, storage efficiency might also be an important topic. I believe the low-rank approximation is also beneficial in terms of memory in some way. On this regard, there are some works on memory-efficient RFF that might be related,

Data-dependent compression of random features for large-scale kernel approximation, AISTATS 2019

Low-Precision Random Fourier Features for Memory-constrained Kernel Approximation, AISTATS 2019

Quantization Algorithms for Random Fourier Features, ICML 2021

In all, I think this paper is a good attempt to apply tensor analysis to machine learning to solve practical problems. If the authors can answer my questions with satisfactory, I would recommend a weak acceptance. 
limitations_and_societal_impact: NA
review_title: null

Meta-review: This paper gives a deterministic version of the random feature model by constructing the features explicitly using certain tensor structure. The additional structure allows more efficient computation and performs well in practice. The reviewers found that the experiments are convincing and the ideas are sound. There were some confusions about the exact complexity of the proposed algorithm, which should be clarified in the revised paper.
Decision: Accept (Poster)