Optimal and Efficient Online Inverse Optimization
- Published
- Source
- arXiv
- Paper number
- 1171
- Field
- Machine Learning
- arXiv ID
- 2610.08735
Key points
- In a setting where the hidden linear criterion is learned only from the expert's observed choices, the algorithm achieves the optimal regret proportional to the square root of the dimension d.
- The previous optimal algorithm required nearly exponential-time computation per round, and this paper presents the first polynomial-time version.
- The key idea is a 'revocation' rule that undoes a metric update once the query point moves too far from where the update was made.
- The algorithm is deterministic and guarantees optimal regret for every horizon T without any randomness.
Paper links
External research summaries. These are not HDATF publications or measured product results.