Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The authors offer a novel version of the random feature map approach to approximately solving large-scale kernel problems: each feature map evaluates the "fourier feature" corresponding to the kernel at a set of randomly sampled quadrature points. This gives an unbiased kernel estimator; they prove a bound its variance and provide experiment evidence that for Gaussian and arc-cos kernels, their suggested qaudrature rule outperforms previous random feature maps in terms of kernel approximation error and in terms of downstream classification and regression tasks. The idea is straightforward, the analysis seems correct, and the experiments suggest the method has superior accuracy compared to prior RFMs for shift-invariant kernels. The work is original, but I would say incremental, and the relevant literature is cited.

The method seems to give significantly lower kernel approximation errors, but the significance of the performance difference in downstream ML tasks is unclear --- the confidence intervals of the different methods overlap sufficiently to make it questionable whether the relative complexity of this method is worth the effort. Since good performance on downstream tasks is the crucial feature that we want RFMs to have, it is not clear that this method represents a true improvement over the state-of-the-art. The exposition of the quadrature method is difficult to follow, and the connection between the quadrature rules and the random feature map is never explicitly stated: e.g. equation 6 says how the kernel function is approximated as an integral, but does not give the feature map that an ML practitioner should use to get that approximate integral.

It would have been a good idea to include figures showing the time-accuracy tradeoff of the various methods, which is more important in large-scale ML applications than the kernel approximation error. It is not clear that the method is *not* more expensive in practice than previous methods (Table 1 gives superior asymptotic runtimes, but I would like to see actual run times, as evaluating the feature maps sound relatively complicated compared to other RFMs). On a related note, I would also like to have seen this method applied to kernels where the probability density in the Bochner integral was not the Gaussian density (e.g., the Laplacian kernel): the authors suggested that their method works there as well when one uses a Gaussian approximation of the density (which is not clear to me),  --- and it may be the case that sampling from their quadrature distribution is faster than sampling from the original non-Gaussian density.
review_title: incremental development in random feature map approach

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper shows that techniques due to Genz & Monahan (1998) can be used to achieve low kernel approximation error under the framework of random fourier feature.

Pros

1. It is new to apply quadrature rules to improve kernel approximation. The only other work I found is
Gaussian Quadrature for Kernel Features NIPS 2017. 
The work is pretty recent so the author might not know it when submitting the paper. But in either case, it will be good to discuss the connections.

2. The proposed method is shown to outperform a few baselines empirically.

Cons

1. I don’t find the theoretical analysis to be very useful. In particular, the theorem shows that the kernel approximation error is O(1/D), which is the same as the original RFF paper. Unless the paper can provide a better characterization of the constants (like the ORF paper), it does not provide much insight in the proposed method. Unlike deep neural networks, since RFF is such a simple model, I think providing precise theoretical understanding is crucial. 

2. Approximating an integral is a well-studied topic. I do not find a good discussion on all the possible methods. Why is Genz & Monahan 1998 better than other alternatives such as Monte-Carlo, QMC etc? One argument seems to be “for kernels with specific specific integrand one can improve on its properties”. But this trick can be used for Monte-Carlo as well. And I do not see benefit of this trick in the curves.

3. When choosing the orthogonal matrix, I think one obvious choice is to sample a matrix from the Stiefel manifold (the Q matrix of a random Gaussian). This baseline should be added in additional to H and B.

4. A wall-time experiment is needed to justify the speedup.

Minor comments:
“For kennels with q(w) other than Gaussian… obtain very accurate results with little effort by using Gaussian approximation of q(w)”. What is the citation of this in the kernel approximation context?
review_title: Interesting method with good empirical result, but not enough insights on why

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper proposes to improve the kernel approximation of random features by using quadratures, in particular, stochastic spherical-radial rules. The quadrature rules have smaller variance given the same number of random features, and experiments show its reconstruction error and classification accuracies are better than existing algorithms.

It is an interesting paper, but it seems the authors are not aware of some existing works [1, 2] on quadrature for random features. Given these previous works, the contribution and novelty of the paper is limited.

[1] Francis Bach. On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions. JMLR, 2017.
[2] Tri Dao, Christopher De Sa, Christopher Ré. Gaussian Quadrature for Kernel Features. NIPS 2017
review_title: Interesting paper, but lacks novelty and comparison to existing work

Meta-review: This an interesting new contribution to construction of random features for approximating kernel functions. While the empirical results look promising, the reviewers have raised concerns about not having insights into why the approach is more effective;  the exposition of the quadrature method is difficult to follow; and the connection between the quadrature rules and the random feature map is never explicitly stated. Some comparisons are missing (e.g., QMC methods). As such the paper will benefit from a revision and is not ready for ICLR-2018 acceptance.
Decision: Reject