In this paper, we consider an online optimization process, where the objective functions are not convex (nor concave) but instead belong to a broad class of continuous submodular functions. We first propose a variant of the Frank-Wolfe algorithm that has access to the full gradient of the objective functions. We show that it achieves a regret bound of $O(\sqrt{T})$ (where $T$ is the horizon of the online optimization problem) against a $(1-1/e)$-approximation to the best feasible solution in hindsight. However, in many scenarios, only an unbiased estimate of the gradients are available. For such settings, we then propose an online stochastic gradient ascent algorithm that also achieves a regret bound of $O(\sqrt{T})$ regret, albeit against a weaker $1/2$-approximation to the best feasible solution in hindsight. We also generalize our results to $\gamma$-weakly submodular functions and prove the same sublinear regret bounds. Finally, we demonstrate the efficiency of our algorithms on a few problem instances, including non-convex/non-concave quadratic programs, multilinear extensions of submodular set functions, and D-optimal design.

本文研究一种在线优化过程，其中目标函数不是凸函数（也不是凹函数），而是属于广泛的连续次模函数类。我们提出了一种Frank-Wolfe算法的变体，它可以访问目标函数的全梯度，并证明它对未来最佳可行解的（1-1/ e）-近似具有O（T的平方根）的遗憾界。对于只能获得梯度的无偏估计的情况，我们还提出了在线随机梯度上升算法，并证明它也具有O（T的平方根）的遗憾界，但只能对未来最佳可行解的1/2的近似度。我们还将结果推广到γ-弱次模函数，并证明相同的次线性遗憾界。最后，在几个问题实例上演示了算法的效率，包括非凸/非凹二次规划，子模集函数的多线性扩展和D-最佳设计。

在线连续子模最大化