Online Primal-Dual Mirror Descent under Stochastic Constraints
Online Primal-Dual Mirror Descent under Stochastic Constraints
复制标题
DOI：
10.1145/3392157
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Xiaohan Wei;Hao Yu;M. Neely
中科院分区：
文献类型：
--
作者：
Xiaohan Wei;Hao Yu;M. Neely
考虑了随机约束下的在线凸优化问题，其中目标函数是任意时变的，约束函数是独立同分布的.随着时间在每个时隙做出决策后，目标函数和约束函数都被揭示出来。最著名的期望后悔解决这样的问题是$\mathcalO（\sqrtT）$，与系数是多项式的决策变量的维度和依赖于斯莱特条件（即存在内点假设），这是限制性的，特别是排除处理等式约束。在本文中，我们表明，这样的斯莱特条件实际上是不需要的。我们提出了一个新的原始-对偶镜像下降算法，并证明了在弱得多的拉格朗日乘子假设下，允许一般等式约束，并显著放宽了以前的斯莱特条件，可以获得$\mathcalO（\sqrtT）$遗憾和约束违反.沿着的方式，对于决策包含在概率单纯形的情况下，我们减少系数，只有对数依赖于决策变量的维数。这种依赖性在镜像血统的文献中早已为人所知，但在这种新的受约束的在线学习场景中似乎是新的。在一个数据中心服务器供应问题上的仿真实验进一步验证了算法的性能。
We consider online convex optimization with stochastic constraints where the objective functions are arbitrarily time-varying and the constraint functions are independent and identically distributed (i.i.d.) over time. Both the objective and constraint functions are revealed after the decision is made at each time slot. The best known expected regret for solving such a problem is $\mathcalO (\sqrtT )$, with a coefficient that is polynomial in the dimension of the decision variable and relies on theSlater condition (i.e. the existence of interior point assumption), which is restrictive and in particular precludes treating equality constraints. In this paper, we show that such Slater condition is in fact not needed. We propose a newprimal-dual mirror descent algorithm and show that one can attain $\mathcalO (\sqrtT )$ regret and constraint violation under a much weaker Lagrange multiplier assumption, allowing general equality constraints and significantly relaxing the previous Slater conditions. Along the way, for the case where decisions are contained in a probability simplex, we reduce the coefficient to have only a logarithmic dependence on the decision variable dimension. Such a dependence has long been known in the literature on mirror descent but seems new in this new constrained online learning scenario. Simulation experiments on a data center server provision problem with real electricity price traces further demonstrate the performance of our proposed algorithm.