research-article

Fast Differentially Private Matrix Factorization

Authors:

Alexander SmolaAuthors Info & Claims

RecSys '15: Proceedings of the 9th ACM Conference on Recommender Systems

Pages 171 - 178

https://doi.org/10.1145/2792838.2800191

Published: 16 September 2015 Publication History

Abstract

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.

Supplementary Material

MP4 File (p171.mp4)

Download
1833.05 MB

References

[1]

A. Ahmed, M. Aly, J. Gonzalez, S. Narayanamurthy, and A. Smola. Scalable Inference in Latent Variable Models. In WSDM, 2012.

Digital Library

[2]

S. Ahn, A. Korattikara, and M. Welling. Bayesian posterior sampling via stochastic gradient fisher scoring. In ICML'12, pages 1591--1598, 2012.

[3]

S. Ahn, A. Korattikara, N. Liu, S. Rajan, and M. Welling. Large scale distributed bayesian matrix factorization using stochastic gradient MCMC. 2015.

Digital Library

[4]

T. Chen, E. B. Fox, and C. Guestrin. Stochastic Gradient Hamiltonian Monte Carlo. 32, 2014.

[5]

C. Dimitrakakis, B. Nelson, A. Mitrokotsa, and B. I. Rubinstein. Robust and private bayesian inference. In Algorithmic Learning Theory, pages 291--305. Springer, 2014.

[6]

N. Ding, C. Chen, R. D. Skeel, and R. Babbush. Bayesian Sampling Using Stochastic Gradient Thermostats. In NIPS, pages 1--14, 2014.

[7]

C. Dwork. Differential privacy. In Automata, Languages and Programming, pages 1--12. Springer, 2006.

Digital Library

[8]

C. Dwork and A. Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211--407, 2013.

Digital Library

[9]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography, pages 265--284. Springer, 2006.

Digital Library

[10]

H. Ebadi, D. Sands, and G. Schneider. Differential privacy: Now it's getting personal. In ACM Symposium on Principles of Programming Languages, pages 69--81. ACM, 2015.

Digital Library

[11]

A. Hartstein, V. Srinivasan, T. Puzak, and P. Emma. On the nature of cache miss behavior: Is it p2? The Journal of Instruction-Level Parallelism, 10:1--22, 2008.

[12]

R. Keshavan, A. Montanari, and S. Oh. Matrix completion from noisy entries. In NIPS'09, pages 952--960, 2009.

[13]

Y. Koren. Collaborative Filtering with Temporal Dynamics. In KDD, number 4, 2009.

Digital Library

[14]

Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. IEEE Computer Society, pages 42--49, 2009.

Digital Library

[15]

A. Kyrola, G. Blelloch, and C. Guestrin. GraphChi : Large-Scale Graph Computation on Just a PC Disk-based Graph Computation. In OSDI, 2012.

Digital Library

[16]

N. P. Laptev. Analysis of cache architectures. Department of Computer Science--University of California Santa Barbara.

[17]

Z. Liu, Y.-X. Wang, and A. J. Smola. Fast differentially private matrix factorization. arXiv:1505.01419, 2015.

[18]

Y. Low, J. E. Gonzalez, A. Kyrola, D. Bickson, C. E. Guestrin, and J. Hellerstein. Graphlab: A new framework for parallel machine learning. arXiv:1408.2041, 2014.

[19]

G. Marsaglia, W. W. Tsang, and J. Wang. Fast Generation of Discrete Random Variables. Journal of Statistical Software, 11, 2004.

[20]

F. Mcsherry and I. Mironov. Differentially Private Recommender Systems : Building Privacy into the Netflix Prize Contenders. In KDD, 2009. ISBN 9781605584959.

Digital Library

[21]

F. McSherry and K. Talwar. Mechanism design via differential privacy. In Foundations of Computer Science, 2007. FOCS'07. 48th Annual IEEE Symposium on, pages 94--103. IEEE, 2007.

Digital Library

[22]

R. Meka, P. Jain, and I. S. Dhillon. Matrix completion from power-law distributed samples. In NIPS, 2009.

Digital Library

[23]

