論文の概要: Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion

• arxiv url: http://arxiv.org/abs/2211.06418v1
• Date: Fri, 11 Nov 2022 18:54:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2022-11-14 16:06:22.748689
• Title: Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion
• Title（参考訳）: Re-Analyze Gauss:Dyson Brownian Motionによるプライベートマトリックス近似の境界
• Authors: Oren Mangoubi and Nisheeth K. Vishnoi
• Abstract要約: 対称行列 $M$ とベクトル $lambda$ が与えられたとき、行列によって$M$ を近似するガウス機構のフロベニウス距離ユーティリティ上の新しい境界を示す。 私たちのバウンダリは、$lambda$と$M$の固有値のギャップの両方に依存します。
• 参考スコア（独自算出の注目度）: 28.431572772564518
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a symmetric matrix $M$ and a vector $\lambda$, we present new bounds on the Frobenius-distance utility of the Gaussian mechanism for approximating $M$ by a matrix whose spectrum is $\lambda$, under $(\varepsilon,\delta)$-differential privacy. Our bounds depend on both $\lambda$ and the gaps in the eigenvalues of $M$, and hold whenever the top $k+1$ eigenvalues of $M$ have sufficiently large gaps. When applied to the problems of private rank-$k$ covariance matrix approximation and subspace recovery, our bounds yield improvements over previous bounds. Our bounds are obtained by viewing the addition of Gaussian noise as a continuous-time matrix Brownian motion. This viewpoint allows us to track the evolution of eigenvalues and eigenvectors of the matrix, which are governed by stochastic differential equations discovered by Dyson. These equations allow us to bound the utility as the square-root of a sum-of-squares of perturbations to the eigenvectors, as opposed to a sum of perturbation bounds obtained via Davis-Kahan-type theorems.
• Abstract（参考訳）: 対称行列 $M$ とベクトル $\lambda$ が与えられたとき、スペクトルが $\lambda$, under $(\varepsilon,\delta)$-differential privacy である行列によって$M$を近似するガウス機構のフロベニウス距離ユーティリティの新たな境界を示す。 我々の境界は$\lambda$と$m$の固有値のギャップの両方に依存しており、$m$の上位の$k+1$固有値が十分に大きなギャップを持つ限り保持する。 プライベートランク-$k$共分散行列近似と部分空間復元の問題に適用すると、我々の境界は以前の境界よりも改善される。 我々の境界は、ガウス雑音を連続時間マトリクスブラウン運動として見ることによって得られる。 この観点から、ダイソンによって発見された確率微分方程式によって支配される行列の固有値と固有ベクトルの進化を追跡することができる。 これらの方程式は、デービス・カハン型の定理によって得られる摂動境界の和とは対照的に、固有ベクトルに対する摂動の和の平方根として効用を束縛することができる。

関連論文リスト

• Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations [29.212403229351253]
  ガウス機構の複素変項を解析し、この機構によって出力される行列と最高のランク-k$近似との差のフロベニウスノルムの上界を求める。 ガウス雑音によって摂動される行列の固有値$M$は高い確率で大きなギャップを持つことを示す。
  論文  参考訳（メタデータ） (2025-02-11T15:46:03Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。 重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。 我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
  論文  参考訳（メタデータ） (2024-05-23T12:26:25Z)
• The matrix permanent and determinant from a spin system [0.0]
  M$ の行列式に対するガウス=ジョーダンは、フェルミオン $breveM$ の一般化ゼロ固有空間の連続的な除去と同値である。 我々の分析は、永久体の古典的および量子的評価のための新しい戦略への道を示すかもしれない。
  論文  参考訳（メタデータ） (2023-07-10T16:34:55Z)
• Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations [28.431572772564518]
  この機構によって出力される行列と最高ランクの$k$の近似との差のフロベニウスノルムが、およそ$tildeO(sqrtkd)$で有界であることを示す。 これは、$M$のすべてのトップ-$k$固有値間のギャップが、同じ境界に対して少なくとも$sqrtd$であることを要求する以前の作業を改善する。
  論文  参考訳（メタデータ） (2023-06-29T03:18:53Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Private Matrix Approximation and Geometry of Unitary Orbits [29.072423395363668]
  この問題は、スペクトルが$Lambda$と同じ行列で$A$を近似しようとする。 近似誤差の上限値と下限値を持つ効率的でプライベートなアルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-07-06T16:31:44Z)
• An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalings [21.727073594338297]
  この研究は、機械学習と統計学の応用によって動機付けられている。 スケーリングシステムにおいて,これらのランダム行列の経験的分布の弱い限界を確立する。 我々の結果は、マルテンコ・パストゥル法と半円法の間の自由加法的畳み込みとして特徴づけられる。
  論文  参考訳（メタデータ） (2022-05-12T18:50:21Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices [23.15629681360836]
  雑音線形観測から係数ベクトル$x_0$ in$RN$を学習する問題を考察する。 平均二乗誤差に対する明示的な式を厳密に導出する。 我々の予測は、非常に適度なサイズであっても、数値と非常によく一致していることを示す。
  論文  参考訳（メタデータ） (2020-02-11T13:43:32Z)

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

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