Online inverse linear optimization improves with small-gradient skipping
Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
Machine LearningData Structures and Algorithms
Summary
This paper studies how to better learn hidden preferences or weights by watching choices made over time. The authors introduce a way to avoid unnecessary updates in learning when the learner's prediction is already good enough, called Small-Gradient Skipping. This approach reduces the number of mistakes and removes some inefficiencies in existing methods, especially for problems that involve integer decisions or special action sets. Their methods provide guarantees that improve on previous results in terms of how mistakes and regrets scale with time and problem size.
What this means in practice
- •For operations research teams: Enhance prediction of decision-maker preferences in integer linear programs with reduced updates and bounded errors over time.
- •For algorithm developers: Design more efficient online learning algorithms for structured action sets without costly computations like center of gravity.
Authors
Akira Kitaoka
Abstract
In online inverse linear optimization, the learner predicts a weight at each round, observes the optimal action of the agent, and updates its prediction. In the general setting, the gap of $\log T$ between the regret upper bound $O(d \log T)$ and the lower bound $Ω(d)$ is unresolved (here $T$ is the total number of rounds and $d$ is the dimension). When the action set is M-convex, the regret is known to be bounded by $O(d \log d)$, but the method attaining it computes a center of gravity at every round. This paper therefore proposes Small-Gradient Skipping (SGS), a mechanism that skips the update at rounds without a mistake in the case where the correct action is uniformly separated from the other candidates, and applies it to online gradient descent, the online Newton step, and MetaGrad. The number of mistakes is then bounded, for all three, by a quantity independent of $T$; and for the online Newton step and for MetaGrad with SGS, the dimension dependence of the regret becomes $O(d^2)$ when the forward problem is an integer linear program, that is, the factor $\log T$ is removed. Moreover, when the action set is M-convex, the regret is bounded efficiently without computing a center of gravity.