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

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 57 references that are in the map.
- First posted on arXiv 20 Jul 2021.

## Builds on (most cited first, 21 of 21)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Variational Autoencoders for Collaborative Filtering](https://mlsanity.com/paper/1802.05814/) (2018)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Private Selection from Private Candidates](https://mlsanity.com/paper/1811.07971/) (2018)
- [RecVAE: a New Variational Autoencoder for Top-N Recommendations with Implicit Feedback](https://mlsanity.com/paper/1912.11160/) (2019)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [On the Difficulty of Evaluating Baselines: A Study on Recommender Systems](https://mlsanity.com/paper/1905.01395/) (2019)
- [Understanding Unintended Memorization in Federated Learning](https://mlsanity.com/paper/2006.07490/) (2020)
- [Is Private Learning Possible with Instance Encoding?](https://mlsanity.com/paper/2011.05315/) (2020)
- [Fast Differentially Private Matrix Factorization](https://mlsanity.com/paper/1505.01419/) (2015)
- [Fast matrix completion without the condition number](https://mlsanity.com/paper/1407.4070/) (2014)
- [Fast Exact Matrix Completion with Finite Samples](https://mlsanity.com/paper/1411.1087/) (2014)
- [Computational Limits for Matrix Completion](https://mlsanity.com/paper/1402.2331/) (2014)
- [Differentially Private Matrix Completion Revisited](https://mlsanity.com/paper/1712.09765/) (2017)

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

- [Optimal Differentially Private PCA and Estimation for Spiked Covariance Matrices](https://mlsanity.com/paper/2401.03820/) (2024)
- [Differentially Private Image Classification from Features](https://mlsanity.com/paper/2211.13403/) (2022)
- [Modeling Recommender Ecosystems: Research Challenges at the Intersection of Mechanism Design, Reinforcement Learning and Generative Models](https://mlsanity.com/paper/2309.06375/) (2023)
- [(Nearly) Optimal Private Linear Regression via Adaptive Clipping](https://mlsanity.com/paper/2207.04686/) (2022)
- [Private Learning with Public Features](https://mlsanity.com/paper/2310.15454/) (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)
- [Introducing the Huber mechanism for differentially private low-rank matrix completion](https://mlsanity.com/paper/2206.07910/) (2022)
- [Near-Optimal differentially private low-rank trace regression with guaranteed private initialization](https://mlsanity.com/paper/2403.15999/) (2024)
- [A Linearized Alternating Direction Multiplier Method for Federated Matrix Completion Problems](https://mlsanity.com/paper/2503.12733/) (2025)

## Abstract (arXiv)

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.