Jayadev Acharya (Cornell University)
We will discuss two fundamental inference tasks, distribution learning, and testing under Local Differential Privacy (LDP).
We start by considering density estimation (distribution learning). We will propose two private-coin LDP schemes, which require log k and one bit of communication per player respectively, while still being sample-optimal. This is contrast with all known schemes (e.g., [EPK14, DJW13, KBW16, YB18]) that require \Omega(k) communication. It is also known that the availability of public-coins does not change the sample complexity of learning.
We then consider distribution testing (goodness-of-fit) problem, where the goal is to test whether a distribution is equal to a known reference distribution, or far from it. Unlike distribution learning, we show that the sample complexity reduces dramatically for public-coin schemes, compared to private-coin protocols.
To prove the lower bounds, we reduce the problem to bounding a new quantity we define, the chi^2 contraction. For public-coin schemes, we bound the min-max chi^2 contraction, and for private-coin schemes, we bound max-min chi^2 contraction. Here the min is over appropriately chosen priors, and and max is over the LDP schemes.
Joint works with Clement Canonne, Cody Freitag, Ziteng Sun, Himanshu Tyagi, and Huanyu Zhang.