Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the relative error of kernel distances when applying the Random Fourier Features (RFF) to the shift-invariant kernels. While a prior work studied only the Gaussian kernel, this work generalizes the prior results to more general shift-invariant kernels. In particular, the authors show that poly(eps*log(n)) features are needed to guarantee the eps-relative errors for all the n data points. They also study a lower bound on the number of features for the Laplace kernel and show that it can be unbounded when an input has a huge magnitude-resolution ratio. In addition, they show that the RFF takes a better bound on the feature dimension on the k-means clustering compared to the Nystrom method. Finally, they provide an alternative embedding for the Laplacian kernel that requires a time in poly-log of the magnitude-resolution ratio. Experimental results evaluating the relative kernel distance under synthetic datasets are provided.

strength_and_weaknesses: Strength:

- This work extends a prior result on the Gaussian kernel to general shift-invariant kernel distances. They also study for the Laplacian kernel the bound of the number of features can be unbounded.
- The authors characterize that the kernel distance guarantee can be used for bounding the k-means clustering.
- They propose an alternative embedding for the Laplacian kernel beyond the RFF. As a result, it requires the number of features poly-log in the magnitude-resolution ratio.


Weakness:

- This paper basically improves the work of (Chen and Phillps, 2017), by generalizing the results to general shift-invariant kernels. However, importantly, the proposed result is worse than that of (Chen and Phillps, 2017), which only focuses on the Gaussian kernel. This makes the contributions weak. 
- The results of the upper bound and lower bound have a different notion, i.e., the magnitude-resolution ratio only appears in the lower bound. This makes it hard to compare those bounds. Can the upper bound involve in this ratio?
- Experiments only show the relative errors on the synthetic datasets. Since the RFF has been used in many practical applications, I think more experiments should be addressed. For example, showing the k-means clustering results and comparing the Nystrom method under real-world datasets would be nice.

clarity,_quality,_novelty_and_reproducibility: This paper is well-written, but needs some improvements, e.g., 
- Theorem 3.1 and 1.2 (which informally states Theorem 3.1) are basically the same. There is no reason to state the same theorem twice, which can be a waste of space.
- It would be better to use the parenthesis for citing references.
- It seems that the inequality in (2) is wrong.
- It would be good to have an independent section for the "Going beyond RFF" part.

The notion of the kernel distance is not new and many technical tools are borrowed from previous works (Chen and Phillps, 2017, Makarychev et al., 2019), hence I feel that the novelty is limited.


summary_of_the_review: This paper extends the prior work on the Gaussian kernel to general shift-invariant ones. But, their result is worse than the prior one and technical tools are also very similar. The writing quality needs to be improved and experimental results do not well support the benefit of the RFF on the kernel distance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies when Random Fourier Features (RFF) is able to create a Johnson-Lindenstrauss-like result for preserving the distances between the feature mappings of vectors given a shift-invariant kernel. Prior work emphasized different metrics, like getting an additive error guarantee on the pairwise distances, instead of more JL-like relative error guarantees. This paper really focuses on relative error guarantees.

Three core results are shown:
1. Suppose a kernel is both shift-invariant and analytic near zero (i.e. kernel is very smooth when it's two input are equal). Then, RFF give a relative error guarantee with a standard $O(\frac{1}{\varepsilon^2})$ sample complexity for fixed failure probability. It has a polylog dependence on failure probability where the additive error guarantees have just a log dependence, I believe.
1. Suppose a kernel is shift-invariant but not analytic near zero, like the Laplacian kernel $K(\vec x, \vec y) = e^{-\|\|\vec x - \vec y\|\|_1}$. Then, RFF for all such kernels cannot give relative error guarantees in general. If we assume the input vectors cannot be arbitrarily close to each other, then relative error guarantees become possible. Roughly speaking, two vectors being arbitrarily close to each other corresponds to approaching the non-analytic part of the shift-invariant kernel, which makes relative error estimation hard.
1. For the Laplacian kernel, a new algorithm is proposed that achieves relative error pairwise distance embedding, but not via RFF. This algorithm relies on embedding an $\ell_1$ space into a very very high dimensional $\ell_2$ space, runs RFF in some way on that $\ell_2$ space, and uses pseudo-random generators to make this computationally efficient.
strength_and_weaknesses: The paper has some really cool results in it. The first 5 pages were a really nice outline of new ideas in thinking about when and why RFF can embed pairwise distances within relative error. The first two major results, at I outlined them in the last box, are really cool and clean. Despite the issues the paper has, which I will discuss momentarily, I think those two results are strong enough to accept the paper.

There's a nice logical flow the the proofs in the paper, so my review will follow that flow.

## 1. RFF gets relative error for analytic shift-invariant kernels

The proof is a nice and intuitive statement, complete with a good sample complexity. The high level proof proceeds in three parts: use complex analysis tools to say that being analytic implies a good moment bound on each RFF feature; use being analytic to prove that the kernel has restricted strong convexity about 0; and combine these results in a fairly standard concentration argument. The burden of the proof lies in the first claim -- the moment bound -- which is proven in the appendix and I did not review in detail. Despite this, the message is pretty clean -- the proof clearly and strongly uses being analytic to create geometry that makes RFF give good accuracy near zero.

I suspect there is a very nice corollary to this relative error result, where an epsilon-net argument can give a whole subspace embedding via RFF; proving something akin to the results in [Avron et al, 2017] but with standard RFF sampling and with the regularization parameter set to zero. I'd like to know if the authors ever considered such a guarantee?

I don't know why the authors chose to prove the concentration argument underlying this result on page 6 of the paper. I checked the details, and I have a minor technical concern I'll ask later, but overall it doesn't feel very enlightening to read. Consider making a short paragraph describing the proof, pushing the details to the appendix, and recovering a bunch of space that could be used to describe the third result in the body of the paper (I'll elaborate what I mean by this later).

