Optimal and Efficient Online Inverse Optimization
Advances theoretical foundations of inverse optimization with practical computational efficiency improvements.
AI Summary
Researchers present a deterministic polynomial-time algorithm achieving optimal O(√d) regret for online inverse linear optimization, solving an open problem.
Excerpt
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