The Price of Privacy for Low-rank Factorization

Jalaj UpadhyayNeurIPS 2018 · OpenReview

Low-rank factorization (LRF) is a workhorse of modern data science, powering everything from recommendation engines to search algorithms. However, the matrices involved often contain highly sensitive information, such as user-item ratings or medical records. While non-private LRF is well-understood, making it differentially private—ensuring that the output doesn't leak specific details about any single entry or row—introduces significant hurdles.

This paper presents the first set of differentially private (DP) algorithms for low-rank matrix factorization that are optimized for real-world constraints like streaming data, arbitrary updates, and distributed systems. The authors prove that their approach achieves optimal accuracy and space complexity, essentially showing that the "price of privacy" in these complex settings is far lower than previously thought.

The Challenges of Private LRF

Transitioning LRF to a differentially private framework involves overcoming three primary challenges:

  1. Dynamic Updates: In practice, data isn't static. It arrives row-by-row or via "turnstile" updates (where any entry can be modified at any time).
  2. Distributed Data: Data is often spread across multiple servers, making communication costs a bottleneck.
  3. Efficiency vs. Accuracy: Previous private algorithms were either too slow, required too much memory, or produced results with high "additive error" (noise) that rendered them useless for large-scale applications.

A Unified Approach: PRIVATE-OPTIMAL-LRF

To tackle these challenges, the authors propose a unified "Meta-Algorithm" that relies on three main pillars:

  • Linear Sketching: Instead of processing the full matrix, the algorithm maintains "sketches"—compact, compressed representations of the matrix created using random projections. Because these sketches are linear, they can easily handle additions and subtractions in a data stream.
  • Hybrid Perturbation: To ensure privacy, the authors combine input perturbation (adding noise to the sketches) and output perturbation. They introduce two privacy notions: Priv1 (protecting against changes of a rank-1 update) and Priv2 (protecting against changes within a fixed Frobenius norm).
  • Advanced Post-Processing: Simply adding noise to a sketch usually ruins accuracy. The authors use sophisticated linear algebra and optimization techniques to "clean" the noisy sketches, extracting the top-$k$ singular components while filtering out the privacy-induced noise.
Summary of theoretical results across different update models and privacy notions.

Key Insights and Theoretical Optimality

The paper introduces several theoretical breakthroughs that challenge previous assumptions about private LRF:

  • Privacy Doesn't Require "Separation": Previous works often assumed "singular value separation" (a large gap between the $k$-th and $(k+1)$-th singular values) to achieve good results. This paper shows that with clever post-processing, optimal accuracy can be achieved without this restrictive assumption.
  • Optimal Space Complexity: The authors prove that their algorithms use $O((m+n)k/\alpha)$ space, which matches the lower bounds for non-private algorithms up to logarithmic factors. In other words, privacy is almost "free" in terms of memory.
  • Continual Release: The paper provides the first instance of an algorithm that can release a private LRF continually as a stream progresses, rather than just once at the very end.
  • Communication Efficiency: In distributed settings, the communication cost is independent of the matrix dimensions, making it highly scalable for massive datasets spread across many servers.
Comparison of the proposed algorithms against prior work and theoretical lower bounds.

Results and Performance

The algorithm achieves a $(1+\alpha)$ multiplicative error with an additive error term that is theoretically optimal. As detailed in the comparative tables, the proposed algorithm consistently incurs lower additive error than prior state-of-the-art methods like the Hardt-Roth algorithm, especially as the target rank $k$ or the privacy parameter $\epsilon$ varies.

The authors complemented their positive results with a mathematical proof showing that no randomized algorithm can use significantly less space than theirs while maintaining the same accuracy in a turnstile model.

Limitations and Future Work

While the theoretical guarantees are robust, there are a few practical considerations:

  • Incoherence Assumptions: Empirical tests were primarily performed on synthetic, incoherent (random) matrices. Performance on highly structured or "sparse" real-world data might require further tuning of the sketching parameters.
  • Computational Overhead of SVD: The post-processing involves multiple Singular Value Decompositions (SVDs) on the sketches. While sketches are small, performing these operations continually in a high-velocity stream could still be computationally demanding.
  • Hyperparameter Sensitivity: The algorithm relies on several parameters that must be carefully set based on the desired privacy budget and accuracy. Automating this tuning for non-experts remains a potential area for future work.

Summary updated

Abstract

In this paper, we study what price one has to pay to release \emph{differentially private low-rank factorization} of a matrix. We consider various settings that are close to the real world applications of low-rank factorization: (i) the manner in which matrices are updated (row by row or in an arbitrary manner), (ii) whether matrices are distributed or not, and (iii) how the output is produced (once at the end of all updates, also known as \emph{one-shot algorithms} or continually). Even though these settings are well studied without privacy, surprisingly, there are no private algorithm for these settings (except when a matrix is updated row by row). We present the first set of differentially private algorithms for all these settings. Our algorithms when private matrix is updated in an arbitrary manner promise differential privacy with respect to two stronger privacy guarantees than previously studied, use space and time \emph{comparable} to the non-private algorithm, and achieve \emph{optimal accuracy}. To complement our positive results, we also prove that the space required by our algorithms is optimal up to logarithmic factors. When data matrices are distributed over multiple servers, we give a non-interactive differentially private algorithm with communication cost independent of dimension. In concise, we give algorithms that incur {\em optimal cost across all parameters of interest}. We also perform experiments to verify that all our algorithms perform well in practice and outperform the best known algorithm until now for large range of parameters.
BibTeX
@inproceedings{upadhyay2018price,
  author = {Jalaj Upadhyay},
  title = {{The Price of Privacy for Low-rank Factorization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=HJZ7CUWdWB},
}
Figure