arXiv：cs.LG· Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff·· 4 小时前AI 评分42
在线逆优化实现最优遗憾与多项式时间：确定性 O(√d) 算法
Optimal and Efficient Online Inverse Optimization
AI 导读
在线逆线性优化中，研究者提出一种确定性算法，在任意时间跨度 T 下取得 O(√d) 遗憾，且运行时间为 d 与 T 的多项式级别。该算法是 Sakaue 等人和 Cai 等人变度量算法的变体，当查询点远离更新位置时撤销度量更新，正面回答了 Sakaue 关于该最优遗憾能否在多项式时间内实现的疑问。
正文
Abstract:In online inverse linear optimization, a learner recommends an action and then observes the choice of an expert who maximizes a fixed, unknown linear objective on $\mathbb{R}^{d}$; the goal is to learn to optimize this objective without observing it. Sakaue recently obtained the optimal regret $O(\sqrt d)$ with a randomized algorithm making $(dT)^{O(d)}$ linear optimizations per round, and asked whether it can be attained in polynomial time. We answer positively: our deterministic algorithm has regret $O(\sqrt d)$ for every horizon $T$ and runs in time polynomial in $d$ and $T$. It is a variant of the variable-metric algorithms of Sakaue et al.\ and Cai et al., in which a metric update is revoked once the query point moves far enough from where the update was made.
| Subjects: | Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2610.08735 [cs.LG] |
| (or arXiv:2610.08735v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.08735 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Honghao Lin [view email]
[v1]
Tue, 6 Oct 2026 17:37:24 UTC (30 KB)
来源：arXiv：cs.LG · arxiv.org