Polyhedral Instability Governs Regret in Online Learning

ArXi:2605.13692v1 Announce Type: new Many online decision problems over combinatorial actions are addressed via convex relaxations, leading to online convex optimization with piecewise linear objectives and induced polyhedral structure. We show that regret in such problems is governed by \emph{polyhedral instability}: the number of changes of the active region.