論文の概要: Distributed Stochastic Algorithms for High-rate Streaming Principal
Component Analysis
- arxiv url: http://arxiv.org/abs/2001.01017v1
- Date: Sat, 4 Jan 2020 00:46:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-14 12:30:28.418455
- Title: Distributed Stochastic Algorithms for High-rate Streaming Principal
Component Analysis
- Title(参考訳): 高速ストリーミング主成分分析のための分散確率アルゴリズム
- Authors: Haroon Raja and Waheed U. Bajwa
- Abstract要約: この論文は、データの高いストリーミング速度に追従できる古典的クラスリナ法(D-クラスリナ法)の分散変種を定式化し分析する。
D-KrasulinaとDM-Krasulinaの高速ストリーミング環境における収束挙動を検証するために,合成および実世界のデータを用いて実験を行った。
- 参考スコア(独自算出の注目度): 14.04898975989048
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the problem of estimating the principal eigenvector of a
covariance matrix from independent and identically distributed data samples in
streaming settings. The streaming rate of data in many contemporary
applications can be high enough that a single processor cannot finish an
iteration of existing methods for eigenvector estimation before a new sample
arrives. This paper formulates and analyzes a distributed variant of the
classical Krasulina's method (D-Krasulina) that can keep up with the high
streaming rate of data by distributing the computational load across multiple
processing nodes. The analysis shows that---under appropriate
conditions---D-Krasulina converges to the principal eigenvector in an
order-wise optimal manner; i.e., after receiving $M$ samples across all nodes,
its estimation error can be $O(1/M)$. In order to reduce the network
communication overhead, the paper also develops and analyzes a mini-batch
extension of D-Krasulina, which is termed DM-Krasulina. The analysis of
DM-Krasulina shows that it can also achieve order-optimal estimation error
rates under appropriate conditions, even when some samples have to be discarded
within the network due to communication latency. Finally, experiments are
performed over synthetic and real-world data to validate the convergence
behaviors of D-Krasulina and DM-Krasulina in high-rate streaming settings.
- Abstract(参考訳): 本稿では,ストリーミング環境における独立分散データサンプルから共分散行列の主固有ベクトルを推定する問題を考察する。
現代の多くのアプリケーションにおけるデータのストリーミング速度は、新しいサンプルが到着する前に、単一のプロセッサが既存の固有ベクトル推定手法のイテレーションを完了できないほど高い。
本稿では,複数の処理ノード間で計算負荷を分散することにより,高いストリーミング速度を追従できる古典的クラスリーナ法(d-krasulina)の分散変種を定式化し,解析する。
この分析は--適切な条件の下で--D-クラシュリーナが順序的に最適に主固有ベクトルに収束することを示し、すなわち全てのノードに$M$サンプルを受け取った後、その推定誤差は$O(1/M)$となる。
ネットワーク通信のオーバーヘッドを削減するために,dm-krasulinaと呼ばれるd-krasulinaのミニバッチ拡張を開発し,解析する。
DM-Krasulinaの分析は、通信遅延によりネットワーク内でいくつかのサンプルが破棄される場合であっても、適切な条件下で順序-最適推定誤差率を達成することができることを示している。
最後に、D-KrasulinaとDM-Krasulinaの高速ストリーミング環境での収束挙動を検証するために、合成および実世界のデータを用いて実験を行う。
関連論文リスト
- Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
静止測度から少数のサンプルを与えられたマルコフ連鎖を用いて多重モーダル分布をサンプリングする問題を考察する。
マルコフ連鎖が$k$dのスペクトルギャップを持つ場合、静止分布からのサンプルは、静止測度からテレビ距離において$varepsilon$-closeの条件法則を持つサンプルを効率よく生成する。
論文 参考訳(メタデータ) (2024-11-14T01:37:02Z) - $O(d/T)$ Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions [6.76974373198208]
我々は、最小限の仮定の下で、人気のあるSDEベースのサンプルラーに対して高速収束理論を確立する。
解析の結果, スコア関数の$ell_2$-accurate推定値が与えられた場合, 対象分布と生成分布の総変動距離は$O(d/T)$で上限値となることがわかった。
これは、逆プロセスの各ステップでエラーがどのように伝播するかの詳細な特徴を提供する、新しい分析ツールセットによって達成される。
論文 参考訳(メタデータ) (2024-09-27T17:59:10Z) - Non-asymptotic bounds for forward processes in denoising diffusions: Ornstein-Uhlenbeck is hard to beat [49.1574468325115]
本稿では,全変動(TV)における前方拡散誤差の非漸近的境界について述べる。
我々は、R$からFarthestモードまでの距離でマルチモーダルデータ分布をパラメライズし、加法的および乗法的雑音による前方拡散を考察する。
論文 参考訳(メタデータ) (2024-08-25T10:28:31Z) - Estimating the Rate-Distortion Function by Wasserstein Gradient Descent [36.24186820465207]
損失圧縮の理論では、レート歪み関数$R(D)$は、データソースが(ビットレートで)どんなレベルの忠実度(歪み)でも圧縮できるかを記述する。
最適輸送の観点から,$R(D)$を推定する新しい手法を提案する。
論文 参考訳(メタデータ) (2023-10-29T05:29:59Z) - Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative
Models [49.81937966106691]
我々は拡散モデルのデータ生成過程を理解するための非漸近理論のスイートを開発する。
従来の研究とは対照的に,本理論は基本的だが多目的な非漸近的アプローチに基づいて開発されている。
論文 参考訳(メタデータ) (2023-06-15T16:30:08Z) - Deep Momentum Multi-Marginal Schr\"odinger Bridge [41.27274841596343]
本稿では,時間的限界制約を満たすシステムに対して,スムーズな測度値アルゴリズムを学習する新しいフレームワークを提案する。
我々のアルゴリズムは、合成データセットと実世界の単一細胞RNAデータセットシーケンスの実験によって証明されたように、ベースラインを著しく上回る。
論文 参考訳(メタデータ) (2023-03-03T07:24:38Z) - Preconditioned Score-based Generative Models [49.88840603798831]
直感的な加速度法はサンプリングの繰り返しを減らし、しかしながら重大な性能劣化を引き起こす。
本稿では,行列プレコンディショニングを利用したモデル非依存型bfem事前条件拡散サンプリング(PDS)手法を提案する。
PDSは、バニラSGMのサンプリングプロセスを限界余剰計算コストで変更し、モデルの再訓練を行わない。
論文 参考訳(メタデータ) (2023-02-13T16:30:53Z) - DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over
Graphs [54.08445874064361]
本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。
Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。
提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
論文 参考訳(メタデータ) (2022-08-29T18:01:42Z) - Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。
我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
論文 参考訳(メタデータ) (2022-07-16T03:09:30Z) - Convergence for score-based generative modeling with polynomial
complexity [9.953088581242845]
我々は、Scoreベースの生成モデルの背後にあるコアメカニックに対する最初の収束保証を証明した。
以前の作品と比較すると、時間的に指数関数的に増加するエラーや、次元の呪いに苦しむエラーは発生しない。
予測器・相関器はどちらの部分のみを使用するよりも収束性が高いことを示す。
論文 参考訳(メタデータ) (2022-06-13T14:57:35Z) - Federated Deep AUC Maximization for Heterogeneous Data with a Constant
Communication Complexity [77.78624443410216]
異種胸部データ検出のための改良型FDAMアルゴリズムを提案する。
本研究は,提案アルゴリズムの通信が機械数に強く依存し,精度レベルにも強く依存していることを示す。
FDAMアルゴリズムのベンチマークデータセットと、異なる組織の医療用胸部X線画像に対する効果を実験により実証した。
論文 参考訳(メタデータ) (2021-02-09T04:05:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。