mlsanityData to 14 Oct 2026

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph

arXiv 2509.16180 ↗First posted 19 Sep 2025cs.DS cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We propose an algorithm with improved query-complexity for the problem of hypothesis selection under local differential privacy constraints. Given a set of k probability distributions Q, we describe an algorithm that satisfies local differential privacy, performs tildeO(k3/2) non-adaptive queries to individuals who each have samples from a probability distribution p, and outputs a probability distribution from the set Q which is nearly the closest to p. Previous algorithms required either Omega(k2) queries or many rounds of interactive queries. Technically, we introduce a new object we dub the Scheff'e graph, which captures structure of the differences between distributions in Q, and may be of more broad interest for hypothesis selection tasks.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 26 of its 44 references that are in the map. First posted on arXiv 19 Sep 2025.

Builds on

26 of 44 references.

References · 26

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2021Numerical Composition of Differential Privacycited by 180
  3. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 107
  4. 2023Federated Learning of Gboard Language Models with Differential Privacycited by 66
  5. 2019Private Hypothesis Selectioncited by 60
  6. 2022Geographic Spines in the 2020 Census Disclosure Avoidance Systemcited by 44
  7. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  8. 2018Inference under Information Constraints I: Lower Bounds from Chi-Square Contractioncited by 31
  9. 2020A Primer on Private Statisticscited by 30
  10. 2014Near-optimal-sample estimators for spherical Gaussian mixturescited by 26
  11. 2013Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussianscited by 20
  12. 2020Locally Private Hypothesis Selectioncited by 17
14 more
  1. 2019The Role of Interactivity in Local Differential Privacycited by 15
  2. 2018Test without Trust: Optimal Locally Private Distribution Testingcited by 13
  3. 2019The Optimal Approximation Factor in Density Estimationcited by 12
  4. 2023User-Level Differential Privacy With Few Examples Per Usercited by 12
  5. 2018Locally Private Hypothesis Testingcited by 11
  6. 2017Local Private Hypothesis Testing: Chi-Square Testscited by 10
  7. 2023Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraintscited by 10
  8. 2022Contraction of Locally Differentially Private Mechanismscited by 8
  9. 2021Statistically Near-Optimal Hypothesis Selectioncited by 7
  10. 2023Data Structures for Density Estimationcited by 4
  11. 2024Distribution Learnability and Robustnesscited by 4
  12. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  13. 2020Robust quantum minimum finding with an application to hypothesis selectioncited by 2
  14. 2024Statistical-Computational Trade-offs for Density Estimationcited by 2

Built on by

Not cited yet.