When Local Geometry Makes Online Learning Easy

Convex relaxations make combinatorial online problems tractable, but the relaxed decision space can still have exponentially many vertices. We exploit a finer structure: the space is partitioned into polyhedral cells, where a cell is a region on which every loss is affine and is therefore determined by its values at that region's vertices. Existing global methods ignore these smaller local action sets, while existing cell-based arguments can conflate two different tasks: learning within a known cell and identifying the relevant cell from past observations. We separate these tasks and first study the setting in which the relevant cell and each change of cell are supplied before play. Our key insight is that the best fixed decision within an affine cell is attained at a vertex. Learning during an epoch with an unchanged cell therefore reduces exactly to prediction with a small set of experts. Restarting multiplicative weights at cell changes yields epochwise regret of order $M\sqrt{ET\log V_{\max }}$ over $T$ rounds and $E$ epochs, where losses are bounded by $M$ and each cell has at most $V_{\max }$ vertices. Thus, for fixed loss and geometry parameters, average regret vanishes whenever $E\log V_{\max }=o(T)$. In submodular–concave games, each Lov\'asz cell has only $n+1$ chain vertices; combining the reduction with projected ascent gives order $M\sqrt{ET\log (n+1)}+L_y{D}_{\text{Y}}\sqrt{ET}$.