Please note: This PhD seminar will take place in DC 1304 and online.
Matthew Regehr, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Gautam Kamath
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.
Download the paper on which this PhD seminar is based.
To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually on Zoom.