Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper makes two methodological contributions: a new approach to constructing randomized approximations to Gaussian and softmax kernels and a proposal to combine multiple randomized approximations to create “hybrid random features” (HRFs). The idea of the hybrid random features is to activate a particular approximation for pairs (x,y) for which that approximation is accurate. Some theoretical results support the use of a particular instance of HRFs that combine trigonometric and positive random features, showing the hybrid has lower mean squared error than either type of random feature. Experiments are presented to verify the benefits of HRFs on a variety of tasks, with a focus on their use in neural network settings. 
main_review: The main idea of the paper – to try to get the “best of both worlds” when different types of random features are useful in different regimes – is very nice. The theoretical results show that HRFs can be superior to either of the “base” random features used. The experiments in section 4.1 on pointwise kernel estimation also nicely support this narrative. The other experiments suggest at least some benefits, with perhaps the strongest results being for the speech model example in section 4.4. However, there are a few serious issues that need to be addressed.

## Writing and presentation

This was a very confusing paper to read.

### Notation 

There is an incredible amount of very dense notation, much of which it should be possible to drastically simplify with a little thoughtful effort. For example, there are many cases where to approximate a function $f(x, y)$, a random feature representation of the form $\mathbb E[\psi^{(1)}(x)^\top\psi^{(2)}(y)]$ is used. But rather than, as I have done, reuse the same symbol for both and distinguish the random functions with an index, different symbols are used (e.g., $\alpha$ and $\beta$). This forces the author(s) to write about $\phi$, which can be either $\alpha$ or $\beta$. Thus, whereas a single symbol plus an index would do, the reader instead has to juggle three symbols. For a particularly egregious example of this, see the sentence that begins before eq. (15). 

Another reason for the difficult notation is the author(s) try to make the methods presented as general as possible, which puts a heavy burden on the reader. However, often this generality is now actually used very much. For example:

* Nearly all of the focus is on “bipolar” HRFs with just $p + 1 = 2$ “base” random features. However, the general case is covered, which requires, e.g., to define $\lambda^k$ for $k=1,\dots,p$, whereas for the most part only a single $\lambda$ function is needed. 
* $\lambda^k$ can take values in $\mathbb R$, but in all examples it is constrained to [0,1] 


### Paper structure 

The paper needs to be restructured on both local and global scales. At the local scale, definitions and semantic explanations often come long after something is used. For example, what is the purpose of $\lambda^k$? It is unclear until a few pages after it is defined. Or, the definitions of $\otimes$ and $\prod^\star$ in Lemma 2.4 are at the very end, leaving the reader unsure what any of the four displayed equations that come before actually mean. Sometimes objects are never defined (e.g., MSE and $\mathcal P(\mathbb R^d)$) or only long after they are first used (e.g., $\boldsymbol i$ is finally defined right before Lemma 2.4). Also, global definitions are put inside lemmas and theorems (e.g., Lemma 2.2). 

At the global scale, the main contribution of trading off whether the trig or positive random features are “active” is in the paragraph at the top of p. 5. If some version of this came, say, after section 2.1, followed by the material in section 3 (theoretical guarantees), the reader would have everything they need to understand all but the experiments in section 4.2, which in any case aren’t very interesting. 

### Use of colons

There is liberal use of colons in the middle of sentences. Please remove these. 

## Scope of contribution

There are a number of places where I don’t think the paper properly describes the scope of its contribution. 

1. Abstract: “By generalizing Bochner’s Theorem for softmax/Gaussian kernels and leveraging random features for compositional kernels, the HRF- mechanism provides strong theoretical guarantees”. Given the generality of Bochner’s theorem, this sounds like a major contribution and an important part of what makes HRFs work. However, I believe the generalization of Bochner’s theorem is Lemma 2.3, which seems to only be used for the HRFs for clustering structure; these make only a brief appearance in the paper: there is no theory for them and they earn a small synthetic experiment (Section 4.2), but there practical utility is never shown. Thus, Lemma 2.3 appears to have nothing to do with the “strong theoretical guarantees” developed in section 3, which are only for the bipolar kernel with trig and positive random features. 

