# Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 1 Jun 2025.

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

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians](https://mlsanity.com/paper/2010.09929/) (2020)
- [Understanding the Sparse Vector Technique for Differential Privacy](https://mlsanity.com/paper/1603.01699/) (2016)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [The Structure of Optimal Private Tests for Simple Hypotheses](https://mlsanity.com/paper/1811.11148/) (2018)
- [Differentially Private Testing of Identity and Closeness of Discrete Distributions](https://mlsanity.com/paper/1707.05128/) (2017)
- [Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians](https://mlsanity.com/paper/1312.1054/) (2013)
- [Locally Private Hypothesis Selection](https://mlsanity.com/paper/2002.09465/) (2020)
- [Private Identity Testing for High-Dimensional Distributions](https://mlsanity.com/paper/1905.11947/) (2019)
- [Test without Trust: Optimal Locally Private Distribution Testing](https://mlsanity.com/paper/1808.02174/) (2018)
- [The Optimal Approximation Factor in Density Estimation](https://mlsanity.com/paper/1902.05876/) (2019)
- [Priv'IT: Private and Sample Efficient Identity Testing](https://mlsanity.com/paper/1703.10127/) (2017)
- [Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms](https://mlsanity.com/paper/2005.12601/) (2020)
- [Local Private Hypothesis Testing: Chi-Square Tests](https://mlsanity.com/paper/1709.07155/) (2017)
- [Privacy Accounting and Quality Control in the Sage Differentially Private ML Platform](https://mlsanity.com/paper/1909.01502/) (2019)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [Sample-Efficient Learning of Mixtures](https://mlsanity.com/paper/1706.01596/) (2017)
- [The Sample Complexity of Simple Binary Hypothesis Testing](https://mlsanity.com/paper/2403.16981/) (2024)
- [PriPeARL: A Framework for Privacy-Preserving Analytics and Reporting at LinkedIn](https://mlsanity.com/paper/1809.07754/) (2018)
- [Statistically Near-Optimal Hypothesis Selection](https://mlsanity.com/paper/2108.07880/) (2021)
- [Pan-Private Uniformity Testing](https://mlsanity.com/paper/1911.01452/) (2019)
- [Differentially private partition selection](https://mlsanity.com/paper/2006.03684/) (2020)
- [Plume: Differential Privacy at Scale](https://mlsanity.com/paper/2201.11603/) (2022)
- [Data Structures for Density Estimation](https://mlsanity.com/paper/2306.11312/) (2023)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Statistical-Computational Trade-offs for Density Estimation](https://mlsanity.com/paper/2410.23087/) (2024)

## Abstract (arXiv)

Estimating the density of a distribution from its samples is a fundamental problem in statistics. Hypothesis selection addresses the setting where, in addition to a sample set, we are given n candidate distributions -- referred to as hypotheses -- and the goal is to determine which one best describes the underlying data distribution. This problem is known to be solvable very efficiently, requiring roughly O(log n) samples and running in tildeO(n) time. The quality of the output is measured via the total variation distance to the unknown distribution, and the approximation factor of the algorithm determines how large this distance is compared to the optimal distance achieved by the best candidate hypothesis. It is known that α = 3 is the optimal approximation factor for this problem. We study hypothesis selection under the constraint of differential privacy. We propose a differentially private algorithm in the central model that runs in nearly-linear time with respect to the number of hypotheses, achieves the optimal approximation factor, and incurs only a modest increase in sample complexity, which remains polylogarithmic in n. This resolves an open question posed by [Bun, Kamath, Steinke, Wu, NeurIPS 2019]. Prior to our work, existing upper bounds required quadratic time.