Differentially Private Matrix Completion through Low-rank Matrix Factorization

Jan 1, 2023·
Lingxiao Wang
Lingxiao Wang
Boxin Zhao
Boxin Zhao
Mladen Kolar
Mladen Kolar
· 0 min read
URL
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.
Type
Publication
International Conference on Artificial Intelligence and Statistics (AISTATS)
publication
Lingxiao Wang
Authors

I am currently a Research Assistant Professor at the Toyota Technological Institute at Chicago. I recevied my Ph.D. in Department of Computer Science at the University of California, Los Angeles, where I was advised by Professor Quanquan Gu. Previously I obtained my MS in Statistics at University of Washington.

My research interests are broadly in machine learning including privacy-preserving machine learning, optimization, federated learning, deep learning, low-rank matrix recovery, high-dimensional statistics and data mining.

Personal website

Boxin Zhao
Authors
PhD (2020-2025)

Boxin Zhao was a PhD student in Econometrics and Statistics at University of Chicago, Booth School of Business. His research interests include probabilistic graphical models, functional data analysis and distributed learning, with a focus on developing novel methodologies with both practical applications and theoretical guarantees.

Personal website

Mladen Kolar
Authors
Professor of Data Sciences and Operations
Mladen Kolar is a Professor of Data Sciences and Operations at the University of Southern California Marshall School of Business and a Visiting Professor of Statistics and Data Science at Mohamed bin Zayed University of Artificial Intelligence. Before joining USC, he was on the faculty of the University of Chicago Booth School of Business. His research is focused on high-dimensional statistical methods, graphical models, varying-coefficient models and data mining, driven by the need to uncover interesting and scientifically meaningful structures from observational data. He is a Fellow of the Institute of Mathematical Statistics.