Fetching the paper…

Reading the bibliography…

2012

Beyond Worst-Case Analysis in Private Singular Vector Computation

Hardt, Moritz, Roth, Aaron

Original
PDF
Post on X

Understand

We consider differentially private approximate singular vector computation.

Known worst-case lower bounds show that the error of any differentially private algorithm must scale polynomially with the dimension of the singular vector.
We are able to replace this dependence on the dimension by a natural parameter known as the coherence of the matrix that is often observed to be significantly smaller than the dimension both theoretically and empirically.
We also prove a matching lower bound showing that our guarantee is nearly optimal for every setting of the coherence parameter.

Beyond Worst-Case Analysis in Private Singular Vector Computation · Around

Built on

Revealing information while preserving privacy
Irit Dinur and Kobbi Nissim · 2003
Earlier work this paper cites.
Practical privacy: the SuLQ framework
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim · 2005
Earlier work this paper cites.
Mechanism design via differential privacy
Frank McSherry and Kunal Talwar · 2007
Earlier work this paper cites.
Robust de-anonymization of large sparse datasets
Arvind Narayanan and Vitaly Shmatikov · 2008
Earlier work this paper cites.
Exact matrix completion via convex optimization
Emmanuel Candes and Benjamin Recht · 2009
Earlier work this paper cites.

Similar

The power of convex relaxation: near-optimal matrix completion
Emmanuel J. Candès and Terence Tao · 2010
Cited alongside, same era.
Boosting and differential privacy
Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan · 2010
Cited alongside, same era.
A multiplicative weights mechanism for privacy-preserving data analysis
Moritz Hardt and Guy Rothblum · 2010
Cited alongside, same era.
Matrix coherence and the nystrom method
Original
Anand Talwalkar and Afshin Rostamizadeh · 2010
Cited alongside, same era.
The Johnson-Lindenstrauss transform itself preserves differential privacy
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet · 2012
Cited alongside, same era.

Then

Near-optimal differentially private principal components
Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha · 2012
Closest in time.
Iterative constructions and private data release
Anupam Gupta, Aaron Roth, and Jonathan Ullman · 2012
Closest in time.
Beating randomized response on incoherent matrices
Moritz Hardt and Aaron Roth · 2012
Closest in time.
On differentially private low rank approximation
Michael Kapralov and Kunal Talwar · 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…