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

Yang Cai; Anupam Gupta; Vineet Gupta; Guru Guruganesh; Yanchen Jiang; Christopher Liaw; Aranyak Mehta; Renato Paes Leme

cs.LGSep 11, 2026

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

Authors: Yang Cai, Anupam Gupta, Vineet Gupta, Guru Guruganesh, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Renato Paes Leme,

Organizations: Google Research · Yale University · New York University · Google DeepMind

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^{Θ(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.

Figures & tables

Method	Regret	Uniform in $T$	Proper	Per-round cost
Bärmann et al. [ 5 , 6 ] (OGD/MWU)	$O(\sqrt{T})$	no	yes	$O(\tau_{\mathrm{sol}}+d)$
Besbes et al. [ 10 , 11 ] (circumcenter)	$O(d^{4}\ln T)$	no	yes	$\mathrm{poly}(d,T)$
Gollapudi et al. [ 20 ] (centroid, scale $1/T$ )	$O(d\ln T)$	no	yes	est. $O(\tau_{\mathrm{sol}}+d^{5}T^{3})$
Gollapudi et al. [ 20 ] (John ellipsoid)	$\exp(O(d\ln d))$	yes	yes	$\mathrm{poly}(d,T)$
Sakaue et al. [ 40 ] (online Newton step)	$O(d\ln T)$	no	yes	$O(\tau_{\mathrm{sol}}+d^{2}+\tau_{\mathrm{proj}})$
Sakaue [ 41 ] (second-order perceptron)	$O(d\ln T)$	no	yes	$O(\tau_{\mathrm{sol}}+d^{2})$

Table 1: Online inverse linear optimization;

\tau_{\mathrm{sol}}

is one linear optimization and

\tau_{\mathrm{proj}}

one Mahalanobis projection onto the domain,

O(d^{3})

for the ball [ 40 ] . The count

T^{\Theta(d)}

is from [ 17 ] itself; there the per-round work is the maximization of a nonconvex vote over

X_{t}

, for which a linear optimization oracle does not suffice.

Panel of Figure 1 — Figure 1: Four rounds in the plane. The shaded set is $\{u:\|u\|_{H_{t}}\leq\alpha\}$ ; steps are large in unexplored directions and short in explored ones, with the preconditioner bending the step away from $v_{t}$ . Drawn with $\alpha=\tau=1$ .

Optimal and Efficient Online Inverse Optimization
Oct 6, 2026Anupam Gupta, Guru Guruganesh, Honghao Lin +3
Google Research · New York University · Carnegie Mellon University
Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
Sep 22, 2026Shinsaku Sakaue
Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
Sep 9, 2026Akira KitaokaRegret Minimization

Oct 6, 2026J/K move · Enter open · S save

Optimal and Efficient Online Inverse Optimization

Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni+2

Google Research · New York University · Carnegie Mellon University

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Optimal and Efficient Online Inverse Optimization

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