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

Steve Chien, Prateek Jain, Walid Krichene, Steffen Rendle, Shuang Song, Abhradeep Thakurta, Li Zhang

Introduction

Recommendation systems rely heavily on "matrix completion"—predicting how a user might rate an item based on a sparse history of previous ratings. However, because these ratings are highly sensitive, standard models can inadvertently leak a user's personal preferences, making privacy a major concern.

While Differential Privacy (DP) offers a mathematical gold standard for protection, applying it to matrix completion has historically been difficult. Previous attempts often suffered from two major flaws:

  1. Poor Utility: The noise required to guarantee privacy often "drowned out" the signal, leading to inaccurate recommendations.
  2. Poor Scaling: Theoretical bounds for existing methods (like Private Frank-Wolfe) required an unrealistic number of ratings per user to guarantee convergence.

The challenge is to protect user-level privacy (protecting all ratings from a single user simultaneously) while maintaining the high accuracy and scalability that non-private algorithms provide. To solve this, researchers introduce DPALS, a differentially private version of the popular Alternating Least Squares (ALS) algorithm that achieves state-of-the-art accuracy and theoretical convergence rates.

The DPALS Algorithm

DPALS adapts the standard ALS algorithm into a private framework. Standard ALS works by alternating between two steps: fixing item embeddings to solve for user embeddings, and then fixing user embeddings to solve for item embeddings.

DPALS makes this process private using a Joint Differential Privacy (JDP) approach:

  • Decoupled Updates: The item embeddings are made public (but protected by DP noise), while each user independently computes their own private embedding. This prevents noise from accumulating across users during the optimization process.
  • Noise Injection & Clipping: To bound the "sensitivity" (how much one user's data can change the model), the algorithm clips user embeddings to a fixed norm and adds Gaussian noise to the item embedding updates.
Block schematic of the DPALS algorithm showing the flow between private user computations and the public, noise-protected item solver.

Practical Heuristics for Data Skew

Real-world data is naturally skewed—a few popular movies receive the vast majority of ratings. In a private setting, rare items easily get lost in the injected noise. The authors introduced two key fixes to make DPALS practical:

  1. Learning on Frequent Items: The algorithm partitions items and focuses training on the most frequent ones to ensure a high signal-to-noise ratio.
  2. Adaptive Sampling: Instead of picking ratings at random (which worsens popularity bias), DPALS prioritizes sampling ratings for rare items to help them "stand out" against the privacy noise.

Key Insights & Theoretical Gains

  • ALS is a Natural Fit for Privacy: Because ALS inherently decouples the optimization for each user and item, it is much more "privacy-friendly" than Stochastic Gradient Descent (SGD). Noise does not need to be added at every tiny gradient step, preserving significantly more utility.
  • Tighter Theoretical Bounds: DPALS requires far fewer samples per user to converge compared to previous state-of-the-art methods. Specifically, it needs only polylogarithmic samples relative to the number of users, whereas previous methods required square-root scaling.

Empirical Results

The algorithm was evaluated on synthetic datasets as well as the standard MovieLens 10M (ML-10M) and MovieLens 20M (ML-20M) benchmarks. DPALS significantly outperformed the previous state-of-the-art, Private Frank-Wolfe (DPFW):

  • Accuracy Boost: On the ML-10M benchmark, DPALS achieved a 7% to 11.6% relative improvement in RMSE (Root Mean Square Error) over DPFW.
  • Competitive with Non-Private Models: On the ML-20M recommendation task, DPALS achieved a Recall@20 of roughly 34.5% (at a privacy budget of $\epsilon=20$), which is remarkably close to the non-private ALS performance of 36%.
  • Scalability: On synthetic data, DPALS showed a 7-fold improvement in error rates for large datasets compared to previous methods.
Privacy-utility trade-off curves on MovieLens datasets. DPALS (blue line) consistently stays closer to the non-private ALS baseline (green dashed line) than other private methods.

Limitations and Future Work

While DPALS is a major step forward for practical private recommendation systems, the authors note a few areas for future improvement:

  • Hyperparameter Sensitivity: The algorithm requires careful tuning of clipping parameters and sampling rates, which can be challenging to execute privately in practice.
  • Theoretical Dependencies: The current proofs have a high polynomial dependence on the rank and the condition number of the matrix, which might be tightened in future theoretical work.
  • Comparison with DPSGD: While ALS is highly effective for least-squares problems, a direct empirical comparison with modern DP-SGD variants for matrix factorization remains an open task for the community.

Summary updated

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) metho...
BibTeX
@inproceedings{chien2021private,
  author = {Steve Chien and Prateek Jain and Walid Krichene and Steffen Rendle and Shuang Song and Abhradeep Thakurta and Li Zhang},
  title = {{Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=3mzWaDUTTDb},
}
Figure