2020/02/22 by Hao Yi, Hao, Yi, Ayush Jain +5
Computer Science · #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2002.09589
openalex publication_date 2020/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.