Skip to yearly menu bar Skip to main content


Differentially Private Matrix Completion through Low-rank Matrix Factorization

Lingxiao Wang · Boxin Zhao · Mladen Kolar

Auditorium 1 Foyer 154


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.

Live content is unavailable. Log in and register to view live content