提出高效安全算法，在部分反馈下实现零约束违规与√T regret
Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback
- 基于李雅普诺夫优化设计，结合梯度与带状反馈
- 实现√T后悔率与累计约束违规为零
- 适合资源受限的在线决策场景，如数据中心调度
本文研究未知线性预算约束下的在线凸优化问题，仅能观测目标函数的梯度和约束函数的带状反馈。我们提出一种安全高效的李雅普诺夫优化算法（SELO），可达到O(√T)的遗憾和零累计约束违规。该结果也表明，当预算为硬约束时，SELO仍可实现O(√T)的遗憾。所提算法计算高效，其结构类似原对偶算法：原问题为无约束、强凸且光滑的问题，对偶问题采用简单梯度更新。算法与理论在分布式数据中心能量高效任务处理的模拟应用中得到验证。
原文摘要 · Abstract (English)
This paper studies online convex optimization with unknown linear budget constraints, where only the gradient information of the objective and the bandit feedback of constraint functions are observed. We propose a safe and efficient Lyapunov-optimization algorithm (SELO) that can achieve an $O(\sqrt{T})$ regret and zero cumulative constraint violation. The result also implies SELO achieves $O(\sqrt{T})$ regret when the budget is hard and not allowed to be violated. The proposed algorithm is computationally efficient as it resembles a primal-dual algorithm where the primal problem is an unconstrained, strongly convex and smooth problem, and the dual problem has a simple gradient-type update. The algorithm and theory are further justified in a simulated application of energy-efficient task processing in distributed data centers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。