Search papers, labs, and topics across Lattice.
This paper introduces a deterministic algorithm for online inverse linear optimization that achieves optimal $O(\sqrt{d})$ regret, addressing the computational bottleneck of prior randomized methods. The algorithm achieves this by modifying variable-metric approaches, revoking metric updates when query points diverge sufficiently. This breakthrough enables polynomial-time execution for learning unknown linear objectives in online settings.
Optimal $O(\sqrt{d})$ regret in online inverse linear optimization is now achievable in polynomial time, shattering previous computational barriers.
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 regret $O(\sqrt 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.
