Differentially Private Matrix Completion through Low-rank Matrix Factorization
Lingxiao Wang, Boxin Zhao, Mladen Kolar
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.
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.}
}