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.
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
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...
The regret attainable in online convex optimization when access to the feasible set is limited to an exact linear optimization oracle is characterized and a curvature-dependent lower bound is identified above which the general characterization remains sharp.
Small-Gradient Skipping (SGS) is proposed, a mechanism that skips the update at rounds without a mistake, and applies it to online gradient descent, the online Newton step, and MetaGrad.
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-...
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· microsoft.comNov 16, 2026
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.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026