Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization
Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization
复制标题
DOI：
--
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Aryan Mokhtari;Hamed Hassani;Amin Karbasi
中科院分区：
文献类型：
--
作者：
Aryan Mokhtari;Hamed Hassani;Amin Karbasi
本文考虑了大量的目标功能（包括凸和连续的子模型）的随机优化问题。随机近端梯度方法已被广泛用于解决此类问题。但是，当问题维度较大并且对凸组集合的投影成本高昂时，它们的适用性仍然有限。取而代之的是，提出了随机条件梯度方法作为替代解决方案，该解决方案依赖于（i）通过简单的平均技术近似梯度，需要单个随机梯度评估。 （ii）解决线性程序以计算下降/上升方向。随着时间的流逝，平均技术降低了梯度近似值的噪声，并通过线性程序替换近端方法的投影步骤降低了每种迭代的计算复杂性。我们表明，在凸度和平滑度假设下，我们提出的方法以$ o（1/t^{1/3}）$的sublinear速率收敛到最佳目标函数值。此外，对于单调和连续的DR-sodumular功能并受到一般凸的身体约束，我们证明我们的建议方法可以使用$ O（1/o（1/o）达到$（（1-1/e）opt- \ eps）$ \ eps^3）$随机梯度计算。此保证与已知的硬度结果匹配，并缩小确定性和随机连续下管最大化之间的差距。此外，我们在使用$ o（1/\ eps^3）$ o（1/e）opt- \ eps）$保证中获得$（1/\ eps^3）$随机梯度，因为目标函数是连续的DR-Submodular dr-submodular in约束集被截断。通过使用随机连续优化作为接口，我们提供了第一个$（1-1/e）$紧密的近似保证，以最大化单调但随机的supodular设置功能，但要受矩阵约束和$（1/e）$（1/e）的近似保证。非单身酮案例。
This paper considers stochastic optimization problems for a large class of objective functions, including convex and continuous submodular. Stochastic proximal gradient methods have been widely used to solve such problems; however, their applicability remains limited when the problem dimension is large and the projection onto a convex set is costly. Instead, stochastic conditional gradient methods are proposed as an alternative solution relying on (i) Approximating gradients via a simple averaging technique requiring a single stochastic gradient evaluation per iteration; (ii) Solving a linear program to compute the descent/ascent direction. The averaging technique reduces the noise of gradient approximations as time progresses, and replacing projection step in proximal methods by a linear program lowers the computational complexity of each iteration. We show that under convexity and smoothness assumptions, our proposed method converges to the optimal objective function value at a sublinear rate of $O(1/t^{1/3})$. Further, for a monotone and continuous DR-submodular function and subject to a general convex body constraint, we prove that our proposed method achieves a $((1-1/e)OPT-\eps)$ guarantee with $O(1/\eps^3)$ stochastic gradient computations. This guarantee matches the known hardness results and closes the gap between deterministic and stochastic continuous submodular maximization. Additionally, we obtain $((1/e)OPT -\eps)$ guarantee after using $O(1/\eps^3)$ stochastic gradients for the case that the objective function is continuous DR-submodular but non-monotone and the constraint set is down-closed. By using stochastic continuous optimization as an interface, we provide the first $(1-1/e)$ tight approximation guarantee for maximizing a monotone but stochastic submodular set function subject to a matroid constraint and $(1/e)$ approximation guarantee for the non-monotone case.