Efficient Online Inverse Optimization with O(d) Regret

We give a deterministic algorithm for online inverse linear optimization with regret O(d), uniform in the horizon and O(d squared) 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 potential by the trace power (H-1/2), which is bounded outright and removes the 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.