A&C Seminar: Mat Regehr - 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 ~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. https://arxiv.org/abs/2509.16180