Large-Scale Learning with Fourier Features and Tensor Decompositions
Authors: Frederiek Wesel
kim batselier
Venue: NeurIPS 2021 Poster (2021)
Keywords: Fourier Features
Kernel Methods
Kernel Machines
Tensors
Tensor Decomposition
Tensor Networks
Kernel Ridge Regression
Gaussian Process Regression
Least-Squares Support Vector Machine

Abstract: Random Fourier features provide a way to tackle large-scale machine learning problems with kernel methods. Their slow Monte Carlo convergence rate has motivated the research of deterministic Fourier features whose approximation error can decrease exponentially in the number of basis functions. However, due to their tensor product extension to multiple dimensions, these methods suffer heavily from the curse of dimensionality, limiting their applicability to one, two or three-dimensional scenarios. In our approach we overcome said curse of dimensionality by exploiting the tensor product structure of deterministic Fourier features, which enables us to represent the model parameters as a low-rank tensor decomposition. We derive a monotonically converging block coordinate descent algorithm with linear complexity in both the sample size and the dimensionality of the inputs for a regularized squared loss function, allowing to learn a parsimonious model in decomposed form using deterministic Fourier features.
We demonstrate by means of numerical experiments how our low-rank tensor approach obtains the same performance of the corresponding nonparametric model, consistently outperforming random Fourier features.

