Online Convex Optimization with Stochastic Constraints
Online Convex Optimization with Stochastic Constraints
复制标题
DOI：
--
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Hao Yu;M. Neely;Xiaohan Wei
中科院分区：
文献类型：
--
作者：
Hao Yu;M. Neely;Xiaohan Wei
本文研究了带随机约束的在线凸优化问题，通过引入多个独立同分布的随机函数约束，将Zinkevich的在线凸优化问题推广到一个已知的简单固定集上.在每一轮中产生，并且仅在做出决定之后才向决策者披露。当决策受到随机环境或具有噪声观测的确定性环境的限制时，这种公式自然会出现。它还包括许多重要问题作为特殊情况，例如具有长期约束的OCO、随机约束凸优化和确定性约束凸优化。为了解决这个问题，本文提出了一种新的算法，该算法实现了$O（\sqrt{T}）$的期望后悔和约束违反以及$O（\sqrt{T}\log（T））$的高概率后悔和约束违反。在实际数据中心调度问题上的实验进一步验证了新算法的性能。
This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich's OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d. generated at each round and are disclosed to the decision maker only after the decision is made. This formulation arises naturally when decisions are restricted by stochastic environments or deterministic environments with noisy observations. It also includes many important problems as special cases, such as OCO with long term constraints, stochastic constrained convex optimization, and deterministic constrained convex optimization. To solve this problem, this paper proposes a new algorithm that achieves $O(\sqrt{T})$ expected regret and constraint violations and $O(\sqrt{T}\log(T))$ high probability regret and constraint violations. Experiments on a real-world data center scheduling problem further verify the performance of the new algorithm.