[2603.25948] Globalized Adversarial Regret Optimization: Robust Decisions with Uncalibrated Predictions

Mathematics > Optimization and Control arXiv:2603.25948 (math) [Submitted on 26 Mar 2026] Title:Globalized Adversarial Regret Optimization: Robust Decisions with Uncalibrated Predictions Authors:Jannis Kurtz, Bart P.G. van Parys View a PDF of the paper titled Globalized Adversarial Regret Optimization: Robust Decisions with Uncalibrated Predictions, by Jannis Kurtz and Bart P.G. van Parys View PDF Abstract:Optimization problems routinely depend on uncertain parameters that must be predicted before a decision is made. Classical robust and regret formulations are designed to handle erroneous predictions and can provide statistical error bounds in simple settings. However, when predictions lack rigorous error bounds (as is typical of modern machine learning methods) classical robust models often yield vacuous guarantees, while regret formulations can paradoxically produce decisions that are more optimistic than even a nominal solution. We introduce Globalized Adversarial Regret Optimization (GARO), a decision framework that controls adversarial regret, defined as the gap between the worst-case cost and the oracle robust cost, uniformly across all possible uncertainty set sizes. By design, GARO delivers absolute or relative performance guarantees against an oracle with full knowledge of the prediction error, without requiring any probabilistic calibration of the uncertainty set. We show that GARO equipped with a relative rate function generalizes the classical adaptation metho...