論文の概要: More Quantum Speedups for Multiproposal MCMC

• arxiv url: http://arxiv.org/abs/2312.01402v2
• Date: Tue, 5 Dec 2023 10:42:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-06 12:35:32.285123
• Title: More Quantum Speedups for Multiproposal MCMC
• Title（参考訳）: 多目的MCMCのさらなる量子スピードアップ
• Authors: Chin-Yi Lin, Kuo-Chin Chen, Philippe Lemey, Marc A. Suchard, Andrew J. Holbrook, Min-Hsiu Hsieh
• Abstract要約: マルチプロポサルマルコフ連鎖モンテカルロ(MCMC)アルゴリズムは、目標分布をより効率的にサンプリングするために、各イテレーションで複数の提案から選択する。 最近の研究は、そのような多目的MCMCアルゴリズムの2次量子スピードアップの可能性を示している。 QPMCMC2は,ターゲット評価に$mathcalO(1)$と$mathcalO(log P)$ qubitsしか必要としない。
• 参考スコア（独自算出の注目度）: 9.09160682938666
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multiproposal Markov chain Monte Carlo (MCMC) algorithms choose from multiple proposals at each iteration in order to sample from challenging target distributions more efficiently. Recent work demonstrates the possibility of quadratic quantum speedups for one such multiproposal MCMC algorithm. Using $P$ proposals, this quantum parallel MCMC QPMCMC algorithm requires only $\mathcal{O}(\sqrt{P})$ target evaluations at each step. Here, we present a fast new quantum multiproposal MCMC strategy, QPMCMC2, that only requires $\mathcal{O}(1)$ target evaluations and $\mathcal{O}(\log P)$ qubits. Unlike its slower predecessor, the QPMCMC2 Markov kernel (1) maintains detailed balance exactly and (2) is fully explicit for a large class of graphical models. We demonstrate this flexibility by applying QPMCMC2 to novel Ising-type models built on bacterial evolutionary networks and obtain significant speedups for Bayesian ancestral trait reconstruction for 248 observed salmonella bacteria.
• Abstract（参考訳）: マルチプロポサルマルコフ連鎖モンテカルロ(MCMC)アルゴリズムは、目標分布をより効率的にサンプリングするために、各イテレーションで複数の提案から選択する。 最近の研究は、そのような多目的MCMCアルゴリズムの2次量子スピードアップの可能性を示している。 P$の提案を用いると、この量子並列MCMC QPMCMCアルゴリズムは各ステップでの目標評価に$\mathcal{O}(\sqrt{P})$のみを必要とする。 ここでは,QPMCMC2という高速な量子多元性MCMC戦略を提案する。これは,$\mathcal{O}(1)$ターゲット評価と$\mathcal{O}(\log P)$クォービットのみを必要とする。 前者とは異なり、QPMCMC2 Markov kernel (1) は詳細なバランスを維持しており、(2) は大規模なグラフィカルモデルに対して完全に明示的である。 細菌進化ネットワーク上に構築された新規Ising型モデルにQPMCMC2を適用し,248種のサルモネラ菌に対するベイズ祖先形質再構成の大幅な高速化を図った。

関連論文リスト

• AutoStep: Locally adaptive involutive MCMC [51.186543293659376]
  AutoStep MCMCは、ターゲット分布の局所幾何学に適合したイテレーション毎に適切なステップサイズを選択する。 本稿では,AutoStep MCMCが,単位コスト当たりの有効サンプルサイズの観点から,最先端の手法と競合することを示す。
  論文  参考訳（メタデータ） (2024-10-24T17:17:11Z)
• Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition [6.872242798058046]
  逐次モンテカルロ法(SMC)アルゴリズムにより得られたサンプルの実証測度の下での関数の分散に関するバウンダリを証明した。 我々は,局所MCMC力学に依存する混合時間を用いて,真のマルチモーダル設定でバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2024-05-29T22:43:45Z)
• 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)
• SMC Is All You Need: Parallel Strong Scaling [0.695967916921061]
  並列高強度スケーリングを実現するための完全並列シーケンシャルモンテカルロ法(pSMC)を開発した。 pSMC は無限小精度 MSE$=O(varepsilon2)$ に収束し、固定された有限時間複素度コスト=O(1)$ であり、効率リークがない。
  論文  参考訳（メタデータ） (2024-02-09T04:13:38Z)
• Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
  我々は、マルコフ連鎖モンテカルロ(MCMC)を本質的に並列なアルゴリズムであるシーケンシャルモンテカルロ(SMC)に置き換えることを提案する。 実験により、SMCと進化的アルゴリズム(EA)を組み合わせることで、MCMCの100倍のイテレーションでより正確な結果が得られることが示された。
  論文  参考訳（メタデータ） (2023-05-30T06:17:35Z)
• Improving multiple-try Metropolis with local balancing [0.0]
  MTM(Multi-try Metropolis)はマルコフ連鎖モンテカルロ法である。 我々は,この重み関数が高次元の病理行動を引き起こすことを理論的にも経験的にも示している。 そこで本稿では,Zanella (2020) の局所平衡分布に類似した重み関数の利用を提案する。
  論文  参考訳（メタデータ） (2022-11-21T16:14:17Z)
• A quantum parallel Markov chain Monte Carlo [0.0]
  我々は、Gumbel-max トリックを用いて、一般化されたアセプション-リジェクトステップを離散最適化問題に変換する。 我々はGroverの量子探索アルゴリズムのよく知られた拡張の中にターゲット密度評価を埋め込む。
  論文  参考訳（メタデータ） (2021-12-01T01:25:06Z)
• Variational Combinatorial Sequential Monte Carlo Methods for Bayesian Phylogenetic Inference [4.339931151475307]
  Vari Combinatorial Monte Carlo (VCSMC) は複雑な構造について学習するための変分探索を確立する強力なフレームワークである。 本稿では,VCSMC と CSMC が,従来のタスクよりも高い確率空間を探索できることを示す。
  論文  参考訳（メタデータ） (2021-05-31T19:44:24Z)
• Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning [66.94149388181343]
  本稿では,MARLのためのQ$-learningアルゴリズムの新バージョンを提案する。 Q*$をアクセスしても、最適なポリシーを回復できることを示します。 また,プレデレータープリとマルチエージェントのStarCraftベンチマークタスクの性能向上を実証した。
  論文  参考訳（メタデータ） (2020-06-18T18:34:50Z)
• 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)

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

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