2015

Private Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression

Sheffet, Or

Understand

We introduce three differentially-private algorithms that approximates the 2nd-moment matrix of the data.

These algorithm, which in contrast to existing algorithms output positive-definite matrices, correspond to existing techniques in linear regression literature.
Specifically, we discuss the following three techniques.
(i) For Ridge Regression, we propose setting the regularization coefficient so that by approximating the solution using Johnson-Lindenstrauss transform we preserve privacy.

Solution of incorrectly formulated problems and the regularization method
A. N. Tikhonov · 1963
Earlier work this paper cites.
Ridge regression: Biased estimation for nonorthogonal problems
A. E. Hoerl and R. W. Kennard · 1970
Earlier work this paper cites.
Multivariate analysis
K.V. Mardia, J.T. Kent, and J.M. Bibby · 1979
Earlier work this paper cites.
Local operator theory, random matrices and banach spaces
Kenneth R. Davidson and Stanislaw J. Szarek · 2001
Earlier work this paper cites.
An elementary proof of a theorem of johnson and lindenstrauss
Sanjoy Dasgupta and Anupam Gupta · 2003
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.
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, and Adam Smith · 2006
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Earlier work this paper cites.
The elements of statistical learning : data mining, inference, and prediction
Trevor J. Hastie, Robert John Tibshirani, and Jerome H. Friedman · 2009
Earlier work this paper cites.

Boosting and differential privacy
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan · 2010
Cited alongside, same era.
Differentially private empirical risk minimization
Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate · 2011
Cited alongside, same era.
Randomized algorithms for matrices and data
Michael W. Mahoney · 2011
Cited alongside, same era.
Mixture of gaussian models and bayes error under differential privacy
Bowei Xi, Murat Kantarcioglu, and Ali Inan · 2011
Cited alongside, same era.
The Johnson-Lindenstrauss transform itself preserves differential privacy
J. Blocki, A. Blum, A. Datta, and O. Sheffet · 2012
Cited alongside, same era.
Beating randomized response on incoherent matrices
Moritz Hardt and Aaron Roth · 2012
Cited alongside, same era.
Private convex optimization for empirical risk minimization with applications to high-dimensional regression
Daniel Kifer, Adam D. Smith, and Abhradeep Thakurta · 2012
Cited alongside, same era.
Topics in Random Matrix Theory
T. Tao · 2012
Cited alongside, same era.
A risk comparison of ordinary least squares vs ridge regression
Paramveer S. Dhillon, Dean P. Foster, Sham M. Kakade, and Lyle H. Ungar · 2013
Cited alongside, same era.

Robust subspace iteration and privacy-preserving spectral analysis
Moritz Hardt · 2013
Later among the works it cites.
On differentially private low rank approximation
Michael Kapralov and Kunal Talwar · 2013
Later among the works it cites.
Differentially private feature selection via stability arguments, and the robustness of the lasso
Abhradeep Thakurta and Adam Smith · 2013
Later among the works it cites.
Private empirical risk minimization: Efficient algorithms and tight error bounds
Raef Bassily, Adam Smith, and Abhradeep Thakurta · 2014
Later among the works it cites.
Analyze gauss - optimal bounds for privacy preserving principal component analysis
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang · 2014
Later among the works it cites.
Differentially private linear algebra in the streaming model
Original
Jalaj Upadhyay · 2014
Later among the works it cites.
Private multiplicative weights beyond linear queries
Jonathan Ullman · 2015
Closest in time.
The differential privacy of bayesian inference
Salil Vadhan and Joy Zheng · 2015
Closest in time.
Privacy for free: Posterior sampling and stochastic gradient monte carlo
Yu-Xiang Wang, Stephen E. Fienberg, and Alexander J. Smola · 2015
Closest in time.

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

alphaXiv is searching for related work…

Reading the bibliography…