Large-Scale Learning with Fourier Features and Tensor Decompositions
Frederiek Wesel
Kim Batselier
Delft Center for Systems and Control Delft University of Technology f. wesel @tudelft.... ftf.tt...
Delft Center for Systems and Control
Delft University of Technology
k. fatsueler@tudelft.
Abstract
Random Fourier features provide a way tackle large-scale machine learning problems with kernel methods. Their slow Monte Carlo convergence rate has motivated the research of deterministic Fourier features whose approximation error can decrease exponentially in the number of basis functions. However, due to their tensor product extension multiple dimensions, these methods suffer heavily from the curse of dimensionalityy limiting their applicability to one, two or three- dimensional scenarios. In our approach we overcome said curse of dimensionality by exploiting the tensor product structure of deterministic Fourier features, which enables us represent the model parameters as a low-rank tensor decomposition. We derive a monotonically converging block coordinate descent algorithm with linear complexity in both the sample size and the dimensionality of the inputs for a regularized squared loss function, allowing to learn parsimonious model in decomposed form using deterministic Fourier features. We demonstrate by means of numerical experiments how our low-rank tensor approach obtains the same per- formance the corresponding nonparametric model, consistently outperforming random Fourier features.
Introduction
Kernel methods such Support Vector Machines and Gaussian Processes are commonly used to tackle problems such as classification, regression and dimensionality reduction. Since they can be universal function approximators [13, kernel methods have received renewed attention in the last few years and have shown equivalent or superior performance to Neural Networks [22 26 [1]. The main idea behind kernel methods is to lift the data into digher-dimensional (or even infinite- dimensional) Reproducing Kernel Hilbert Space H by means of a feature map Φ (-) X + H. Considering then the pairwise similarities between the mapped data allows tackle problems which are highly nonlinear the original sample space X', but linear in H. This can be done equivalently by considering kernel function & (:.))= X' x X' R such that (d) (a=) Φ (a))) k (æ, x²) and performing thus said mapping implicitly. Although effective at learning nonlinear patterns in the data, kernel methods known to scale poorly the number of data points N increases. For example, when considering Kernel Ridge Regression (KRR), Gaussian Process Regression (GPR) [33] or Least-Squares Support Vector Machine (LS-SVM) [4 42 training usually consist in inverting the Gram matrix K;j = & (z;, 2,), which encodes the pairwise relation between all data. As consequence, the associated storage complexity is O (N2) and the computational complexity is O (N*),, rendering these methods unfeasible for large data. In order to lower the computational cost, data dependent methods approximate the kernel function by means of data dependent basis functions. Due to their reduced-rank formulation, the computational complexity is reduced to O M?) for N > M. However, e.g. for the Nyström method [46], the convergence rate is
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

only of O (1/M) 7 limiting its effectiveness. As the name suggests, data independent methods approximate the kernel function by M data independent basis functions. good example is the celebrated Random Fourier Features approach by Rahimi and Recht [31. where the authors propose
for stationary kernels a low-dimensional random mapping 2 x+) IR. RRM such that
(,, x²) (z) oz)")) = (z (a) (ax))
(1)
As in the case of data dependent methods, the reduced-rank formulation allows for computational complexity of O ( (2M for N >> M. Probabilistic error bounds on the approximation are provided which result in a convergence rate of O (1/VM), which is again the Monte Carlo rate.
Improvements in this sense were achieved by considering deterministic features resulting from dense quadrature methods [3] 25 36 and kernel cigenfunctions [6 39]. These methods are able to achieve exponentially decreasing upper bounds on uniform convergence guarantees when certain conditions are met. However, for a D-dimensional input space these methods take the tensor product of D vectors, resulting in exponential increase in the number of basis functions and thus of model weights, effectively limiting the applicability of deterministic features to low-dimensional data. In this work consider deterministic features. In order to take advantage of the tensor product structure which arises when mapping the inputs to H. we represent the weights as a low-rank tensor. This allows us to learn the inter-modal relations in the tensor product of (low-dimensional) Hilbert spaces, avoiding the exponential computational and storage complexities in D. In this way we are able to obtain a linear computational complexity in both the number of samples and in the input dimension during training, without having to resort to the use of sparse grids or additive modeling of kernels.
The main contribution of this work is in lifting the curse of dimensionality affecting deterministic Fourier features by modeling the weights as a low-rank tensor. This enables the efficient solution of large-scale and high-dimensional kernel learning problems. We derive an iterative algorithm under the exemplifying case of regularized squared loss and test it on regression and classification problems.
2 Related work
Fourier Features (FF) are collection of data independent methods that leverage Bochner's theo- rem (35) from harmonic analysis approximate stationary kernels by numerical integration of their spectral density p (-):
1: (zx x²) Stationarity 1 (x x²) Bochner
FF / (w) exp exp (liw, (x - x²1)) dw Ro (z (z), (x'))
Rahimi and Recht [3]] proposed approximate the integral by Monte Carlo integration i.e. by drawing M random frequencies w ~ (.)). In their work they show how the method converges uniformly at the Monte Carlo rate. See [23] for an overview of random FF. In order to achieve faster convergence and a lower sample complexity, a multitude of approaches that rely on deterministic numerical quadrature of the Fourier integral were developed. These methods generally consider product kernels whose spectral density factors in the frequency domain, which enables in turn to factor the Fourier integral. The resulting deterministic Fourier features are then the tensor product of D oie-dimensional deterministic features.
For example, in [5] the authors give analysis of the sample complexity of features resulting from dense Gaussian Quadrature (GQ). In (25) the authors present a similar quadrature approach for kernels whose spectral density factors over the dimensions of the inputs. They provide an explicit construction for their Quadrature Fourier Features relying on a dense Cartesian grid, and note that their method, well GQ, can attain exponentially decreasing uniform convergence bounds in the total number of basis functions per dimensions AM [25] Theorem 1]. To avoid the curse of dimensionality, they make use of additive modeling of kernels. Variational Fourier Features (VFF) [6] are derived probabilisticaly in a one-dimensi setting for Matérn kernels by projecting a Gaussian Process onto set of Fourier basis. An extension to multiple dimensions when considering product kernels then achieved by taking the tensor product of the one-dimensional features, incurring however again in exponentially rising computational costs in D. In what they call Hilbert- GP [39 the authors diagonalize stationary kernels in terms of the eigenvalues and eigenfunctions of the Laplace operator with Dirichlet boundary conditions. Due to the multiplicative structure of the
2

---

eigenfunctions of the Laplace operator, the complexity of the basis function increases exponentially in D when one considers product kernels. Like with other deterministic approximations, bounds on the uniform convergence enror which decrease exponentially in M can be achieved 39 Theorem 8].
Tensor decompositions have been used extensively in machine learning in order to benefit from structure in data [8), in particular to obtain efficient representation of the model parameters. In the context of Gaussian Process Regression, the tensor product structure which arises when the inputs are located on Cartesian grid have been exploited to speedup inference [1]. In their variational inference framework, [19] proposed to parameterize the posterior mean of a Gaussian Process by means of a tensor decomposition in order to exploit the tensor product structure which arises when interpolating the kernel function. In the context of neural networks, [27] proposed to represent the weights in deep neural networks as a tensor decomposition to speed up training. A similar approach was carried out in case of recurrent neural networks [8] 43
Tensor decompositions have also been used learn from simple features. In 45 multivariate functions are learned from a Fourier basis, which corresponds to assuming uniform spectral density in (2). Motivated by spin vectors in quantum mechanics, [40] consider trigonometric feature maps which they argue induce uninformative kernels. On a similar note, [28] and [[] leverage the tensor product structure of polynomial mappings to induce polynomial kernel and consider model parameters in decomposed form. While these existing approaches are able to overcome the curse of dimensionality affecting tensor product feature maps by modeling the parameter tensor as a tensor network, they consider simple and empirical feature maps which induce uninformative kernels. In the following section we show how deterministic Fourier features can be used for supervised learning in both large and high-dimensional scenarios by assuming that the model weights are low-rank tensor, thereby linking tensor decompositions with stationary product kernels.
Learning with deterministic Fourier features
3.1 Notation
All tensor operations and mappings can be formulated over both the complex and the real field. For the remainder of this article real-valued mappings will be considered. Vectors and matrices are denoted by boldface lowercase and uppercase letters, respectively. Higher-order tensors are denoted by boldface calligraphic letters. Tensor entries are always written as lightface lowercase letters with subscript index notation. For example, element i1, i2, is of the third-order tensor written i2is The vectorization vec (A) of tensor A e
A E R x/2 is IR 1gxxxxx-- x is the vector such that
vec (A); Qiiégmiin
where the relationship between the linear index i and i .
in is given by
A-1
+
(ia
1)
II
IN.
d=2
k=1
The Frobenius inner product between tensors A E RR 11xxxxx--xIl and B E x/xx1xxxxx is defined as
(A, = i1
in bi iniiiii vec (A) vec (B3)
Depending the context, the symbol @ either denotes the tensor outer product or the matrix Kronecker product. The Khatri-Rao product A @ B of the matrices A E N and B E MxR is the NM R matrix that is obtained by taking the column-wise Kronecker product. The Hadamard (element-wise) matrix product of A E IR NxR and B E N is denoted by A O B.
3.2
The model
In this article we assume models of the form
(x) = (w, & (x)), y = fz) tc.
(3)
3

---

Here x E RP is the input vector, Φ : H. is a feature map, w E H. are the model weights, y E IR is the corresponding available observation corrupted by a zero mean i.idd noise Learning such a kernelized model consists in finding as set of weights w such that:
N
(Yas I (xxn) + X (wx w)pp Σ
(4)
RR is symmetric and positive loss function and À (w, w)p a p-th norm regularization term. A variety of primal machine learning formulations arise when con- sidering different combinations of loss functions and regularization terms. For example, considering p 2 and squared loss leads to Kernel Ridge Regression [42], while considering hinge loss leads to SVM 4 and so on. Furthermore, applying the kernel trick when considering & (-) recovers the non- parametric formulation which, depending on the choice of kernel, enables to perform inference using infinitely many basis functions with a computational complexity of ((NS). Considering instead a low-dimensional finite mapping (-) : X - TR such as Random Fourier Features or the Nyström method leads primal approach and to computational savings with a computational complexity of O (N 22) for > M. However, as already discussed, these low-dimensional random mappings converge at the slow Monte Carlo rate, motivating our approach.
minimized. Here, L (.,-)
In order to approximate the kernel function with faster and possibly exponential convergence, we consider deterministic, sittee-dmessional features which are the tensor product of D vectors. For a given D-dimensional input point æ we define the deterministic feature mapping 2 (-) RD
R M @ Ma @ @ RMM as
(x) (1) (x1) & (2)
(22) 2z(00 (D) (ID);
(5)
where z (dd) is a deterministic mapping applied to the d-th dimension. The dimension of the feature space is denoted M T2- Ma. Without loss of generality it is from here on assumed that M₁ =... = MD M such that M DTD It easy to verify by applying the kernel trick that the features of (5) yield product kernels. The mapping 2 (-) encompasses for instance the mappings derived by quadrature [5] 25 36) and by projection [66 39]. Note that these mappings cover many popular kernels such as the Gaussian and Matérn kernels. To give concrete example, in the framework of A. Solin and S. Särkkä [39 Equation 60), for input data centered in hyperbox X' 1-U1, U1] @ ... @ [-UD, Up) the Gaussian kernel is approximated by means of D tensor products of MM weighted sinusoidal basis functions with frequencies lying on a harmonic scale such that:
((a)) io Vua"
Tid 20A
sin
Tid (x. + Ua)
+Ua)
is = 1, M.
(6)
2Ua
Here p (-) is the spectral density of the Gaussian kernel with one-dimensional inputs, which is known in closed-fome B3 page 83]. This deterministic mapping then approximates the Gaussian kernel function 39 Equation 59] such that
At (ar, a²) A (vee (z (z)), vec (zx))) = (3 (a:) )).
and converges uniformly with exponentially decreasing bounds
39 Theorem 8). We therefore use
(-)) instead of (0-) in (3) to obtain
f (x) = (w, vec(Z(x))) = (W, (W,z(z))) Z(x))F
(7)
where the weight vector w has been reshaped into D-dimensional tensor W E M Maxx XM Learning the exponential number of model parameters W in (7) under a hinge loss leads to Support Vector Machines, while considering squared loss leads to the primal formulation of Kernel Ridge Regression, which we will consider as exemplifying case from here on:
min W
Σ (yn 1W, z (z,))))²² + XWW
(8)
Since the number of elements M in W and Z grows exponentially in D, this primal approach is advantageous compared to the nonparametric dual approach only if 17 < N, limiting it to low-dimensional inputs. In order to lift this curse of dimensionality, we propose to represent and to learn W directly as a low-rank tensor decomposition. A low-rank tensor decomposition allows us to exploit redundancies in W in order to obtain a parsimonious model with storage complexity that scales linearly both M and D. The low-rank structure will, as explicitly shown in the experiments, act as form of regularization by limiting the total number of degrees of freedom of the model.

