2012

The Geometry of Differential Privacy: the Sparse and Approximate Cases

Nikolov, Aleksandar, Talwar, Kunal, Zhang, Li

Understand

In this work, we study trade-offs between accuracy and privacy in the context of linear queries over histograms.

This is a rich class of queries that includes contingency tables and range queries, and has been a focus of a long line of work.
For a set of $d$ linear queries over a database $x \in \R^N$, we seek to find the differentially private mechanism that has the minimum mean squared error.
For pure differential privacy, an $O(\log^2 d)$ approximation to the optimal mechanism is known.

Built on

Extremum problems with inequalities as subsidiary conditions
F. John · 1948
Earlier work this paper cites.
An algorithm for quadratic programming
M. Frank and P. Wolfe · 1956
Earlier work this paper cites.
The brunn-minkowski inequality in gauss space
C. Borell · 1975
Earlier work this paper cites.
The complexity of satisfiability problems
T.J. Schaefer · 1978
Earlier work this paper cites.
Discrepancy of set-systems and matrices
L. Lovász, J. Spencer, and K. Vesztergombi · 1986
Earlier work this paper cites.
Invertibility of large submatrices with applications to the geometry of banach spaces and harmonic analysis
J. Bourgain and L. Tzafriri · 1987
Earlier work this paper cites.
Approximation of the sphere by polytopes having few vertices
I. Bárány and Z. Füredi · 1988
Earlier work this paper cites.
A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio
I. Adler and R. Shamir · 1993
Earlier work this paper cites.
Handbook of combinatorics (vol. 2)
József Beck and Vera T. Sós · 1995
Earlier work this paper cites.
Rounding of polytopes in the real number model of computation
L.G. Khachiyan · 1996
Earlier work this paper cites.
Geometric Discrepancy (An Illustrated Guide)
Jiří Matoušek · 1999
Earlier work this paper cites.
The Discrepancy Method: Randomness and Complexity
Bernard Chazelle · 2000
Earlier work this paper cites.
Inapproximability results for set splitting and satisfiability problems with no mixed clauses
V. Guruswami · 2000
Earlier work this paper cites.
John’s decompositions: Selecting a large part
R. Vershynin · 2001
Earlier work this paper cites.
Revealing information while preserving privacy
Irit Dinur and Kobbi Nissim · 2003
Earlier work this paper cites.
Notes on isotropic convex bodies
Apostolos Giannopoulos · 2003
Earlier work this paper cites.
Practical privacy: the sulq framework
A. Blum, C. Dwork, F. McSherry, and K. Nissim · 2005
Earlier work this paper cites.
Minimum-volume enclosing ellipsoids and core sets
P. Kumar and EA Yildirim · 2005
Earlier work this paper cites.
Our data, ourselves: Privacy via distributed noise generation
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor · 2006
Earlier work this paper cites.
Our data, ourselves: Privacy via distributed noise generation, 2006
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor · 2006
Earlier work this paper cites.
Calibrating noise to sensitivity in private data analysis
C. Dwork, F. Mcsherry, K. Nissim, and A. Smith · 2006
Earlier work this paper cites.

Similar

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
Cited alongside, same era.
The price of privacy and the limits of LP decoding
Cynthia Dwork, Frank McSherry, and Kunal Talwar · 2007
Cited alongside, same era.
Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces
E.D. Gluskin · 2007
Cited alongside, same era.
Smooth sensitivity and sampling in private data analysis
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith · 2007
Cited alongside, same era.
The boundary between privacy and utility in data publishing
Vibhor Rastogi, Sungho Hong, and Dan Suciu · 2007
Cited alongside, same era.
On khachiyan’s algorithm for the computation of minimum-volume enclosing ellipsoids
M.J. Todd and E.A. Yıldırım · 2007
Cited alongside, same era.
A learning theory approach to non-interactive database privacy
Avrim Blum, Katrina Ligett, and Aaron Roth · 2008
Cited alongside, same era.
New efficient attacks on statistical disclosure control mechanisms
Cynthia Dwork and Sergey Yekhanin · 2008
Cited alongside, same era.
On the complexity of differentially private data release: efficient algorithms and hardness results
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan · 2009
Cited alongside, same era.
Universally utility-maximizing privacy mechanisms
Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan · 2009
Cited alongside, same era.
Constructive algorithms for discrepancy minimization
N. Bansal · 2010
Cited alongside, same era.
Impossibility of differentially private universally optimal mechanisms
Hai Brenner and Kobbi Nissim · 2010
Cited alongside, same era.

Then

Interactive privacy via the median mechanism
Aaron Roth and Tim Roughgarden · 2010
Later among the works it cites.
Differential privacy via wavelet transforms
Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke · 2010
Later among the works it cites.
Differentially private data release through multidimensional partitioning
Yonghui Xiao, Li Xiong, and Chun Yuan · 2010
Later among the works it cites.
Tight hardness results for minimizing discrepancy
M. Charikar, A. Newman, and A. Nikolov · 2011
Later among the works it cites.
A discrepancy based approach to integer programming
Original
Karthekeyan Chandrasekaran and Santosh Vempala · 2011
Later among the works it cites.
Differentially private data cubes: optimizing noise sources and consistency
Bolin Ding, Marianne Winslett, Jiawei Han, and Zhenhui Li · 2011
Later among the works it cites.
Privately releasing conjunctions and the statistical query barrier
Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman · 2011
Later among the works it cites.
On range searching in the group model and combinatorial discrepancy
Kasper Green Larsen · 2011
Later among the works it cites.
The determinant bound for discrepancy is almost tight
Original
Jiří Matoušek · 2011
Later among the works it cites.
Minimax rates of estimation for high-dimensional linear regression over¡ formula formulatype=
G. Raskutti, M.J. Wainwright, and B. Yu · 2011
Later among the works it cites.
The multiplicative weights update method: a meta algorithm and applications
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2012
Closest in time.
Unconditional differentially private mechanisms for linear queries
Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, and Kunal Talwar · 2012
Closest in time.
Lower bounds in differential privacy
A. De · 2012
Closest in time.
Iterative constructions and private data release
Anupam Gupta, Aaron Roth, and Jonathan Ullman · 2012
Closest in time.
A simple and practical algorithm for differentially private data release
Moritz Hardt, Katrina Ligett, and Frank McSherry · 2012
Closest in time.
An adaptive mechanism for accurate query answering under differential privacy
Chao Li and Gerome Miklau · 2012
Closest in time.
Measuring the achievable error of query sets under differential privacy
Original
Chao Li and Gerome Miklau · 2012
Closest in time.
Optimal private halfspace counting via discrepancy
S. Muthukrishnan and Aleksandar Nikolov · 2012
Closest in time.
Topics in random matrix theory
Terence Tao · 2012
Closest in time.
Low-rank mechanism: Optimizing batch queries under differential privacy
Original
Ganzhao Yuan, Zhenjie Zhang, Marianne Winslett, Xiaokui Xiao, Yin Yang, and Zhifeng Hao · 2012
Closest in time.
The power of linear reconstruction attacks
Shiva Kasiviswanathan, Mark Rudelson, and Adam Smith · 2013
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…