arXiv cs.LG· Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff·· 11 小时前AI 评分17
在线逆优化实现最优遗憾与多项式时间：确定性算法回答 Sakaue 开放问题
Optimal and Efficient Online Inverse Optimization
AI 导读
针对在线逆线性优化，研究者提出一种确定性算法，在任意时间跨度 T 下取得 O(√d) 的最优遗憾，且运行时间为 d 和 T 的多项式级。此前 Sakaue 用随机算法达到该最优遗憾，但每轮需 (dT)^{O(d)} 次线性优化，并公开询问能否在多项式时间内实现。新算法是 Sakaue 等人与 Cai 等人变尺度算法的变体，当查询点远离更新位置时撤销度量更新。
来源：arXiv cs.LG · arxiv.org