---

3.3 Low-rank tensor decompositions
Tensor decompositions (also called tensor networks) can be seen as generalizations of the Singular Value Decomposition (SVD) of matrix to tensors [20]. Three common tensor decompositions are the Tucker decomposition Decomposition (CPD) 17 21
the Tensor Train decomposition [29] and the Canonical Polyadic where each of them encompasses different properties of the matrix SVD. In this subsection we briefty discuss these three decompositions and list both their advantages and disadvantages for modeling W in (8) For a detailed exposition on tensor decompositions we refer the reader to 2 and the references therein.
important property tensor decompositions that they can always be written linearly in their components, which implies that applying block coordinate descent algorithm to solve results a series of linear least-squares problems.
rank-R CPD of W consists of D factor matrices W (d) E R xxM and a vector & IR such that
(1))
W
W(D)
Σ
w!!)
Note that the entries of the vector were absorbed in one of the factor matrices when writing the CPD as sum of R terms. The CPD has been shown, in contrast to matrix factorizations, to be unique under mild conditions (37]. The storage complexity comes mainly from the D factor matrices and is therefore D). The Tucker decomposition generalizes the CPD in two ways. First, the Khatri-Rao product is replaced with Kronecker product. The s vector has to grow in length accordingly from R to RD. Second, the R-dimension of each of the factor matrices is allowed to vary, resulting in multi-lineat rank (R,, R
w (W()) ( 8 .... W())
The Tucker decomposition is inherently non-unique and its storage complexity O(RP) is dominated by the s vector, which limits its use to low-dimensional input data. For this reason we do not consider the Tucker decomposition any further in this article.
The Tensor Train (TT) decomposition consists of D third-order tensors W RRRaxMMRR- such that
R2
Roy1 Σ PD+1=1
(1) Piirre
(D) "riiprp
Wigf2--ip
w
W
(9)
P1=1
The auxiliary dimensions R1, R2,... RD+1 are called the TT-ranks. In order to ensure that the right-hand side of (9) is a scalar, the boundary condition R2 = RD-1 = enforced. The TT decomposition is. just like the Tucker decomposition, non-unique and its storage complexity R M due to the D tensor components (( Considering their storage complexity, both the CPD and TT decomposition are viable candidates replace W in (8). The CP-rank R and TT-ranks Re.... RD are additional hyperparameters, which favors the CPD in practice. For the TT, one could choose Rp reduce the number of additional hyperparameters but this constraint turns out in practice to lead to suboptimal results, For these reasons we limit the discussion of the learning algorithm to the CPD case.
Ra R3
3.4 Tensor learning with deterministic Fourier features
We now wish to minimize the standard regularized squared loss function as in ( with the additional constraint that the weight tensor has rank-Rt R CPD structure:
min W
Σ yn (W, Z (xx)))p)² + A... W)
(10)
subject to
CP-rank (W) R.
(11)
Note that if R equals the true CP-rank of the underlying weight tensor then the exact solution of (
would be obtained. practice low-rank solution for W achieves a sufficiently complex decision
boundary that is practically indistinguishable from the full-rank solution, is demonstrated in the
5

---

experiments. Imposing the rank R reduces the number of unknowns from M to RMD and allows the application of a block coordinate descent algorithm (also known as alternating linear scheme), which is shown to converge monotonically [ 18 34). Each of the factor matrices W is optimized in an iterative fashion while keeping the others fixed. Such factor matrix update is obtained by solving a linear least-squares problem with M R unknowns. In what follows we derive the linear problem for the d-th factor matrix W(4), The data-fitting term (W, (xx)) can be rewritten linearly terms of the unknown factor matrix as
(W. 3(x)) = =< (vec (wr()) gg(t)) (a))
(12)
where g(d) (x) 2(1) & (z()'W(!)? o... 20)) w(()) Similarly, for the regularization term:
W(1)
(w.W) = vve Wi Wrll" vec (H())
(13)
Here (d) = (w W
w(D' Derivations of and 13 can be found
in Appendix. Substitution of the expressions least-squares problem for vec (W(d)):
12 and 13 into 10 and leads to a linear
N Σ
yn ( vee (wil)) (d) (o.))) + A (vec (wr W(,)) (wrl)""(ad)) vec (H))) (14)
min vec ((
Its unique solution can be computed exactly in efficient manner by solving the normal equations, requiring N 2 + M R2 operations. Since we are solving non-convex optimization problem that consists of a series of convex and exactly solvable sub-problems, our algorithm is indeed monotonically decreasing, and, although it is not guaranteed converge the global optimum, it is the standard choice when dealing with tensors [3, 120). The total computational complexity of the algorithm when N >> M is then O(N DM rendering it suitable for problems which are large in both N and D. provided that R and M are small. The necessary memory is equal to RMD + 2R A12 2RM (storing the weight tensor W in decomposed form, the RaM Gram matrix and regularization matrix, the transformed responses and the solution of the linear system), leading to storage complexity of O [ (M2) for RM > D. Notably the cost independent of N, which allows processing large data on modest hardware.
When learning, the selection of À and of the kernel-related hyperparameters can be carried out by standard methods such as cross-validation. The choice of M and the additional hyperparameter R which we introduce are directly linked with the available computational budget. One should in fact choose M so that the model has access to sufficiently complex set of basis functions to learn from. In practice we notice that for our choices of kernel function hyperparameters, at most M = 40 basis functions per dimension suffice. can then be fixed accordingly in order to match the computational budget at hand. As we will show in the next section, learning is possible with small values MM and R.
4 Numerical experiments
We implemented our Tensor- Kernel Ridge Regression (T-KRR) algorithm in Mathworks MATLAB
2021a (Update 1) [24 and tested it on several regression and classification problems. Our im- plementation can be freely downloaded from ltttps://tithiii reproduction of all experiments in this section. In our implementation we avoid constructing g (.) and (d) from scratch at every iteration by updating their components iteratively. With the exception of the first experiment 4.1 we further speedup implementation by considering only the diagonal of the regularization term H (4), All experiments were run on a Dell Inc. Latitude 7410 laptop with 16 GB of RAM and an Intel Core 17-10610U CPU running at 1.80 GHz. all our experiments the Gaus- sian kernel lo (z, x²) = exp (-I -ilae=='l ='11///27 21/221)) 212) was approximated by considering the Hilbert-GP (39] mapping of (6). In all experiments inputs were scaled to lie in a D-dimensional unit hypercube. When dealing with regression, the responses were standardized around the mean, while when considering
com/ www.e//weeeeeeeee and allows

---

(a) R=
R 44
(c) R= 6
(d) R= M 144
Figure 1: Classification boundary of the two-dimensional banana dataset for increasing CP-ranks. In the last plot the chosen CP-rank matches the true matrix rank. The dashed line is the Hilbert-Gi while the full line is T-KRR.
binary classification inference done by looking at the sign of the model response (LS-SVM 41 One sweep of our T-KRR algorithm is defined as updating factor matrices in the order + and then back from D - 1. All initial factor matrices were initialized with standard normal numbers and normalized by dividing all entries with their Frobenius norm. For all experiments the number of sweeps of T-KRR algorithm proposed T-KRR algorithm is stable and recovers the full KRR estimate in case of low number of frequencies M and low rank R, consistently outperforming RFF. Finally, our model exhibits very competitive performance on large-scale problems when compared with other kernel methods.
set to 10. In the following three experiments is shown how
4.1 Banana classification
The banana dataset is a two-dimensional classification problem [15] consisting datapoints. Since the data is wwo-dimensional, we consider A/ = 12 frequencies per dimension, which enables to compare T-KRR with Hilbert-GP. Furthermore since for tensors of order two (i.e matrices) the CP-rank is the matrix rank, we can deduce that our approach should recover the underlying Hilbert-GP method with R = M/2 = 144. In this example we fix the kernel hyperparameters of our method and of the Hilbert-GP to 1 = 1/2 and À 10-3 for visualization purposes. In Figure [ we plot the decision boundary of T-KRR (full line) and of the associated Hilbert-GP (dashed line). We can that already when R 6 the learned decision boundary is indistinguisaalee to the one of Hilbert-GP, meaning that in this example it is possible to obtain low-rank representation of the model weights. From computational point of view, we solve series of linear systems with M R unknowns instead of A However due the low-dimensionality of the dataset, the computational savings per iteration are very modest, i.e. for R and M 12, we solve per iteration linear system with 72 unknowns as opposed to the one-time solve of linear system with 144 unknowns as in case of Hilbert-GP, As we show in Subsection [4.2] the linear computational complexity in D of our algorithm results in ever-increasing performance benefits as the dimensionality of the problem becomes larger, where it becomes impossible to consider a full weight tensor.
= 5300
4.2 Model performance with baseline
We consider five UCI 8 datasets in order to compare the performance of our model with RFF and the GPR/KRR baseline. For each dataset, we consider 90% of the data for training and the remaining 10% for testing. In particular, in all regression datasets, of the Gaussian kernel and regularization term À by -og-magginal likelihood optimization over the whole training set using the GPLM toolbox (32). We subsequently train GPR/KRR, RFF and our method with the estimated hyperparameter. In case of classification, we choose the lengthscale to be the sample mean of the sample standard deviation of our data (which the default choice in the Matlab Machine Learning Toolbox and scikit-learn 300 and X = 10-5, We repeat this procedure ten times over different random splits and report the sample mean and sample standard deviation of the predictive mean-squee meuaee error (MSE) and the misclassification rate for regression and classification respectively. In order to test the approximation capabilities of our approach, we set M/ and R such
first obtain an estimate of the lengthscale
7

---

0.9
Misclassification rate
0.8
Loss
0.6
0.5
0.1
Number of sweeps
Number of sweeps
Figure 2: Normalized loss and misclassification rate while training on the Spambase dataset.
Table 1: Predictive MSE (regression) and misclassification rate (classification) with one standard
deviation for RFF, T-KRR and KRR on different UCI datasets.
Dataset
N 4
D
M
R
RFF
T-KRR
KRR
Yacht
308
6
10
25
0.0021
0.0018
0.0009 0.0006
0.0007 + 0.0004
Energy
768
9
20
10
0.0275 + 0.0075
0.0200 + 0.0066
0.0200 + 0.0087
Airfoil
1503
5
20
0.2180 0.0336
0.1679 0.0258
0.1587 + 0.0232
Spambase
4601
57
40
10
0.3620 + 0.0188
0.0935 = 0.0095
0.0909 + 0.0115
Adult 45222
96
40
10
0.3976 + 0.0056
0.1596 + 0.0046
N/A
that MR & N in order to benefit from computational gains. Furthermore, we note that due to the curse of dimensionality it is not possible to compare our approach with RFF while considering the same total number of basis functions M D. Hence we select MRFF M R such that the computational complexity of both methods is similar. Table [ shows the MSE for different UCI datasets. We see that our approach comes close the performance RFF on all datasets when considering the same number of model parameters. This is because our approach considers implicitly D frequencies to learn low-rank parsimonious model which is fully described by M MD parameters, as opposed to RFF where the number of frequencies is the same as the number of model weights. Similarly to what is reported in [47 Figure 2] we observe lower performance of RFF on the Adult dataset than reported in [3I]. Figure plots the monotonically decreasing loss function as well as the corresponding misclassification rate while training with T-KRR on the Spambase dataset. After four sweeps the misclassification rate has converged. Since T-KRR is able to obtain similar performance as the KRR baseline on a range small datasets, we proceed to tackle large-scale regression problem.
full KRR and outperforms
4.3 Large-scale experiment
In order to highlight the ability of our method to deal with large data we consider the Airline dataset. The Airline dataset [14 [6] is a large-scale regression problem originally considered in [1] which often used to compare state-of-the-art Gaussian Process Regression approximations due its large size and its non-stationary features. The goal is in fact predict the delay of flight given eight features, which are the age of the airplane, route distance, airtime, departure time, arrival time, day of the week, day of the month, and month. We follow the same exact preprocessing steps as in the experiments in [16), [39] and [9], which consider subsets of data of size N 10000, 100000, 1000000, 5929413, each chosen uniformly random. Training the model is then accomplished with ?/2N datapoints, with the remaining portion reserved for testing. The entire procedure is then repeated 10 times with random initialization in order to obtain sample mean and sample standard deviation estimate of the MSE. Following exactly the approach in Hilbert- GP [39], we consider M = 40 basis functions per dimension, with the crucial difference that T-KRR

---

Table 2: Predictive MSE with one standard deviation for T-KRR. The prefix -A indicates that the model in question considers an additive kernel.
N
10000
100000
1000000
5929413
T-KRR (R = 5)
0.91 + 0.10
0.82 + 0.03
0.80 0.02
0.800 0.008
T-KRR (R 10)
0.89 0.05
0.80 + 0.05
0.79
0.785 + 0.009
T-KRR (R- 15)
0.90
0.00
0.78
0.773 0.007
T-KRR (R 20)
0.97
0.77 0.78
0.763 = 0.007
A- Hilbbert-Cr GG [39
0.17
0.00
0.83
A-VFF [6
0.89
0.82
0.83 - 0.01
0.827 = 0.004
SVIGP 14
0.89
0.79 + 0.05
0.79 = 0.01
0.791 0.005
VISH 9
0.90
0.81 + 0.05
0.83 = 0.03
0.834 + 0.055
GPR 33
0.89
N/A
N/A
N/A
A-GPR 10
0.89
N/A
N/A
N/A
approximates a standard product Gaussian kernel, opposed to an additive model. As was the case in the previous section for classification, we select the lengthscale of the kernel as the mean of the standard deviations of the eight features and choose xy 100/N for the different splits, where the dependency on N is suggested by standard learning theory. We then train four distinct models for R 10, 15, 20. Table 2 compares T-KRR with the best performing models found in the literature, which all (except for GPR) rely on low-rank approximation of the kernel function. The T-KRR method is able to recover the baseline GPR performance already with R = 5 and remarkably outperform all other approaches although we choose the hyperparameters naively and consider equal lengthscales / for all dimensions. Interestingly, a higher choice of R does result in better performance in all cases except for N = 10000, where model performance very much depends on the random split (note that consider different splits for each experiment). The SVIGP [4] achieves comparable results to T-KRR, indicating that performance gain is possible from product kernels. The difficulty with SVIGP however that the kernel function interpolated locally M nodes in a data- data-dependent fashion, requiring an increasing amount of interpolation nodes to cover the whole domain to allow for good generalization. In contrast, T-KRR considers an exponentially large amount of basis functions in the frequency domain, and learns an efficient representation of the model weights. In light of the performance of the additive Hilbert-GP and additive VFF models, we expect similar performance when considering other feature maps which induce stationary kernels. When considering the whole dataset, training our model with R = 5 takes 1565 + seconds on laptop, while for = 20 takes 7141 + 245 seconds. Reported training times of SVIGP indicate 18360 + 360 seconds [16] on a cluster. Since the computational complexity of our algorithm dominated by matrix-matrix multiplications, we expect significant speedups when relying on GPU computations.
Conclusion
In this work a framework to perform large-scale supervised learning with tensor decompositions which leverages the tensor product structure of deterministic Fourier features was introduced. Concretely, a monotonically decreasing learning algorithm with linear complexity in both sample size and dimensionality was derived. This algorithm leverages the efficient format of the Canonical Polyadic Decomposition in combination with exponentially fast converging deterministic Fourier features which allow to implicitly approximate stationary product kernels up to machine precision. Numerical experiments show how the performance of the baseline Kernel Ridge Regression is recovered with a very limited number of parameters. The proposed method can handle problems which are both large in the number of samples well as in their dimensionality, effectively enabling large-scale supervised learning with stationary product kernels. The biggest limitation of the current approach that it is does not allow for uncertainty quantification, which motivates further work in that direction.

---

Funding transparency statement
Frederick Wesel, and thereby this work, is supported by the Delft University of Technology Al Labs program. The authors declare no competing interests.
Acknowledgments
We would like to thank Arno Solin and Vincent Dutordoir for the help received with the Airline dataset.
References
[1] Z. Chen, K. Batselier, J. A. K. Suykens, and N. Wong. Parallelized Tensor Train Learning of Polynomial Classifiers. IEEE Transactions on Neural Networks and Learning Systems, 29(10) 4621-4632, Oct. 2018.
[2] A. Cichocki, N. Lee, I. Oseledets, A.-H. Phan, Q. Zhao, and D. Mandic. Tensor Net- works for Dimensionality Reduction and Large-scale Optimization: Part 1 Low-Rank Tensor Decompositions. Foundations and Trends@ in Machine Learning, 9(4-5):2494422 2016.
[3] Comon, Luciani, and A. L. de Almeida. Tensor decompositionss, alternating least squares and other tales. Journal of Chemometrics, (377-8):933-405 July 2009.
[4] C. Cortes and V. Vapnik. Support- networks. Machine Learning, 20(3):273-297 Sept. 1995.
[5] T. Dao, D. Sa, and C. Ré. Gaussian quadrature for kernel features. Proceedings of the 31st International Conference on Neural Information Processing Systems. NIPS' 17, pages 6109-61199 Red Hook, NY, USA, Dec. 2017. Curran Associates Inc.
[6] L. De Lathauwer, De Moor, and J. Vandewalle. Multilinear Singular Value Decomposition. SIAM Journal on Matrix Analysis and Applications, 2154): Jan. 2000.
[7] P. Drineas and M. W. Mahoney, On the Nystrom Method for Approximating a Gram Matrix for Improved Kernel-Based Learning. Journal of Machine Learning Research, 6(72):2153-2175, 2005.
[8] D. Dua and C. Graff. UCI Machine Learning Repository. http://archive.iss.uiiii
2017.
[9] V. Dutordoir, N. Durrande, and J. Hensman. Sparse Gaussian Processes with Spherical Harmonic Features. In International Conference Machine Learning, pages 2793-2802. PMLR, Nov. 2020.
[10] D. Duvenaud, H. Nickisch, and C. E. Rasmussen. Additive gaussian processes. In Proceedings of the 25th International Conference on Neural Information Processing Systems, NIPS' 11, pages 226-234, Red Hook, NY, USA, 2011. Curran Associates Inc.
[11] A. Garriga-Alonso, C. E. Rasmussen, and L. Aitchison. Deep Convolutional Networks as shallow Gaussian Processes. In International Conference Learning Representations, 2018.
[12] E. Gilboa, Y. Saatçi, and J. P. Cunningham. Scaling Multidimensional Inference for Structured Gaussian Processes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(2): 124-436, Feb. 2015.
[13] B. Hammer and K. Gersmann. A Note the Universal Approximation Capability of Support Vector Machines. Neural Processing Letters, ((1)):43533, Feb. 2003.
[14] J. Hensman, N. Fusi, and N. D. Lawrence. Gaussian processes for Big data. In Proceedings of the Tweht Conference on Uncertainty in Artificial Intelligence, UAI' 13, pages 282-290, Arlington, Virginia, USA, Aug. 2013. AUAI Press.
[15] Hensman, Matthews, and 7. Ghahramani. Scalable Variational Gaussian Process Classifi- cation. In Artificial Intelligence and Statistics, pages 351-360, PMLR, Feb, 2015.
10

---

[16] J. Hensman, N. Durrande, and A. Solin. Variational Fourier features for Gaussian processes. The Journal of Machine Learning Research, 18():55537-5588 Jan. 2017.
[17] F. L. Hitchcock. The Expression of a Tensor or a Polyadic as a Sum of Products. Journal of Mathemalics and Physics, 6(1-4): 164.1,9,, 1927.
[18] Holtz, T. Rohwedder, and R. Schneider. The alternating linear scheme for tensor optimization in the tensor train format. SIAM J. Sci. Comput., 34(2)A683-A713, 2012.
[19] Izmailov, A. Novikov, and Kropotov. Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decomposition. In International Conference on Artificial Intelligence and Statistics, pages 726-735. PMLR, Mar. 2018.
[20] T. G. Kolda and B. W. Bader. Tensor Decompositions and Applications. SIAM Review, 51(3): 455-500, Aug. 2009.
[21] B. Kruskal. Three-way arrays: Rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra and its Applications, 18(2): 95-138, Jan. 1977.
[22] J. Lee, Y. Bahri, R. Novak, S. S. Schoenholz, J. Pennington, and J. Sohl-Dickstein Deep Neural Networks as Gaussian Processes. 11X0v:1711.00165 [cs, stat], Mar. 2018.
[23] F. Liu, X. Huang, Y. Chen, and J. A. K. Suykens. Random features for kernel approximation: A survey on algorithms, theory, and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, PP, July 2021.
[24] Matlab. 9.10.0.1649659 (R2021a) Update 1. The MathWorks Inc., Natick, Massachussetts, 2021.
[25] M. Mutný and A. Krause. Efficient high dimensional Bayesian optimization with additivity and quadrature fourier features. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pages 9019-9030, Red Hook, NY, USA, Dec. 2018. Curran Associates Inc.
[26] R. Novak, L. Xiao, Y. Bahri, J. Lee, G. Yang, J. Hron, D. A. Abolafia, J. Pennington, and J. Sohl-dickstein. Bayesian deep convolutional networks with many channels are gaussian processes, In International Conference on Learning Representations, 2018.
[27] A. Novikov, D. Podoprikhin, A. Osokin, and D. P. Vetrov. Tensorizing neural networks. In C. Cortes, N. Lawrence, D. Lec, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[28] A. Novikov, M. Trofimov, and I. Oseledets. Exponential Machines. 1605v:1605.0377 [cs, stat], Dec. 2017.
[29] I. V. Oseledets. Tensor-Train Decomposition. SIAM Journal Scientific Computing, 33(5):
2295-2317, Jan. 2011.
[30] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and É. Duchesnay. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, (2885):22552833) 2011.
[31] A. Rahimi and Recht. Random features for large-scale kernel machines. In Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS' 07, pages 1177-1184, Red Hook, NY, USA, Dec. 2007. Curran Associates Inc.
[32] C. E. Rasmussen and H. Nickisch. Gaussian Processes for Machine Learning (GPML) Toolbox. Journal of Machine Learning Research, 111100:3011-3015 2010.
[33] C. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. Adaptive Computation and Machine Learning, MIT Press, Cambridge, Mass, 2006.

---

[34] T. Rohwedder and A. Uschmajew. On local convergence of alternating schemes for optimization of convex problems in the tensor train format. SIAM Journal on Numerical Analysis, 51(2): 1134-1162, 2013.
[35] W. Rudin. Fourier Analysis on Groups. Number 12 in Interscience Tracts in Pure and Applied Mathematics. Interscience Publishers, New York, 1962.
[36] F. Shustin and H. Avron. Gauss-Legendre Features for Gaussian Process Regression. 1rXiv:2101.01137 [cs, math], Jan. 2021.
[37] N. D. Sidiropoulos and R. Bro. On the uniqueness of multilinear decomposition of N-way arrays. Journal of Chemometrics, 14(3):229-239, 2000.
[38] N. D. Sidiropoulos, L. De Lathauwer, X. Fu, K. Huang, E. E. Papalexakis. and C. Faloutsos. Tensor Decomposition for Signal Processing and Machine Learning. IEFE Transactions on Signal Processing, 65(13):3551-33 333355521.,18.111 July 2017.
[39] A. Solin and S. Särkkä. Hilbert space methods for reduced-rant Gaussian process regression. Statistics and Computing, 30(2):419 Mar. 2020.
[40] E. M. Stoudenmire and D. J. Schwab. Supervised learning with tensor networks. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, pages 4806-4814 4, Red Hook, NY, USA, Dec. 2016. Curran Associates Inc.
[41] J. Suykens and J. Vandewalle. Least Squares Support Vector Machine Classifiers. Neural Processing Letters, 9(3):293-300 300, June 1999.
[42] A. Suykens, T. Van Gestel, De Brabanter, B. De Moor, and Vandewalle. Least Squares Support Vector Machines. World Scientific, Nov. 2002.
[43] A. Tjandra, S. Sakti, and S. Nakamura. Compressing recurrent neural network with tensor train. In 2017 International Joint Conference on Neural Networks (IJCNN), pages 4451-4458, May 2017.
[44] L. R. Tucker. Some mathematical notes three-mode factor analysis. Psychometrika, 31(3): 279-311, Sept. 1966.
[45] S. Wahls, V. Koivunen, H. V. Poor, and M. Verhaegen. Learning multidimensional Fourier series with tensor trains. In 2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 394-398, Dec. 2014.
[46] C. Williams and M. Seeger. Using the nyström method to speed up kernel machines. In Proceedings of the 14th International Conference on Neural Information Processing Systems, 01, pages 682-688. MIT Press, 2001.
[47] T. Yang, Y.-f. Li, M. Mahdavi, R. Jin, and Z. Zhou. Nyström method vs random fourier features: theoretical and empirical comparison. In Pereira, C. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[48] Y. Yang, D. Krompass, and V. Tresp. Tensor-Traee Recurrent Neural Networks for Video Classification. International Conference on Machine Learning, pages 3891-3900. PMLR, July 2017.
12


Reviews:
[{"review_id": "jz3C1qQN2r2", "reviewer": "Reviewer_pffh", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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?\n\nFinally, 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations were addressed but there was no mention of societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "cY5Ia0rtOe", "reviewer": "Reviewer_kD5f", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n* 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. \n* It seems that the defining equation of G^(d) should be G^d?\n\n\n================================================\nAfter 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "SytYvaI3Q7a", "reviewer": "Reviewer_LNEF", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is written very clearly, and the organization is neat, so it's very easy to follow. \n\nIn 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.\n\nRegarding 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.\n\nQuestions:\n\n1) 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.\n\n2) How does RFF compare with T-KRR in terms of exact running time? What is the optimization algorithm for RFF?\n\n3) 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.\n\n4) 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,\n\nData-dependent compression of random features for large-scale kernel approximation, AISTATS 2019\n\nLow-Precision Random Fourier Features for Memory-constrained Kernel Approximation, AISTATS 2019\n\nQuantization Algorithms for Random Fourier Features, ICML 2021\n\nIn 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "H28y_LAPo_n", "reviewer": "Reviewer_h3fL", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the fundamental idea is solid but I have the following questions about the implementation of the model\n\n1.) 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?\n2.) 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\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed their limitations. I do not see any potential negative societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)