arXiv:2603.21375cs.LGstat.ML2026-03AAAI

解决带记忆的约束优化问题,实现低误差与低违规的在线学习。

Constrained Online Convex Optimization with Memory and Predictions

  • 引入自适应惩罚机制,处理历史决策依赖的约束。
  • 在无预测时实现次线性累积违规与次线性损失,有预测时更优。
  • 适用于动态系统控制、调度等需考虑历史状态的实际场景。

我们研究带有记忆的约束在线凸优化(COCO-M),其中损失函数和约束条件均依赖于学习者过去有限窗口内的决策。该设定扩展了以往的无约束在线优化框架,适用于受约束动力系统控制和具有重配置预算的调度等实际问题。针对此问题,我们首次提出可在时间变化约束下实现次线性后悔与次线性累积约束违规的算法,涵盖无预测与有短期不可靠预测两种情形。无预测时,采用自适应惩罚方法保证次线性结果;有预测时,将问题重视为延迟反馈下的在线学习,设计乐观算法,性能随预测精度提升而改善,且在预测不准确时仍保持鲁棒性。研究成果弥合了经典约束在线凸优化与记忆依赖设置之间的差距,提供了一个可广泛应用于多场景的学习工具箱。

原文摘要 · Abstract (English)

We study Constrained Online Convex Optimization with Memory (COCO-M), where both the loss and the constraints depend on a finite window of past decisions made by the learner. This setting extends the previously studied unconstrained online optimization with memory framework and captures practical problems such as the control of constrained dynamical systems and scheduling with reconfiguration budgets. For this problem, we propose the first algorithms that achieve sublinear regret and sublinear cumulative constraint violation under time-varying constraints, both with and without predictions of future loss and constraint functions. Without predictions, we introduce an adaptive penalty approach that guarantees sublinear regret and constraint violation. When short-horizon and potentially unreliable predictions are available, we reinterpret the problem as online learning with delayed feedback and design an optimistic algorithm whose performance improves as prediction accuracy improves, while remaining robust when predictions are inaccurate. Our results bridge the gap between classical constrained online convex optimization and memory-dependent settings, and provide a versatile learning toolbox with diverse applications.

在线学习约束优化记忆机制

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。