論文の概要: Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates

• arxiv url: http://arxiv.org/abs/2102.03646v1
• Date: Sat, 6 Feb 2021 19:21:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-09 15:16:53.412526
• Title: Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
• Title（参考訳）: k-PCAのストリーミング: Ojaのアルゴリズムに対する効率的な保証。
• Authors: De Huang and Jonathan Niles-Weed and Rachel Ward
• Abstract要約: Ojaの$k$-PCAストリーミングアルゴリズムは、最適なオフラインアルゴリズムとほぼ一致する性能を達成する。 我々はOjaのアルゴリズムが期待値のトップ$k$固有ベクトルの部分空間への正確な近似を得ることができることを示す。
• 参考スコア（独自算出の注目度）: 14.728207711693406
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze Oja's algorithm for streaming $k$-PCA and prove that it achieves performance nearly matching that of an optimal offline algorithm. Given access to a sequence of i.i.d. $d \times d$ symmetric matrices, we show that Oja's algorithm can obtain an accurate approximation to the subspace of the top $k$ eigenvectors of their expectation using a number of samples that scales polylogarithmically with $d$. Previously, such a result was only known in the case where the updates have rank one. Our analysis is based on recently developed matrix concentration tools, which allow us to prove strong bounds on the tails of the random matrices which arise in the course of the algorithm's execution.
• Abstract（参考訳）: 我々はOjaのアルゴリズムで$k$-PCAをストリーミングし、最適化されたオフラインアルゴリズムとほぼ一致する性能を実現する。 i. i. d. のシーケンスにアクセスすると $d \times d$ symmetric matrices, we show that Oja's algorithm can obtained a accurate approximation to the top $k$ eigenvectors of the top $k$ eigenvectors of their expectation with a many sample that scales polylogarithmically with $d$。 以前は、更新がランク1の場合にのみ、そのような結果が知られていた。 私たちの分析は、アルゴリズムの実行中に発生するランダム行列の尾に強い境界を証明することを可能にする、最近開発されたマトリックス濃度ツールに基づいています。

関連論文リスト

• Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation [48.92318828548911]
  政策改善と政策評価の段階を交互に行うモデルフリー学習アルゴリズムであるLoRa-PI(Low-Rank Policy Iteration)を提案する。 LoRa-PIは$widetildeO(S+Aover mathrmpoly (1-gamma)varepsilon2)$サンプルを使用して$varepsilon$-optimal Policyを学習する。
  論文  参考訳（メタデータ） (2024-10-30T20:22:17Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• A fixed-point algorithm for matrix projections with applications in quantum information [7.988085110283119]
  このアルゴリズムは反復数において最適解に指数関数的に収束することを示す。 量子資源理論および量子シャノン理論における我々のアルゴリズムのいくつかの応用について論じる。
  論文  参考訳（メタデータ） (2023-12-22T11:16:11Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Nonparametric Matrix Estimation with One-Sided Covariates [5.457150493905064]
  mathbbRntimes m$ のデータセット $X をスパシティ $p$ で観測する行列推定のタスクを考える。 我々は,行数が小さすぎる場合に,各行を別々に推定することで,アルゴリズムの精度が向上することを示すアルゴリズムと解析を提供する。
  論文  参考訳（メタデータ） (2021-10-26T19:11:45Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries [4.230158563771147]
  低階行列補完のための新しい,単純で,計算効率のよい反復法を提案する。 我々のアルゴリズムは、R2RILS(R2RILS for rank $2r$peterative least squares)と呼ばれ、メモリ要件が低い。
  論文  参考訳（メタデータ） (2020-02-05T16:20:58Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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