論文の概要: Tight Differentially Private PCA via Matrix Coherence

• arxiv url: http://arxiv.org/abs/2510.26679v1
• Date: Thu, 30 Oct 2025 16:47:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-31 16:05:09.907644
• Title: Tight Differentially Private PCA via Matrix Coherence
• Title（参考訳）: マトリックスコヒーレンスによる高感度PCA
• Authors: Tommaso d'Orsi, Gleb Novikov,
• Abstract要約: 特異値分解と標準摂動機構に基づく単純で効率的なアルゴリズムが、プライベートランク-r$近似を返すことを示す。 私たちの推定器は、いくつかの体制において、芸術の状態を著しく上回ります。 我々は、同様の挙動がグラフの植込み問題を含む他の構造化モデルに対して成り立つと推測する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 我々は、差分プライバシーの下で行列のトップ$r$特異ベクトル$u_1, \ldots, u_r$の幅を計算するタスクを再考する。 特異値分解と標準摂動機構に基づく単純かつ効率的なアルゴリズムは、誤差が$u_1, \ldots, u_r$の \emph{rank-$r$ coherence} とスペクトルギャップ$\sigma_r - \sigma_{r+1}$にのみ依存するプライベートランク-$r$近似を返す。 これにより、Hardt and Roth~\cite{hardt2013beyond} の主張が解決される。 われわれの推定値は、一部の政権で最先端の状況を上回っている。 特に、密接な環境では、Wishartモデルにおける単一スパイクPCAが最適な非プライベートアルゴリズムで達成されるのに対して、以前のプライベートアルゴリズムでは達成できなかったのと同じ保証を達成することを示す。 さらに、(rank-$r$)コヒーレンスがガウス摂動の下では増加しないことを示す。 これは、ガウス機構に基づく任意の推定器が入力のコヒーレンスを保っていることを意味する。 我々は、同様の挙動がグラフの植込み問題を含む他の構造化モデルに対して成り立つと推測する。 グラフ問題へのコヒーレンスの適用についても検討する。 特に、低コヒーレンス仮定下でのマックス・クートや他の制約満足度問題に対する微分プライベートアルゴリズムを提案する。

関連論文リスト

• Differential Privacy in Kernelized Contextual Bandits via Random Projections [8.658538065693206]
  コンテキストによるカーネルの帯域幅の問題について考察する。 基礎となる報酬関数は、既知の再生ケルネルヒルベルト空間に属する。 我々は、$widetildemathcalO(sqrtgamma_TT+fracgamma_Tvarepsilon_mathrmDP)の最先端の累積後悔を実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-18T03:54:49Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。 DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。 本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
  論文  参考訳（メタデータ） (2024-11-27T00:48:48Z)
• Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More [5.893651469750359]
  マルチウェイカットと最小$k$cutのためのエッジ微分プライベートアルゴリズムを導入する。 最小$k$-cut問題に対して、指数的メカニズムと近似$k$-cutの数の有界性を組み合わせた別のアプローチを用いる。
  論文  参考訳（メタデータ） (2024-07-09T14:46:33Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)

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

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