pipette
ESEspañol

Optimal and Efficient Online Inverse Optimization

Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff

Preprint

In the authors' words

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 ; the goal is to learn to optimize this objective without observing it. Sakaue recently obtained the optimal regret with a randomized algorithm making linear optimizations per round, and asked whether it can be attained in polynomial time. We answer positively: our deterministic algorithm has regret for every horizon and runs in time polynomial in and . 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.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.