Efficient online method cuts error in inverse optimization tasks
Efficient Online Inverse Optimization with $O(d)$ Regret
Machine LearningData Structures and Algorithms
Summary
Inverse optimization means figuring out the rules or costs that led to a series of decisions. This paper presents a new way to do this step-by-step quickly and with less total error, even when seeing many rounds of data. The authors’ method improves over past work by running much faster and having clearer guarantees on how much error accumulates. They also extend the method to handle messy or changing data and broader types of problems.
What this means in practice
- •For operations research teams: Integrate the method to recover unknown linear cost parameters efficiently from observed decisions over time, improving adaptive system tuning.
- •For machine learning engineers: Use the algorithm to estimate underlying model parameters in adaptive settings where data arrives sequentially with possible noise or corruption.
Authors
Yang Cai, Anupam Gupta, Vineet Gupta, Guru Guruganesh, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Renato Paes Leme, Grigoris Velegkas, Di Wang
Abstract
We give a deterministic algorithm for online inverse linear optimization with regret $O(d)$, uniform in the horizon and $O(d^{2})$ time per round. A bound of this order was obtained recently by Dewasurendra, settling a question of Gollapudi et al.\ and of Oki and Sakaue, but by an improper rule that enumerates covers at every scale and costs $T^{Θ(d)}$ a round; ours is the first efficient such bound and the first proper one. We build on the variable-metric framework of Sakaue et al., adding a self-normalized rank-one update, and we replace the $\log\det$ potential by the trace power $\tr(H^{-1/2})$, which is bounded outright and removes the $\ln T$. The bound also holds against an expert that does not optimize, and we give corruption-robust and rank-adaptive variants, and an application to convex minimization.