# Random Features for Compositional Kernels

arXiv: https://arxiv.org/abs/1703.07872 · HTML: https://mlsanity.com/paper/1703.07872/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2017.

## Built on by (most cited first, 5 of 5)

- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Space](https://mlsanity.com/paper/2307.01177/) (2023)
- [Unlocking Pixels for Reinforcement Learning via Implicit Attention](https://mlsanity.com/paper/2102.04353/) (2021)
- [Multi-layer random features and the approximation power of neural networks](https://mlsanity.com/paper/2404.17461/) (2024)
- [Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization](https://mlsanity.com/paper/2606.11255/) (2026)

## Abstract (arXiv)

We describe and analyze a simple random feature scheme (RFS) from prescribed compositional kernels. The compositional kernels we use are inspired by the structure of convolutional neural networks and kernels. The resulting scheme yields sparse and efficiently computable features. Each random feature can be represented as an algebraic expression over a small number of (random) paths in a composition tree. Thus, compositional random features can be stored compactly. The discrete nature of the generation process enables de-duplication of repeated features, further compacting the representation and increasing the diversity of the embeddings. Our approach complements and can be combined with previous random feature schemes.