論文の概要: 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種のサルモネラ菌に対するベイズ祖先形質再構成の大幅な高速化を図った。
関連論文リスト
- SMC Is All You Need: Parallel Strong Scaling [0.7374586159008119]
並列高強度スケーリングを実現するための完全並列シーケンシャルモンテカルロ法(pSMC)を開発した。
pSMC は無限小精度 MSE$=O(varepsilon2)$ に収束し、固定された有限時間複素度コスト=O(1)$ であり、効率リークがない。
論文 参考訳(メタデータ) (2024-02-09T04:13:38Z) - SpreadNUTS -- Moderate Dynamic Extension of Paths for No-U-Turn Sampling
& Partitioning Visited Regions [0.0]
本稿では,no-U-turn sampler (NUTS) として知られる特定のハミルトンモンテカルロ (HMC) アルゴリズムの変更を紹介する。
NUTS は NUTS よりも早くサンプル空間を探索することを目的としており、真分布への収束が NUTS より高速なサンプリング器を提供する。
論文 参考訳(メタデータ) (2023-07-09T05:00:25Z) - 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) - Orbital MCMC [82.54438698903775]
任意の微分同相写像から周期軌道を構築するための2つの実用的なアルゴリズムを提案する。
また,両カーネルの実用的メリットを実証した実証的研究を行った。
論文 参考訳(メタデータ) (2020-10-15T22:25:52Z) - Involutive MCMC: a Unifying Framework [64.46316409766764]
iMCMCでは,幅広いMCMCアルゴリズムについて述べる。
我々は、新しいMCMCアルゴリズムを開発するための設計原則として使用できる多くのトリックを定式化する。
後者は、既知の可逆MCMCアルゴリズムをより効率的な可逆アルゴリズムに変換する2つの例で示す。
論文 参考訳(メタデータ) (2020-06-30T10:21:42Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。