# SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2020.

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

- [TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm](https://mlsanity.com/paper/2202.07172/) (2022)

## Abstract (arXiv)

Sample- and computationally-efficient distribution estimation is a fundamental tenet in statistics and machine learning. We present SURF, an algorithm for approximating distributions by piecewise polynomials. SURF is: simple, replacing prior complex optimization techniques by straight-forward empirical probability approximation of each potential polynomial piece through simple empirical-probability interpolation, and using plain divide-and-conquer to merge the pieces; universal, as well-known polynomial-approximation results imply that it accurately approximates a large class of common distributions; robust to distribution mis-specification as for any degree d ≤ 8, it estimates any distribution to an ℓ1 distance < 3 times that of the nearest degree-d piecewise polynomial, improving known factor upper bounds of 3 for single polynomials and 15 for polynomials with arbitrarily many pieces; fast, using optimal sample complexity, running in near sample-linear time, and if given sorted samples it may be parallelized to run in sub-linear time. In experiments, SURF outperforms state-of-the art algorithms.