在线学习中，多面体不稳定性决定后悔值，影响算法性能。
Polyhedral Instability Governs Regret in Online Learning
- 用多面体区域切换次数衡量在线学习的不稳定性。
- 后悔值与区域切换数和顶点数呈平方根关系，可覆盖多种学习场景。
- 适用于组合优化问题，实测表明实际中常出现低不稳定性情况。
许多组合动作的在线决策问题通过凸松弛求解，形成具有分段线性目标的在线凸优化，其内在结构为多面体。本文发现，此类问题的后悔值受多面体不稳定性（即活跃区域的切换次数）主导。在完全信息反馈和固定划分假设下，若记 $\mathrm{RS}_T$ 为区域切换次数，$V_{\max}$ 为每区域最大顶点数，则后悔值满足 $\Regret_T= Θ(\sqrt{(1+\mathrm{RS}_T)\,T\,\log V_{\max}})$，介于专家类与维度相关在线凸优化速率之间。对于洛瓦兹凸化下的在线子模-凹博弈，该结果退化为排列切换次数 $\mathrm{SC}_T$，得到匹配率 $\Regret_T= Θ(\sqrt{(1+\mathrm{SC}_T)\,T\,\log n})$。合成与真实组合问题（最短路径、影响力最大化）的实验验证了预测的标度关系，并表明无需显式枚举动作即可在实践中出现低不稳定性情形。
原文摘要 · Abstract (English)
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. Under full information feedback and fixed partition assumptions, if $\mathrm{RS}_T$ denotes the number of region switches and $V_{\max}$ the maximum number of vertices per region, we prove $\Regret_T= Θ(\sqrt{(1+\mathrm{RS}_T)\,T\,\log V_{\max}})$ interpolating between experts-like and dimension-dependent OCO rates. For online submodular--concave games under Lovász convexification, this reduces to the permutation-switch count $\mathrm{SC}_T$, yielding the matching rate $\Regret_T= Θ(\sqrt{(1+\mathrm{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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。