Hybrid Random Features

By Krzysztof Marcin Choromanski, Haoxian Chen, Han Lin, Yuanzhe Ma, Arijit Sehanobish, Deepali Jain, Michael S. Ryoo, Jacob Varley, Andy Zeng, Valerii Likhosherstov and 3 more. 2021

27 citations recorded by the source corpus.

We propose a new class of random feature methods for linearizing softmax and Gaussian kernels called hybrid random features (HRFs) that automatically adapt the quality of kernel estimation to provide most accurate approximation in the defined regions of interest. Special instantiations of HRFs lead to well-known methods such as trigonometric (Rahimi and Recht, 2007) or (recently introduced in the context of linear-attention Transformers) positive random features (Choromanski et al., 2021). By generalizing Bochner's Theorem for softmax/Gaussian kernels and leveraging random features for compositional kernels, the HRF-mechanism provides strong theoretical guarantees - unbiased approximation and strictly smaller worst-case relative errors than its counterparts. We conduct exhaustive empirical evaluation of HRF ranging from pointwise kernel estimation experiments, through tests on data admitting clustering structure to benchmarking implicit-attention Transformers (also for downstream Robotics applications), demonstrating its quality in a wide spectrum of machine learning problems.

Subfields: Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Representation & Self-Supervised Learning

Citations in the corpus

Socratic Models: Composing Zero-Shot Multimodal Reasoning with Language (2022, methodology): “In the scenario of strict mem- ory requirements, we propose to leverage recently introduced techniques on linear attention (Choromanski et al. 2021b) combined with modern continuous associative memory (MCAM) models (Ramsauer et al. 2021).”