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