Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates

We study the problem of differentially private (DP) matrix completion under\nuser-level privacy. We design a joint differentially private variant of the\npopular Alternating-Least-Squares (ALS) method that achieves: i) (nearly)\noptimal sample complexity for matrix completion (in terms of number of items,\nusers), and ii) the best known privacy/utility trade-off both theoretically, as\nwell as on benchmark data sets. In particular, we provide the first global\nconvergence analysis of ALS with noise introduced to ensure DP, and show that,\nin comparison to the best known alternative (the Private Frank-Wolfe algorithm\nby Jain et al. (2018)), our error bounds scale significantly better with\nrespect to the number of items and users, which is critical in practical\nproblems. Extensive validation on standard benchmarks demonstrate that the\nalgorithm, in combination with carefully designed sampling procedures, is\nsignificantly more accurate than existing techniques, thus promising to be the\nfirst practical DP embedding model.\n