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

CREATORYuetai Li Fengqing Jiang Yichen Feng Kaiyuan Zheng Basel Alomair, Luyao Niu Bhaskar Ramasubramanian Linda Bushnell Radha Poovendran
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92145
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13692

Browse the full library · About the Tower of Babel