The power of factorization mechanisms in local and central differential privacy
By Alex Edmonds, Aleksandar Nikolov, Jonathan Ullman. 2019
76 citations recorded by the source corpus.
We give new characterizations of the sample complexity of answering linear queries (statistical queries) in the local and central models of differential privacy: (1) In the non-interactive local model, we give the first approximate characterization of the sample complexity. Informally our bounds are tight to within polylogarithmic factors in the number of queries and desired accuracy. Our characterization extends to agnostic learning in the local model. (2) In the central model, we give a characterization of the sample complexity in the high-accuracy regime that is analogous to that of Nikolov, Talwar, and Zhang (STOC 2013), but is both quantitatively tighter and has a dramatically simpler proof. Our lower bounds apply equally to the empirical and population estimation problems. In both cases, our characterizations show that a particular factorization mechanism is approximately optimal, and the optimal sample complexity is bounded from above and below by well studied factorization norms of a matrix associated with the queries.
Subfields: Artificial Intelligence, Statistics and Probability
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Albert Cheu
- Jonathan Ullman
- Thomas Steinke
- Mark Bun
- Aaron Roth
- Adam D. Smith
- Kobbi Nissim
- Uri Stemmer
In Statistics and Probability
Citations in the corpus
- The limits of pan privacy and shuffle privacy for learning and estimation (2020, background): “However, for problems such as learning parities and selecting the most common attribute, where the local model is most severely limited [19, 28, 40, 47], there is no evidence that either the pan-private or shuffle model can overcome these limitations.”