Optimal and Efficient Online Inverse Optimization
A deterministic polynomial-time algorithm matches the known optimal regret bound for online inverse linear optimization.
The paper addresses whether Sakaue’s optimal `O(√d)` regret result could be achieved without an exponential-per-round randomized procedure. It says yes: the authors give a deterministic algorithm with `O(√d)` regret for every horizon `T`, running in time polynomial in `d` and `T`. The method modifies prior variable-metric algorithms by revoking a metric update once the query point has moved far enough from where that update was made. Source: ArXiv · AI/CL/LG's note.
The paper addresses whether Sakaue’s optimal `O(√d)` regret result could be achieved without an exponential-per-round randomized procedure. It says yes: the authors give a deterministic algorithm with `O(√d)` regret for every horizon `T`, running in time polynomial in `d` and `T`. The method modifies prior variable-metric algorithms by revoking a metric update once the query point has moved far enough from where that update was made. Source: ArXiv · AI/CL/LG's note.
score 4