Source-linked AI summary
Fast Differentially Private Matrix Factorization
Ziqi Liu, Yu-Xiang Wang, Alexander J. Smola
TL;DR
Collaborative filtering benefits from sharing preferences, but individualized behavioral patterns can raise privacy concerns. This paper applies posterior sampling via SGLD to differentially private matrix factorization. It reports roughly threefold speed over GraphChi and favorable privacy–accuracy tradeoffs, while noting convergence challenges as models grow more complex.
Problem
Method
The paper uses Bayesian posterior sampling via SGLD for differentially private matrix factorization, with personalized privacy calibration and efficient updates.
Source: §1 · pp. 1–2, §3.1 · p. 4Results
Approximately 3 times as fast as GraphChi, the matrix-factorization system is reported to retain good utility with a favorable privacy–accuracy tradeoff.
Source: §7 · p. 11Takeaways & Limitations
The authors conclude that collaborative filtering can achieve accuracy, speed, and privacy without significant sacrifice on any of them.
Source: §7 · p. 11SGLD convergence worsens for more complex models, possibly because sampling a larger state space slows mixing.
Source: §6.3 · p. 9
Abstract
from arXiv · showhide
Differentially private collaborative filtering is a challenging task, both in terms of accuracy and speed. We present a simple algorithm that is provably differentially private, while offering good performance, using a novel connection of differential privacy to Bayesian posterior sampling via Stochastic Gradient Langevin Dynamics. Due to its simplicity the algorithm lends itself to efficient implementation. By careful systems design and by exploiting the power law behavior of the data to maximize CPU cache bandwidth we are able to generate 1024 dimensional models at a rate of 8.5 million recommendations per second on a single PC.
1. INTRODUCTION
Recommender systems need to share preferences to improve recommendations, yet individualized patterns can expose sensitive behavior. The paper proposes combining differential privacy with efficient matrix factorization to address that tension.
1. INTRODUCTION
- The introduction frames the core tension as useful sharing of similar users’ preferences versus privacy risks from individualized behavioral patterns.Such patterns are described as facilitating user de-anonymization [36].Source: §1 · p. 1
- The approach uses posterior sampling, such as SGLD, to obtain sufficiently private estimates for matrix-factorization recommenders without custom-designing a statistical model.The authors say existing inference algorithms can be reused with a trivial modification.Source: §1 · p. 1
- 3 times faster than GraphChi on identical hardware, the system achieves peak numerical performance for recommendation by exploiting the data’s power-law properties.The comparison is against GraphChi, described as a state-of-the-art recommender system.Source: §1 · p. 1
- The framework combines cache-efficient matrix factorization for general SGD updates with SGLD bookkeeping that avoids adding Gaussian noise to the whole parameter space at every update.Source: §1 · p. 2
- The paper proposes sampling from a scaled posterior to guarantee user-level differential privacy and calibrating privacy and accuracy individually for each user.Source: §1 · p. 2
- Experiments report high efficiency and a favorable privacy–accuracy tradeoff that nearly matches non-private systems at meaningful privacy levels.Source: §1 · p. 2
2. BACKGROUND
The background introduces collaborative filtering, differential privacy, and computer architecture as ingredients for the approach. It motivates posterior sampling for privacy and cache-aware processing for speed.
2.1 Collaborative Filtering
- Collaborative filtering estimates missing ratings with low-rank user and item factors; this paper focuses on a simple inner-product model with bias and uses its Bayesian interpretation.The background contrasts SGD’s speed and cache locality with ALS’s conditional convexity.Source: §2.1 · p. 2
2.2 Differential Privacy
- Differential privacy limits how much a randomized algorithm’s output changes when one data point is replaced, while posterior sampling can provide private estimates when the sampler is sufficiently converged.The background also notes that equal per-user privacy can limit the influence of users who submit many reviews.Source: §2.2 · p. 3
2.3 Computer Architecture
- User and item accesses are highly nonuniform, a property that can be exploited to use CPU cache bandwidth more effectively than disk or main-memory access.The paper identifies retaining frequently reused movies in cache as a key throughput strategy.Source: §2.3 · p. 3
- Table 1 reports single-threaded performance on a 2011 MacBook Pro; the L1 and L3 bandwidth ranges reflect different packet sizes.Source: Table 1 · p. 3
3. DIFFERENTIALLY PRIVATE MATRIX FACTORIZATION
The paper makes matrix-factorization recommendation differentially private by preprocessing user ratings and sampling from a scaled posterior. It also personalizes privacy through per-user weights, while arguing that sampling retains useful predictive accuracy.
3. DIFFERENTIALLY PRIVATE MATRIX FACTORIZATION
- Trimming or reweighting users with many ratings controls their contribution to the privacy bound; neither procedure changes the underlying subspace if the fully observed matrix is truly low-dimensional.The bound uses each user’s rating count capped at τ, their weight, and a bounded rating-loss term.Source: §3 · p. 4
- Exact sampling gives ε-differential privacy, while sampling from a distribution δ away in L1 gives (ε, (1 + e^ε)δ)-differential privacy.The mechanism uses a scaled posterior distribution, with its scale adjusted to the chosen privacy parameter.Source: §3 · pp. 3–4
- At ε = 4B, one posterior sample is argued to retain near-optimal predictive accuracy under the stated consistency and asymptotic-normality conditions, while avoiding point-estimator collapse.For ε < 4B, the stated asymptotic relative efficiency is 1 + 4B/ε; monotonic rescaling leaves rating order unchanged.Source: §3 · p. 4
3.1 Personalized Differential Privacy
- User-specific weights let the method strengthen privacy for particular users, with privacy protection linear in each user’s assigned weight.At ε = 4B, the stated guarantee for user i is 2B_i-personalized differential privacy.Source: §3.1 · pp. 4–5
4. EFFICIENT SAMPLING VIA SGLD
The paper uses Stochastic Gradient Langevin Dynamics (SGLD) to sample from a posterior with updates resembling stochastic gradient descent plus Gaussian noise. As the step size shrinks, the method transitions toward noise-dominated sampling; the cited convergence results support its use for differentially private sampling.
4. EFFICIENT SAMPLING VIA SGLD
- SGLD updates the parameters using a stochastic gradient from one or a few ratings, then adds Gaussian noise to the update.The update is nearly the same as stochastic gradient descent, with the added noise enabling posterior sampling.Source: §4 · p. 5
- Far from convergence, the gradient dominates; as the step size shrinks near convergence, noise dominates and the update behaves like Brownian motion.The Metropolis-Hastings acceptance probability approaches 1 as the step size decreases, so the adjustment can be omitted as designed.Source: §4 · p. 5
- Convergence results support SGLD sampling after many iterations, and additional iterations can make δ arbitrarily small for the stated (ε, δ)-differential privacy guarantee.Source: §4 · p. 5
5. SYSTEM DESIGN
The system combines cache-aware processing, pipelining, prefetching, and SGLD-specific optimizations to reduce recommendation-model training costs. Its design exploits skewed item popularity and reports a large reduction against an estimated memory-traffic baseline.
5. SYSTEM DESIGN
- Approximately 10 seconds versus over 6 minutes for the estimated memory-traffic baseline on a 2,048-dimensional Netflix model; speedups combine cache efficiency, prefetching, pipelining, power-law use, and random-number-generation optimization.Source: §5 · p. 5
5.1 Processing Pipeline
- Processing users sequentially amortizes retrieval over their ratings and halves I/O, while pipelined disk reads hide latency and snapshots periodically save U and V.Source: §5.1 · p. 5
5.2 Cache Efficiency
- Popularity tiers exploit skewed ratings: the Top 500 fit in L1 and cover 44% of Netflix ratings, while the Next 4000 fit in L2; even at 2,048 dimensions, about 55% fit in cache.Batches of users preserve user vectors in cache; movie updates proceed in a Hogwild fashion without locks.Source: §5.2 · p. 6, Figure 1 · p. 6
5.3 Latency Hiding and Prefetching
- Prefetching requests the next movie vector before its rating update; for dimensions below 256, accurate prefetching can bring it into L1 cache.At larger dimensions, latent vectors may be too large to benefit from the lowest-level cache.Source: §5.3 · p. 6
5.4 Optimizations for SGLD
- SGLD’s per-rating gradient approximation is nonzero only for the active user-item pair, while repeated Gaussian-noise updates can be aggregated into one draw based on their count.The method relies on needing the user and item vectors only when a new rating triple is encountered.Source: §5.4 · p. 6
- A pre-generated Gaussian lookup table replaces costly random draws; contiguous segments with random offsets improve cache efficiency, but the approach’s effect on SGLD’s stationary distribution and privacy is unknown.Experiments found results indistinguishable for moderately sized finite lookup tables.Source: §5.4 · pp. 6–7
6. EXPERIMENTS AND DISCUSSION
The experiments compare recommender runtimes and accuracy across Netflix and Yahoo, then examine convergence, cache behavior, and privacy–accuracy trade-offs. They report faster C-SGD than GraphChi and GraphLab, while SGLD remains comparable to GraphChi in throughput.
6.1 Comparisons
- The comparisons include public CPU and GPU recommenders and closed-source GraphLab Create, alongside the authors’ SGD and SGLD solvers.GraphLab Create is described as slightly faster than GraphChi, but its closed-source status limits fine-grained diagnostics.Source: §6.1 · p. 7
6.2 Data
- Netflix contains 99M training ratings from 480k customers, while Yahoo Music contains almost 263M ratings from 1M users.The experiments use released validation sets; Yahoo ratings are rescaled to a 0–5 scale, and its larger item set presents additional cache-efficiency challenges.Source: §6.2 · p. 7
6.3 Runtime
- C-SGD is around 2 to 3 times faster than GraphChi and GraphLab while outperforming GraphChi in accuracy.The runtime comparison uses identical hardware; Figure 2 covers Netflix and Yahoo at factor dimensions 512 and 2048.Source: Figure 2 · p. 8, §6.3 · p. 9
- Fast SGLD has throughput comparable to GraphChi, but convergence worsens for more complex models, possibly because of slow mixing in the larger state space.The authors identify faster-mixing samplers that retain cache efficiency as future work.Source: §6.3 · p. 9
6.4 Convergence
- On 16-dimensional Netflix models, SGLD does not overfit; beyond 10,000 Gaussian lookup values, test RMSE is essentially indistinguishable from explicit sampling.Larger-dimensional models may need somewhat more lookup values; SGLD also requires burn-in, and careful learning-rate tuning is critical.Source: §6.4 · p. 9, Figure 6 · p. 10
6.5 Cache-efficient Design
- Cachegrind results show higher cache miss rates for GraphChi than C-SGD across dimensions.The authors attribute GraphChi’s less efficient access-frequency portfolio to its blockwise data traversal and link it to more frequent memory fetches.Source: Table 2 · p. 10, §6.5 · p. 10
6.6 Privacy and Accuracy
- The privacy–accuracy experiment trims users to at most 100 Netflix ratings or 200 Yahoo ratings and evaluates private models at dimension 16 across privacy budgets.Figure 7 plots local prediction utility against privacy loss.Source: §6.6 · p. 10
6.7 Rating privacy, user privacy and average personalized privacy
- With τ = 200, the authors report nearly no accuracy loss at rating-level privacy ϵ < 1, matching and slightly improving on Mcsherry and Mironov.They also report that a typical user’s personalized privacy loss in Figure 7 is about ϵ/25.Source: §6.7 · pp. 10–11
7. CONCLUSION
The paper presents efficient collaborative filtering compatible with differential privacy, aiming to preserve accuracy, speed, and privacy without significant sacrifice. Its implementation uses caching and latency hiding, and it introduces personalized differential privacy for users with different privacy needs.
7. CONCLUSION
- The algorithm accomplishes accuracy, speed, and privacy without significant sacrifice on any of these goals.The implementation exploits caching and latency hiding to obtain near-peak performance.Source: §7 · p. 11
- Personalized differential privacy defines and proves estimates that respect different privacy levels for individual users.The authors suggest this notion is relevant when users' privacy expectations vary with factors such as service cost and hardware quality.Source: §7 · p. 11
- Approximately 3 times as fast as GraphChi, the next-fastest recommender system, the implementation retains good utility with differentially private estimates.The authors describe this as an endorsement of Stochastic Gradient Langevin Dynamics for private recommender systems.Source: §7 · p. 11
APPENDIX
The appendix derives privacy guarantees for matrix-factorization posterior sampling, including personalized guarantees based on user-specific likelihood bounds. It also establishes sensitivity conditions and explains why retrying preserves the constrained sampling distribution.
APPENDIX
- The proof applies the exponential mechanism with utility −F(U,V) to establish ε-DP for the sampled output.The appendix relates the sampling distribution to a posterior whose user log-likelihood is bounded.Source: APPENDIX · pp. 11–12
- Because each user contributes one row and trimming/reweighting is applied, the sensitivity of F(U,V) is bounded under the stated constraints.The derivation also uses the rating range 1 ≤ r_ij ≤ 5 and constraints on U and V.Source: APPENDIX · p. 11
- The retry-if-fail procedure samples from the distribution conditioned on the parameter constraint without changing event-probability ratios.The proof states that retrying does not affect relative probabilities within the conditional distribution's support.Source: APPENDIX · p. 11
- Bounding one user's log-likelihood by B′ bounds the posterior probability ratio by e^2B′.The proof considers adding or removing a particular user.Source: APPENDIX · pp. 11–12
- A customized B′ subset yields personalized differential privacy for user x′.The appendix describes adjusting the subset using w.Source: APPENDIX · p. 12