グローバル化された敵対的後悔最適化：較正されていない予測で頑健な意思決定

arXiv cs.LG / 2026/3/30

💬 オピニオンIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、古典的な頑健最適化および後悔（regret）最適化の手法は、予測誤差が較正されていない場合に破綻しやすく、しばしば形式的な（空虚な）保証や、公称解（nominal solution）に比べて過度に楽観的な意思決定を招くと主張する。
それに対し、Globalized Adversarial Regret Optimization（GARO）を提案する。これは、敵対的後悔を「不確実性集合のサイズにわたって一様に」最悪ケースとオラクル性能との差として定義し、それを制御する。
GAROは、不確実性集合に対する確率的較正を要求せず、予測誤差を完全に把握したオラクルに対して、絶対的または相対的な性能保証を与えることを設計目標とする。
著者らは、相対レート関数を用いたGAROがLepskiの適応（adaptation）手法を一般化することを示し、さらに、多面体のノルム不確実性集合における、アフィンな最悪ケースコストに対する正確で扱いやすい（可換な）再定式化を導出する。
より一般の場合には、離散化と制約生成のアルゴリズムを提示し、収束保証を与える。また、実験により、最悪ケースと平均（mean）におけるアウト・オブ・サンプル間のトレードオフが改善されることを示す。

Abstract

最適化問題は、意思決定が行われる前に予測されなければならない不確実なパラメータに、日常的に依存しています。古典的なロバストおよび後悔（レグレット）定式化は、誤った予測を扱うよう設計されており、単純な設定では統計的な誤差上界を与えることができます。とはいえ、予測に厳密な誤差上界が欠けている場合（典型的に現代の機械学習手法ではそうなります）、古典的なロバストモデルはしばしば空疎な保証をもたらします。一方で、後悔定式化は逆説的に、名目上の解よりもさらに楽観的な意思決定を生成してしまうことがあります。ここで我々は、確率変数の不確実性集合のサイズが取り得るあらゆる場合にわたって一様に、最悪時コストとオラクルのロバストコストの差として定義される敵対的後悔を制御する意思決定枠組み、Globalized Adversarial Regret Optimization（GARO）を導入します。設計により、GAROは、不確実性集合に対するいかなる確率的なキャリブレーションも要求せず、予測誤差を完全に知っているオラクルに対して、絶対的または相対的な性能保証を提供します。相対率関数を備えたGAROは、ダウンストリームの意思決定問題に対するルペスキ（Lepski）の古典的適応手法を一般化することを示します。さらに、不確実性に対する最悪時コストがアフィン関数であり、ノルムの不確実性集合が多面体である問題に対して、厳密で計算可能な再定式化を導出します。また、一般の設定に対して、離散化と制約生成のアルゴリズムを提示し、収束保証を与えます。最後に、実験により、GAROが最悪時と平均のサンプル外性能の間のより好ましいトレードオフをもつ解、およびより強いグローバルな性能保証を実現することを示します。