Either way, first result it cool and clear. All in favor.

## 2. RFF is incapable of relative error embedding for non-analytic kernels

The key proof under this claim is really simple, and just follows from the asymptotic Gaussianity of individual the RFF features (formalized via the Berry-Eissen theorem). The authors prove that all shift invariant kernels have failure probability that depends on the ratio of the standard deviation of an RFF feature to the mean value of an RFF feature, formally denoted by $s_k$ in Theorem 4.1 on page 7. When we allow two input vectors to get arbitrarily close to each other, this ratio is well controlled for analytic kernels, but may be arbitrarily bad for non-analytic kernels.

Somewhat frustratingly, in Remark 4.1 at the bottom of page 7, the authors intuitively argue why this ratio is bad for Laplacian kernels and good for analytic kernels, but do not include a formal proof. Their description makes it sound pretty easy to prove, but it really should be formalized in the appendix. A concern I have is about the hardness of _other_ non-analytic kernels. Without that proof in the appendix, it's not immediately clear to me how many other non-analytic kernels will suffer the same hardness condition. Can we state an condition on (e.g.) the Laurent coefficients of a kernel that implies RFF is incapable of giving relative error?

Either way, it's a pretty intuitive big picture, but is lacking detail in the formalization.

## 3. Pseudorandom generators and fancier ways to make JL-style guarantees for the Laplacian kernel

This result is not really described within the body of the paper. It's discussed for 5 paragraphs in the introduction ("Going beyond RFF" on page 3). But that's it. The rest is fully described in 4 pages of the appendix. I don't have spare time to review that unfortunately, so I actually have no idea how it really works or how correct it seems. 5 paragraphs of introduction ain't a lot. I'd say the proof on page 6 of the paper should be appendicized. Maybe even cut out the experiments entirely (though I realize other ICLR reviewers may not agree with this). Then the authors could fit the third contribution within the body of the paper.

I can't judge how correct it is, but it would be cool if it was correct, I guess?

## Smaller Notes and Judgements

Section 3.2 on page 7 is a short blurb about improved sample complexity for kernel clustering. The result is neat, I guess, but is not well contextualized within the world of prior work. They also call their metric an $\ell_p$-objective, where the norm really is $\|\|\cdot\|\|_2^p$, which would not usually be called an $\ell_p$ norm. Pick a new name for it, maybe call it an $\ell_2^p$-objective?

Similarly, I know that prior work on RFF like algorithms have cared about certain kinds of relative error guarantees, like in [Avron et al, 2017]. While these are cited in the paper, the results here are not well contrasted against the prior work. This is clear in Section 1.2, which is basically a block of citations without any discussion of similarity. Why does their notions of relative error subspace embedding not extend to the authors' setting? (Formally, make a subspace embedding via RFF or RFF-LS for a 2x2 kernel matrix, and see if that subspace embedding guarantee implies a relative error pairwise guarantee like what the authors are aiming for; I can clarify if this description isn't clear).

In the experiments, the authors use SVD as an algorithm to attempt to preserve pairwise distances. Why is this a benchmark? Do people really use low-rank approximation algorithms to preserve pairwise distances? This feels intuitively doomed to fail. Also, if you run an algorithm for 20 iterations, could you include measures of confidence intervals in the plot? I'm personally a fan of plotting the medians with 25th and 75th quantiles, but anything that gives a sense of typical variation would be nice.

