論文の概要: Private Matrix Approximation and Geometry of Unitary Orbits
- arxiv url: http://arxiv.org/abs/2207.02794v1
- Date: Wed, 6 Jul 2022 16:31:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-07 13:15:22.102988
- Title: Private Matrix Approximation and Geometry of Unitary Orbits
- Title（参考訳）: プライベートマトリックス近似と単位軌道の幾何学
- Authors: Oren Mangoubi, Yikai Wu, Satyen Kale, Abhradeep Guha Thakurta,
Nisheeth K. Vishnoi
- Abstract要約: この問題は、スペクトルが$Lambda$と同じ行列で$A$を近似しようとする。
近似誤差の上限値と下限値を持つ効率的でプライベートなアルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 29.072423395363668
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider the following optimization problem: Given $n \times n$ matrices $A$
and $\Lambda$, maximize $\langle A, U\Lambda U^*\rangle$ where $U$ varies over
the unitary group $\mathrm{U}(n)$. This problem seeks to approximate $A$ by a
matrix whose spectrum is the same as $\Lambda$ and, by setting $\Lambda$ to be
appropriate diagonal matrices, one can recover matrix approximation problems
such as PCA and rank-$k$ approximation. We study the problem of designing
differentially private algorithms for this optimization problem in settings
where the matrix $A$ is constructed using users' private data. We give
efficient and private algorithms that come with upper and lower bounds on the
approximation error. Our results unify and improve upon several prior works on
private matrix approximation problems. They rely on extensions of
packing/covering number bounds for Grassmannians to unitary orbits which should
be of independent interest.
- Abstract（参考訳）: 以下の最適化問題を考える:$n \times n$ matrices $A$ and $\Lambda$, max $\langle A, U\Lambda U^*\rangle$ ここで$U$はユニタリ群$\mathrm{U}(n)$に対して異なる。
この問題は、スペクトルが$\Lambda$と等しい行列によって$A$を近似し、$\Lambda$を適切な対角行列として設定することにより、PCAやランク-k$近似のような行列近似問題を復元することができる。
本研究では,行列$A$がユーザのプライベートデータを用いて構築される設定において,この最適化問題に対する微分プライベートアルゴリズムの設計問題を考察する。
近似誤差の上限値と下限値を持つ効率的でプライベートなアルゴリズムを与える。
我々は,プライベート行列近似問題に関するいくつかの先行研究を統一し,改善する。
それらは、グラスマン多様体が独立した興味を持つべきユニタリ軌道にパッキング/カバー数境界の拡張に依存している。
関連論文リスト
- Oja's Algorithm for Sparse PCA [7.059472280274011]
Oja's algorithm for streaming principal Component Analysis (PCA) for $n$ datapoints achieve the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。
単純なシングルパスプロシージャは、$O(d)$ space と $O(nd)$ time の規則性条件下でのミニマックス誤差を達成可能であることを示す。
論文 参考訳（メタデータ） (2024-02-11T16:36:48Z) - Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
論文 参考訳（メタデータ） (2023-10-27T16:54:29Z) - Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex
Gaussian Perturbations [28.431572772564518]
この機構によって出力される行列と最高ランクの$k$の近似との差のフロベニウスノルムが、およそ$tildeO(sqrtkd)$で有界であることを示す。
これは、$M$のすべてのトップ-$k$固有値間のギャップが、同じ境界に対して少なくとも$sqrtd$であることを要求する以前の作業を改善する。
論文 参考訳（メタデータ） (2023-06-29T03:18:53Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - 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) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment [46.145969174332485]
プロジェクションフリーの高速な一般メトリック学習フレームワークを提案する。
距離あたりの線形制約が考えられるため、距離学習問題におけるPDコーン制約を置き換える。
実験により,我々のグラフ距離の最適化はコーン射影方式よりもはるかに高速であることが示された。
論文 参考訳（メタデータ） (2020-06-15T23:15:12Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。