pipette
ENEnglish

Optimal and Efficient Online Inverse Optimization

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

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.