Research
Efficient Online Inverse Optimization with O(d) Regret
arXiv:2609.13440v1 Announce Type: new 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 o
arXiv:2609.13440v1 Announce Type: new 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^{Theta(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 loget potential by the trace power r(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.
Related
- Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization
- Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization
- Latent-IMH: Efficient Bayesian Inference for Inverse Problems with Approximate Operators
Source: arXiv cs.LG | 2026-09-15