针对动态约束的在线优化,提出能自适应环境规律的新算法。
Structure-Dependent Regret and Constraint Violation Bounds for Online Convex Optimization with Time-Varying Constraints
- 根据约束变化规律(平滑漂移、周期性、稀疏切换)设计自适应算法
- 实验显示约束违反减少最高达53%,性能优于传统方法
- 适合电力调度、网络负载管理等存在规律性动态的场景
带时变约束的在线凸优化是动态网络系统中序列决策的关键框架,要求学习者在满足随轮次变化的可行区域的同时最小化累积损失。现有理论分析通常将约束变化视为单一对抗过程,导致联合后悔与违规界限过于保守。本文引入约束变化的结构化表征——平滑漂移、周期性循环和稀疏切换,并将其映射到慢信道衰落、昼夜流量模式、离散维护窗口等常见网络现象。我们推导出依赖结构的联合界,在约束过程具有规律性时严格优于对抗性速率。为此,提出结构自适应原对偶(SA-PD)算法,利用可观测约束信号在线检测环境结构并相应调整对偶更新策略。在合成基准和真实数据集(包括在线电力调度与变压器负载管理)上的大量实验表明,相比无结构感知基线,SA-PD将累积约束违规降低高达53%,同时保持竞争力的效用。本工作为利用时间规律性在受限在线学习中实现稳健网络工程提供了全面指导。
原文摘要 · Abstract (English)
Online convex optimization (OCO) with time-varying constraints is a critical framework for sequential decision-making in dynamic networked systems, where learners must minimize cumulative loss while satisfying regions of feasibility that shift across rounds. Existing theoretical analyses typically treat constraint variation as a monolithic adversarial process, resulting in joint regret and violation bounds that are overly conservative for real-world network dynamics. In this paper, we introduce a structured characterization of constraint variation - smooth drift, periodic cycles, and sparse switching - mapping these classes to common network phenomena such as slow channel fading, diurnal traffic patterns, and discrete maintenance windows. We derive structure-dependent joint bounds that strictly improve upon adversarial rates when the constraint process exhibits regularity. To realize these gains, we propose the Structure-Adaptive Primal-Dual (SA-PD) algorithm, which utilizes observable constraint signals to detect environmental structure online and adapt dual update strategies accordingly. Extensive experiments on synthetic benchmarks and real-world datasets - including online electricity scheduling and transformer load management - demonstrate that SA-PD reduces cumulative constraint violation by up to 53% relative to structure-agnostic baselines while maintaining competitive utility. This work serves as a comprehensive guide for exploiting temporal regularity in constrained online learning for robust network engineering.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。