论文标题
随机连续的下次化最大化：通过非掩饰功能增强
Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function
论文作者
论文摘要
在本文中，我们在离线和在线设置中重新访问随机连续的次管次最大化，这可以使机器学习和操作研究领域中的广泛应用受益。我们提出了一个增强框架，涵盖了梯度上升和在线梯度上升。 The fundamental ingredient of our methods is a novel non-oblivious function $F$ derived from a factor-revealing optimization problem, whose any stationary point provides a $(1-e^{-γ})$-approximation to the global maximum of the $γ$-weakly DR-submodular objective function $f\in C^{1,1}_L(\mathcal{X})$.在离线情况下，我们提出了一种增强梯度上升方法，以实现$（1-e^{ - γ}-ε^{2}）$ - $（1/ε^2）$迭代后的近似值，从而改善了$（\ frac {γ^2} {γ^2} {1+γ^2} $ clangio clancior clangio clancio clancio caltio callipry and and and and and and and and and and callime anctire and Maties and Mations。在在线环境中，我们首次考虑了随机梯度反馈的对抗性延迟，根据该延迟，我们提出了一种具有相同非掩饰函数$ f $的在线梯度算法。同时，我们验证这种增强在线算法的遗憾使$ o（\ sqrt {d}）$相对于$（1-e^{ - γ}）$ - 在$ d $的情况下，$（1-e^{ - γ}）$ - 在$ d $的情况下，近似可行的解决方案。据我们所知，这是获得$ o（\ sqrt {t}）$遗憾的第一个结果，而对于$（1-e^{ - γ}）$ - 在每个时间步骤中使用$ o（1）$梯度查询的近似值，当没有延迟时，即，即，即，$ d = t $。最后，数值实验证明了我们提升方法的有效性。
In this paper, we revisit Stochastic Continuous Submodular Maximization in both offline and online settings, which can benefit wide applications in machine learning and operations research areas. We present a boosting framework covering gradient ascent and online gradient ascent. The fundamental ingredient of our methods is a novel non-oblivious function $F$ derived from a factor-revealing optimization problem, whose any stationary point provides a $(1-e^{-γ})$-approximation to the global maximum of the $γ$-weakly DR-submodular objective function $f\in C^{1,1}_L(\mathcal{X})$. Under the offline scenario, we propose a boosting gradient ascent method achieving $(1-e^{-γ}-ε^{2})$-approximation after $O(1/ε^2)$ iterations, which improves the $(\frac{γ^2}{1+γ^2})$ approximation ratio of the classical gradient ascent algorithm. In the online setting, for the first time we consider the adversarial delays for stochastic gradient feedback, under which we propose a boosting online gradient algorithm with the same non-oblivious function $F$. Meanwhile, we verify that this boosting online algorithm achieves a regret of $O(\sqrt{D})$ against a $(1-e^{-γ})$-approximation to the best feasible solution in hindsight, where $D$ is the sum of delays of gradient feedback. To the best of our knowledge, this is the first result to obtain $O(\sqrt{T})$ regret against a $(1-e^{-γ})$-approximation with $O(1)$ gradient inquiry at each time step, when no delay exists, i.e., $D=T$. Finally, numerical experiments demonstrate the effectiveness of our boosting methods.
