- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper provides a sharper concentration analysis of Fastfood for approximating Gaussian and other radial kernels. For the Gaussian kernel, it establishes an unbiased feature map with evaluation time and additive error with failure probability using frequencies. The bound removes the dependence on input distance present in earlier analyses and nearly matches the concentration of independent random Fourier features.
The main technical contribution combines randomized Hadamard flattening with a Brascamp–Lieb inequality to control dependencies between features. A spherical version of this argument, together with Schoenberg's representation, extends the result to continuous positive-definite normalized radial kernels. The paper also gives a lower bound establishing optimality up to logarithmic factors and an application to additive-error kernel density estimation. Validation is entirely theoretical; no new experiments are presented.
Critical strengths
-
A substantial improvement in the computational guarantees for an established method. The analysis combines near-linear feature evaluation with nearly subgaussian concentration, without dependence on the distance between the input points. This resolves a significant limitation of previous Fastfood guarantees and shows that its computational advantage can be obtained with only a logarithmic overhead in feature count relative to independent RFF. The accompanying lower bound and kernel-density-estimation application make the significance of this improvement concrete.
-
An effective proof technique with applicability beyond the Gaussian kernel. The Brascamp–Lieb argument controls dependent features through the geometry of their projection directions, avoiding the distance-dependent losses of earlier approaches. Its extension through spherical concentration and Schoenberg's representation gives the contribution broader scope, including exponential, rational-quadratic, and Matérn kernels. This is a meaningful methodological advance rather than merely a refinement of constants.
Critical weaknesses
The guarantees establish pointwise kernel approximation, while their implications for learning remain indirect. The main concentration result concerns each fixed input pair, and the principal application concerns additive-error estimation at a fixed query. The paper does not establish spectral approximation of a dataset's kernel matrix or downstream statistical guarantees that preserve the computational improvement. This limits the demonstrated reach of the result for learning applications, although it does not diminish the validity of the stated kernel-approximation contribution.
Mathematical Consistency and Rigor:
The main proofs appear sound on inspection. The issues identified below concern local inaccuracies and clarification of the computational model, rather than a demonstrated failure of the principal theorems.
1. Definition 4.1 omits assumptions needed to define the radial measure as a probability distribution.
On page 7, Definition 4.1 assumes that the kernel is shift-invariant and positive definite, but does not explicitly require normalization or continuity. It then treats the spectral measure as a probability measure and defines the radial measure as the distribution of for .
For a continuous positive-definite shift-invariant kernel, the spectral measure has total mass . It is therefore a probability measure only when . The range restriction does not imply this normalization; for example, the constant kernel satisfies that restriction.
2. The independence statement in the RFF background is incorrect as written.
On page 4, lines 201–204, the paper justifies Hoeffding concentration by saying that the coordinates of are i.i.d. This is false for the sine–cosine construction: and share the same frequency and are dependent. The sine and cosine coordinates also generally have different distributions.
The correct argument is that
and these summands are independent, identically distributed, and bounded in .
3. The stated evaluation complexity needs a convention for .
Theorems 1.1 and 1.2 allow but state evaluation time . Literally, this expression vanishes when , although producing the features still requires computation.
Questions for authors
-
Clarification of the optimality claim: The upper and lower bounds leave logarithmic gaps in their dependence on dimension, accuracy, and failure probability. Could you explicitly distinguish which dependencies are established as necessary from those introduced by the flattening and concentration arguments? In particular, is there evidence that the additional factor is intrinsic to this Fastfood construction?
-
Clarification of the computational lower bound: The proof of Theorem 1.3 combines an output-dimension lower bound with the assertion that evaluating the map requires reading all input coordinates. Could you specify the computational model and justify the term for randomized evaluation procedures, including whether the claimed bound concerns worst-case or expected running time?
2 comments
Thank you for the detailed responses and clarifications. These address my concerns, and I appreciate the proposed revisions. I maintain my original score of 3 (Weak acceptance).
Thank you for your helpful and thorough review.
Our response to TSbv shows that our results also yield uniform approximation guarantees, which are more relevant for learning settings where queries are adaptive. Spectral approximation remains an intriguing extension to future work. Our response to Hhha demonstrates that our techniques are quite general and robust and may be more broadly applicable. We believe they could be applicable to spectral kernel matrix approximation, although this remains to be explored in future work.
Thank you for the careful reading and comments. We hope it is evident that these are not substantive errors but rather the result of common colloquial writing and do not bear on the mathematical correctness of our paper. Nonetheless, we will revise the text accordingly. Specifically:
We required continuity and normalization in the definition of the spectral measure (line 186), and since Definition 4.1 assumes the existence of a spectral measure, we deemed them implied. However, we agree this may be confusing, and we will add them explicitly to Definition 4.1.
Correct, we meant that we sample summands where each summand represents a pair of sine-cosine coordinates with the same frequency, rather than single coordinates, as you point out.
Correct: the statements are trivial for d=1, and therefore we implicitly assumed d>1 in the theorems; we will write this explicitly.
Correct, we only claim that the lower bound is nearly optimal (line 122) up to log factors (line 131). Specifically, our lower bound shows that the term O(ε−2log(1/δ)) is necessary in the regime δ≤ε4. We have no evidence that the additional log(d/eta) factor is intrinsic to Fastfood. Tightening the log factors between the upper and lower bounds, and perhaps gauging the precise asymptotic bound, is an interesting topic for future work.
Theorem 1.3 gives a lower bound on the expected time to evaluate the map on worst-case inputs, in the standard unit-cost RAM model with dense input and explicit output. The expectation is over the random choice of the map and any randomness used during evaluation. The input x∈Rd is assumed to be given as a dense array, the evaluator may read coordinates adaptively, and it returns F(x)∈Rm written explicitly. Each coordinate read or written costs one unit.