In this paper, we consider online convex optimization (OCO) with time-varying loss and constraint functions. Specifically, the decision maker chooses sequential decisions based only on past information, meantime the loss and constraint functions are revealed over time. We first develop a class of model-based augmented Lagrangian methods (MALM) for time-varying functional constrained OCO (without feedback delay). Under standard assumptions, we establish sublinear regret and sublinear constraint violation of MALM. Furthermore, we extend MALM to deal with time-varying functional constrained OCO with delayed feedback, in which the feedback information of loss and constraint functions is revealed to decision maker with delays. Without additional assumptions, we also establish sublinear regret and sublinear constraint violation for the delayed version of MALM. Finally, numerical results for several examples of constrained OCO including online network resource allocation, online logistic regression and online quadratically constrained quadratical program are presented to demonstrate the efficiency of the proposed algorithms.
翻译：在本文中,我们考虑的是具有时间变化损失和制约功能的在线线性优化(OCO) 。 具体地说, 决策者仅根据过去的信息选择顺序决定, 而损失和制约功能则随时间推移而暴露。 我们首先为时间变化功能受限的 OCO 开发了一类基于模型的增强Lagrangian 方法(MALM ) 。 根据标准假设, 我们建立了亚线性遗憾和亚线性限制 违反 MALM 。 此外, 我们扩展了 MLAM, 处理时间变化功能受限 OCO 的延迟反馈, 在反馈中, 损失和制约功能的反馈信息被披露给决策人, 并被拖延。 没有额外的假设, 我们还为延迟版本的 MLAMM 设定了亚线性遗憾和亚线性限制 。 最后, 对若干受限制的 OCO 实例, 包括在线网络资源配置、 在线物流回归和在线四边限制程序, 提供了数字结果, 以显示拟议算法的效率 。
相关内容
微信扫码咨询专知VIP会员