Theorem 1.4 isn't clearly phrased. The theorem clearly creates a mapping $\pi$ which has dimension $D$ which does not depend on the precision $\frac{\Delta}{\rho}$, but the first sentence after the theorem clearly sets the dimension depends on $\log \frac\Delta\rho$.

## Summary

The paper has cool results, but is somewhat lacking in some parts of the presentation. The first results is clear and compelling. The second is compelling but a bit less clear, and the third result isn't clear at all since it's not in the body of the paper.

Nevertheless, the clear and compelling parts are absolutely strong enough to merit publication.
clarity,_quality,_novelty_and_reproducibility: The writing of the paper is overall clear and nice to read.

The reproducibility, for a theoretical paper, has some proofs that I'd like to see elaborated, but is overall in good condition.

I didn't review the contribution of the paper that's completely buried in the appendix.

The results are novel, though I'd like a better comparison against the prior work.

## Typos and small notes

1. Consider using a different typeface for vectors versus scalars. Not vital by any means, but I think it'd help legibility a bit.
1. [Proof of theorem 3.1, page 6, the line that starts "Assume $\delta \leq$"] I think the actual constants are mixed up here a bit. I think it's $t = 32 \log^2 (2D^2/\delta)$ and $k=\log(2D^2/\delta)$
1. [Proof of theorem 3.1, page 6, the line that starts "For simplicity denote"] Consider putting brackets in the subscript of the indicator function. I think that $1_{[|X_i| \geq t l]} tl$ reads better than $1_{|X_i| \geq t l} tl$. Also, consider using `\ell` instead of `l` in latex: $\ell$ instead of $l$.
1. [Proof of theorem 3.1, page 6, the line that starts "By Lemma 3.1 for every"] I got the rightmost probability being $(\frac 4l)^{-\sqrt{alpha}/8}$ instead of $4^{-\sqrt\alpha / 8}$. I could have messed up my algebra fwiw.
1. [Proof of theorem 3.1, page 6, the math immediately below "By Lemma 3.1 for every"] You should write out how this inequality on the right hand side appears. I assume it's some linear combination of indicator functions, but I didn't figure out how to recover this bound.
1. [Proof of theorem 3.1, page 6, the math immediately above "By out choice of $t$"] What is the rate of this integral? What happens to it? It seems to shrink in $t$, but how does that tradeoff with the $O(\frac{t\delta}{D^2})$ term next to it?
1. [Remark 4.1, bottom of page 7] At the start of the remark, $D = \Theta(...)$ has a mis-typed parenthesis
summary_of_the_review: ## Summary

The paper has cool results, but is somewhat lacking in some parts of the presentation. The first results is clear and compelling. The second is compelling but a bit less clear, and the third result isn't clear at all since it's not in the body of the paper.

Nevertheless, the clear and compelling parts are absolutely strong enough to merit publication.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies dimensionality reduction techniques for estimating the kernel distance up to a (1+eps)-factor. First, the paper shows one can sample the random Fourier features to preserve $\Vert\phi(x) - \phi(y)\Vert_2$, where $\phi$ is the feature map such that $\langle \phi(x),\phi(y)\rangle = K(x,y)$ for some shift-invariant and analytic kernel $K$ and then applies to kernel k-means clustering. Then the paper shows a lower bound on the target dimension, which depends on the ‘condition number’ of the point set. The earlier upper bound requires the kernel function to be analytic at the origin, which excludes the Laplacian kernel. To remedy for this, the paper uses the fact that an $\ell_1$ metric space can be embedded into a metric space of metric $\Vert x-y\Vert_2^2$, thus turning the dimensionality reduction for a Laplacian kernel into that for a Gaussian kernel, for which the earlier random Fourier feature sampling scheme applies. 
strength_and_weaknesses: Strengths: Giving dimensionality reduction results for distances induced by shift-invariant kernels, where the kernel is analytic or a Laplacian kernel. The idea is simple (which is good) and some parts of the proof are nontrivial.

Weaknesses: It is not entirely convincing that the method for the Laplacian kernel is a bigger framework for other kernels. The bound $\max\{\epsilon^{-1}\log^3(1/\delta), \epsilon^{-2}\log(1/\delta)\}$ looks less satisfying.
clarity,_quality,_novelty_and_reproducibility: The paper is mostly well-written in the sense that it describes the motivation and the ideas/techniques well. The overall quality looks good, though I do not have time to verify all the proofs. The main technical innovation is the upper bound in Lemma 3.1. The proof is kind of straightforward, though not trivial.

