Optimal and Efficient Online Inverse Optimization

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 ℝd; the goal is to learn to optimize this objective without observing it. Sakaue recently obtained the optimal regret O(√ 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(√ 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.