SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm
Authors:
- Yi HaoYHYi Hao
- Ayush JainAJAyush Jain
- Alon OrlitskyAOAlon Orlitsky
- Vaishakh RavindrakumarVRVaishakh Ravindrakumar
Preprint
Abstract
Sample- and computationally-efficient distribution estimation is a fundamental tenet in statistics and machine learning. We present $\mathrm{SURF}$, an algorithm for approximating distributions by piecewise polynomials. $\mathrm{SURF}$ is simple, replacing existing general-purpose optimization techniques by straight-forward approximation of each potential polynomial piece by a simple empirical-probability interpolation, and using plain divide-and-conquer to merge the pieces. It is universal, as well-known low-degree polynomial-approximation results imply that it accurately approximates a large class of common distributions. $\mathrm{SURF}$ is robust to distribution mis-specification as for any degree $d\le 8$, it estimates any distribution to an $\ell_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. It is fast, using optimal sample complexity, and running in near sample-linear time. In experiments, $\mathrm{SURF}$ significantly outperforms state-of-the art algorithms.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Polynomials and the exponent of matrix multiplicationBulletin of the London Mathematical Society, 2018
- Combinatorial Methods in Density Estimation2001
- Consistency of data-driven histogram methods for density estimation and classificationThe Annals of Statistics, 1996
- A Probabilistic Theory of Pattern Recognition1996
- Density Estimation for Statistics and Data AnalysisTechnometrics, 1987
- X. Contributions to the mathematical theory of evolution.—II. Skew variation in homogeneous materialPhilosophical Transactions of the Royal Society of London. (A.), 1895