arXiv:2603.25948math.OCcs.LG2026-03

面对不可靠预测,新方法能保证决策在最坏情况下的稳定表现。

Globalized Adversarial Regret Optimization: Robust Decisions with Uncalibrated Predictions

  • 设计全局对抗后悔优化框架,统一控制不同不确定性规模下的最坏代价差距。
  • 在仿射代价函数与多面体范数不确定性下,可精确求解;一般情形有收敛算法。
  • 无需预测误差的概率校准,适合机器学习预测不准确的现实场景。

优化问题常依赖需预先预测的不确定参数。经典鲁棒与后悔模型虽能处理预测错误,在简单场景下提供统计误差界,但当现代机器学习方法缺乏严格误差界时,传统鲁棒模型常给出无意义保证,而后悔模型反而可能产生比名义解更乐观的决策。本文提出全局对抗后悔优化(GARO),通过统一控制所有不确定性集合大小下的对抗后悔(即最坏代价与已知预测误差的最优代价之差),实现对拥有完整预测误差信息的最优者的表现保证。该方法无需不确定性集的概率校准。我们证明,引入相对速率函数的GARO可推广经典Lepski适应方法至下游决策问题。对于仿射最坏代价函数与多面体范数不确定性集,推导出精确可解形式;针对一般情形,提出具有收敛性保障的离散化与约束生成算法。实验表明,GARO在最坏情况与样本外平均性能间取得更优权衡,且具备更强的全局性能保证。

原文摘要 · Abstract (English)

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 method of Lepski to downstream decision problems. We derive exact tractable reformulations for problems with affine worst-case cost functions and polyhedral norm uncertainty sets, and provide a discretization and a constraint-generation algorithm with convergence guarantees for general settings. Finally, experiments demonstrate that GARO yields solutions with a more favorable trade-off between worst-case and mean out-of-sample performance, as well as stronger global performance guarantees.

优化鲁棒决策预测误差

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。