Abstract
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), our error bounds scale significantly better with respect to the number of items and users. Extensive validation on standard benchmarks demonstrate that the algorithm, in combination with carefully designed sampling procedures, is significantly more accurate than existing techniques, promising to be the first practical DP embedding model.
Introduction
Matrix completion is the foundational technology behind modern recommendation systems, used by platforms like Netflix and Amazon to predict user preferences. By factorizing a sparse matrix of user-item ratings into low-rank embeddings, these systems can suggest content with high accuracy. However, these embeddings are sensitive; they can inadvertently leak private user information.
While Differential Privacy (DP) offers a robust framework for protecting data, applying it to matrix completion has historically resulted in a significant "utility gap." Previous private algorithms often introduced so much noise that recommendations became barely better than random. This paper introduces DPALS (Differentially Private Alternating Least Squares), a method that bridges this gap by providing strong user-level privacy without sacrificing practical accuracy.
The Challenge of User-Level Privacy
Protecting privacy in recommendation systems is particularly difficult due to the requirement of user-level privacy. While protecting a single rating (entry-level privacy) is straightforward, user-level privacy requires protecting all ratings provided by a single user. Because a user's preferences are highly correlated across different items, a single user's data has a high "sensitivity," meaning it can significantly influence the final model. Traditional DP methods often struggle to scale to millions of items while maintaining this level of protection.
The DPALS Method
The authors build upon the standard Alternating Least Squares (ALS) algorithm, which iteratively updates user embeddings ($U$) and item embeddings ($V$). The key innovation is the use of Joint Differential Privacy (Joint DP). In this framework, the item embeddings are maintained by a central server and updated with added Gaussian noise to ensure privacy. Users, however, compute their own embeddings locally using their private data and the shared (noisy) item embeddings.
This architecture naturally decouples the optimization process. Because users are processed independently, noise does not accumulate across the user dimension during a single update step, making ALS inherently more "privacy-friendly" than standard gradient-descent methods.
Key Insights: Decoupling and Adaptive Sampling
Beyond the core algorithm, the paper identifies several critical heuristics for practical performance:
- Noisy Power Iteration: ALS requires a strong starting point. The authors use a private version of power iteration to initialize item embeddings, proving it requires far fewer users ($n \approx m$) than standard private PCA techniques ($n \approx m\sqrt{m}$).
- Adaptive Sampling: Recommendation data typically follows a power-law distribution. Standard uniform sampling in DP can increase skew, making rare items impossible to learn. DPALS uses adaptive sampling to oversample "rare" items, balancing the signal-to-noise ratio across the dataset.
- Clipping and Frequency Filtering: To manage sensitivity, user embeddings are clipped to a fixed norm. Additionally, at high privacy regimes, the algorithm focuses on training frequent items while using global averages for the "long tail" where noise would otherwise overwhelm the signal.
Empirical Performance
DPALS was evaluated against several baselines, including Private Frank-Wolfe (DPFW) and Private SVD (DPSVD), on standard benchmarks like MovieLens 10M and 20M.
The results demonstrate a significant leap in utility:
- Accuracy Boost: On ML-10M, DPALS achieved a 7% to 11.6% relative improvement in RMSE over the previous state-of-the-art (DPFW).
- Data Efficiency: DPALS reached the same error rates as previous methods using only 23% of the user data.
- Real-world Viability: On the larger MovieLens 20M dataset, DPALS achieved a Recall@20 of ~34%, coming remarkably close to the non-private ALS baseline of ~36%.
Conclusion
DPALS represents a major step forward in making differentially private recommendation systems practical. By combining a rigorous global convergence analysis with clever sampling heuristics, the authors demonstrate that it is possible to achieve near-optimal sample complexity and high utility. While challenges remain regarding hyperparameter sensitivity and rank dependence, DPALS provides a scalable and effective foundation for the next generation of privacy-preserving machine learning models.
Summary updated