Differentially Private Matrix Completion Revisited
  We provide the first provably joint differentially private algorithm with
formal utility guarantees for the problem of user-level privacy-preserving
collaborative filtering. Our algorithm is based on the Frank-Wolfe method, and
it consistently estimates the underlying preference matrix as long as the
number of users $m$ is $\omega(n^{5/4})$, where $n$ is the number of items, and
each user provides her preference for at least $\sqrt{n}$ randomly selected
items. Along the way, we provide an optimal differentially private algorithm
for singular vector computation, based on the celebrated Oja's method, that
provides significant savings in terms of space and time while operating on
sparse matrices. We also empirically evaluate our algorithm on a suite of
datasets, and show that it consistently outperforms the state-of-the-art
private algorithms.