D. J. Mir. Differential privacy: an exploration of the privacy-utility landscape. PhD thesis, Rutgers University-Graduate School-New Brunswick, 2013.

Digital Library

[24]

B. Mobasher, R. Burke, R. Bhaumik, and C. Williams. Toward trustworthy recommender systems: An analysis of attack models and algorithm robustness. ACM Transactions on Internet Technology (TOIT), 7(4):23, 2007.

Digital Library

[25]

A. Narayanan and V. Shmatikov. Robust de-anonymization of large sparse datasets. In Security and Privacy, 2008. SP 2008. IEEE Symposium on, pages 111--125. IEEE, 2008.

Digital Library

[26]

R. M. Neal. Mcmc using hamiltonian dynamics. Handbook of Markov Chain Monte Carlo, 2, 2011.

[27]

F. Niu, B. Recht, R. Christopher, and S. J. Wright. Hogwild ! : A Lock-Free Approach to Parallelizing Stochastic Gradient Descent. In NIPS, pages 1--22, 2011.

[28]

R. Salakhutdinov, A. Mnih, and G. Hinton. Restricted Boltzmann Machines for Collaborative Filtering. In ICML, 2007.

Digital Library

[29]

I. Sato and H. Nakagawa. Approximation analysis of stochastic gradient langevin dynamics by using fokker-planck equation and ito process. In ICML'14, pages 982--990, 2014.

[30]

N. Srebro and R. R. Salakhutdinov. Collaborative filtering in a non-uniform world: Learning with the weighted trace norm. In NIPS'10, pages 2056--2064, 2010.

[31]

Y. W. Teh, A. Thiéry, and S. Vollmer. Consistency and fluctuations for stochastic gradient langevin dynamics. arXiv preprint:1409.0578, 2014.

[32]

Y. W. Teh, S. J. Vollmer, and K. C. Zygalakis. (Non-) asymptotic properties of Stochastic Gradient Langevin Dynamics. arXiv preprint:1501.00438, 2015.

[33]

Y.-X. Wang and H. Xu. Stability of matrix factorization for collaborative filtering. In ICML'12, pages 417--424, 2012.

[34]

Y.-X. Wang, S. E. Fienberg, and A. Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In ICML, 2015.

Digital Library

[35]

M. Welling and Y. W. Teh. Bayesian Learning via Stochastic Gradient Langevin Dynamics. In ICML, 2011.

Digital Library

[36]

Y. Xin and T. Jaakkola. Controlling privacy in recommender systems. In NIPS, 2014.

Digital Library

[37]

A. Zhang, N. Fawaz, S. Ioannidis, and A. Montanari. Guess who rated this movie: Identifying users through subspace clustering. arXiv preprint arXiv:1208.1544, 2012.

[38]

H. Zhao and J. F. Canny. High Performance Machine Learning through Codesign and Rooflining. PhD thesis, EECS Department, University of California, Berkeley, Sep 2014.

Cited By

Hu WFang H(2024)Towards Differential Privacy in Sequential Recommendation: A Noisy Graph Neural Network ApproachACM Transactions on Knowledge Discovery from Data10.1145/3643821Online publication date: 30-Jan-2024
https://doi.org/10.1145/3643821
Saha SImtiaz H(2024)Privacy-Preserving Non-Negative Matrix Factorization with OutliersACM Transactions on Knowledge Discovery from Data10.1145/363296118:3(1-26)Online publication date: 12-Jan-2024
https://dl.acm.org/doi/10.1145/3632961
Zhang SYuan WYin H(2024)Comprehensive Privacy Analysis on Federated Recommender System Against Attribute Inference AttacksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.329560136:3(987-999)Online publication date: Mar-2024
https://doi.org/10.1109/TKDE.2023.3295601
Show More Cited By

Index Terms

Fast Differentially Private Matrix Factorization

Recommendations

Applying Differential Privacy to Matrix Factorization
RecSys '15: Proceedings of the 9th ACM Conference on Recommender Systems

Recommender systems are increasingly becoming an integral part of on-line services. As the recommendations rely on personal user information, there is an inherent loss of privacy resulting from the use of such systems. While several works studied ...
Differentially Private Matrix Factorization using Sketching Techniques
IH&MMSec '16: Proceedings of the 4th ACM Workshop on Information Hiding and Multimedia Security

