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.
Lingxiao Wang
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.
Boxin Zhao
PhD student
Boxin Zhao is 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.
Mladen Kolar
Associate Professor of Econometrics and Statistics
Mladen Kolar is an Associate Professor of Econometrics and Statistics at 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.