Source-linked AI summary
Optimal and Efficient Online Inverse Optimization
Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff
TL;DR
Online inverse linear optimization seeks to learn an expert’s unknown linear objective from observed choices, with optimal regret and efficient computation as the target. The paper uses variable-metric updates that are revoked when the query leaves their slabs. It reports optimal regret uniformly over horizons with a deterministic proper algorithm and polynomial running time.
Problem
The learner must match an expert’s choices under an unknown fixed linear objective, and the optimal regret bound had not been achieved by a deterministic, proper, polynomial-time learner.
Source: §1 · pp. 1–2Method
A deterministic proper variable-metric algorithm revokes each stretch when the query leaves its associated slab.
Source: §1.1 · p. 5Results
The algorithm attains optimal regret uniformly over horizons and has polynomial arithmetic cost, while the inverse-optimization reduction uses one linear optimization over Xt per round.
Source: §1.1 · pp. 3–4Takeaways & Limitations
The optimal regret order is attainable by a deterministic proper learner without knowing the horizon or restarting.
Source: §1.1 · p. 3The main complexity bounds count real-RAM arithmetic operations; polynomial bit complexity is provided by a rounded variant in Appendix A.
Source: §2.1 · p. 8
Abstract
from arXiv · showhide
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.
1 Introduction
Online inverse linear optimization asks a learner to match an expert’s choices under an unknown linear criterion, using only observed actions. The paper presents a deterministic proper learner with optimal regret and polynomial computation, built around revocable metric updates.
1 Introduction
- The learner observes an expert’s maximizing action but not the expert’s fixed objective or the value of the mistake.The goal is to keep cumulative shortfall, measured under the expert’s criterion, small.Source: §1 · p. 1
- Before this work, optimal regret was attained only by a randomized improper rule without a polynomial running-time bound, while the best known proper, deterministic, and efficient bounds were O(d).The cited optimal-order approach uses polynomial feature spaces and can require (dT)^O(d) linear optimizations per round.Source: §1 · p. 3
1.1 Our Results
- The algorithm achieves optimal regret uniformly over horizons while remaining deterministic, proper, and polynomial-time.It is anytime and needs neither the horizon nor restarts.Source: §1.1 · pp. 3–4
- The game guarantee transfers to online inverse linear optimization for every adaptive sequence of action sets, using one linear optimization over Xt per round.The reduction makes the game learner’s query its objective estimate and bounds action shortfall by twice the game regret.Source: §1 · p. 3, §1.1 · p. 4
- The regret order is optimal: every learner, deterministic or randomized, faces a matching lower bound for horizons T ≥ d.The paper identifies the optimal regret as Θ(R√d).Source: §1.1 · p. 4
- RVM(α) adapts variable-metric updates by revoking a stretch when the query leaves its associated slab.The metric records learned directions; revocation lets the query change direction when it reaches a slab boundary.Source: §1.1 · p. 4
2 Analysis
The analysis establishes a regret guarantee for every horizon and strong separation oracle, then accounts for the move, stretch lifetimes, surviving stretches, and computational cost.
2 Analysis
- Theorem 2.1 gives a regret guarantee for every horizon, comparator w*, and strong separation oracle.The reduction yields a deterministic proper learner whose queries are estimates of the hidden objective.Source: §2 · p. 6
2.1 The move and its cost
- Round t uses O(td^2 + t^2d) arithmetic operations, averaging O(d^2 + Td) per round over the first T rounds.The stated counts use the real-RAM model; a rounded variant with polynomial bit complexity is given in Appendix A.Source: §2 · p. 6, §2.1 · p. 8
- The move is uniquely defined and piecewise linear, with at most one more path segment than the number of stretches revoked.Each revoked stretch is removed when the path reaches the boundary of its slab.Source: §2.1 · p. 7
2.2 One move
- A single move tracks the change in squared distance to w* in the current metric, including changes caused by revocations.The query follows the inverse-metric direction of the feedback vector; the move cannot travel arbitrarily far along that direction in one round.Source: §2.2 · p. 8
2.3 The lifetime of a stretch
- Revocation refunds a stretch’s quadratic penalty, leaving a loss-linear term controlled by the slab boundary.A revoked stretch pays for its preceding step; a surviving stretch leaves a residual term for the next potential bound.Source: §2.3 · p. 9
2.4 The surviving stretches
- The surviving-stretches argument bounds the residual contribution using the trace of the inverse metric built from surviving stretches.The analysis identifies this trace as an A-optimality criterion when stretches are viewed as observations.Source: §2.4 · p. 10
3 Further Properties
The section explains why stretches must be revoked at slab boundaries and gives a skipping variant that reduces the number of active stretches and computational cost.
3.1 Why revocation, and why on the boundary
- Without revocation, repeated feedback in one direction can stall the query: for d ≥ 10, it never reaches w* and incurs loss at least R(1−3/d) each round.The example uses K1 = RB and an oracle returning e1 in every round.Source: §3.1 · p. 11
- A stretch remains active only until the query advances 4αs_i^2 beyond its creation point, preventing repeated confirmation from accumulating weight indefinitely.The revocation rule takes effect at the slab boundary.Source: §3.1 · p. 11
3.2 Fewer active stretches
- Skipping stretch t whenever s_t^2 ≤ (t+1)^−4 limits the active set to O(d log t) stretches.The variant retains the analysis of RVM for stretches it does make.Source: §3.2 · p. 11
4 Conclusion and AI Disclosure
The conclusion presents a deterministic proper learner with optimal-order regret and polynomial-in-d-and-T arithmetic cost, while leaving horizon-independent polynomial-in-d runtime open. It also describes an extension to corrupted feedback and discloses the role of automated proof generation.
4 Conclusion and AI Disclosure
- The learner achieves regret O(√d) with polynomial-in-d-and-T arithmetic cost, and a rounded variant uses polynomial bit operations per round.The conclusion identifies O(√d) as the optimal order.Source: §4 · p. 12
- Revoking stretches when the query moves far enough from their creation point lets their weight remain a constant multiple of 1/s².This is the change to the variable-metric method highlighted by the authors.Source: §4 · p. 12
- The average arithmetic cost is O(d² log T) per round, so achieving O(√d) regret with poly(d) work independent of T remains open.The logarithmic factor reflects the number of active stretches.Source: §4 · p. 12
- Colosseum [12] initially produced the proof end to end; the authors verified it and edited it for clarity.The raw output and a Lean 4 verification are available at links referenced in the paper.Source: §4 · p. 12
- For feedback with total violation C, the extension gives regret O(√d + C) without knowing C, unlike [10, Section 3.2], which requires an upper bound on C.The authors chose to focus the main presentation on revocable stretches.Source: §4 · p. 12
A Polynomial Bit Complexity
A rounded version of RVM retains O(√d) regret with polynomial bit complexity under a finite-precision reply interface. Rounding uses slack in the weights and slabs so queries remain exact dyadic vectors.
A Polynomial Bit Complexity
- The rounded algorithm retains regret O(√d) with bit operations polynomial in d, log t, and the encoding length of R.The bound is stated relative to the reply interface described in the appendix.Source: A Polynomial Bit Complexity · pp. 14–15
- Rounding uses smaller weights and wider slabs to leave slack, rounds replies inward and velocities toward zero, and revokes stretches in the outer half of a slab.The inverse metric is stored using an integer matrix's determinant and adjugate to avoid accumulating denominators.Source: A Polynomial Bit Complexity · p. 15
- The bit model reads replies through a coordinate interface at requested precision, and outputs queries exactly as dyadic vectors.When reply coordinates are explicit rationals, the interface rounds them at additional cost polynomial in their encoding length.Source: A Polynomial Bit Complexity · p. 15
- The reduction yields a proper learner in the bit model, answering [27] relative to the specified reply interface.The theorem's constant 21 in place of 51/8 is attributed to the slack.Source: A Polynomial Bit Complexity · pp. 14–15
A.1 The rounded algorithm
The rounded algorithm discretizes each round's motion under a metric built from active stretches. It rounds replies and velocities to a dyadic grid, stopping motions before leaving a slab and revoking stretches in its outer half.
A.1 The rounded algorithm
- The step scale is α = R/(8ν), while the grid uses g_t = 2^-b_t with b_t = O(log(d(t + 1))).The precision makes the grid fine enough for the stated rounding bounds.Source: §A.1 · pp. 15–16
- Each round rounds the reply inward, then moves in discrete ticks using the inverse metric of active stretches until time runs out or a slab boundary is near.After each motion, stretches whose query displacement reaches half their slab width are revoked.Source: §A.1 · p. 15
- A motion stops at the last tick before leaving an active slab, so revocation occurs in the outer half rather than exactly at the boundary.The figure's darker shells mark the outer halves where stretches are revoked.Source: §A.1 · pp. 15–16, Figure 2 · p. 16
- The rounded motion controls velocity and metric growth: velocities stay within distance d g_t of the metric-preconditioned reply, and the trace is bounded by d + t³/64.The lemma also bounds stretch weights and the query norm.Source: §A.1 · p. 16
- Every motion lasts a positive multiple of αg_t, and every stretch remains in its slab while active before being revoked at a displacement of at least half its width.Only the last motion of a round need not revoke a stretch.Source: §A.1 · p. 17
A.2 Regret
The regret analysis adapts a ledger to rounded replies and motions. It bounds movement through stretch refunds and charges surviving stretches to a potential.
A.2 Regret
- When a stretch is made, its refund controls the loss term because its displacement is bounded by the slab half-width and γ_t h_t = α/2.The resulting coefficient on the rounded loss lies between −3α and −α.Source: §A.2 · p. 18
- When no stretch is made, the ledger bounds the loss term, while accumulated rounding errors are bounded by 129/1024 times α² per round.The proof also bounds α²s_t² by α²(t + 1)^−2 in this case.Source: §A.2 · p. 18
- A surviving stretch decreases the potential by at least its normalized squared reply magnitude, using the rounded-reply norm bound.The proof applies the surviving-stretch argument with the rounded direction in place of the original reply.Source: §A.2 · p. 18
- A determinant-and-trace argument bounds the number of active stretches using tr H_t ≤ d + t³/64.Each determinant factor is at least 65/64.Source: §A.2 · p. 19
A.3 Exact integer arithmetic
The rounded variable-metric method is implemented with exact integer arithmetic by storing a determinant and adjugate instead of the inverse metric. Rank-one stretch updates and revocations preserve this representation, while the bit-length analysis bounds the algorithm’s computation and memory.
A.3 Exact integer arithmetic
- Queries are computed exactly throughout each round, and the only roundings are the reply rounding, floors in motion ticks, and ceiling in κt.The matrices encountered remain 2µI plus positive semidefinite terms, so Lemma A.4 applies.Source: §A.3 · pp. 19–20
- The method stores D = det G and J = adj G instead of H^-1, allowing rank-one stretch changes to update the integer representation exactly.The adjugate update computes det G′ = D ± κ⟨z, Jz⟩ and adj G′ = (det G′)J ∓ κ(Jz)(Jz)⊤; the division is exact.Source: §A.3 · p. 19
- Motions advance by integer ticks, revoke active stretches when their threshold is reached, and create a new stretch when 64(t + 1)^2S > D.Each motion scans active stretches and revokes them one at a time; a new stretch stores zt, Yt+1, bt, and κt.Source: §A.3 · pp. 19–20
- Round t uses (kt + 1)(d^4 + d|At|)b^2 bit operations, with kt ≤ |At| = O(d log(t+1)) and total stretch count at most T.The algorithm stores D and J in O(d^3bt) bits, active stretches in O(dbt) bits each, and the query in O(d(ℓR + bt)) bits.Source: §A.3 · p. 20
A.4 Inverse optimization in the bit model
The bit-model reduction yields a deterministic proper learner for online inverse linear optimization using one linear optimization per round. It achieves regret at most 42√d for every horizon, with polynomial bit complexity.
A.4 Inverse optimization in the bit model
- The reduction replies with half the action difference, avoiding a square root and requiring no precision beyond that of the actions.The coordinate interface reads the actions at precision b + 2 and rounds the scaled difference to answer the reply at cost O(db).Source: §A.4 · p. 20
- RT ≤ 42√d for every T, every w* ∈ B, and every adaptive sequence of action sets.The guarantee is for a deterministic proper learner in the bit model.Source: §A.4 · p. 20
- Each round uses one linear optimization over Xt with an integer objective having O(bt) bits per coordinate, and costs O((d^5 + d^3 log(t + 1)) log(t + 1) b²t) bit operations.The first T rounds use O((d^4 + d^2 log(T + 1)) b²T) bit operations per round on average.Source: §A.4 · p. 20
- The learner recommends an action optimizing its current query and replies with half the observed action difference, yielding shortfall at most twice the round regret.The proof bounds the regret by applying Theorem A.1 to the reply constructed from the difference between the expert’s action and the recommendation.Source: §A.4 · p. 20