Benchmark test of Black-box optimization using D-Wave quantum annealer

[Kashalpha]

一言でいうと

acquisition functionがQUBOになるようなblack-box最適化において、acquisition functionの最適化のソルバーにD-Wave 2000Q、シミュレーテッド・アニーリング(SA)、半正定値計画(SDP)を使った場合の比較を行った論文

論文リンク

https://arxiv.org/abs/2103.12320

概要

• 大本のアイデアは、Bayesian Optimization of Combinatorial Structures
• black-box関数はスパースなSKモデル（一定の確率でJ_ij=0となる）
• スパースなベイズ線形回帰の事後分布からのサンプリングにより、acquisition functionのパラメータを決定
• ベイズ線形回帰の尤度関数にはガウス分布を使用し、事前分布にはhorseshoe分布を使用
• QUBOソルバー（D-Wave 2000Q、SA、SDP）を使って、acquisition functionの最適解を探索
• 50のインスタンスを生成、各インスタンスで10回アルゴリズム実行
• 評価指標は、各イテレーション回数におけるresidual energyの全インスタンスとトライアルでの平均
• SDPと比較するとD-WaveマシンとSAは優れているが、D-WaveマシンとSAには差がない
• オリジナルの論文ではSDPのほうがSAよりも良かったが、問題が異なるため違う結果となっている -> SDPでは局所最適になっている？

先行研究

コメント