Differentially Private Matrix Completion Revisited

Prateek Jain, Om Dipakbhai Thakkar, Abhradeep Thakurta
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2215-2224, 2018.

Abstract

We provide the first provably joint differentially private algorithm with formal utility guarantees for the problem of user-level privacy-preserving collaborative filtering. Our algorithm is based on the Frank-Wolfe method, and it consistently estimates the underlying preference matrix as long as the number of users $m$ is $\omega(n^{5/4})$, where $n$ is the number of items, and each user provides her preference for at least $\sqrt{n}$ randomly selected items. Along the way, we provide an optimal differentially private algorithm for singular vector computation, based on the celebrated Oja’s method, that provides significant savings in terms of space and time while operating on sparse matrices. We also empirically evaluate our algorithm on a suite of datasets, and show that it consistently outperforms the state-of-the-art private algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-jain18b, title = {Differentially Private Matrix Completion Revisited}, author = {Jain, Prateek and Thakkar, Om Dipakbhai and Thakurta, Abhradeep}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2215--2224}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/jain18b/jain18b.pdf}, url = {https://proceedings.mlr.press/v80/jain18b.html}, abstract = {We provide the first provably joint differentially private algorithm with formal utility guarantees for the problem of user-level privacy-preserving collaborative filtering. Our algorithm is based on the Frank-Wolfe method, and it consistently estimates the underlying preference matrix as long as the number of users $m$ is $\omega(n^{5/4})$, where $n$ is the number of items, and each user provides her preference for at least $\sqrt{n}$ randomly selected items. Along the way, we provide an optimal differentially private algorithm for singular vector computation, based on the celebrated Oja’s method, that provides significant savings in terms of space and time while operating on sparse matrices. We also empirically evaluate our algorithm on a suite of datasets, and show that it consistently outperforms the state-of-the-art private algorithms.} }
Endnote
%0 Conference Paper %T Differentially Private Matrix Completion Revisited %A Prateek Jain %A Om Dipakbhai Thakkar %A Abhradeep Thakurta %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-jain18b %I PMLR %P 2215--2224 %U https://proceedings.mlr.press/v80/jain18b.html %V 80 %X We provide the first provably joint differentially private algorithm with formal utility guarantees for the problem of user-level privacy-preserving collaborative filtering. Our algorithm is based on the Frank-Wolfe method, and it consistently estimates the underlying preference matrix as long as the number of users $m$ is $\omega(n^{5/4})$, where $n$ is the number of items, and each user provides her preference for at least $\sqrt{n}$ randomly selected items. Along the way, we provide an optimal differentially private algorithm for singular vector computation, based on the celebrated Oja’s method, that provides significant savings in terms of space and time while operating on sparse matrices. We also empirically evaluate our algorithm on a suite of datasets, and show that it consistently outperforms the state-of-the-art private algorithms.
APA
Jain, P., Thakkar, O.D. & Thakurta, A.. (2018). Differentially Private Matrix Completion Revisited. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2215-2224 Available from https://proceedings.mlr.press/v80/jain18b.html.

Related Material