# Efficient Online Inverse Optimization with O(d) Regret

arXiv: https://arxiv.org/abs/2609.13440 · HTML: https://mlsanity.com/paper/2609.13440/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 43 references that are in the map.
- First posted on arXiv 11 Sep 2026.

## Builds on (most cited first, 23 of 23)

- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Inverse Optimization: Theory and Applications](https://mlsanity.com/paper/2109.03920/) (2021)
- [Inverse Optimization with Noisy Data](https://mlsanity.com/paper/1507.03266/) (2015)
- [Data-driven Inverse Optimization with Imperfect Information](https://mlsanity.com/paper/1512.05489/) (2015)
- [Data-Driven Estimation in Equilibrium Using Inverse Optimization](https://mlsanity.com/paper/1308.3397/) (2013)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [Contextual Inverse Optimization: Offline and Online Learning](https://mlsanity.com/paper/2106.14015/) (2021)
- [An Online-Learning Approach to Inverse Optimization](https://mlsanity.com/paper/1810.12997/) (2018)
- [Contextual Recommendations and Low-Regret Cutting-Plane Algorithms](https://mlsanity.com/paper/2106.04819/) (2021)
- [Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates](https://mlsanity.com/paper/1506.04838/) (2015)
- [Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithms](https://mlsanity.com/paper/2305.07730/) (2023)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [ℓp Row Sampling by Lewis Weights](https://mlsanity.com/paper/1412.0588/) (2014)
- [Contextual Search in the Presence of Adversarial Corruptions](https://mlsanity.com/paper/2002.11650/) (2020)
- [Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel-Young Loss Perspective and Gap-Dependent Regret Analysis](https://mlsanity.com/paper/2501.13648/) (2025)
- [Inverse Optimization via Learning Feasible Regions](https://mlsanity.com/paper/2505.15025/) (2025)
- [Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets](https://mlsanity.com/paper/2602.01682/) (2026)
- [Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness](https://mlsanity.com/paper/2603.20826/) (2026)
- [Tight Generalization Bounds for Noiseless Inverse Optimization](https://mlsanity.com/paper/2605.08866/) (2026)
- [Inverse Optimization for Routing Problems](https://mlsanity.com/paper/2307.07357/) (2023)
- [Multiscale Reward Hedging from Correct Demonstrations](https://mlsanity.com/paper/2608.06825/) (2026)

## Built on by (most cited first, 3 of 3)

- [Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights](https://mlsanity.com/paper/2609.26978/) (2026)
- [Cogentic: Multi-Agent Orchestration for Automated Proof Discovery](https://mlsanity.com/paper/2609.40324/) (2026)
- [Optimal and Efficient Online Inverse Optimization](https://mlsanity.com/paper/2610.08735/) (2026)

## Abstract (arXiv)

We give a deterministic algorithm for online inverse linear optimization with regret O(d), uniform in the horizon and O(d2) 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 TTheta(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 logdet 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.