# Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph

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

## 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 (most cited first, 26 of 26)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Federated Learning of Gboard Language Models with Differential Privacy](https://mlsanity.com/paper/2305.18465/) (2023)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Geographic Spines in the 2020 Census Disclosure Avoidance System](https://mlsanity.com/paper/2203.16654/) (2022)
- [On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians](https://mlsanity.com/paper/2010.09929/) (2020)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [A Primer on Private Statistics](https://mlsanity.com/paper/2005.00010/) (2020)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [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)
- [The Role of Interactivity in Local Differential Privacy](https://mlsanity.com/paper/1904.03564/) (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)
- [User-Level Differential Privacy With Few Examples Per User](https://mlsanity.com/paper/2309.12500/) (2023)
- [Locally Private Hypothesis Testing](https://mlsanity.com/paper/1802.03441/) (2018)
- [Local Private Hypothesis Testing: Chi-Square Tests](https://mlsanity.com/paper/1709.07155/) (2017)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Statistically Near-Optimal Hypothesis Selection](https://mlsanity.com/paper/2108.07880/) (2021)
- [Data Structures for Density Estimation](https://mlsanity.com/paper/2306.11312/) (2023)
- [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)
- [Robust quantum minimum finding with an application to hypothesis selection](https://mlsanity.com/paper/2003.11777/) (2020)
- [Statistical-Computational Trade-offs for Density Estimation](https://mlsanity.com/paper/2410.23087/) (2024)

## 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.