Abstract
データ駆動型の逆最適化は、最適化モデルの未知パラメータを、ノイズを含み、場合によっては最適でない意思決定の観測から推定する。適用範囲は、物流、ポートフォリオ選択、アソートメント、そしてエネルギー市場にまで及ぶ。KKT残差、変分不等式、または観測された意思決定への二乗距離に基づく既存手法は、非凸または非微分であり、サンプルサイズに対してスケールしにくく、ノイズの下でしばしば退化する。そこで本研究では、凸な実行可能集合上での線形な順問題目的に対する逆最適化のための 93\emph{Fenchel-Young (FY)損失} 00 アプローチを提案する。すなわち、正則化された順問題の劣等（サブオプティマリティ）損失が、構造化予測における Fenchel-Young損失と一致することを観察する。その結果得られる代理（サロゲート）は凸であり、閉形式の勾配を持ち、不可能（非実行可能）な観測にも頑健であり、反復ごとの計算コストが n に依存しない形で確率的勾配降下法により学習できる。理論面では、FY推定量の過剰リスクが、配備（デプロイ）に関連する 93\emph{regret}（後悔/損失）を制御することを示す。幾何学を考慮した上界を与え、正則化を不要とする強凸な実行可能集合では、パラメトリック 93\tilde O(p/n) であり、指数 93\beta \geq 1 を持つマージン条件のもとで多面体（ポリヘドラル）な実行可能集合では、93\lambda^93\star \asymp n^{-1/(2\beta)} において 93\tilde O((p/n)^{(\beta+1)/(2\beta)}) となる。実験的には、FY推定量は合成ベンチマーク（多面体、滑らか、強凸な実行可能集合を含む）およびUber Movement Los Angelesの最短経路データセットの両方において、KKT残差、変分不等式、セミパラメトリック、最大最適性マージンのベースラインを上回る。後者ではサブパーセントのregretを達成しつつ、計算は10倍から100倍高速である。
