2019

The Power of Factorization Mechanisms in Local and Central Differential Privacy

Edmonds, Alexander, Nikolov, Aleksandar, Ullman, Jonathan

Understand

We give new characterizations of the sample complexity of answering linear queries (statistical queries) in the local and central models of differential privacy: *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.
*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.

Built on

Résumé de la théorie métrique des produits tensoriels topologiques
A. Grothendieck · 1953
Earlier work this paper cites.
Convex analysis
R. Tyrrell Rockafellar · 1970
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael J. Kearns · 1993
Earlier work this paper cites.
Weakly learning DNF and characterizing statistical query learning using fourier analysis
Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, and Steven Rudich · 1994
Earlier work this paper cites.
Toward efficient agnostic learning
Michael J Kearns, Robert E Schapire, and Linda M Sellie · 1994
Earlier work this paper cites.
On the degree of boolean functions as real polynomials
Noam Nisan and Mario Szegedy · 1994
Earlier work this paper cites.
On choosing and bounding probability metrics
Alison L Gibbs and Francis Edward Su · 2002
Earlier work this paper cites.
Revealing information while preserving privacy
Irit Dinur and Kobbi Nissim · 2003
Earlier work this paper cites.
Limiting privacy breaches in privacy preserving data mining
Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant · 2003
Earlier work this paper cites.
Estimating the optimal margins of embeddings in euclidean half spaces
Jürgen Forster, Niels Schmitt, Hans Ulrich Simon, and Thorsten Suttorp · 2003
Earlier work this paper cites.
Privacy-preserving datamining on vertically partitioned databases
Cynthia Dwork and Kobbi Nissim · 2004
Earlier work this paper cites.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith · 2006
Earlier work this paper cites.
Privacy, accuracy, and consistency too: a holistic solution to contingency table release
Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar · 2007
Earlier work this paper cites.
Complexity measures of sign matrices
Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman · 2007
Earlier work this paper cites.
What can we learn privately?
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith · 2008
Earlier work this paper cites.
Lower bounds in communication complexity based on factorization norms
Nati Linial and Adi Shraibman · 2009
Earlier work this paper cites.
Characterizing statistical query learning: Simplified notions and proofs
Balázs Szörényi · 2009
Earlier work this paper cites.

Similar

Differential privacy under continual observation
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum · 2010
Cited alongside, same era.
On the geometry of differential privacy
Moritz Hardt and Kunal Talwar · 2010
Cited alongside, same era.
The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman · 2010
Cited alongside, same era.
Optimizing linear counting queries under differential privacy
Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor · 2010
Cited alongside, same era.
Private and continual release of statistics
T-H Hubert Chan, Elaine Shi, and Dawn Song · 2011
Cited alongside, same era.
Privately releasing conjunctions and the statistical query barrier
Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman · 2011
Cited alongside, same era.
The pattern matrix method
Alexander A. Sherstov · 2011
Cited alongside, same era.
Unconditional differentially private mechanisms for linear queries
Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, and Kunal Talwar · 2012
Cited alongside, same era.
Private data release via learning thresholds
Moritz Hardt, Guy N. Rothblum, and Rocco A. Servedio · 2012
Cited alongside, same era.
Grothendieck-type inequalities in combinatorial optimization
Subhash Khot and Assaf Naor · 2012
Cited alongside, same era.
Grothendieck’s theorem, past and present
Gilles Pisier · 2012
Cited alongside, same era.
Faster algorithms for privately releasing marginals
Justin Thaler, Jonathan Ullman, and Salil P. Vadhan · 2012
Cited alongside, same era.

Then

New Computational Aspects of Discrepancy Theory
Aleksandar Nikolov · 2014
Later among the works it cites.
Efficient algorithms for privately releasing marginals via convex relaxations
Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar · 2015
Later among the works it cites.
An improved private mechanism for small databases
Aleksandar Nikolov · 2015
Later among the works it cites.
Approximating hereditary discrepancy via small width ellipsoids
Aleksandar Nikolov and Kunal Talwar · 2015
Later among the works it cites.
The geometry of differential privacy: The small database and approximate cases
Aleksandar Nikolov, Kunal Talwar, and Li Zhang · 2016
Later among the works it cites.
Learning with privacy at scale
Apple Differential Privacy Team · 2017
Later among the works it cites.
Prochlo: Strong privacy for analytics in the crowd
Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld · 2017
Later among the works it cites.
The modernization of statistical disclosure limitation at the U.S. census bureau, 2017
Aref N. Dajani, Amy D. Lauger, Phyllis E. Singer, Daniel Kifer, Jerome P. Reiter, Ashwin Machanavajjhala, Simson L. Garfinkel, Scot A. Dahl, Matthew Graham, Vishesh Karwa, Hang Kim, Philip Lelerc, Ian M. Schmutte, William N. Sexton, Lars Vilhuber, and John M. Abowd · 2017
Later among the works it cites.
Heavy hitters and the structure of local privacy
Mark Bun, Jelani Nelson, and Uri Stemmer · 2018
Later among the works it cites.
Minimax optimal procedures for locally private estimation
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright · 2018
Later among the works it cites.
The right complexity measure in locally private estimation: It is not the fisher information
Original
John C. Duchi and Feng Ruan · 2018
Later among the works it cites.
Towards practical differential privacy for sql queries
Noah Johnson, Joseph P Near, and Dawn Song · 2018
Later among the works it cites.
Optimizing error of high-dimensional statistical queries under differential privacy
Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala · 2018
Later among the works it cites.
High-dimensional probability
Roman Vershynin · 2018
Later among the works it cites.
Towards instance-optimal private query release
Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke · 2019
Closest in time.
Differentially private sql with bounded user contribution
Original
Royce J Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…