Abstract
We consider three classes of locally private algorithms: non-interactive algorithms, sequentially interactive algorithms, and fully interactive algorithms. It has long been known that sequentially interactive algorithms can have exponentially smaller sample complexity than non-interactive algorithms for certain problems, but the relationship between sequential interactivity and full interactivity has been much murkier. We define a natural class of mechanisms parameterized by a number k, for which we can show that sequentially interactive algorithms can simulate fully interactive algorithms in this class with an O(k) blowup in sample complexity. We show this is tight by exhibiting a problem for which this O(k) blowup in sample complexity is necessary.
We then define a class of compound hypothesis testing problems (including every simple hypothesis testing problem) for which there always exists a non-interactive hypothesis test that is optimal, even within the class of fully interactive locally private algorithms.