Skip to content

Efficient Online Inverse Optimization with $O(d)$ Regret

Sep 2026 · 3 citations · ⚡ 1 influential · 43 references
Computer Science

TL;DR

This work builds on the variable-metric framework of Sakaue et al., adding a self-normalized rank-one update, and replaces the $\log\det$ potential by the trace power $\tr(H^{-1/2})$, which is bounded outright and removes the $\ln T$.

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 $\log\det$ 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.

View source

Similar papers

#machine learning Preprint Oct 2026

Optimal and Efficient Online Inverse Optimization

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 rando...

Anupam Gupta, G. Guruganesh, Hong-Hao Lin et al. · 1 citation

Lower Bounds for Linear-Oracle Online Learning

Can a constant number of linear minimizations per round improve on the $T^{3/4}$ regret rate of online Frank-Wolfe on general convex sets? Weibel et al. conjectured that fixed-coefficient methods cannot. We prove their conjecture and extend the lower bound to every deterministic learner in an oracle-only model. The lea...

Mohit Sinha · 0 citations
#machine learning Preprint Aug 2026

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

The upper bound for the expert problem is achieved by a corrected variant of Hedge, in which carefully designed correction terms cancel the unfavorable curvature arising in the alternating-regret analysis, and the same corrected-potential argument is extended to continuous action sets to obtain the optimal alternating-...

Meng-Xiao Zhang · 0 citations
Preprint Aug 2026

Optimal Alternating Regret for Online Learning and Games

The minimax-optimal alternating regret is settled, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex optimization (OCO) and a matching lower bound is proved of the $\Omega(\log T)$ factor.

Yixin Tao, Weiqiang Zheng · 2 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.