# The Mondrian Kernel

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2016.

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

- [GP-BART: a novel Bayesian additive regression trees approach using Gaussian processes](https://mlsanity.com/paper/2204.02112/) (2022)
- [Towards a Unified Framework for Uncertainty-aware Nonlinear Variable Selection with Theoretical Guarantees](https://mlsanity.com/paper/2204.07293/) (2022)
- [Gradient Boosting Performs Gaussian Process Inference](https://mlsanity.com/paper/2206.05608/) (2022)
- [BARK: A Fully Bayesian Tree Kernel for Black-box Optimization](https://mlsanity.com/paper/2503.05574/) (2025)
- [Autoencoding Random Forests](https://mlsanity.com/paper/2505.21441/) (2025)
- [TrIM: Transformed Iterative Mondrian Forests for Gradient-based Dimension Reduction and High-Dimensional Regression](https://mlsanity.com/paper/2407.09964/) (2024)
- [Bayesian Additive Distribution Regression](https://mlsanity.com/paper/2603.06462/) (2026)
- [Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation](https://mlsanity.com/paper/2610.05174/) (2026)
- [A Framework for an Assessment of the Kernel-target Alignment in Tree Ensemble Kernel Learning](https://mlsanity.com/paper/2108.08752/) (2021)
- [The Uniformly Rotated Mondrian Kernel](https://mlsanity.com/paper/2502.04323/) (2025)
- [Seeing the Forest for the Trees: The Gaussian Process Limit of BART](https://mlsanity.com/paper/2607.28844/) (2026)

## Abstract (arXiv)

We introduce the Mondrian kernel, a fast random feature approximation to the Laplace kernel. It is suitable for both batch and online learning, and admits a fast kernel-width-selection procedure as the random features can be re-used efficiently for all kernel widths. The features are constructed by sampling trees via a Mondrian process [Roy and Teh, 2009], and we highlight the connection to Mondrian forests [Lakshminarayanan et al., 2014], where trees are also sampled via a Mondrian process, but fit independently. This link provides a new insight into the relationship between kernel methods and random forests.