# The Optimal Approximation Factor in Density Estimation

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2019.

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

- [Probably Approximately Precision and Recall Learning](https://mlsanity.com/paper/2411.13029/) (2024)
- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [No Free Lunch: Fundamental Limits of Learning Non-Hallucinating Generative Models](https://mlsanity.com/paper/2410.19217/) (2024)
- [Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning](https://mlsanity.com/paper/2510.03181/) (2025)
- [A Theoretical Framework for Statistical Evaluability of Generative Models](https://mlsanity.com/paper/2604.05324/) (2026)
- [Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale](https://mlsanity.com/paper/2605.13684/) (2026)
- [TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm](https://mlsanity.com/paper/2202.07172/) (2022)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)
- [Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph](https://mlsanity.com/paper/2509.16180/) (2025)
- [On Robust Hypothesis Testing with respect to the Hellinger Distance](https://mlsanity.com/paper/2510.16750/) (2025)
- [Hypothesis Selection via Weighted Medians](https://mlsanity.com/paper/2610.20375/) (2026)

## Abstract (arXiv)

Consider the following problem: given two arbitrary densities q1,q2 and a sample-access to an unknown target density p, find which of the qi's is closer to p in total variation. A remarkable result due to Yatracos shows that this problem is tractable in the following sense: there exists an algorithm that uses O(ε-2) samples from p and outputs~qi such that with high probability, TV(qi,p) ≤ 3·mathsfopt + ε, where mathsfopt= minTV(q1,p),TV(q2,p). Moreover, this result extends to any finite class of densities Q: there exists an algorithm that outputs the best density in Q up to a multiplicative approximation factor of 3. We complement and extend this result by showing that: (i) the factor 3 can not be improved if one restricts the algorithm to output a density from Q, and (ii) if one allows the algorithm to output arbitrary densities (e.g. a mixture of densities from Q), then the approximation factor can be reduced to 2, which is optimal. In particular this demonstrates an advantage of improper learning over proper in this setup. We develop two approaches to achieve the optimal approximation factor of 2: an adaptive one and a static one. Both approaches are based on a geometric point of view of the problem and rely on estimating surrogate metrics to the total variation. Our sample complexity bounds exploit techniques from it Adaptive Data Analysis.