Tight Differentially Private PCA via Matrix Coherence

• URL: http://arxiv.org/abs/2510.26679v1
• Date: Thu, 30 Oct 2025 16:47:26 GMT
• Title: Tight Differentially Private PCA via Matrix Coherence
• Authors: Tommaso d'Orsi, Gleb Novikov,
• Abstract summary: 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.
• Score: 12.864472925970242
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the task of computing the span of the top $r$ singular vectors $u_1, \ldots, u_r$ of a matrix under differential privacy. We show that a simple and efficient algorithm -- based on singular value decomposition and standard perturbation mechanisms -- returns a private rank-$r$ approximation whose error depends only on the \emph{rank-$r$ coherence} of $u_1, \ldots, u_r$ and the spectral gap $\sigma_r - \sigma_{r+1}$. This resolves a question posed by Hardt and Roth~\cite{hardt2013beyond}. Our estimator outperforms the state of the art -- significantly so in some regimes. In particular, we show that in the dense setting, it achieves the same guarantees for single-spike PCA in the Wishart model as those attained by optimal non-private algorithms, whereas prior private algorithms failed to do so. In addition, we prove that (rank-$r$) coherence does not increase under Gaussian perturbations. This implies that any estimator based on the Gaussian mechanism -- including ours -- preserves the coherence of the input. We conjecture that similar behavior holds for other structured models, including planted problems in graphs. We also explore applications of coherence to graph problems. In particular, we present a differentially private algorithm for Max-Cut and other constraint satisfaction problems under low coherence assumptions.

Related papers

• Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits [0.8122270502556375]
  We present the first algorithms for generalized linear contextual bandits under shuffle differential privacy and joint differential privacy.<n>For adversarial contexts, we provide a joint-DP algorithm with $tildeO(dsqrtT/sqrtvarepsilon)$ regret.
  arXiv  Detail & Related papers  (2026-01-31T00:15:20Z)
• Differential Privacy in Kernelized Contextual Bandits via Random Projections [8.658538065693206]
  We consider the problem of contextual kernel bandits with contexts.<n>The underlying reward function belongs to a known Reproducing Kernel Hilbert Space.<n>We propose a novel algorithm that achieves the state-of-the-art cumulative regret of $widetildemathcalO(sqrtgamma_TT+fracgamma_Tvarepsilon_mathrmDP)$
  arXiv  Detail & Related papers  (2025-07-18T03:54:49Z)
• Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
  We investigate the Generalized Gaussian mechanism, which samples the additive noise term $x$ with probability proportional to $e-frac| x |sigmabeta $ for some $beta geq 1$.<n>We show that privacy accounting for the GG Mechanism and its variants is independent, which substantially improves computational costs of privacy accounting.
  arXiv  Detail & Related papers  (2025-06-14T15:49:25Z)
• On the Price of Differential Privacy for Hierarchical Clustering [21.64775530337936]
  We present a novel algorithm in the weight privacy model that shows significantly better approximation than known impossibility results in the edge-level DP setting.<n>Our results show that our algorithm performs well in terms of extra cost and has good scalability to large graphs.
  arXiv  Detail & Related papers  (2025-04-22T04:39:40Z)
• Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
  Under privacy constraints, the complexity of private linear regression is emphnot captured by the usual covariance matrix.<n>We introduce an Information-Weighted Regression method that attains the optimal rates.<n> Notably, our results demonstrate that joint privacy comes at almost no additional cost.
  arXiv  Detail & Related papers  (2025-02-18T18:35:24Z)
• 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)
• Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More [5.893651469750359]
  We introduce edgedifferentially private algorithms for the multiway cut and the minimum $k$cut.<n>For the minimum $k$-cut problem we use a different approach, combining the exponential mechanism with bounds on the number of approximate $k$-cuts.
  arXiv  Detail & Related papers  (2024-07-09T14:46:33Z)
• 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)
• Differential Privacy for Clustering Under Continual Observation [5.220940151628734]
  We consider the problem of clustering privately a dataset in $mathbbRd$ that undergoes both insertion and deletion of points. We give an $varepsilon$-differentially private clustering mechanism for the $k$-means objective under continual observation.
  arXiv  Detail & Related papers  (2023-07-07T07:23:56Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. We introduce a emphmisspecified kernelized bandit setting where the unknown function can be $epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS) We show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
  arXiv  Detail & Related papers  (2021-11-09T09:00:02Z)

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.