NIPS 2018
Sun Dec 2nd through Sat the 8th, 2018 at Palais des Congrès de Montréal
Paper ID: 5500 Quadrature-based features for kernel approximation

### Reviewer 1

Post rebuttal: Thanks for the feedback. Summary of the paper: This paper proposes a novel class of random feature maps that subsumes the standard random Fourier features by Rahimi and orthogonal random features by [16]. The approach is based on spherical radial quadrature rules by Genz and Monahan [18]. Some theoretical guarantees are provided, and impressive experimental results are reported. ~~~ Quality ~~~ Strength: Extensive experimental results have been conducted, showing impressive empirical performance of the proposed approach. Also some theoretical guarantees are provided. Weakness: Theoretical error-bounds seem not very tight, and it is theoretically not very clear why the proposed works well; see the detailed comments below. I guess this would be because of the property of spherical radial rules being exact for polynomials up to a certain order. ~~~ Clarity ~~~ Strength: This paper is basically written well, and connections to the existing approaches are discussed concisely. Weakness: It would be possible to explain theoretical properties of spherical quadrature rules more explicitly, and this would help understand the behaviour of the proposed method. ~~~ Originality ~~~ Strength: I believe the use of spherical radial quadrature is really novel. Weakness: It seems that theoretical arguments basically follow those of [32]. ~~~ Significance ~~~ Strength: The proposed framework subsumes the standard random Fourier features by Rahimi and orthogonal random features by [16]; this is very nice, as it provides a unifying framework for existing approaches to random feature maps. Also the experimental results are impressive (in particular for approximating kernel matrices). The proposed framework would indicate a new research direction, encouraging the use of classical quadrature rules in the numerical analysis literature. %%% Detailed comments %%% ++ On the properties of spherical radial rules ++ You mentioned that the weights of a spherical radial rule [18] are derived so that they are exact for polynomials up to a certain order and unbiased for other functions. We have the following comments: - Given that [18] is a rather minor work (guessing from the number of citations; I was not aware of this work), it would be beneficial for the reader to state this property in the form of Theorem or something similar, at least in Appendix. From the current presentation it is not very clear what exactly the this property means mathematically. - Are spherical radial rules related to Gauss-Hermite quadrature, which are (deterministic) quadrature rules that are exact for polynomials up to a certain order and deals with Gaussian measures? ++ Line 109 and Footnote 3 ++ From what you mentioned that with some probability $a_0$ can be an imaginary number. What should one do if this is the case? ++ Proposition 3.1 ++ The upper bound is polynomial in $\epsilon$, which seems quite loose, compared to the exponential bound derived in the following paper: Optimal rates for random Fourier features B. K. Sriperumbudur and Z. Szabo Neural Information Processing Systems, 2015 ++ Proposition 3.2 ++ What is $\lambda$? Where is this defined?