Comment on the problem background: It says that the feature map $\phi$ is from $\mathbb{R}^d$ to a general Hilbert space $H$, on the other hand the distance is defined to be the $\ell_2$ norm. Does this mean that the Hilbert space $H$ must be embeddable into $\ell_2$? It seems that the distance does not need to be $\ell_2$ norm, it just needs to be induced by the inner product on $H$. 

Minor points:
- Page 2, Line -5: it would be good to elaborate on "nearly matches"
- Page 3, Line 8: “Cauchy’s evaluation formula” -> “Cauchy’s integral formula for multiple-variable functions”
Line 3 below Theorem 3.1: i.i.d. sampled -> i.i.d. samples
- Fact 3.1, last bullet point: no need to state $\operatorname{dist}_{\phi}(x,y)^2$ as this can be inferred without difficulty from the first bullet point.
- Fact 3.1: need citation or a short proof. 
- Proof of Theorem 3.1, the series of inequalities in the middle of the page: the integral $\int_t^\infty 4^{-\sqrt{\alpha/8}} d\alpha$ can be calculated directly that $\int_t^\infty e^{-c\sqrt{\alpha}}d\alpha = \frac{2}{c^2}e^{-c\sqrt{t}}(1 + c\sqrt{t})$. What is written there is just a change of variable but then you still need an upper bound. 
- Proof of Theorem 3.1: “By our choice of $t$ and $\delta$, … $\leq \delta l$, denote $\sigma’^2$ …, so …” -> “By our choice of $t$ and $delta$, … $\leq \delta l$. Let $\sigma’^2$ …, then …”
- Proof of Theorem 3.1, last line: “combine it together” -> “combine them together”. It would be good to be explicit about what intermediate results are combined here.
- Theorem 4.1: please rephrase the theorem statement. “For every …, every …, denoting…, there exists…” do not read very well. It might be better to say “Suppose that …”
- Page 7, line 1 after the proof of Theorem 4.1: right hand -> right-hand
- Page 7, line -7:”$\geq\Omega(1)$” -> “$ = \Omega(1)$”
- Page 7, Line -2: insert a comma after $O(1)$
- Page 8: please use different line styles - colours cannot be distinguished when printed black and white.
- Proof of Lemma 3.1: I feel there may be some small mistakes or gaps in the proof. For instance, $g_k(x)/i!$ seems to be $g_i(x)/i!$? What happens for the terms of $i < 2k$? Why do they vanish? In particular I don't see why Lemma A.2 means that they'll vanish because there is no limiting process here? Perhaps it should be an inequality here that $g_k(x)$ is dominated by the remainder term. 
- Section E.1: Do NOT use $\ell_2^2$ as this typically means a two-dimensional $\ell_2$ space.

summary_of_the_review: This is a solid and neat paper. I do enjoy reading it and would recommend accepting it. But I am not sure if ICLR is the correct place. Theoretical conferences may be more suitable, such as AISTATS, ICALP, ESA, RANDOM, ...
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Though kernel methods are among the most powerful techniques of our times with a large number of successful applications, this flexibility can be restricted by their scalability. In this submission the authors focus on the well-known and popular acceleration scheme of (continuous bounded translation-invariant) kernels called random Fourier features (RFF). Particularly, they pursue the derivation of relative error guarantees for the kernel distance, as defined in the 1st displayed equation of page 2. The authors present both negative and positive results in this direction. They show that (i) for instance for the Laplacian kernel (Theorem 1.1 and Theorem 4.1) preserving small relative error using low dimension is not feasible, (ii) but for analytic kernels it is the case (Theorem 1.2 and Theorem 3.1), (iii) the latter result can also be propagated to kernel k-means (Theorem 1.3 and Theorem 3.2), and (iv) Laplacian kernels are amenable to efficient data-oblivious dimension reduction (Theorem 1.4 and Theorem E.1).

The importance of kernel methods is inevitable; analyzing scalable kernel techniques is of paramount interest to the machine learning community. The authors present valuable new results in this direction (with focus on the theoretical side) as it was assessed by the reviewers. As it was also pointed out by the reviewers, the manuscript would benefit from slight adjustments: removal of 'close-to-repetitive' statements, and using the resulting space to one of the main results (Theorem E.1) currently hidden in the supplement.
justification_for_why_not_higher_score:  
justification_for_why_not_lower_score:
Decision: Accept: poster