Differentially Private Matrix Completion through Low-rank Matrix Factorization

Lingxiao Wang, Boxin Zhao, Mladen Kolar
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:5731-5748, 2023.

Abstract

We study the matrix completion problem under joint differential privacy and develop a non-convex low-rank matrix factorization-based method for solving it. Our method comes with strong privacy and utility guarantees, has a linear convergence rate, and is more scalable than the best-known alternative (Chien et al., 2021). Our method achieves the (near) optimal sample complexity for matrix completion required by the non-private baseline and is much better than the best known result under joint differential privacy. Furthermore, we prove a tight utility guarantee that improves existing approaches and removes the impractical resampling assumption used in the literature. Numerical experiments further demonstrate the superiority of our method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-wang23d, title = {Differentially Private Matrix Completion through Low-rank Matrix Factorization}, author = {Wang, Lingxiao and Zhao, Boxin and Kolar, Mladen}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {5731--5748}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/wang23d/wang23d.pdf}, url = {https://proceedings.mlr.press/v206/wang23d.html}, abstract = {We study the matrix completion problem under joint differential privacy and develop a non-convex low-rank matrix factorization-based method for solving it. Our method comes with strong privacy and utility guarantees, has a linear convergence rate, and is more scalable than the best-known alternative (Chien et al., 2021). Our method achieves the (near) optimal sample complexity for matrix completion required by the non-private baseline and is much better than the best known result under joint differential privacy. Furthermore, we prove a tight utility guarantee that improves existing approaches and removes the impractical resampling assumption used in the literature. Numerical experiments further demonstrate the superiority of our method.} }
Endnote
%0 Conference Paper %T Differentially Private Matrix Completion through Low-rank Matrix Factorization %A Lingxiao Wang %A Boxin Zhao %A Mladen Kolar %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-wang23d %I PMLR %P 5731--5748 %U https://proceedings.mlr.press/v206/wang23d.html %V 206 %X We study the matrix completion problem under joint differential privacy and develop a non-convex low-rank matrix factorization-based method for solving it. Our method comes with strong privacy and utility guarantees, has a linear convergence rate, and is more scalable than the best-known alternative (Chien et al., 2021). Our method achieves the (near) optimal sample complexity for matrix completion required by the non-private baseline and is much better than the best known result under joint differential privacy. Furthermore, we prove a tight utility guarantee that improves existing approaches and removes the impractical resampling assumption used in the literature. Numerical experiments further demonstrate the superiority of our method.
APA
Wang, L., Zhao, B. & Kolar, M.. (2023). Differentially Private Matrix Completion through Low-rank Matrix Factorization. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:5731-5748 Available from https://proceedings.mlr.press/v206/wang23d.html.

Related Material