論文の概要: SMC Is All You Need: Parallel Strong Scaling
- arxiv url: http://arxiv.org/abs/2402.06173v1
- Date: Fri, 9 Feb 2024 04:13:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-12 18:08:19.052913
- Title: SMC Is All You Need: Parallel Strong Scaling
- Title(参考訳): SMCは本当に必要なもの:パラレル・ストロング・スケーリング
- Authors: Xinzhu Liang, Sanjaya Lohani, Joseph M. Lukens, Brian T. Kirby, Thomas
A. Searles, Kody J.H. Law
- Abstract要約: 並列高強度スケーリングを実現するための完全並列シーケンシャルモンテカルロ法(pSMC)を開発した。
pSMC は無限小精度 MSE$=O(varepsilon2)$ に収束し、固定された有限時間複素度コスト=O(1)$ であり、効率リークがない。
- 参考スコア(独自算出の注目度): 0.7374586159008119
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the general framework of Bayesian inference, the target distribution can
only be evaluated up-to a constant of proportionality. Classical consistent
Bayesian methods such as sequential Monte Carlo (SMC) and Markov chain Monte
Carlo (MCMC) have unbounded time complexity requirements. We develop a fully
parallel sequential Monte Carlo (pSMC) method which provably delivers parallel
strong scaling, i.e. the time complexity (and per-node memory) remains bounded
if the number of asynchronous processes is allowed to grow. More precisely, the
pSMC has a theoretical convergence rate of MSE$ = O(1/NR)$, where $N$ denotes
the number of communicating samples in each processor and $R$ denotes the
number of processors. In particular, for suitably-large problem-dependent $N$,
as $R \rightarrow \infty$ the method converges to infinitesimal accuracy
MSE$=O(\varepsilon^2)$ with a fixed finite time-complexity Cost$=O(1)$ and with
no efficiency leakage, i.e. computational complexity
Cost$=O(\varepsilon^{-2})$. A number of Bayesian inference problems are taken
into consideration to compare the pSMC and MCMC methods.
- Abstract(参考訳): ベイズ推論の一般的な枠組みでは、対象分布は比例性の定数までしか評価できない。
シーケンシャルモンテカルロ (SMC) やマルコフ連鎖モンテカルロ (MCMC) のような古典的一貫したベイズ的手法は、非有界な時間複雑性要求を持つ。
非同期プロセスの数が増加すると、時間的複雑性(およびノード単位のメモリ)が制限されるため、並列の強いスケーリングを実現するための完全並列シーケンシャルモンテカルロ法(pSMC)を開発した。
より正確には、pSMC は MSE$ = O(1/NR)$ の理論的収束率を持ち、$N$ は各プロセッサにおける通信サンプルの数を表し、$R$ はプロセッサ数を表す。
特に、好ましくは、問題依存の$N$に対して、$R \rightarrow \infty$ は無限小精度 MSE$=O(\varepsilon^2)$ に収束し、固定有限時間複雑度コスト=O(1)$ と効率リークのない、すなわち計算複雑性のコスト=O(\varepsilon^{-2})$ に収束する。
pSMC法とMCMC法を比較するため,ベイズ推定問題もいくつか検討されている。
関連論文リスト
- More Quantum Speedups for Multiproposal MCMC [9.09160682938666]
マルチプロポサルマルコフ連鎖モンテカルロ(MCMC)アルゴリズムは、目標分布をより効率的にサンプリングするために、各イテレーションで複数の提案から選択する。
最近の研究は、そのような多目的MCMCアルゴリズムの2次量子スピードアップの可能性を示している。
QPMCMC2は,ターゲット評価に$mathcalO(1)$と$mathcalO(log P)$ qubitsしか必要としない。
論文 参考訳(メタデータ) (2023-12-03T14:05:08Z) - Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
我々は、マルコフ連鎖モンテカルロ(MCMC)を本質的に並列なアルゴリズムであるシーケンシャルモンテカルロ(SMC)に置き換えることを提案する。
実験により、SMCと進化的アルゴリズム(EA)を組み合わせることで、MCMCの100倍のイテレーションでより正確な結果が得られることが示された。
論文 参考訳(メタデータ) (2023-05-30T06:17:35Z) - Quantum Metropolis-Hastings algorithm with the target distribution
calculated by quantum Monte Carlo integration [0.0]
MCMCの量子アルゴリズムが提案され、古典的なスペクトルギャップに対して$Delta$の2次スピードアップが得られる。
我々は状態生成だけでなく、ベイズ推定における共通課題であるパラメータの信頼区間も見いだすと考えている。
提案した信頼区間計算法では、$Delta$で$ell$スケールを計算するための量子回路へのクエリ数、$epsilon$で必要な精度$epsilon$、および標準偏差$sigma$$$ $ell$ as $tildeO(sigma/epsilonを演算する。
論文 参考訳(メタデータ) (2023-03-10T01:05:16Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - Parallel Approaches to Accelerate Bayesian Decision Trees [1.9728521995447947]
本稿では,MCMCにおける並列性を利用した2つの手法を提案する。
第一に、MCMCを別の数値ベイズ的アプローチで置き換える。
第2に、データのパーティショニングについて検討する。
論文 参考訳(メタデータ) (2023-01-22T09:56:26Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳(メタデータ) (2022-10-05T22:52:00Z) - De-Sequentialized Monte Carlo: a parallel-in-time particle smoother [3.97478982737167]
我々は、$mathcalO(log T)$ timeで$T$観測を処理できる新しい粒子スムーズなdSMC(de-Sequentialized Monte Carlo)を提案する。
これは標準粒子スムースラーと比較してよいが、その複雑さは$T$で線型である。
また、dSMCに基づく粒子ギブスサンプリングを設計し、並列ハードウェアで$mathcalO(log(T))$コストで状態空間モデルでパラメータ推論を行うことができる。
論文 参考訳(メタデータ) (2022-02-04T17:46:32Z) - Variational Combinatorial Sequential Monte Carlo Methods for Bayesian
Phylogenetic Inference [4.339931151475307]
Vari Combinatorial Monte Carlo (VCSMC) は複雑な構造について学習するための変分探索を確立する強力なフレームワークである。
本稿では,VCSMC と CSMC が,従来のタスクよりも高い確率空間を探索できることを示す。
論文 参考訳(メタデータ) (2021-05-31T19:44:24Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳(メタデータ) (2021-03-03T22:42:15Z) - On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
論文 参考訳(メタデータ) (2020-06-15T21:36:00Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。