Collaborative filtering is a popular technique for recommendation system due to its domain independence and reliance on user behavior data alone. But the possibility of identification of users based on these personal data raise privacy concerns. ...
A differentially private algorithm for location data release

The rise of mobile technologies in recent years has led to large volumes of location information, which are valuable resources for knowledge discovery such as travel patterns mining and traffic analysis. However, location dataset has been confronted ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

RecSys '15: Proceedings of the 9th ACM Conference on Recommender Systems

September 2015

414 pages

ISBN:9781450336925

DOI:10.1145/2792838

General Chairs:
Hannes Werthner
TU Wien, Austria
,
Markus Zanker
Alpen-Adria-Universität Klagenfurt, Austria
,
Program Chairs:
Jennifer Golbeck
University of Maryland, USA
,
Giovanni Semeraro
University of Bari Aldo Moro, Italy

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGCHI: ACM Special Interest Group on Computer-Human Interaction

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 September 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation
National Natural Science Foundation of China
Ministry of Education of the People's Republic of China
Science Fund for Creative Research Groups
National Research Foundation-Prime Minister's office, Republic of Singapore

Conference

RecSys '15

Sponsor:

SIGCHI

RecSys '15: Ninth ACM Conference on Recommender Systems

September 16 - 20, 2015

Vienna, Austria

Acceptance Rates

RecSys '15 Paper Acceptance Rate 28 of 131 submissions, 21%;

Overall Acceptance Rate 254 of 1,295 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
1,009
Total Downloads

Downloads (Last 12 months)45
Downloads (Last 6 weeks)5

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hu WFang H(2024)Towards Differential Privacy in Sequential Recommendation: A Noisy Graph Neural Network ApproachACM Transactions on Knowledge Discovery from Data10.1145/3643821Online publication date: 30-Jan-2024
https://doi.org/10.1145/3643821
Saha SImtiaz H(2024)Privacy-Preserving Non-Negative Matrix Factorization with OutliersACM Transactions on Knowledge Discovery from Data10.1145/363296118:3(1-26)Online publication date: 12-Jan-2024
https://dl.acm.org/doi/10.1145/3632961
Zhang SYuan WYin H(2024)Comprehensive Privacy Analysis on Federated Recommender System Against Attribute Inference AttacksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.329560136:3(987-999)Online publication date: Mar-2024
https://doi.org/10.1109/TKDE.2023.3295601
Feng SMohammady MWang HLi XQin ZHong Y(2024)DPI: Ensuring Strict Differential Privacy for Infinite Data Streaming2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00124(1009-1027)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00124
Chang SWu HYan KHuang SWu Y(2024)Federated Multimedia Recommendation Systems with Privacy Protection2024 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting (BMSB)10.1109/BMSB62888.2024.10608307(1-7)Online publication date: 19-Jun-2024
https://doi.org/10.1109/BMSB62888.2024.10608307
Cai LTang JDang SChen G(2024)Privacy protection and utility trade-off for social graph embeddingInformation Sciences: an International Journal10.1016/j.ins.2024.120866676:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.120866
Mugdho SImtiaz H(2024)Privacy-preserving matrix factorization for recommendation systems using Gaussian mechanism and functional mechanismInternational Journal of Machine Learning and Cybernetics10.1007/s13042-024-02276-315:12(5745-5763)Online publication date: 14-Jul-2024
https://doi.org/10.1007/s13042-024-02276-3
Miehling ENair RDaly ERamamurthy KRedmond ROh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Cookie consent has disparate impact on estimation accuracyProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667610(34308-34328)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667610
Yang ZGe YSu CWang DZhao XYing Y(2023)Fairness-aware Differentially Private Collaborative FilteringCompanion Proceedings of the ACM Web Conference 202310.1145/3543873.3587577(927-931)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543873.3587577
Hu WFang H(2023)Decentralized Matrix Factorization with Heterogeneous Differential Privacy2023 IEEE 22nd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom60117.2023.00148(1068-1075)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TrustCom60117.2023.00148
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents