論文の概要: SMC Is All You Need: Parallel Strong Scaling

• arxiv url: http://arxiv.org/abs/2402.06173v2
• Date: Sun, 2 Jun 2024 19:19:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-04 18:53:33.884635
• Title: SMC Is All You Need: Parallel Strong Scaling
• Title（参考訳）: SMCは本当に必要なもの:パラレル・ストロング・スケーリング
• Authors: Xinzhu Liang, Joseph M. Lukens, Sanjaya Lohani, Brian T. Kirby, Thomas A. Searles, Kody J. H. Law,
• Abstract要約: 並列高強度スケーリングを実現するための完全並列シーケンシャルモンテカルロ法(pSMC)を開発した。 pSMC は無限小精度 MSE$=O(varepsilon2)$ に収束し、固定された有限時間複素度コスト=O(1)$ であり、効率リークがない。
• 参考スコア（独自算出の注目度）: 0.695967916921061
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Bayesian posterior distribution can only be evaluated up-to a constant of proportionality, which makes simulation and consistent estimation challenging. 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 Mean Square Error (MSE)$ = O(1/NP)$, where $N$ denotes the number of communicating samples in each processor and $P$ denotes the number of processors. In particular, for suitably-large problem-dependent $N$, as $P \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 は Mean Square Error (MSE)$ = O(1/NP)$ の理論的収束率を持ち、$N$ は各プロセッサにおける通信サンプルの数を表し、$P$ はプロセッサ数を表す。 特に、問題依存の$N$ に対して、$P \rightarrow \infty$ は無限小精度 MSE$=O(\varepsilon^2)$ に収束し、固定された有限時間複雑度コスト=O(1)$ と効率リークのない、すなわち計算複雑性のコスト=O(\varepsilon^{-2})$ に収束する。 pSMC法とMCMC法を比較するため,ベイズ推定問題もいくつか検討されている。

関連論文リスト

• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation [0.0]
  量子モンテカルロ積分(Quantum Monte Carlo integration, QMCI)は、確率変数の予測を推定する量子アルゴリズムである。 本稿では直交級数密度推定に基づいて$U_X(t)$を分割する手法を提案する。 本手法は,回路深度と総クエリ複雑性のスケーリングを,それぞれ$O(sqrtN)$と$O(N3/2)$として達成する。
  論文  参考訳（メタデータ） (2024-06-04T01:50:21Z)
• Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition [6.872242798058046]
  逐次モンテカルロ法(SMC)アルゴリズムにより得られたサンプルの実証測度の下での関数の分散に関するバウンダリを証明した。 我々は,局所MCMC力学に依存する混合時間を用いて,真のマルチモーダル設定でバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2024-05-29T22:43:45Z)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。 本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。 Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
  論文  参考訳（メタデータ） (2024-05-24T13:33:30Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• More Quantum Speedups for Multiproposal MCMC [9.09160682938666]
  マルチプロポサルマルコフ連鎖モンテカルロ(MCMC)アルゴリズムは、目標分布をより効率的にサンプリングするために、各イテレーションで複数の提案から選択する。 最近の研究は、そのような多目的MCMCアルゴリズムの2次量子スピードアップの可能性を示している。 QPMCMC2は,ターゲット評価に$mathcalO(1)$と$mathcalO(log P)$ qubitsしか必要としない。
  論文  参考訳（メタデータ） (2023-12-03T14:05:08Z)
• Convergence Analysis of Stochastic Gradient Descent with MCMC Estimators [8.493584276672971]
  勾配降下(SGD)とその変種は機械学習に不可欠である。 本稿では,マルコフ連鎖モンテカルロ(MCMC)推定器を用いて勾配を計算するSGDアルゴリズムについて考察する。 MCMC-SGDはサドル点から脱出し、$(epsilon,epsilon1/4)$2次定常点に達することが示されている。
  論文  参考訳（メタデータ） (2023-03-19T08:29:49Z)
• 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)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• 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)

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

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