Polyhedral Instability Governs Regret in Online Learning

arXiv:2605.13692v1 Announce Type: new Abstract: 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 polyhedral instability: the number of changes of the active region. Under full information feedback and fixed partition assumptions, if RS_T denotes the number of region switches and V_{max} the maximum number of vertices per region, we prove Regret_T= Theta(sqrt{(1+RS_T),T,log V_{max}}) interpolating between experts-like and dimension-dependent OCO rates. For online submodular--concave games under Lovasz convexification, this reduces to the permutation-switch count SC_T, yielding the matching rate Regret_T= Theta(sqrt{(1+SC_T),T,log n}). Experiments on synthetic and real combinatorial problems (shortest path, influence maximization) validate the predicted scaling and indicate that low-instability regimes can arise in practice without explicit enumeration of actions.

Source: arXiv cs.LG | 2026-05-14