Tight Lower Bounds for Locally Differentially Private Selection

Understand

We prove a tight lower bound (up to constant factors) on the sample complexity of any non-interactive local differentially private protocol for optimizing a linear function over the simplex.

• This lower bound also implies a tight lower bound (again, up to constant factors) on the sample complexity of any non-interactive local differentially private protocol implementing the exponential mechanism.
• These results reveal that any local protocol for these problems has exponentially worse dependence on the dimension than corresponding algorithms in the central model.
• Previously, Kasiviswanathan et al.