论文标题
在线DR-subodular最大化，随机累积约束
Online DR-Submodular Maximization with Stochastic Cumulative Constraints
论文作者
论文摘要
在本文中，我们考虑通过线性随机长期约束在线连续DR-submodular最大化。与先前关于在线supsodular最大化的工作相比，我们的设置引入了随机线性约束功能的额外并发症。在每个回合中生成。确切地说，在\ {1，\ dots，t \} $中，在步骤$ t \ in ot dr-submodular实用程序函数$ f_t（\ cdot）$和约束向量$ p_t $，i.i.d.在承诺采用$ x_t $的情况下，从平均$ p $的未知分布中产生，我们的目的是最大化整体效用，而预期的累积资源消耗$ \ sum_ {t = 1}^t \ langle p，x_t \ rangle $低于固定的预算$ b_t $。随机的长期限制自然出现在预算有限或资源有限的应用中，并且每个步骤的资源消耗受随机时间变化的环境的约束。我们建议在线Lagrangian Frank-Wolfe（OLFW）算法解决此类问题。我们分析了OLFW算法的性能，并获得了次线性遗憾界限以及在预期和高概率上都具有较高的累积约束违规范围。
In this paper, we consider online continuous DR-submodular maximization with linear stochastic long-term constraints. Compared to the prior work on online submodular maximization, our setting introduces the extra complication of stochastic linear constraint functions that are i.i.d. generated at each round. To be precise, at step $t\in\{1,\dots,T\}$, a DR-submodular utility function $f_t(\cdot)$ and a constraint vector $p_t$, i.i.d. generated from an unknown distribution with mean $p$, are revealed after committing to an action $x_t$ and we aim to maximize the overall utility while the expected cumulative resource consumption $\sum_{t=1}^T \langle p,x_t\rangle$ is below a fixed budget $B_T$. Stochastic long-term constraints arise naturally in applications where there is a limited budget or resource available and resource consumption at each step is governed by stochastically time-varying environments. We propose the Online Lagrangian Frank-Wolfe (OLFW) algorithm to solve this class of online problems. We analyze the performance of the OLFW algorithm and we obtain sub-linear regret bounds as well as sub-linear cumulative constraint violation bounds, both in expectation and with high probability.
