openreview

概要

• Huawei所属のCedric Malherbeらの研究グループによる論文
• 木探索アルゴリズムに基づく0-1組合せ最適化問題に対するblack-box solverを提案
  • ベイズ最適化に基づく手法と比較して計算コストが低く、進化計算アルゴリズムに基づく手法と比較して理論的な保証が強い
• 連続関数に対する木探索ベースの理論保証つきblack-box solverは提案されてきたが、組合せ最適化問題に対しては、連続関数の木探索と対応する概念がなく、前例があまりない
• 仮定の違いによって2つのアルゴリズム、OLTSとOCTSを提案。
• いずれのアルゴリズムも、線形の収束率を達成する。

問題設定

• バイナリ変数のベクトルを入力とする実数値関数$f$をブラックボックスな設定で最大化する
• 実行可能領域は$d$次元の単位超球の境界
• 当たり前だけど、線形性、2次性、sub-modularityは仮定しない
• 実行可能領域内の全ての点で$f$の値を評価できる

理論的な結果

設定

• 探索木として、左側の子ノードが親ノードと同じになるようなものを考える
• 単位超球の境界を定義域とする関数のリプシッツ性を、リプシッツ定数を$k$として$|f(x)-f(x’)|\leq k\cdot d_H(x, x’)$, $d_H$はハミング距離、とする
• 最適化したい関数$f$のリプシッツ定数$k$が既知とする
• $f$がただ一つの最適解$x^$を持つとして、$x^$におけるリプシッツ性が成立するような最大の定数$k^*$ をconditioning numberとする

結果

1. conditioning numberが既知の場合、問題の次元$d$とある定数$C$について、線形に収束する→OLTS algorithm
2. conditioning numberが未知の場合、$f$のリプシッツ定数$k$がわかっていれば、問題の次元$d$とある定数$C$について、線形に収束する→OCTS algorithm

実験

• ベンチマーク問題であるOneMax, Harmonic, LeadingOndesなどに対して、Random search (RS)と比較。（d=30, 50, 100）
• 当然っちゃ当然だけど、random searchよりも極めて優れた結果を示した
• より現実的な問題について、SA, RS, RLS(ランダム化局所探索), GA, EA, GHC(貪欲山登り)と比較。どの問題に対しても概ね他の手法を上回る性能を示した。
  • low autocorrelation binary sequences
  • concatenated trap
  • maxmum independent set
  • maxsat
  • ising model
  • contamination