A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization

技術要約：組合せ最適化のための圧縮センシングに着想を得たモンテカルロ法

問題提起
本論文は、離散的なバイナリ空間 $\{0,1\}^N$ で定義される組合せ最適化問題を解く際の課題に取り組んでいる。著者らは、目的関数（コストまたは報酬）が複雑で、非凸、非微分的、あるいは明示的な解析形式を持たない「ブラックボックス」であるシナリオに焦点を当てている。これらの問題（一般化イジング・ハミルトニアン、ナップサック問題、巡回セールスマン問題など）は、総当たり攻撃や単純な探索によってアプローチした場合、指数関数的な時間計算量に苦しむ。シミュレーテッド・アニーリングや遺伝的アルゴリズムのようなメタヒューリスティクスは標準的ではあるが、著者らは、一般的なバイナリコスト関数に対して効率的な手法は依然として限られていると主張している。

手法：モンテカルロ圧縮最適化 (MCCO)
提案されている解決策は、モンテカルロ圧縮最適化（MCCO）アルゴリズムである。これは、圧縮センシング、統計的圧縮学習、およびモンテカルロ法の原理を統合し、サンプリング中に最適値そのものが直接観測されない場合でも、その関数の値のサンプルに基づいてグローバルな最適解を見つけ出すものである。

アルゴリズムは以下のステップで進行する：

1. ランダムサンプリング: 一様分布から $n$ 個のインデックスを抽出し、目的関数 $f$ のサンプル $S_f$ を生成する。
2. 閾値処理: サンプルに対してハード閾値演算子 $T_t$ を適用し、特定の閾値 $t$ 未満の値をゼロにする。このステップは、単純なランダム線形写像よりも優れた性能を発揮するための非線形性を導入するため、極めて重要である。
3. スケーチャリング（計測）: 閾値処理されたサンプルにスケーチャリング写像 $\Phi$ を適用し、スケッチベクトル $y$ を生成する。このベクトルには、分布の一般化モーメントの経験的推定値が含まれる。本論文では、3種類のスケッチ関数を利用している：
   • クアドラプレット（4つ組）/ クインテット（5つ組）相互作用: 局所的なビット列の相互作用（例：連続する4つまたは5つのビット）に基づく構造化された決定論的写像。
   • ランダムスケッチ: ガウス分布から抽出された係数を持つ行列。
4. デコーディング（復元）: $y$ から推定値 $\tilde{f}$ を再構成するために、貪欲なデコーディング手順 $\Delta$（数値実験では直交マッチング追跡法：Orthogonal Matching Pursuitを使用）を適用する。著者らは、特定のサンプルへの過学習を避け、分布のグローバルな特徴を捉えるために、$\ell_1$ 最小化（基底追求法：Basis Pursuit）ではなく貪欲法を明示的に選択している。
5. 最適化: 再構成された関数 $\tilde{f}$ の最大値を、グローバルな最適値の推定値とする。

この手法は、「圧縮可能（compressible）」な問題、すなわち、コスト関数が既知の基底における短いルール（疎な表現）によって決定または良好に近似できる問題（たとえその表現がユーザーに明示的に知られていなくても）向けに設計されている。

主な貢献

• アルゴリズムの新規性: 圧縮センシングの復元技術を組合せ最適化へと転用し、特にモンテカルロの設定において過学習を防ぐために貪欲法を活用したMCCOを導入した。
• 理論的正当性: 理論的分析（定理1）を提供し、サンプリングとスケーチャリングの過程で真の最大値が生存する確率は、目的関数の最大値と第2最大値の間のギャップの平均と分散に依存することを示した。十分なサンプリングが行われれば、最大値が高い確率で保持されることを証明している。
• 実践的な実装: MCCOを実装したオープンソースのPythonライブラリである TrOMA (Tractable Optimization Modeling Approach) を開発した。このライブラリはハードウェアに依存せず（古典的および量子バックエンド、特にIBMの量子コンピュータをサポート）、ユーザーは単にコスト関数を提供するだけで、あらゆる問題を最適化できる。
• 定義された範囲: 著者らは「圧縮可能」な問題のクラスを定義し、MCCOがこれら（多くのNP完全問題を含む）に対して特に効果的であることを主張している。

数値結果
著者らは、サイズ $N=12$（$2^{12}$ の空間）の問題（圧縮可能な問題のクラスからランダムに抽出）を用いて数値シミュレーションを行った。そして、MCCOを Dual Annealing（シミュレーテッド・アニーリングと高速アニーリングの組み合わせ）と比較した。

• 性能: 構造化されたスケッチ関数（クアドラプレットおよびクインテット）を用いたMCCOは、Dual Annealingを上回った。
  • 成功率: クアドラプレット・スケッチを用いたMCCOは、約58%のケースでグローバルな最大値を回収し、クインテットでは約49%であったのに対し、Dual Annealingは約46%であった。
  • 近接性: グローバルな最大値が見つからなかった場合でも、MCCOの推定値は最適値に著しく近かった。クアドラプレットの場合、推定値の91%が真の最適値とのハミング距離1以内にあったのに対し、Dual Annealingでは81%であった。
  • サンプル効率: MCCOは、小さなサンプルサイズ（50から400サンプル）においても、競争力のある、あるいは優れた性能を示した。
• ランダムスケッチ: ガウス分布によるランダムスケッチを用いたMCCOは、構造化スケッチよりも性能が悪く、グローバルな最適値の回収に関してはDual Annealingと同等であった（6%）。ただし、ハミング距離の観点では、純粋なランダム推測よりも優れた性能を示した。

意義と主張
本論文は、MCCOが、広範な組合せ問題（特に「圧縮可能」な問題）に対して、Dual Annealingのような確立されたメタヒューリスティクスに代わる競争力のある選択肢を提供すると主張している。その意義は、以下の点にある：

1. 勾配情報を必要とせずに、ブラックボックスかつ複雑な目的関数を扱うことができる。
2. （未知であっても）基礎となる問題の構造の疎性を活用し、より少ない関数評価で最適解を見つけることができる。
3. ヒューリスティックなパラメータやスケッチ関数を調整することで、利用可能な計算リソースに合わせてチューニングが可能である。
4. 構造化行列のデコーディングは量子アルゴリズムによって促進できるため、古典的最適化と量子コンピューティングの架け橋となる。

著者らは、MCCOの適用限界に関する正確な境界については、圧縮可能な問題のクラスは大きいものの、MCCOがすべての手法を凌駕する正確な限界を特定することは、さらなる調査が必要な未解決の領域であるとして、慎重な姿勢を維持している。彼らは、TrOMAライブラリを通じてコミュニティがこの手法をテストすることを推奨している。