Quadrature-based features for kernel approximation
We consider the problem of improving kernel approximation via randomized feature maps. These maps arise as Monte Carlo approximation to integral representations of kernel functions and scale up kernel methods for larger datasets. Based on an efficient numerical integration technique, we propose a unifying approach that reinterprets the previous random features methods and extends to better estimates of the kernel approximation. We derive the convergence behaviour and conduct an extensive empirical study that supports our hypothesis 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?