# TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 36 references that are in the map.
- First posted on arXiv 15 Feb 2022.

## Builds on (most cited first, 7 of 7)

- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [Sample-Optimal Density Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1506.00671/) (2015)
- [The Optimal Approximation Factor in Density Estimation](https://mlsanity.com/paper/1902.05876/) (2019)
- [Statistically Near-Optimal Hypothesis Selection](https://mlsanity.com/paper/2108.07880/) (2021)
- [Unified Sample-Optimal Property Estimation in Near-Linear Time](https://mlsanity.com/paper/1911.03105/) (2019)
- [Robust estimation algorithms don't need to know the corruption level](https://mlsanity.com/paper/2202.05453/) (2022)
- [SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm](https://mlsanity.com/paper/2002.09589/) (2020)

## Abstract (arXiv)

Approximating distributions from their samples is a canonical statistical-learning problem. One of its most powerful and successful modalities approximates every distribution to an ℓ1 distance essentially at most a constant times larger than its closest t-piece degree-d polynomial, where t≥1 and d≥0. Letting ct,d denote the smallest such factor, clearly c1,0=1, and it can be shown that ct,d≥ 2 for all other t and d. Yet current computationally efficient algorithms show only ct,1≤ 2.25 and the bound rises quickly to ct,d≤ 3 for d≥ 9. We derive a near-linear-time and essentially sample-optimal estimator that establishes ct,d=2 for all (t,d)ne(1,0). Additionally, for many practical distributions, the lowest approximation distance is achieved by polynomials with vastly varying number of pieces. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation. Experiments combining the two techniques confirm improved performance over existing methodologies.