ONLINE INVERSE INTEGER LINEAR OPTIMIZATION VIA SMALL-GRADIENT SKIPPING: CONSTANT REGRET AND FINITE MISTAKES

In online inverse linear optimization, a learner aims to estimate an agent's unknown objective function by observing their optimal actions over time. Existing methods often suffer from regret bounds that grow with the total number of rounds (T) or require computationally expensive operations, such as calculating a center of gravity at every step. This paper addresses the open question of whether it is possible to achieve regret bounds independent of T that are polynomial in the dimension (d) using light computation, specifically for integer linear programs (ILPs).

The author proposes Small-Gradient Skipping (SGS), a mechanism that skips parameter updates and internal state advancements during rounds where the learner's current prediction already correctly identifies the agent's optimal action. By assuming a uniform margin—where the objective value of the optimal action is separated from all other candidates by at least a constant gap—the author applies SGS to three standard online learning algorithms: Online Gradient Descent (OGD), the Online Newton Step (ONS), and MetaGrad.

The primary contribution is that SGS allows these algorithms to achieve regret bounds that are entirely independent of the total number of rounds T. By re-analyzing these methods through the lens of mistake-counting rather than round-counting, the author demonstrates that the number of mistakes is finite and bounded by the problem's combinatorial structure.

For ONS and MetaGrad, the regret becomes polynomial in the dimension, specifically O(d^2) for ILPs, effectively removing the logarithmic dependence on T that plagued previous methods. Furthermore, the author provides explicit lower bounds for the uniform margin across various feasible set structures, including general ILPs, linear inequalities, and M-convex sets. This allows for concrete, problem-specific regret bounds that remain computationally efficient, requiring only O(d^2) operations plus a single projection per mistake round.

This work bridges the gap between theoretical online learning and practical inverse optimization. By demonstrating that a simple skipping mechanism can eliminate T-dependence, the paper provides a robust framework for learning objective functions in settings where the agent's decision-making process is discrete and structured. The results are particularly significant for applications like electricity market modeling or clinical pathway analysis, where the underlying optimization problems are often ILPs and the learner must operate efficiently over long time horizons.