Optimal and Efficient Online Inverse Optimization

Anupam Gupta; Guru Guruganesh; Honghao Lin; Vahab Mirrokni; Renato Paes Leme; David P. Woodruff

cs.LGOct 6, 2026

Optimal and Efficient Online Inverse Optimization

Authors: Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff

Organizations: Google Research · New York University · Carnegie Mellon University

Abstract

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 randomized algorithm making $(dT)^{O(d)}$ linear optimizations per round, and asked whether it can be attained in polynomial time. We answer positively: our deterministic algorithm has regret $O(\sqrt d)$ for every horizon $T$ and runs in time polynomial in $d$ and $T$ . It is a variant of the variable-metric algorithms of Sakaue et al.\ and Cai et al., in which a metric update is revoked once the query point moves far enough from where the update was made.

Figures & tables

Method	Regret	Uniform in $T$	Proper	Deterministic	Per-round cost
Bärmann et al. [ 4 , 5 ] (OGD/MWU)	$O(\sqrt{T})$	no	yes	yes	$O(\tau_{\mathrm{sol}}+d)$
Besbes et al. [ 7 , 8 ] (circumcenter)	$O(d^{4}\ln T)$	no	yes	yes	$\tau_{\mathrm{sol}}+\mathrm{poly}(d,T)$
Gollapudi et al. [ 16 ] (centroid)	$O(d\ln T)$	no	yes	yes	$\tau_{\mathrm{sol}}+\mathrm{poly}(d,T)$
Gollapudi et al. [ 16 ] (John ellipsoid)	$\exp(O(d\ln d))$	yes	yes	yes	$\tau_{\mathrm{sol}}+\mathrm{poly}(d,T)$
Sakaue et al. [ 28 ] (online Newton step)	$O(d\ln T)$	no	yes	yes	$O(\tau_{\mathrm{sol}}+d^{2}+\tau_{\mathrm{proj}})$
Sakaue [ 29 ] (second-order perceptron)	$O(d\ln T)$	no	yes	yes	$O(\tau_{\mathrm{sol}}+d^{2})$

Table 1: Regret

R_{T}

of online inverse linear optimization on the unit ball.

\tau_{\mathrm{sol}}

: one linear optimization over

X_{t}

;

\tau_{\mathrm{proj}}

: one Mahalanobis projection; † in expectation.

Panel of Figure 1 — Figure 1: One move of RVM $(\alpha)$ in the plane, to scale ( $\alpha=1$ ). The path (red) leaves the slab $L_{i}$ at $q_{i}$ and the slab $L_{j}$ at $q_{j}$ , turning at each revocation; the dotted segment is the single step with the metric frozen.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: A motion of the rounded RVM, not to scale. It advances in ticks (dots) and stops at $q_{i}$ , the last tick before the ray (dotted) leaves the slab $L_{i}$ , inside the darker outer half, where stretch $i$ is revoked.

Explore similar work

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
Sep 22, 2026Shinsaku SakaueMultiscale
Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
Sep 9, 2026Akira KitaokaLinear Programming Nonconvex
Lower Bounds for Linear-Oracle Online Learning
Sep 29, 2026Mohit Sinha\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Lower Bounds

Sep 22, 2026, stat.MLJ/K move · Enter open · S save

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

Shinsaku Sakaue

Multiscale

Open paper AskPDF arXiv

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the

d

-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is

O(\sqrt d)

in expectation for every time horizon, without knowledge of the horizon. The dependence on

d

is optimal up to a constant factor by the known

Ω(\sqrt d)

lower bound for horizons

T\ge d

. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the

O(\sqrt d)

regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.

Abstract

Explore similar work

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes

Lower Bounds for Linear-Oracle Online Learning