Efficient Online Inverse Optimization with O(d) Regret
Not on the map. Why?
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.
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
23 of 43 references.
References · 23
- 2018Stochastic bandits robust to adversarial corruptionscited by 119
- 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
- 2021Inverse Optimization: Theory and Applicationscited by 48
- 2015Inverse Optimization with Noisy Datacited by 34
- 2015Data-driven Inverse Optimization with Imperfect Informationcited by 34
- 2013Data-Driven Estimation in Equilibrium Using Inverse Optimizationcited by 32
- 2016Multidimensional Binary Search for Contextual Decision-Makingcited by 27
- 2018Contextual Search via Intrinsic Volumescited by 26
- 2021Contextual Inverse Optimization: Offline and Online Learningcited by 20
- 2018An Online-Learning Approach to Inverse Optimizationcited by 18
- 2021Contextual Recommendations and Low-Regret Cutting-Plane Algorithmscited by 15
- 2015Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updatescited by 14
11 more
- 2023Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithmscited by 10
- 2025Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Boundcited by 9
- 2014ℓp Row Sampling by Lewis Weightscited by 8
- 2020Contextual Search in the Presence of Adversarial Corruptionscited by 8
- 2025Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel-Young Loss Perspective and Gap-Dependent Regret Analysiscited by 8
- 2025Inverse Optimization via Learning Feasible Regionscited by 8
- 2026Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Setscited by 8
- 2026Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustnesscited by 6
- 2026Tight Generalization Bounds for Noiseless Inverse Optimizationcited by 6
- 2023Inverse Optimization for Routing Problemscited by 5
- 2026Multiscale Reward Hedging from Correct Demonstrationscited by 5
Built on by
Citing papers per year: 2026: 3.
3 papers.