知识卡片：在线逆向线性优化的最优且高效算法

一句话结论

本文给出一个确定性算法，在在线逆向线性优化中达到最优的 (O(\sqrt d)) 遗憾，并将运行时间降到 (d) 与 (T) 的多项式，正面回答 Sakaue 提出的“能否在多项式时间内达到该遗憾”的问题。

事件概述或研究问题

在线逆向线性优化设定中，学习器先推荐一个动作，然后观察一个专家的选择；该专家在 (\mathbb{R}^{d}) 上最大化一个固定但未知的线性目标。学习器的目标是不观察该目标函数，也学会优化它。

材料指出，Sakaue 最近用一个随机算法取得了最优遗憾 (O(\sqrt d))，但该算法每轮需要 ((dT)^{O(d)}) 次线性优化，并询问这一最优遗憾能否在多项式时间内达到。本文回答：可以。

方法/产品要点

• 本文给出的是确定性算法。
• 对每个时间范围 (T)，遗憾均为 (O(\sqrt d))。
• 运行时间为 (d) 和 (T) 的多项式；摘要未给出具体多项式次数。
• 算法是 Sakaue 等与 Cai 等的 variable-metric algorithms 的变体。
• 关键机制：当查询点离度量更新发生的位置足够远时，撤销该度量更新。原文表述为：“a metric update is revoked once the query point moves far enough from where the update was made.”

主要结果或产业意义

主要理论结果是：在保持最优 (O(\sqrt d)) 遗憾的同时，把 Sakaue 随机算法中的指数级计算开销改为 (d) 和 (T) 的多项式时间。也就是说，本文同时实现了最优遗憾与多项式时间计算效率。

产业意义方面，材料未提供实验、系统实现或具体应用场景，因此实际产业影响待核实。可确认的是，它对在线决策、逆向优化和学习优化未知目标等理论问题具有直接意义。

为什么重要

本文正面回应了在线逆向线性优化中的一个核心计算效率问题：最优遗憾是否必然伴随指数级计算代价。答案是“不需要”——存在确定性多项式时间算法达到同一遗憾阶。

与已有相关卡片相比，本条与“稳定移动用于非对偶 Lipschitz 凸优化”“超越 Adam：SOAP 与 Muon”“STRACE 轨迹分析与因果提取”没有直接重叠，也不构成对它们的延续或更新；增量信息集中在在线逆向线性优化的“遗憾—计算效率”权衡上。

局限与不确定性

• 材料为 arXiv 预印本信息，是否已通过同行评审或会议接收，待核实。
• 摘要未给出算法的具体多项式次数、每轮线性优化次数、常数项或完整证明细节，待核实。
• 材料未提供实验或数值结果，实际部署效果待核实。
• 是否可推广到非线性目标、其他范数设定、带约束动作空间或更广泛的逆向优化问题，材料未说明，待核实。

可用于图书/PPT/简报的角度

• 作为一个“开放问题被正面解决”的理论算法案例。
• 展示从随机算法到确定性算法、从指数时间到多项式时间的效率提升。
• 讲解 variable-metric 方法与“撤销度量更新”这一技巧。
• 讨论在线学习中的遗憾界与计算复杂度如何同时优化。
• 用于说明逆向优化的基本设定：只观察专家选择，不观察其目标函数。

原始材料

• 英文标题：Optimal and Efficient Online Inverse Optimization
• 英文关键词：online inverse linear optimization; regret; deterministic algorithm; variable-metric algorithms; metric update; polynomial time
• arXiv ID：2610.08735v1
• 作者：Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff
• 发布时间：2026-10-06T17:37:24Z
• 分类：cs.LG, cs.DS
• 摘要 URL：https://arxiv.org/abs/2610.08735v1
• PDF URL：https://arxiv.org/pdf/2610.08735v1