The authors study online inverse linear optimization, where a learner recommends actions from adversarially chosen compact sets X_t ⊆ R^d and observes the expert's optimal action under a fixed unknown linear objective w* (the expert's criterion).
Deterministic algorithm achieves optimal regret for online inverse optimization
A proper, polynomial-time learner attains O(sqrt(d)) regret without horizon knowledge.
Big Tech
Anupam Gupta · Guru Guruganesh · Honghao Lin · Vahab Mirrokni · Renato Paes Leme · David P. Woodruff
Google Research · New York University · Carnegie Mellon University
Research Digest··3 min read
The authors provide a deterministic algorithm for online inverse linear optimization that achieves the optimal O(sqrt(d)) regret for any horizon T, and runs in time polynomial in the dimension d and T.
Why this paper
From Google Research and 2 others
In one line
A deterministic polynomial-time learner achieves optimal O(sqrt(d)) regret in online inverse linear optimization for every horizon.
What we could check
- ·No code link found
- ·No weights link found
- ·No dataset link found
- ·No compute details found
- ✓Limitations stated by the authors (2 noted)
- ·No benchmark numbers found
Observed from the paper text and links we have. Absence here means we did not find it, not that it does not exist.
§