2. Related work at the end of section 1: “rather than focusing on improving [the] sampling mechanism for a given approximation algorithm, [HRFs] provide a completely new algorithm.” I find this claim to be misleading. HRFs provide a way to combine existing random feature algorithms. 

3. Generality. As I’ve mentioned above, the paper presents HRFs in great generality, but very little of that generality is actually used in a consequential way. It may be that this generality is quite useful! I really like the idea, and could imagine othe HRFs will be developed or the cluster-based HRF will find use cases. But the theory and experiments given in the paper don’t support such grand claims about “strong theoretical guarantees” for the “HRF mechanism.” On the contrary, the paper shows that one particular instantiation of the HRF mechanism has smaller relative MSE than the underlying components. 

## Experiments

Section 4.1: This was a nice clean demonstration of the theory. I think the red dotted lines in Fig. 2 are for zero. Please clarify this in the caption. 

Section 4.2: As mentioned above, unless this experiment is supported by some practical application, it should be moved to the appendix as a “proof-of-concept”.

Section 4.3: It seems like none of the random feature approaches give very good approximations (Fig. 4). There are no error bars in Fig. 5, so I’m unsure if the differences are meaningful. Moreover, I’m not convinced the ordering would remain the same if the experiment were run for, say, 10 more epochs. 

Section 4.4: This is a potentially strong experiment. However, the statement that “ ≥ 0.2% are considered to be statistically significant for that task” makes no sense. The differences are either statistically significant or not, given a particular test and choice of test size. 

Section 4.5: The results here are promising. A 3x improvement in FLOPS certainly is something. But the lower variation in reward, particular in the step-stone locomotion task, is also noteworthy.  

## Recommendations 

1. Simplify the notation 

2. Focus only on bipolar random features in the main text and move the other types and the general definitions  (e.g., material around eq. (14), Gaussian lambda coefficients, adaptation data admitting clustering structure, section 4.2) to the SM or to a separate section that can be skipped on first reading. 

3. Restructure the paper so motivation and semantic interpretations come before definitions

4. Clarify scope and contributions. 

5. Strengthen experiments by including error bars for all performance metrics and running the experiments in section 4.3 for at least 10 more epochs, or until the perplexities stabilize. 

summary_of_the_review: A potentially useful method with a nice idea and some promising results. But the paper structure and writing need to be improved, the scope and contributions clarified, and the experiments tightened up.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a new type of estimators of softmax and gaussian kernels based on random features, consisting of compositions of base estimators such as the trigonometric and positive random features. The composition is a linear function, such that the new estimator (called hybrid) is unbiased, whose coefficients (called $\lambda$-coefficients) are independent of the base estimators and are also kernel functions (to better adapt the estimator to the compared data) hence also need to be linearized for scalability. 

Three different instantiations of the hybrid estimator are proposed using base estimators of the form of the defined complex exponential one (an asymmetric generalization of random feature estimators). In particular the angular one (i.e. $\lambda$-coefficients depending on the angle between the pair of data points) is shown to have low variance and low maximal relative error for small and large kernel values.
HRF has also a lower computational complexity in the total number of random features w.r.t. non compositional estimators.

Experiments are carried out on multiple applications, first to verify the approximation capability of the hybrid estimator w.r.t true kernel, and trigonometric and positive estimators in simple settings, then to show the improvement (either in quality scores or computational) of using the proposed estimator in models requiring the use of softmax at scale.
main_review: **The contributions of the paper are original and very well motivated**, as they aim at providing a scalable and unbiased estimator of the widely used softmax and gaussian kernels which also has low variance.
Namely, the principal contributions are:
1. Hybrid Random Features as composition of base estimators, unbiased, that adapt to data points and can be linearized;
2. Generic form of base estimators, named complex exponential estimator;
3. Three instantiations of HRF that provide low variance estimators.

