Fast Differentially Private Matrix Factorization

By Ziqi Liu, Yu-Xiang Wang, Alex Smola. 2015

133 citations recorded by the source corpus.

Differentially private collaborative filtering is a challenging task, both in terms of accuracy and speed. We present a simple algorithm that is provably differentially private, while offering good performance, using a novel connection of differential privacy to Bayesian posterior sampling via Stochastic Gradient Langevin Dynamics. Due to its simplicity the algorithm lends itself to efficient implementation. By careful systems design and by exploiting the power law behavior of the data to maximize CPU cache bandwidth we are able to generate 1024 dimensional models at a rate of 8.5 million recommendations per second on a single PC.

Subfields: Artificial Intelligence, Computer Science Applications

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

In Computer Science Applications

Citations in the corpus

Privacy-Preserving Tensor Factorization for Collaborative Health Data Analysis (2019, background): “[22] proposed a new idea that sampling from the posterior distribution of a Bayesian model can sufficiently guarantee differential privacy.”
Certified Data Removal from Machine Learning Models (2019, neutral): “Many classical machine learning algorithms have been shown to support diﬀerentially private versions, including PCA (Chaudhuri et al., 2012), matrix factorization (Liu et al., 2015), linear models (Chaudhuri et al., 2011), and neural networks (Abadi et al., 2016).”
Per-instance Differential Privacy and the Adaptivity of Posterior Sampling in Linear and Ridge regression (2017, background): “…by Pure-DP[11] sup [13, 4] sup Z sup z D subG ( P (cid:107) Q ) A only Rényi-DP[24] sup Z sup z D α ( P (cid:107) Q ) A only Personal-DP[15, 20] sup Z ﬁxed z D δ ∞ ( P (cid:107) Q ) A and z TV-privacy[2] sup Z sup z P − Q (cid:107) TV A only KL-privacy[2] sup Z sup z D KL ( P (cid:107) Q )…”
A Simple and Efficient Federated Recommender System (2019, background): “Conventional distributed recommender systems speed up the computations by dividing encrypted data into chunks and processing on multiple threads of a trusted server [18].”
Recommender Systems (2016, unknown): “A differentially private matrix factorization has recently been proposed in [372].”
Towards a More Reliable Privacy-preserving Recommender System (2017, methodology): “As Liu et al. [12] has proved that introducing noises to SGLD can guarantee the diﬀerential privacy.”
Per-instance Differential Privacy (2017, background): “The closest existing definition to ours is perhaps the personalized-DP, first seen in Ebadi et al. (2015); Liu et al. (2015).”
Differentially Private Matrix Completion, Revisited (2017, methodology): “…we consider the following setting of the hidden matrix Y ∗ ∈ m × n and the set of released entries Ω We compare our results with the best non-private algorithm for matrix completion based on nuclear norm minimization [39], and the prior work on diﬀerentially private matrix completion [35, 36].”