Introduction
Recommender systems face a fundamental "privacy-utility" tension. To provide high-quality suggestions, these systems must identify behavioral patterns among similar users. However, sharing these individualized patterns exposes users to de-anonymization attacks. While Differential Privacy (DP) provides a rigorous mathematical framework to mitigate these risks, existing implementations are often custom-built, slow, and difficult to scale.
This paper introduces a high-performance approach to differentially private matrix factorization. By linking DP to Bayesian posterior sampling via Stochastic Gradient Langevin Dynamics (SGLD), the authors demonstrate that existing models can be retrofitted for privacy with minimal code changes. The resulting system not only provides strong privacy guarantees but also outperforms state-of-the-art non-private systems by up to 3x on a single machine.
Methodology
Bayesian Privacy via SGLD
The core insight of this work is that sampling from a Bayesian posterior distribution is inherently differentially private. The authors utilize Stochastic Gradient Langevin Dynamics (SGLD), which modifies standard Stochastic Gradient Descent (SGD) by adding a calibrated amount of Gaussian noise to the updates. This noise serves a dual purpose: it enables sampling from the posterior to prevent overfitting and provides the necessary stochasticity required for DP.
To satisfy formal DP requirements, the influence of any single user must be bounded. The authors implement "trimming" (randomly deleting ratings from high-volume "whale" users) and reweighting. Furthermore, they introduce Personalized DP, allowing users to select individual privacy levels by adjusting a weight parameter ($w_i$), effectively creating a "privacy slider" for end-users.
Systems Optimization
To achieve industry-leading performance, the authors implemented several low-level optimizations:
- Cache-Aware Design: Recommendation data typically follows a power-law distribution. By identifying the most frequently rated items and pinning them to the CPU's L1/L2 cache, the system achieves massive bandwidth gains.
- Gaussian Lookup Tables: To avoid the high computational cost of generating random numbers, the system uses pre-computed tables of Gaussian noise.
- Pipelining: A multi-threaded architecture hides disk I/O latency behind active computation.
Datasets
The system was evaluated on two massive benchmarks:
- Netflix Prize Dataset: 99 million ratings from 480,000 customers across 18,000 movies.
- Yahoo Music Dataset: Approximately 263 million ratings of 635,000 items by 1 million users. This dataset's scale and sparsity make it particularly challenging for cache efficiency.
Key Results
Performance and Scalability
The system demonstrates exceptional throughput, generating up to 8.5 million recommendations per second for 1024-dimensional models on a single PC. It handles 2048-dimensional models on the Netflix dataset in approximately 10 seconds per iteration, a task that typically takes minutes using standard RAM-bound approaches.
Accuracy-Privacy Tradeoff
The privacy-accuracy tradeoff is highly favorable. As shown in the comparative analysis, Fast SGLD achieves stable Root Mean Square Error (RMSE) significantly faster than previous standards like GraphChi. Even with meaningful privacy guarantees, the RMSE remains close to that of non-private SGD.
Conclusion
By bridging the gap between Bayesian inference and Differential Privacy, this work proves that privacy does not have to come at the cost of performance. The proposed system provides a scalable, efficient, and easily implementable framework for modern recommender systems, outperforming existing non-private benchmarks while maintaining rigorous data protection.
Summary updated