Adaptive Power Iteration Method for Differentially Private PCA

• URL: http://arxiv.org/abs/2602.11454v2
• Date: Fri, 13 Feb 2026 02:41:02 GMT
• Title: Adaptive Power Iteration Method for Differentially Private PCA
• Authors: Ta Duy Nguyen, Alina Ene, Huy Le Nguyen,
• Abstract summary: We study $(,)$-differentially private algorithms for the problem of approximately computing the top singular vector of a matrix.<n>Our work departs from and complements the work by Hardt-Roth (STOC 2013) which designed a private power iteration method for the privacy model.
• Score: 20.48591080590442
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study $(ε,δ)$-differentially private algorithms for the problem of approximately computing the top singular vector of a matrix $A\in\mathbb{R}^{n\times d}$ where each row of $A$ is a datapoint in $\mathbb{R}^{d}$. In our privacy model, neighboring inputs differ by one single row/datapoint. We study the private variant of the power iteration method, which is widely adopted in practice. Our algorithm is based on a filtering technique which adapts to the coherence parameter of the input matrix. This technique provides a utility that goes beyond the worst-case guarantees for matrices with low coherence parameter. Our work departs from and complements the work by Hardt-Roth (STOC 2013) which designed a private power iteration method for the privacy model where neighboring inputs differ in one single entry by at most 1.

Related papers

• Tight Differentially Private PCA via Matrix Coherence [12.864472925970242]
  We show that a simple and efficient algorithm -- based on singular value decomposition and standard perturbation mechanisms -- returns a private rank-$r$ approximation.<n>Our estimator outperforms the state of the art -- significantly so in some regimes.<n>We conjecture that similar behavior holds for other structured models, including planted problems in graphs.
  arXiv  Detail & Related papers  (2025-10-30T16:47:26Z)
• An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise [8.555773470114698]
  We propose an algorithm capable of estimating the top $k$ eigenvectors for arbitrary $k leq d$.<n>Our algorithm achieves near-optimal statistical error even when $n = tilde!O(d)$.
  arXiv  Detail & Related papers  (2025-08-14T17:48:45Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  We introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm.<n>DaRRM is parameterized by a data-dependent noise function $gamma$, and enables efficient utility optimization over the class of all private algorithms.<n>We show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility.
  arXiv  Detail & Related papers  (2024-11-27T00:48:48Z)
• Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation [48.92318828548911]
  We present LoRa-PI (Low-Rank Policy Iteration), a model-free learning algorithm alternating between policy improvement and policy evaluation steps. LoRa-PI learns an $varepsilon$-optimal policy using $widetildeO(S+Aover mathrmpoly (1-gamma)varepsilon2)$ samples where $S$ denotes the number of states (resp. actions) and $gamma$ the discount factor.
  arXiv  Detail & Related papers  (2024-10-30T20:22:17Z)
• On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
  We study the problem of computing pairwise statistics, i.e., ones of the form $binomn2-1 sum_i ne j f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $tau$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc.
  arXiv  Detail & Related papers  (2024-06-24T04:06:09Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Improved Privacy-Preserving PCA Using Optimized Homomorphic Matrix Multiplication [0.0]
  Principal Component Analysis (PCA) is a pivotal technique widely utilized in the realms of machine learning and data analysis. In recent years, there have been endeavors to utilize homomorphic encryption in privacy-preserving PCA algorithms for the secure cloud computing scenario. We propose a novel approach to privacy-preserving PCA that addresses these limitations, resulting in superior efficiency, accuracy, and scalability compared to previous approaches.
  arXiv  Detail & Related papers  (2023-05-27T02:51:20Z)
• Private Matrix Approximation and Geometry of Unitary Orbits [29.072423395363668]
  This problem seeks to approximate $A$ by a matrix whose spectrum is the same as $Lambda$. We give efficient and private algorithms that come with upper and lower bounds on the approximation error.
  arXiv  Detail & Related papers  (2022-07-06T16:31:44Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
  DP-PCA is a single-pass algorithm that overcomes both limitations. For sub-Gaussian data, we provide nearly optimal statistical error rates even for $n=tilde O(d)$.
  arXiv  Detail & Related papers  (2022-05-27T02:02:17Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.