Cost-aware Stopping for Bayesian Optimization

技術要約：ベイズ最適化におけるコストを考慮した停止則

問題提起
自動機械学習、科学的発見、およびその他のベイズ最適化（BO）の応用において、実務者は高価なブラックボックス関数の評価をいつ終了すべきかを決定するという課題に直面している。既存の停止規則は存在するものの、評価コストの変動を原理的な方法で考慮できていないことが多い。

• ヒューリスティックな規則（例：固定の反復回数や、最良値が変化しなくなった時に停止するなど）は、理論的な保証に欠け、早期に停止しすぎたり、不必要な評価を招いたりする可能性がある。
• 後悔ベースの規則（例：UCB-LCB、Knowledge Gradient）は、単純な後悔（simple regret）を最小化するために理論的に裏付けられているが、通常は一様なコスト設定を想定している。これらは評価コストを明示的に考慮していないため、コストが高い場合に累積コストが増大し、*コスト調整済み後悔（cost-adjusted regret）*が高くなる傾向がある。
• コストを考慮した獲得関数（例：Pandora's Box Gittins Index (PBGI) や Log Expected Improvement per Cost (LogEIPC)）は、解の質とコストのトレードオフを最適化するために開発されているが、それらを適応的な停止規則と統合することについては、体系的な研究が行われていない。

核心となる目的は、期待コスト調整単純後悔（expected cost-adjusted simple regret）、すなわち単純後悔（見出された最良の解とグローバル最適値との差）とデータ収集の累積コストの総和を最適化する停止規則を設計することである。

手法
著者らは、Pandora's Box の意思決定フレームワークから導出された、新しい原理的なコスト考慮型停止規則を提案している。この手法は、2つの最先端のコスト考慮型獲得関数の間の理論的なつながりを確立している。

1. Pandora's Box Gittins Index (PBGI): 相関のあるベイズ最適化に適応させた、Pandora's Box 問題の動的計画法による解から導出される。
2. Log Expected Improvement per Cost (LogEIPC): ベイズ最適方策の一ステップ近似。

提案される停止規則は、PBGI/LogEIPC 停止規則と呼ばれ、「未観測の点が、その評価コストに見合う期待改善量を提供しない場合、最適化を停止すべきである」という条件によって定義される。数学的には、停止時刻 $\tau$ において以下が成立する場合に停止する：
$$\min_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{PBGI}^\tau(x) \geq y^*_{1:\tau}$$
または、等価的に：
$$\max_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{LogEIPC}^\tau(x) \leq 0$$
ここで、$y^*_{1:\tau}$ はこれまでに観測された最良の値である。

主な実装の詳細には以下が含まれる：

• 事後分布更新のタイミング: この規則は、現在の反復の事後分布更新後に計算された獲得関数の値（フォワードルッキング）を利用する。著者らは、これが「公正な価値（fair value）」という直感をより良く反映し、バックワードルッキングのアプローチよりも経験的な利点をもたらすと主張している。
• 未知のコストの扱い: コストが未知の場合、それらは確率的にモデル化され（例：対数コストに対するガウス過程）、期待コスト $E[c(x)]$ が停止条件に使用される。
• 安定化: モデルの変動や獲得関数の最適化の不完全さ（特に高次元において）による誤った停止を防ぐため、著者らは安定化期間を設け、停止信号に移動平均による平滑化を適用している。

主な貢献

1. 新しいコスト考慮型停止規則: 本論文は、Pandora's Box 理論から導出された、期待改善設計の原理に自然に拡張可能な適応的停止規則を提示している。これは、古典的なベイズ最適化とコスト考慮型ベイズ最適化の両方に適用可能な統一されたフレームワークを提供する。
2. 理論的保証: 著者らは、提案された停止規則が PBGI または LogEIPC 獲得関数と組み合わされたとき、期待コスト調整単純後悔に対して理論的な上限を満たすことを証明している。具体的には、この方策は「即時停止（immediate stopping）」のベースライン（最初の評価直後に停止する）よりも悪い結果にならないことが保証されている。これは、ベイズ最適化における適応的停止規則に対する、この種の最初の理論的保証である。
3. 経験的検証: 合成タスクおよび経験的ベンチマーク（ハイパーパラメータ最適化のための LCBench およびニューラルアーキテクチャ探索のための NATS-Bench）を用いた体系的な評価を行っている。

結果

• 合成タスク: 1D および 8D のベイズ後悔設定において、一様、線形、および周期的なコスト関数の下で、PBGI/LogEIPC 停止規則は、対応する獲得関数と組み合わされた場合、他のペア（UCB-LCB、LogEIPC-med、PRB を含む）と同等またはそれを上回る性能を一貫して示した。これは特に高コストのシナリオにおいて堅牢である。
• 経験的ベンチマーク:
  • LCBench（35 個のデータセット）において、提案された規則は PBGI または LogEIPC と組み合わされた際、約 75% のタスクでトップ 3 にランクインした。
  • NATS-Bench において、本規則は競争力のある性能を示し、事後的な最適性能（hindsight-optimal performance）に接近した。
  • 本規則は、反復上限（200 回）に達する前に確実に停止する一方で、ベースラインの後悔ベースの規則（SRGap-med や UCB-LCB など）は頻繁に早期停止に失敗し、過剰なコストを発生させている。
  • 著者らは、特定の小規模なデータセットにおけるパフォーマンスの低下は、停止規則自体ではなく、ベンチマーク固有の検証/テストのミスマッチに起因する可能性が高いと指摘している。

意義と主張
本論文は、ベイズ最適化における極めて重要かつ未探索の実用的検討事項である「コストを考慮した停止時期の決定」に対処している。

• 理論的進展: 本研究は、コスト考慮型獲得関数と適応的停止の間の溝を埋め、適応的な方策が即時停止よりも悪いコスト調整後悔を招かないという最初の形式的な保証を提供した。
• 実用的有用性: 提案された規則は、評価コストから直接閾値を導出することで、停止閾値（固定定数や中央値ベースの閾値など）のヒューリスティックなチューニングの必要性を排除する。
• 堅牢性: 本フレームワークは、様々なコスト構造やモデルの誤設定に対しても堅牢性を示しており、高価な最適化タスクにおけるヒューリスティックな停止基準に代わる、原理的な選択肢を提供する。

著者らは、本フレームワークがノイズを含む設定、マルチフィデリティ、またはバッチ評価、および代替の目的関数へと拡張可能であると結論づけているが、これらは現在の貢献ではなく、将来の方向性として記されている。