{"id":6108,"date":"2025-08-15T07:00:40","date_gmt":"2025-08-15T07:00:40","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/08\/15\/2508-10879\/"},"modified":"2025-08-15T07:00:40","modified_gmt":"2025-08-15T07:00:40","slug":"2508-10879","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/08\/15\/2508-10879\/","title":{"rendered":"An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise"},"content":{"rendered":"

An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2508.10879v1 Announce Type: new
\nAbstract: Given $n$ i.i.d. random matrices $A_i in mathbb{R}^{d times d}$ that share a common expectation $Sigma$, the objective of Differentially Private Stochastic PCA is to identify a subspace of dimension $k$ that captures the largest variance directions of $Sigma$, while preserving differential privacy (DP) of each individual $A_i$. Existing methods either (i) require the sample size $n$ to scale super-linearly with dimension $d$, even under Gaussian assumptions on the $A_i$, or (ii) introduce excessive noise for DP even when the intrinsic randomness within $A_i$ is small. Liu et al. (2022a) addressed these issues for sub-Gaussian data but only for estimating the top eigenvector ($k=1$) using their algorithm DP-PCA. We propose the first algorithm capable of estimating the top $k$ eigenvectors for arbitrary $k leq d$, whilst overcoming both limitations above. For $k=1$ our algorithm matches the utility guarantees of DP-PCA, achieving near-optimal statistical error even when $n = tilde{!O}(d)$. We further provide a lower bound for general $k > 1$, matching our upper bound up to a factor of $k$, and experimentally demonstrate the advantages of our algorithm over comparable baselines.<\/div>\n

\t

\n
<\/BR>
\n Johanna D"ungler, Amartya Sanyal
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise arXiv:2508.10879v1 Announce Type: new Abstract: Given $n$ i.i.d. random matrices $A_i in mathbb{R}^{d times d}$ that share a common expectation $Sigma$, the objective of Differentially Private Stochastic PCA is to identify a subspace of dimension $k$ that captures the largest variance directions of $Sigma$, while […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,412,414,113,415,190,112,191],"tags":[778,2647,2753],"class_list":["post-6108","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-cr","category-cs-it","category-cs-lg","category-math-it","category-math-st","category-stat-ml","category-stat-th","tag-algorithm","tag-dp","tag-pca"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/6108"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=6108"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/6108\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=6108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=6108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=6108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}