ブラックボックス最適化の考え方

何を仮定できないかを先に決めることが、手法選びの出発点になる。

仮定できないもの#

• 勾配・ヘッセ行列
• 凸性、単峰性
• 関数の連続性すら怪しい場合がある
• 評価が決定的であること（同じ入力で同じ値が返るとは限らない）

それでも置く仮定#

何も仮定しなければ、ランダム探索に 勝てない。実際、すべての関数を平均すればどの手法も同じという主張が ノーフリーランチ定理。有効な手法は必ず何かを仮定している。

仮定	それを使う手法
近い点の値は近い（滑らかさ）	ベイズ最適化のガウス過程
良い解の近くに良い解がある	局所探索全般
変数間の相関に構造がある	CMA-ESの共分散行列
実効次元が低い	ランダム探索が効く場面

手法が何を仮定しているかと、対象の問題がその仮定を満たすかを 照らし合わせるのが、選択の実質。

評価回数の予算で考える#

予算	向く手法
〜数百回	ベイズ最適化
数千〜数万回	CMA-ES、進化計算
ノイズが大きい	SPSA、CMA-ES

参考文献#

• David H. Wolpert, William G. Macready. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation 1(1), 1997. https://doi.org/10.1109/4235.585893
• Charles Audet, Warren Hare. Derivative-Free and Blackbox Optimization. Springer, 2017. https://doi.org/10.1007/978-3-319-68913-5