Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
Gautam Kamath, Alireza F. Pour, Matthew Regehr, David Woodruff
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.
BibTeX
@inproceedings{
kamath2025queryefficient,
title={Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph},
author={Gautam Kamath and Alireza F. Pour and Matthew Regehr and David Woodruff},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=2Ybm2W1o9m}
}