Optimal and Efficient Online Inverse Optimization

The gist The authors present a deterministic and efficient algorithm for online inverse linear optimization that achieves an optimal regret bound of O(√d) in polynomial time, which addresses long-standing questions regarding the complexity of learning hidden linear objectives from expert choices.

Online Inverse Linear Optimization Problem

The problem involves a learner recommending an action when the expert chooses one to maximize a fixed, unknown linear objective vector w∗ on R d without observing w∗ itself The learner is charged the cumulative shortfall of its recommendations, defined by RT:= X T t=1 to T ⟨w∗, xt − xˆt⟩ ≥ 0 This setup models scenarios like a resident learning from an attending physician's choices where the criterion is unknown

Algorithm Overview and Core Mechanism

The proposed solution is the variable-metric algorithm RVM(α), which modifies existing methods by revoking metric updates when the query point moves far from where the update was made The core idea involves maintaining a metric Ht that records what has been learned about w∗, and each round stretches this metric along the direction of the received unit vector vt to indicate more knowledge in that direction A key feature is that a stretch is revoked as soon as the query moves far along its direction from the query point at which it was made, which allows for a constant multiple of 1/s 2t weight

Performance and Regret Bounds

The main result establishes that there is a deterministic proper learner for online inverse linear optimization with RT ≤ 51/4√d < 13√d for every T, every w∗ ∈ B and every adaptive sequence of action sets This bound is achieved using the reduction to a cutting-plane game where the learner plays an action based on a query point pt and receives a unit vector vt subject to rt:= ⟨w∗ − pt, vt⟩ ≥ 0 The algorithm's round t uses one linear optimization over Xt and O(td squared + t 2d) arithmetic operations, with the first T rounds using O(d squared + Td) per round on average

Efficiency and Complexity Analysis

The analysis shows that the cost of a single move is O(td squared + t 2d) arithmetic operations, which sums up to O(T d squared + T squared d) in total for the first T rounds The algorithm is deterministic and anytime, requiring neither T nor restarts A variant that skips small stretches yields a regret of RegT ≤ 51/8 + 0.03d/R√d < 6.41 R√d, with a round cost of O(d cubed log2 t) arithmetic operations

Bit Complexity and Practical Implementation

The paper also provides a rounded variant that uses polynomial bit operations per round, achieving RegT ≤ 21 R√d This version utilizes integer arithmetic with exact computations for queries and replies, leading to a complexity of O((d 4 + d squared log(T + 1)) b 2 T) bit operations per round on average The final result in the bit model shows RT ≤ 42√d

Conclusion

The paper concludes by confirming that the variable-metric method of [10] with revocable stretches is effective, achieving an optimal regret of O(√d) deterministically and efficiently The analysis demonstrates that the total loss is bounded by R squared + 74dα for a specific choice of parameters, confirming the established lower bounds for the optimal regret in this problem. The work also provides a corruption-robust guarantee against oracle responses violating P rt ≥ 0 by C, yielding RegT = O(R√d + C)

--- Page 1 ---

Optimal and Efficient Online Inverse Optimization Anupam Gupta∗, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff† Google Research 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 R d; the goal is to learn to optimize this objective without observing it Sakaue recently obtained the optimal regret O(√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(√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 Consider a resident who learns by watching the decisions of an attending physician on a hospital ward Every patient comes with a handful of possible interventions — this drug or another, operate now or wait — and the attending picks one The reasoning behind the pick is seldom spelled out: it balances how well a treatment works against what it does to the patient, and how fast recovery comes against what it costs The resident never sees the criterion the attending uses, only the intervention chosen, one patient at a time The goal is for the resident’s recommendations to become as good as the attending’s in the long run: each recommendation falls short of the attending’s choice by some amount, measured by the attending’s own criterion, and we want the total shortfall over all patients to stay small This is the problem of online inverse linear optimization Online inverse linear optimization Fix a hidden w∗ ∈ B For t = 1, 2,...: 1. a compact nonempty action set Xt ⊆ B is revealed, chosen adversarially as a function of the history; 2. the learner recommends an action ˆxt ∈ Xt; 3. the expert takes xt ∈ arg maxx∈Xt⟨w∗, x⟩, which the learner then observes Here B is the unit ball of R d and∥·∥ the Euclidean norm The learner is charged the cumulative shortfall of its recommendations, in the expert’s own currency, RT:= X T t=1 to T ⟨w∗, xt − xˆt⟩ ≥ 0 (1)∗ Also with New York University †Also with Carnegie Mellon University

--- Page 2 ---

Method Regret Uniform in T Proper Deterministic Per-round cost B¨armann et al. [4, 5] (OGD/MWU) O(√T) no yes yes O(τsol + d) Besbes et al. [7, 8] (circumcenter) O(d 4 ln T) no yes yes τsol + poly(d, T) Gollapudi et al. [16] (centroid) O(d ln T) no yes yes τsol + poly(d, T) Gollapudi et al. [16] (John ellipsoid) exp(O(d ln d)) yes yes yes τsol + poly(d, T) Sakaue et al. [28] (online Newton step) O(d ln T) no yes yes O(τsol + d squared + τproj) Sakaue [29] (second-order perceptron) O(d ln T) no yes yes O(τsol + d 2) Dewasurendra [13] (multiscale vote) O(d) yes no yes T Θ(d) Cai et al. [10] (variable metric) O(d) yes yes yes O(τsol + d 2) Sakaue [27] (multiscale matrix weights) O(√d) † yes no no (dT)

--- Page 3 ---

History The online formulation is due to B¨armann, Pokutta and Schneider [4, 5], who obtained O(√T) by online gradient descent and multiplicative weights Besbes, Fonseca and Lobel [7, 8] obtained O(d 4 ln T) by a circumcenter rule ProjectedCones Gollapudi et al. [16], Guruganesh, Kollias, Manurangsi, Paes Leme and Schneider [16] obtained O(d ln T) by a centroid cutting-plane rule and exp(O(d ln d)), uniform in T from the John ellipsoid Sakaue et al.

1. Bold Header: Optimal Regret Guarantee for Online Inverse Optimization

The system can achieve a regret of O(√d) with a deterministic proper learner in polynomial time in d and T, solving the challenge of learning an unknown linear objective without observing it, which is crucial for real-world decision-making under uncertainty.

2. Bold Header: Computationally Efficient Learning Under High Dimensionality

The improved system can run its round operations in O(td squared + t 2d) arithmetic operations, ensuring that the learning process remains feasible even when dealing with high-dimensional attribute spaces (large d).

3. Bold Header: Robustness to Model Uncertainty via Revocable Metric Updates

By employing the revocable variable metric method, the system can dynamically adapt its hypothesis about the unknown criterion, as a stretch is revoked as soon as the query moves far along its direction from the query point at which it was made, preventing accumulated error from stale information.

4. Bold Header: Real-Time Adaptivity with Low Latency

The algorithm allows for continuous movement along a path defined by Hˆt(η)−1vt, enabling it to make any recommendation based on the current state of knowledge, which is vital for applications requiring fast, sequential decision-making.

5. Bold Header: Scalable Performance via Skipping Small Stretches

The system can be modified to skip stretches where "s 2t > (t + 1)−4, leading to a regret bound of O(√d) + 0.083 α and reducing the running time cost per round to O(d cubed log2 t)," allowing for longer horizons.

6. Bold Header: High-Precision Implementation via Integer Arithmetic

The system can be implemented using exact integer arithmetic, where the metric is maintained through integer matrices, ensuring that the queries are computed exactly and avoiding accumulated rounding errors in the core optimization steps.