Search papers, labs, and topics across Lattice.
To resolve the persistent $\log T$ gap in online inverse linear optimization without relying on computationally prohibitive center-of-gravity oracles, this work analyzes structured discrete action spaces where the agent solves a forward integer linear program. The authors establish that uniform separation between discrete candidates enables Small-Gradient Skipping (SGS), a selective update rule compatible with online gradient descent, the online Newton step, and MetaGrad. Applied to ONS and MetaGrad, SGS achieves finite mistake bounds independent of the time horizon $T$ and yields $O(d^2)$ constant regret, while efficiently bounding regret on M-convex action sets without center-of-gravity computations.
Skipping gradient updates on rounds without prediction errors completely removes the long-standing $\log T$ horizon dependence in online inverse optimization, securing constant $O(d^2)$ regret for forward integer programs without expensive geometric oracles.
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 $\Omega(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.
