Fugu-MT 論文翻訳(概要): Tight Differentially Private PCA via Matrix Coherence

論文の概要: 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$)コヒーレンスがガウス摂動の下では増加しないことを示す。これは、ガウス機構に基づく任意の推定器が入力のコヒーレンスを保っていることを意味する。我々は、同様の挙動がグラフの植込み問題を含む他の構造化モデルに対して成り立つと推測する。グラフ問題へのコヒーレンスの適用についても検討する。特に、低コヒーレンス仮定下でのマックス・クートや他の制約満足度問題に対する微分プライベートアルゴリズムを提案する。

関連論文リスト

Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits [0.8122270502556375]
シャッフル差分プライバシーと連立差分プライバシーに基づく一般化線形文脈帯域のアルゴリズムを提案する。逆の文脈では、$tildeO(dsqrtT/sqrtvarepsilon)$ regret というジョイントDPアルゴリズムを提供する。
論文参考訳（メタデータ） (2026-01-31T00:15:20Z)
Differential Privacy in Kernelized Contextual Bandits via Random Projections [8.658538065693206]
コンテキストによるカーネルの帯域幅の問題について考察する。基礎となる報酬関数は、既知の再生ケルネルヒルベルト空間に属する。我々は、$widetildemathcalO(sqrtgamma_TT+fracgamma_Tvarepsilon_mathrmDP)の最先端の累積後悔を実現する新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2025-07-18T03:54:49Z)
Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning [49.66162382667325]
一般化ガウス機構(英語版)を考察し、ある$beta geq 1$に対して$e-frac| x |sigmabeta $ に比例した付加雑音項 $x$ をサンプリングする。 GGメカニズムとその変種に対するプライバシ会計は独立であり、プライバシ会計の計算コストを大幅に向上させることを示す。
論文参考訳（メタデータ） (2025-06-14T15:49:25Z)
On the Price of Differential Privacy for Hierarchical Clustering [21.64775530337936]
本稿では, エッジレベルのDP設定において, 既知の可視性よりもはるかに高い近似性を示す, 重み付きプライバシモデルにおける新しいアルゴリズムを提案する。以上の結果から,提案アルゴリズムはコストの面では良好に動作し,大規模グラフに対するスケーラビリティも良好であることがわかった。
論文参考訳（メタデータ） (2025-04-22T04:39:40Z)
Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
プライバシー制約の下では、プライベート線形回帰の複雑さは通常の共分散行列によって捉えられる。最適率を達成するための情報重み付け回帰手法を提案する。特に、我々の結果は、共同プライバシーは追加費用がほとんどないことを示している。
論文参考訳（メタデータ） (2025-02-18T18:35:24Z)
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)
Differential Privacy for Clustering Under Continual Observation [5.220940151628734]
我々は、点の挿入と削除の両方を行う$mathbbRd$のデータセットをプライベートにクラスタリングする問題を考える。連続観測において、$k$-meansの目的に対して、$varepsilon$-differentially private clustering 機構を提供する。
論文参考訳（メタデータ） (2023-07-07T07:23:56Z)
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)
Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文参考訳（メタデータ） (2021-11-09T09:00:02Z)

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

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