論文の概要: Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations

• arxiv url: http://arxiv.org/abs/2502.07657v1
• Date: Tue, 11 Feb 2025 15:46:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 14:06:47.902734
• Title: Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations
• Title（参考訳）: 共分散行列, ダイソンブラウン運動, 固有値ギャップ境界に対する私的低ランク近似
• Authors: Oren Mangoubi, Nisheeth K. Vishnoi,
• Abstract要約: ガウス機構の複素変項を解析し、この機構によって出力される行列と最高のランク-k$近似との差のフロベニウスノルムの上界を求める。 ガウス雑音によって摂動される行列の固有値$M$は高い確率で大きなギャップを持つことを示す。
• 参考スコア（独自算出の注目度）: 29.212403229351253
• License:
• 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 obtain upper bounds on the Frobenius norm of the difference between the matrix output by this mechanism and the best rank-$k$ approximation to $M$. Our analysis provides improvements over previous bounds, particularly when the spectrum of $M$ satisfies natural structural assumptions. The novel insight is to view the addition of Gaussian noise to a matrix 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 enable us to upper bound the Frobenius distance between the best rank-$k$ approximation of $M$ and that of a Gaussian perturbation of $M$ as an integral that involves inverse eigenvalue gaps of the stochastically evolving matrix, as opposed to a sum of perturbation bounds obtained via Davis-Kahan-type theorems. Subsequently, again using the Dyson Brownian motion viewpoint, we show that the eigenvalues of the matrix $M$ perturbed by Gaussian noise have large gaps with high probability. These results also contribute to the analysis of low-rank approximations under average-case perturbations, and to an understanding of eigenvalue gaps for random matrices, both of which may be of independent interest.
• Abstract（参考訳）: 我々は、$d \times d$ covariance matrix $M$ を $(\varepsilon,\delta)$-differential privacy の下でランク-$k$ 行列で近似する問題を考える。 この機構によって出力される行列と最高の階数-k$近似との差のフロベニウスノルムの上界を求める。 我々の分析は、特にM$のスペクトルが自然構造的仮定を満たす場合、以前の境界よりも改善する。 新たな洞察は、行列へのガウスノイズの付加を連続時間行列ブラウン運動として見ることである。 この視点により、ダイソンによって発見された確率微分方程式によって支配される行列の固有値と固有ベクトルの進化を追跡することができる。 これらの方程式はフロベニウス距離を最高階数-k$$$M$の近似と、デービス=カハン型定理によって得られる摂動境界の和とは対照的に、確率的に進化する行列の逆固有値ギャップを含む積分としてM$のガウス摂動とを上界にすることができる。 その後、ダイソン・ブラウン運動の視点を用いて、ガウス雑音によって摂動される行列の固有値が高い確率で大きなギャップを持つことを示す。 これらの結果は、平均ケース摂動下での低ランク近似の解析や、ランダム行列の固有値ギャップの理解にも寄与する。

関連論文リスト

• Optimal Quantization for Matrix Multiplication [35.007966885532724]
  我々は、近似誤差を明確に保証したネスト格子に基づく普遍的量子化器を構築する。 我々の量子化器の実用的低複雑さバージョンは、非常に最適に近い性能を達成する。
  論文  参考訳（メタデータ） (2024-10-17T17:19:48Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。 重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。 我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
  論文  参考訳（メタデータ） (2024-05-23T12:26:25Z)
• Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations [28.431572772564518]
  この機構によって出力される行列と最高ランクの$k$の近似との差のフロベニウスノルムが、およそ$tildeO(sqrtkd)$で有界であることを示す。 これは、$M$のすべてのトップ-$k$固有値間のギャップが、同じ境界に対して少なくとも$sqrtd$であることを要求する以前の作業を改善する。
  論文  参考訳（メタデータ） (2023-06-29T03:18:53Z)
• 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)
• An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalings [21.727073594338297]
  この研究は、機械学習と統計学の応用によって動機付けられている。 スケーリングシステムにおいて,これらのランダム行列の経験的分布の弱い限界を確立する。 我々の結果は、マルテンコ・パストゥル法と半円法の間の自由加法的畳み込みとして特徴づけられる。
  論文  参考訳（メタデータ） (2022-05-12T18:50:21Z)
• When Random Tensors meet Random Matrices [50.568841545067144]
  本稿では,ガウス雑音を伴う非対称次数-$d$スパイクテンソルモデルについて検討する。 検討したモデルの解析は、等価なスパイクされた対称テクシットブロック-ワイドランダム行列の解析に起因していることを示す。
  論文  参考訳（メタデータ） (2021-12-23T04:05:01Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• 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)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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