Learning to Assess the Reliability of Number-of-Runs Estimation in Stochastic Optimization

技術的概要：確率的最適化における実行回数の推定信頼性を評価する学習

問題提起
大規模な確率的最適化アルゴリズムのベンチマークは、実験的信頼性と計算効率の間に根本的な緊張関係に直面している。有効な性能評価には反復実行が必要であるが、アルゴリズムポートフォリオの規模や問題の次元が増大するにつれて、広範な反復のコストは急速に増大する。現在の慣行は、実行回数を 15、25、または 50 に固定するなどの静的な設計選択に依存しており、これは問題全体にわたってアルゴリズムの挙動が均一であるという暗黙の仮定を置いているが、この仮定は経験的証拠によってほとんど支持されていない。

最近の研究では、性能の安定性と分布の対称性を監視することで、インスタンスごとに必要な実行回数を適応的に推定する経験的オンラインヒューリスティックが導入された。この手法は総実行数を約 50% 削減することで効率を向上させるが、決定的な限界を有している：ケースのサブセット（5〜25% の乖離）において、推定された実行回数が不正確であることである。これらの不正確さは、すべての実行が完了した後になって初めて検出可能であり、リアルタイムの意思決定が求められる完全なオンラインベンチマークシナリオには不適切である。

手法
本研究は、既存の経験的オンラインヒューリスティックを学習ベースの拡張へと発展させ、実行回数推定の信頼性を早期に検出可能な自己評価システムへと変換することを提案する。

• データソースと注釈: 本研究は、20 次元（COCO ベンチマークスイート）の 24 問題クラスにおける Nevergrad フレームワークからの 11 最適化アルゴリズムの 132,000 回の実行から派生したデータセットを利用する。真のラベル（信頼できる対信頼できない推定）は、3 つの異常値検出方法（IQR、パーセンタイルトリミング、修正 z スコア）と 4 つの歪度閾値（0.05、0.10、0.15、0.20）を用いた元の適応的停止実験の事後分析によって確立された。
• 特徴量抽出: 教師あり学習を可能にするため、可変長の目的関数値の系列は固定次元の特徴ベクトルに変換される。合計 23 の特徴量が抽出され、以下のカテゴリに分類される：
  • 統計的: 平均、中央値、標準偏差、分散、四分位数、四分位範囲、MAD、変動係数。
  • 分布的: 歪度、尖度、エントロピー。
  • エネルギー関連: 和、絶対値の和、信号エネルギー、実効値（RMS）。
  • 形状と安定性: 性能改善の傾き、ローリング標準偏差、FFT エネルギー、自己相関。
• 学習タスク: この問題は、実行回数推定が正しいか（1）誤っているか（0）を予測する二値分類タスクとして定式化される。
  • クラス不均衡: データセットは強いクラス不均衡を示す。本研究は、過早な停止を回避するため、誤った推定（少数クラス）の検出を優先する。
  • モデル選択: 決定木、ランダムフォレスト、XGBoost、LightGBM、CatBoost といった木ベースおよびアンサンブルモデルに対して、Optuna を用いてハイパーパラメータ最適化を行う。目的関数は、偽陰性（信頼できない推定を信頼できると予測すること）が偽陽性よりも有害であるため、精度や F1 スコアではなく、Recall0（少数クラスの再現率）を最大化する。
  • 実験設定: 「構成内（within-configuration）」学習設定を採用する。モデルは、同じ最適化器、異常値検出方法、歪度閾値を共有するデータ上で訓練およびテストされる。これにより、3 方法 × 4 閾値 × 11 アルゴリズムの 132 の固有データセットが生成される。

主な貢献

1. 適応的停止の再定義: 本論文は、単に実行回数を推定することから、その推定の信頼性をリアルタイムで評価することへと焦点を移す。
2. 最適化ダイナミクスのための特徴量エンジニアリング: 最適化軌道から導出された 23 の統計的、エネルギー非依存、および形状/安定性特徴量の特定のセットを導入し、収束挙動を特徴づける。
3. 不均衡分類戦略: ベンチマーク文脈における不均衡データの処理に対する特定のアプローチを実証する。ここでは、信頼できない推定を見逃すこと（偽陰性）のコストが、冗長な実行（偽陽性）のコストを上回る。

結果
評価は、固定構成内での信頼性の学習において、顕著な課題と特定の成功を示している：

• 限られた一般化性: 有効な分類器（$F1_1 > 0.70$ かつ $Recall_0 > 0.80$ を満たす）は、132 の構成のうちわずか48.5%（64/132）で得られた。これは、単一の最適化器と固定された実験パラメータに制限された場合、信頼できるモデルを学習することの難しさを浮き彫りにしている。
• アルゴリズムのばらつき: 予測可能性はアルゴリズムによって大きく異なった。差分進化（DE）、対角 CMA、NGOpt14、NGOpt38 は最高成功率（有効構成 66.7%）を達成した一方、NaiveIsoEMNA は予測が最も困難であった（有効構成 8.3%）。
• ベースラインとのトレードオフ: 多数クラスベースライン（すべてのインスタンスを信頼できると予測する）と比較すると、訓練された分類器は $F1_1$ の点でしばしば劣っていた（データセットの 6.8% しかベースラインを上回らなかった）。しかし、ベースラインは $Recall_0$ が 0.00 であり、信頼できない推定を完全に特定できなかった。対照的に、訓練された分類器は一貫して 0.80 以上の $Recall_0$ 値を達成し、ベースラインが見逃した問題のある収束ケースを正常に特定した。

意義と主張
本論文は、構成内シナリオにおいて実行回数の信頼性を学習でき、高い少数クラス再現率で信頼できない推定を検出可能であると主張する。この能力により、適応的ヒューリスティックは、適応的実行推定の効率性を維持しつつ、リアルタイムの実験的決定を支援するシステムへと変容する。

しかし、著者はこれらの知見の範囲については控えめである。彼らは明確に、性能は「固定構成内の制限されたデータ多様性によって制限されている」と述べている。構成あたり 240 インスタンスしか存在しないため、モデルは多数クラス予測を超えて学習することに苦労する。本研究は、信頼性の予測は可能であるが、データが制限された環境では依然として困難であり、今後の研究は異なる最適化アルゴリズムからのデータを組み合わせて訓練の多様性を増やすシナリオを探るべきであると結論づけている。