Abstract
We study the problem of hypothesis selection under the constraint of local differential privacy. Given a class F of k distributions and a set of i.i.d. samples from an unknown distribution h, the goal of hypothesis selection is to pick a distribution f whose total variation distance to h is comparable with the best distribution in F (with high probability). We devise an ε-locally-differentially-private (ε-LDP) algorithm that uses Θ(k/α²min {ε²,1}) samples to guarantee that d_TV(h,f)≤ α + 9 min_f∈ Fd_TV(h,f) with high probability. This sample complexity is optimal for ε<1, matching the lower bound of Gopi et al. (2020). All previously known algorithms for this problem required Ω(klog k/α²min { ε² ,1} ) samples to work. Moreover, our result demonstrates the power of interaction for ε-LDP hypothesis selection. Namely, it breaks the known lower bound of Ω(klog k/α²min { ε² ,1} ) for the sample complexity of non-interactive hypothesis selection. Our algorithm breaks this barrier using only Θ(log log k) rounds of interaction. To prove our results, we define the notion of \emph{critical queries} for a Statistical Query Algorithm (SQA) which may be of independent interest. Informally, an SQA is said to use a small number of critical queries if its success relies on the accuracy of only a small number of queries it asks. We then design an LDP algorithm that uses a smaller number of critical queries.