从对偶损失视角重看逆线性优化，实现更优的在线学习性能。
Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel$-$Young Loss Perspective and Gap-Dependent Regret Analysis
- 用Fenchel-Younh损失统一理解在线学习方法
- 无需假设决策最优，仍可保证预测目标解释力
- 利用目标值间隙实现超越标准√T的收敛速度
本文重新审视Bärmann等人（2017）研究的在线学习在逆线性优化中的应用，目标是从代理的输入-输出序列中推断其未知的线性目标函数。首先，通过与在线凸优化中的Fenchel-Young损失的联系，提供了一种简洁的理解方式；作为副产品，我们给出了一个不依赖于代理决策最优性的离散子最优性损失的离线保证。其次，在假设代理决策问题中存在最优与次优目标值之间的间隙条件下，我们得到了子最优性损失与估计损失之和的上界，该上界与时间范围T无关。有趣的是，尽管损失函数及其定义域均不具备强凸性等理想性质，我们的间隙依赖分析仍实现了比标准O(√T)更快的收敛速率。
原文摘要 · Abstract (English)
This paper revisits the online learning approach to inverse linear optimization studied by Bärmann et al. (2017), where the goal is to infer an unknown linear objective function of an agent from sequential observations of the agent's input-output pairs. First, we provide a simple understanding of the online learning approach through its connection to online convex optimization of \emph{Fenchel--Young losses}. As a byproduct, we present an offline guarantee on the \emph{suboptimality loss}, which measures how well predicted objectives explain the agent's choices, without assuming the optimality of the agent's choices. Second, assuming that there is a gap between optimal and suboptimal objective values in the agent's decision problems, we obtain an upper bound independent of the time horizon $T$ on the sum of suboptimality and \emph{estimate losses}, where the latter measures the quality of solutions recommended by predicted objectives. Interestingly, our gap-dependent analysis achieves a faster rate than the standard $O(\sqrt{T})$ regret bound by exploiting structures specific to inverse linear optimization, even though neither the loss functions nor their domains enjoy desirable properties, such as strong convexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。