Tutorials
Optimal and Efficient Online Inverse Optimization
arXiv:2610.08735v1 Announce Type: new 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 ob
arXiv:2610.08735v1 Announce Type: new 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(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.
Related
- Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
- Uncovering expert objectives in production planning via inverse optimization: An industrial case study
- Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions
Source: arXiv cs.LG | 2026-10-07