Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
Abstract
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 $\tilde{O}(k^{3/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(k^2)$ 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.
Cite
Text
Kamath et al. "Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph." Advances in Neural Information Processing Systems, 2025.Markdown
[Kamath et al. "Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph." Advances in Neural Information Processing Systems, 2025.](https://mlanthology.org/neurips/2025/kamath2025neurips-queryefficient/)BibTeX
@inproceedings{kamath2025neurips-queryefficient,
title = {{Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph}},
author = {Kamath, Gautam and Pour, Alireza F. and Regehr, Matthew and Woodruff, David},
booktitle = {Advances in Neural Information Processing Systems},
year = {2025},
url = {https://mlanthology.org/neurips/2025/kamath2025neurips-queryefficient/}
}