The proposed HRF can benefit the ICLR community at large and in particular the fervent research around transformers.
The theoretical results seem sound, however I haven't checked in details the proofs of Lemma 2.4, Lemma 3.2, Lemma 3.4 and Theorem 3.4.

**The paper itself is hard to read** in particular because intuitions and justifications for the derivations and definitions are rarely provided.
I have few suggestions for improving its presentation:

1. The ordering of the exposition of the contributions does not help the reader understand the train-of-thoughts and intuitions. I'd suggest to first introduce HRF (Section 2.3) to then show how base estimators can be chosen (Section 2.2) and how $\lambda$-coefficients can be defined accordingly.
Moreover, it would help the presentation of the complex exponential estimators to start from defining the new feature map $\Phi_M^m(u)$'s components $\exp(wMu)$ to clarify first the goal of defining a generalized form of random features that can be specialized to well known ones depending on $M$. In the current presentation the new choice of $z$ comes out of the blue.

2. When presenting HRF, the choice of having kernels as $\lambda$-coefficients and not e.g. constants is not motivated and not sufficiently highlighted. I understood only later, when examples of instantiations are provided, the interest of this choice which is to reduce the variance of the estimator. Still it is not clear to me why they need to be shifted (with the offset parameter $a_k$) and whether in practice this choice provides better results than fixing these coefficients to constants, e.g. learned from a subset of data. 

3. Maths and notation could be simplified. Namely, Section 2.3 could be written for $p=1$ (2 base estimators), and the general form for $p > 1$ could be reported in the appendix.

4. When presenting the theoretical results, it should be made more explicit which results are new and which are not. This is not clear especially for Lemma 2.3. A reference for Definition 2.1 should be provided and in general pointers to the proofs in the appendix should be added. 

5. The experimental section of the main text is too packed. It is valuable to have carried out the empirical analysis on multiple tasks and contexts, but reporting them all comes at the cost of losing clarity, as experiments and results are not thoroughly described and commented.  
More precisely:
(a) Figure 1: colorbar is missing and it is not clear why the light blue is both for low and high MSE values.
(b) Section 4.1: What study is referred to as complete ablations? Why the results for gaussian $\lambda$-coefficients are not reported? What is the number of random features for Angular Hybrid?
(c) Section 4.2: Why is $s$ a vector of size 4 when $l(A)$ should be a scalar?
(d) Section 4.3: Which task is performed here and what is it meant by negative classes? Are the differences between methods for the three metrics significant? What is the perplexity score? A note should be added on why negative fractions are not reported for FAVOR+.
(e) Section 4.5: Why is training with state-of-the-art estimators unstable on this task (loss going to Nan for particular numbers of random features)? What are the "drastic compute improvements" given that score differences between methods are not significant for the same number of iterations?
I'd suggest to select the most important experiments and present them thoroughly in the main text, while reporting the rest in the appendix. 

Minor:
1. MSE in this context should be defined in the introduction.
2. Gaussian kernel's inputs are missing in Eq. (1).
summary_of_the_review: The paper makes strong contributions with potential high impact, however its presentation is over-complicated and lacks clarity. I suggest to improve on this point and I am willing to increase my score accordingly.

## UPDATE AFTER REBUTTAL
The presentation of the paper has improved and, while some notation are still hard to read, I believe that the paper's contributions are now more accessible. I am hence increasing my score to 8. I am looking forward to seeing how the paper will be presented in video lectures.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Author rebuttal checked. I increase my score to 8. BTW, I strongly suggest the authors polish this paper as the current version appears uneasy to follow, especifically for researchers unfamiliar with RFF.
=============================================================
This paper proposes a hybrid random features that combines the classical trigonometric and positive random features, which aims to achieve good approximation performance for softmax kernel with both small and large values. This framework is also applicable to Gaussian kernels. Numerical experiments on softmax kernel approximation in linear attention and robotics are conducted to support their algorithm and theory.
main_review: Pros:

1, The motivation of this work is clear: current random features based algorithms are difficult to approximate softmax kernels with very small/large values. I agree with the authors on this issue.

