論文の概要: Spectral Guarantees for Adversarial Streaming PCA

• arxiv url: http://arxiv.org/abs/2408.10332v1
• Date: Mon, 19 Aug 2024 18:15:53 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-21 18:03:34.469313
• Title: Spectral Guarantees for Adversarial Streaming PCA
• Title（参考訳）: 逆ストリーミングPCAのためのスペクトル保証
• Authors: Eric Price, Zhiyang Xun,
• Abstract要約: 既存のアルゴリズムでは、$R = widetildeOmega(sqrtd)$でストリーミングPCAを$widetildeO(d)$スペースで解決する必要がある。 R = widetildeOmega(sqrtd)$ がすべてのマージ可能な要約に対して必要であることを示す。 我々の分析は,Ojaのアルゴリズムを逆流に応用した最初のものである。
• 参考スコア（独自算出の注目度）: 4.7097861261175895
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In streaming PCA, we see a stream of vectors $x_1, \dotsc, x_n \in \mathbb{R}^d$ and want to estimate the top eigenvector of their covariance matrix. This is easier if the spectral ratio $R = \lambda_1 / \lambda_2$ is large. We ask: how large does $R$ need to be to solve streaming PCA in $\widetilde{O}(d)$ space? Existing algorithms require $R = \widetilde{\Omega}(d)$. We show: (1) For all mergeable summaries, $R = \widetilde{\Omega}(\sqrt{d})$ is necessary. (2) In the insertion-only model, a variant of Oja's algorithm gets $o(1)$ error for $R = O(\log n \log d)$. (3) No algorithm with $o(d^2)$ space gets $o(1)$ error for $R = O(1)$. Our analysis is the first application of Oja's algorithm to adversarial streams. It is also the first algorithm for adversarial streaming PCA that is designed for a spectral, rather than Frobenius, bound on the tail; and the bound it needs is exponentially better than is possible by adapting a Frobenius guarantee.
• Abstract（参考訳）: ストリーミングPCAでは、ベクトルのストリームが$x_1, \dotsc, x_n \in \mathbb{R}^d$となり、共分散行列のトップ固有ベクトルを推定したい。 スペクトル比$R = \lambda_1 / \lambda_2$が大きければ、これは簡単である。 ストリーミングPCAを$\widetilde{O}(d)$スペースで解決するためには、$R$がどれくらい必要か? 既存のアルゴリズムには$R = \widetilde{\Omega}(d)$が必要である。 1) マージ可能なすべての要約に対して、$R = \widetilde{\Omega}(\sqrt{d})$ が必要である。 2)挿入専用モデルでは、Ojaのアルゴリズムの変種は、$R = O(\log n \log d)$に対して$o(1)$エラーを得る。 (3)$o(d^2)$スペースを持つアルゴリズムは、$R = O(1)$に対して$o(1)$エラーを得る。 我々の分析は,Ojaのアルゴリズムを逆流に応用した最初のものである。 また、Frobeniusではなくスペクトルのために設計され、テールに縛られている逆ストリーミングPCAのアルゴリズムとしては初めてであり、Frobeniusの保証を適用することで、必要となるバウンダリは指数関数的に優れている。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
  Oja's Algorithm for Streaming principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。 Ojaのアルゴリズムの出力をしきい値にする単純なシングルパス手順は、$O(d)$ space と $O(nd)$ time の正則性条件下での最小誤差を達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-11T16:36:48Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
  任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。 我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
  論文  参考訳（メタデータ） (2023-04-06T16:15:19Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
  最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。 最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。 これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
  論文  参考訳（メタデータ） (2020-04-16T22:57:06Z)

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

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