論文の概要: An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise

• arxiv url: http://arxiv.org/abs/2508.10879v1
• Date: Thu, 14 Aug 2025 17:48:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-15 22:24:48.44047
• Title: An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise
• Title（参考訳）: 適応雑音を考慮した微分プライベート$k$-PCAの反復アルゴリズム
• Authors: Johanna Düngler, Amartya Sanyal,
• Abstract要約: 任意の$k leq d$に対してトップ$k$固有ベクトルを推定できるアルゴリズムを提案する。 我々のアルゴリズムは、$n = tilde!O(d)$ であっても、ほぼ最適統計誤差を達成する。
• 参考スコア（独自算出の注目度）: 8.555773470114698
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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.
• Abstract（参考訳）: n$ i.d. ランダム行列$A_i \in \mathbb{R}^{d \times d}$が共通の期待値である$\Sigma$を与えられた場合、微分プライベート確率PCAの目的は、各$A_i$の差分プライバシー(DP)を保ちながら、最大分散方向をキャプチャする次元$k$の部分空間を特定することである。 既存のメソッドも。 (i)$A_i$のガウス的仮定の下でさえ、次元$d$で超直線的にスケールするにはサンプルサイズ$n$が必要である。 (i)$A_i$の内在的ランダム性が小さい場合であっても、DPに対して過剰ノイズを導入する。 Liu et al (2022a) はガウス以下のデータに対するこれらの問題に対処したが、そのアルゴリズム DP-PCA を用いてトップ固有ベクトル (k=1$) を推定するためにのみ対処した。 上記の2つの制限を克服しつつ、任意の$k \leq d$に対して最上位の$k$固有ベクトルを推定できる最初のアルゴリズムを提案する。 k=1$のアルゴリズムはDP-PCAの実用性保証と一致し、$n = \tilde{\! O(d)$。 さらに、一般の$k > 1$に対してより低いバウンダリを提供し、上位バウンダリを$k$に設定し、同等のベースラインに対するアルゴリズムの利点を実験的に示す。

関連論文リスト

• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。 我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
  論文  参考訳（メタデータ） (2024-05-30T18:20:35Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
  DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。 準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
  論文  参考訳（メタデータ） (2022-05-27T02:02:17Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)
• Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing [22.337756118270217]
  基本統計量に対する2つの方法を開発した:$epsilon$-corrupted set of $n$ sample from a $d$-linear sub-Gaussian distribution。 最初のロバストなアルゴリズムは反復フィルタリングを時間内に実行し、近似固有ベクトルを返し、単純なフィルタリングアプローチに基づいている。 私たちの2つめは、わずかに悪い近似係数を達成し、軽度のスペクトルギャップ仮定の下でほぼ自明な時間とイテレーションで実行します。
  論文  参考訳（メタデータ） (2020-06-12T07:45:38Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。