# Differentially Private Matrix Completion Revisited

arXiv: https://arxiv.org/abs/1712.09765 · HTML: https://mlsanity.com/paper/1712.09765/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2017.

## Built on by (most cited first, 8 of 8)

- [Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates](https://mlsanity.com/paper/2107.09802/) (2021)
- [Clients Collaborate: Flexible Differentially Private Federated Learning with Guaranteed Improvement of Utility-Privacy Trade-off](https://mlsanity.com/paper/2402.07002/) (2024)
- [Private Learning with Public Features](https://mlsanity.com/paper/2310.15454/) (2023)
- [Differential Privacy with Random Projections and Sign Random Projections](https://mlsanity.com/paper/2306.01751/) (2023)
- [Multi-Task Differential Privacy Under Distribution Skew](https://mlsanity.com/paper/2302.07975/) (2023)
- [Private Matrix Factorization with Public Item Features](https://mlsanity.com/paper/2309.11516/) (2023)
- [Noise is All You Need: Private Second-Order Convergence of Noisy SGD](https://mlsanity.com/paper/2410.06878/) (2024)
- [Introducing the Huber mechanism for differentially private low-rank matrix completion](https://mlsanity.com/paper/2206.07910/) (2022)

## Abstract (arXiv)

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 ω(n5/4), where n is the number of items, and each user provides her preference for at least √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.