# Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2014.

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

- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)
- [Statistically Near-Optimal Hypothesis Selection](https://mlsanity.com/paper/2108.07880/) (2021)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [Breaking the curse of dimensionality in structured density estimation](https://mlsanity.com/paper/2410.07685/) (2024)
- [On the Learnability of Distribution Classes with Adaptive Adversaries](https://mlsanity.com/paper/2509.05137/) (2025)
- [Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning](https://mlsanity.com/paper/2510.03181/) (2025)
- [To bootstrap or to rollout? An optimal and adaptive interpolation](https://mlsanity.com/paper/2411.09731/) (2024)

## Abstract (arXiv)

Let p be an unknown and arbitrary probability distribution over [0,1). We consider the problem of em density estimation, in which a learning algorithm is given i.i.d. draws from p and must (with high probability) output a hypothesis distribution that is close to p. The main contribution of this paper is a highly efficient density estimation algorithm for learning using a variable-width histogram, i.e., a hypothesis distribution with a piecewise constant probability density function. In more detail, for any k and ε, we give an algorithm that makes tildeO(k/ε2) draws from p, runs in tildeO(k/ε2) time, and outputs a hypothesis distribution h that is piecewise constant with O(k log2(1/ε)) pieces. With high probability the hypothesis h satisfies dTV(p,h) ≤ C · optk(p) + ε, where dTV denotes the total variation distance (statistical distance), C is a universal constant, and optk(p) is the smallest total variation distance between p and any k-piecewise constant distribution. The sample size and running time of our algorithm are optimal up to logarithmic factors. The "approximation factor" C in our result is inherent in the problem, as we prove that no algorithm with sample size bounded in terms of k and ε can achieve C<2 regardless of what kind of hypothesis distribution it uses.