mlsanityData to 14 Oct 2026

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

arXiv 2506.01162 ↗First posted 1 Jun 2025cs.DS cs.CR cs.LGcited by 0

Not on the map. Why?

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.

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

27 of 55 references.

References · 27

  1. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 272
  2. 2019Private Hypothesis Selectioncited by 60
  3. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  4. 2016Understanding the Sparse Vector Technique for Differential Privacycited by 27
  5. 2014Near-optimal-sample estimators for spherical Gaussian mixturescited by 26
  6. 2018The Structure of Optimal Private Tests for Simple Hypothesescited by 26
  7. 2017Differentially Private Testing of Identity and Closeness of Discrete Distributionscited by 25
  8. 2013Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussianscited by 20
  9. 2020Locally Private Hypothesis Selectioncited by 17
  10. 2019Private Identity Testing for High-Dimensional Distributionscited by 15
  11. 2018Test without Trust: Optimal Locally Private Distribution Testingcited by 13
  12. 2019The Optimal Approximation Factor in Density Estimationcited by 12
15 more
  1. 2017Priv'IT: Private and Sample Efficient Identity Testingcited by 11
  2. 2020Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanismscited by 11
  3. 2017Local Private Hypothesis Testing: Chi-Square Testscited by 10
  4. 2019Privacy Accounting and Quality Control in the Sage Differentially Private ML Platformcited by 10
  5. 2023Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraintscited by 10
  6. 2017Sample-Efficient Learning of Mixturescited by 9
  7. 2024The Sample Complexity of Simple Binary Hypothesis Testingcited by 8
  8. 2018PriPeARL: A Framework for Privacy-Preserving Analytics and Reporting at LinkedIncited by 7
  9. 2021Statistically Near-Optimal Hypothesis Selectioncited by 7
  10. 2019Pan-Private Uniformity Testingcited by 6
  11. 2020Differentially private partition selectioncited by 6
  12. 2022Plume: Differential Privacy at Scalecited by 5
  13. 2023Data Structures for Density Estimationcited by 4
  14. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  15. 2024Statistical-Computational Trade-offs for Density Estimationcited by 2

Built on by

Not cited yet.