論文の概要: 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 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 [21.727073594338297]
  我々は、(非線形)カーネル関数をペアの内積に適用することにより、エントリが得られるランダム行列を考える。 このモデルは、機械学習、統計学、信号処理における問題によって動機付けられている。 mathbbN および $kappain mathbb の固定的な $ell に対して、$d, n から infty$ に対する $n / dell to kappa in (0, infty)$ のとき、これらの行列の経験スペクトル分布の弱極限を確立する。
  論文  参考訳（メタデータ） (2022-05-12T18:50:21Z)
• Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics [8.90202564665576]
  一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。 3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
  論文  参考訳（メタデータ） (2022-03-19T07:26:45Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。 我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
  論文  参考訳（メタデータ） (2022-02-09T15:26:03Z)
• When Random Tensors meet Random Matrices [50.568841545067144]
  本稿では,ガウス雑音を伴う非対称次数-$d$スパイクテンソルモデルについて検討する。 検討したモデルの解析は、等価なスパイクされた対称テクシットブロック-ワイドランダム行列の解析に起因していることを示す。
  論文  参考訳（メタデータ） (2021-12-23T04:05:01Z)
• 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)
• Faster Kernel Matrix Algebra via Density Estimation [46.253698241653254]
  正半定核行列 $K の基本特性を $n$ 点に対応する n$ で計算するための高速アルゴリズムについて研究する。
  論文  参考訳（メタデータ） (2021-02-16T18:25:47Z)
• Quantum algorithms for spectral sums [79.28094304325116]
  対称正定値行列(SPD)の最も一般的なスペクトル和を推定するための新しい量子アルゴリズムを提案し,解析する。 関数 $f$ と行列 $A に対して、スペクトル和は $S_f(A) :=textTr[f(A)] = sum_j f(lambda_j)$, ここで $lambda_j$ は固有値である。
  論文  参考訳（メタデータ） (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)
• Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
  この写本は、ランクラパース行列と$sスパース行列の和として表現できる$mtimes n$が計算的に抽出可能な方法で復元可能であることを示す同様の保証を開発する。 その結果, 合成問題, 動的地上/静電分離, マルチスペクトルイメージング, ロバストPCAが得られた。
  論文  参考訳（メタデータ） (2020-07-18T15:36:11Z)
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices [23.15629681360836]
  雑音線形観測から係数ベクトル$x_0$ in$RN$を学習する問題を考察する。 平均二乗誤差に対する明示的な式を厳密に導出する。 我々の予測は、非常に適度なサイズであっても、数値と非常によく一致していることを示す。
  論文  参考訳（メタデータ） (2020-02-11T13:43:32Z)

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

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