Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
This work addresses the challenge of efficiently selecting the closest probability distribution from a set under privacy constraints, which is incremental as it builds on prior methods by reducing query complexity.
The paper tackles the problem of hypothesis selection under local differential privacy constraints by proposing an algorithm that uses a new object called the Scheffé graph to capture differences between distributions, resulting in a query complexity of $ ilde{O}(k^{3/2})$ non-adaptive queries, improving upon previous algorithms that required $Ω(k^2)$ queries or many interactive rounds.
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 $Ω(k^2)$ queries or many rounds of interactive queries. Technically, we introduce a new object we dub the Scheffé graph, which captures structure of the differences between distributions in $Q$, and may be of more broad interest for hypothesis selection tasks.