論文の概要: Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations

• arxiv url: http://arxiv.org/abs/2306.16648v1
• Date: Thu, 29 Jun 2023 03:18:53 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-30 14:57:17.591320
• Title: Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations
• Title（参考訳）: 複素ガウス摂動に対するプライベート共分散近似と固有値ギャップ境界
• Authors: Oren Mangoubi, Nisheeth K. Vishnoi
• Abstract要約: この機構によって出力される行列と最高ランクの$k$の近似との差のフロベニウスノルムが、およそ$tildeO(sqrtkd)$で有界であることを示す。 これは、$M$のすべてのトップ-$k$固有値間のギャップが、同じ境界に対して少なくとも$sqrtd$であることを要求する以前の作業を改善する。
• 参考スコア（独自算出の注目度）: 28.431572772564518
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of approximating a $d \times d$ covariance matrix $M$ with a rank-$k$ matrix under $(\varepsilon,\delta)$-differential privacy. We present and analyze a complex variant of the Gaussian mechanism and show that the Frobenius norm of the difference between the matrix output by this mechanism and the best rank-$k$ approximation to $M$ is bounded by roughly $\tilde{O}(\sqrt{kd})$, whenever there is an appropriately large gap between the $k$'th and the $k+1$'th eigenvalues of $M$. This improves on previous work that requires that the gap between every pair of top-$k$ eigenvalues of $M$ is at least $\sqrt{d}$ for a similar bound. Our analysis leverages the fact that the eigenvalues of complex matrix Brownian motion repel more than in the real case, and uses Dyson's stochastic differential equations governing the evolution of its eigenvalues to show that the eigenvalues of the matrix $M$ perturbed by complex Gaussian noise have large gaps with high probability. Our results contribute to the analysis of low-rank approximations under average-case perturbations and to an understanding of eigenvalue gaps for random matrices, which may be of independent interest.
• Abstract（参考訳）: 我々は、$d \times d$ covariance matrix $M$を$(\varepsilon,\delta)$-differential privacyの下でランク-$k$行列で近似する問題を考える。 ガウス機構の複素変種を提示・解析し、この機構によって出力される行列の差のフロベニウスノルムと、$m$ の最高のランク-$k$近似は、$k$ と $k+1$'th の固有値の間に適切な大きな差があるとき、大まかに$\tilde{o}(\sqrt{kd})$ で区切られることを示した。 これは、同じ境界に対して、$M$のすべてのトップ-$k$固有値のペア間のギャップが少なくとも$\sqrt{d}$であるような以前の作業を改善する。 解析では、複素行列ブラウン運動の固有値が実数よりも多く減少するという事実を利用し、その固有値の進化を規定するdysonの確率微分方程式を用いて、複素ガウス雑音によって摂動される行列の固有値が高いギャップを持つことを示す。 本研究は, 平均ケース摂動下における低ランク近似の解析と, 独立興味を持つ確率行列に対する固有値ギャップの理解に寄与する。

関連論文リスト

• Distribution of lowest eigenvalue in $k$-body bosonic random matrix ensembles [0.8999666725996978]
  有限多ボソン系の最小固有値分布を$k$-body相互作用で数値的に検討する。 以上の結果から, ガウス分布は 1 に近い$q$ のガウス分布から, 中間値が$q$ のガウベル分布へ, 良く知られた Tracy-Widom 分布が$q=0$ のガウス分布へ滑らかな遷移を示した。
  論文  参考訳（メタデータ） (2024-04-30T20:44:31Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion [28.431572772564518]
  対称行列 $M$ とベクトル $lambda$ が与えられたとき、行列によって$M$ を近似するガウス機構のフロベニウス距離ユーティリティ上の新しい境界を示す。 私たちのバウンダリは、$lambda$と$M$の固有値のギャップの両方に依存します。
  論文  参考訳（メタデータ） (2022-11-11T18:54:01Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• 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)
• Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics [8.90202564665576]
  一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。 3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
  論文  参考訳（メタデータ） (2022-03-19T07:26:45Z)
• Largest Eigenvalues of the Conjugate Kernel of Single-Layered Neural Networks [0.0]
  最大固有値は、よく知られた線形確率行列のアンサンブルと同じ極限(確率)を持つことを示す。 これは機械学習の応用にとって大きな関心事かもしれない。
  論文  参考訳（メタデータ） (2022-01-13T00:48:20Z)
• 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)
• 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)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)

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

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