Polyhedral Instability Governs Regret in Online Learning
Yuetai Li Fengqing Jiang Yichen Feng Kaiyuan Zheng Basel Alomair, Luyao Niu Bhaskar Ramasubramanian Linda Bushnell Radha Poovendran · 2026
Read Polyhedral Instability Governs Regret in Online Learning by Yuetai Li Fengqing Jiang Yichen Feng Kaiyuan Zheng Basel Alomair, Luyao Niu Bhaskar Ramasubramanian Linda Bushnell Radha Poovendran (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13692.txt.
Description
Yuetai Li and eight colleagues show regret in online learning over combinatorial actions is governed by polyhedral instability, the number of active-region changes. Under full information feedback and fixed partitions, they prove regret equals theta of the square root of one plus region switches times horizon times log max vertices. For online submodular-concave games under Lovász convexification, that reduces to the permutation-switch count with a matching rate. Tests on synthetic and real combinatorial problems validate the predicted scaling.
Catalog record
| CREATOR | Yuetai Li Fengqing Jiang Yichen Feng Kaiyuan Zheng Basel Alomair, Luyao Niu Bhaskar Ramasubramanian Linda Bushnell Radha Poovendran |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92145 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.13692