2, the algorithm to approximate softmax kernel in Sec. 2.3.1 can be regarded as a combination of SM^{++} and SM^{trig}, with an extra cosine similarity function.
This function is in essence close to the zero-order arc-cosine kernel [Cho and Saul, 2009], and thus is actually approximated by the standard random features with the Hesivide activiation function. The algorithm enjoys theoretical guarantees on smaller worst-case relative errors.

3, Experiments on various applications are good to support their findings.

Cons:

1, Personally, this paper is not easy to follow even though I’m quite familiar with random features. For example, I understand the first part in Sec. 2.3, e.g., Eq. (14), (15) till reading Sec. 2.3.1; The notation SM^{hyb}_{m,n}(x,y) is not defined until Lemma 2.4; Some notations are unclear. I suggest the author carefully polish this paper.

2, the relationship between Sec 2.2 and the algorithm in Sec. 2.3 is not clear to me. The authors attempt to unify trigonometric and positive random features under a same framework, i.e., SM^{cexp}. However, the proposed algorithm in Sec. 2.3 to approximate softmax kernel is the exact combination of them. The complex exponential estimator appears unused for Gaussian/softmax kernel approximation. More importantly, this estimator is asymmetric, which appears strange. This only holds for two special cases (symmetric due to A=(A^T)^{-1}) by A:= iI_d or I_d. This estimator appears invalid/asymmetric for general case. In fact, the asymmetric property destroyed the foundation of kernel associated with RKHS. In this case, this estimator (the approximated kernel) under a general matrix A is not well-defined in kernel methods.

3, In theory, Theorem 3.1/3.5 is not clear to show that whether SM^{anghyb} achieves variance reduction or smaller MSE when compared to SM^{trig} and SM^{++}. Refer to a survey with discussion on the variance reduction: 

[S1] Liu, F., Huang, X., Chen, Y., & Suykens, J. A.K. (2020). Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond. TPAMI 2021.

4, it’s good to see many experiments but evaluation on kernel approximation error is needed. Experimental results in Figure 3 is not enough. In fact, kernel approximation error (as well as unbiasedness) is quite important in random features based algorithms. To validate the reduction on approximation error, it would be better to compare the proposed algorithms with SM^{trig} and SM^{++} as well as other representative algorithms including ORF and QMC on typical datasets.
(ORF and QMC can be also used for softmax/Gaussian kernel approximation. The proposed algorithm might be inferior to ORF and QMC due to the standard sampling strategies. It's ok for me but at least it can beat SM^{trig} and SM^{++} on typical datasets.)

Besides, regarding to the experiments on Transformers for language modelling, the following refs is missing.

[S2] Peng, H., Pappas, N., Yogatama, D., Schwartz, R., Smith, N., & Kong, L. Random Feature Attention. ICLR2021.

summary_of_the_review: In sum, this paper provides a novel random features algorithm with theoretical guarantees and has good applications. Nevertheless, some parts on algorithm and experiments are unclear, which would devalue this paper. I would like to see the response from the authors
review_title: null

Meta-review: Kernel methods are among the most flexible and powerful approaches of our times. Random features (RF) provide a recent mechanism to also make them scalable due to the associated finite (and often small)-dimensional approximate feature map (in the paper referred to as linearization). The focus of the submission is the linearization of the softmax kernel (defined in (1)) while making sure that the obtained RF approximation is accurate simultaneously for the small and the large kernel values. The authors present a hybrid random feature (HRF, defined in (8)) construction parameterized by base estimators and weights, and show that specific choice of these parameters is capable of implementing the goal. Some of the HRF estimators are also accompanied by theoretical guarantees (Section 3). Their numerical efficiency is illustrated (Section 4) on synthetic examples and in the context of natural language and speech modelling, and in robotics.

Scaling up kernel methods is a fundamental task of machine learning. The authors present a nice and valuable construction in this direction which can be of both theoretical and practical interest to the community.

The submission would benefit from implementing the remarks of the reviewers to improve its clarity.
Decision: Accept (Poster)