论文标题
随机约束凸的条件梯度方法
Conditional gradient methods for stochastically constrained convex minimization
论文作者
论文摘要
我们提出了两种基于条件梯度的新型方法，用于用大量线性约束解决结构化随机凸优化问题。该模板的实例自然源于组合问题的SDP - 释放，这涉及问题维度多项式的许多约束。我们框架的最重要特征是，在每次迭代中只处理约束的一个子集，因此比需要完整通行证的先前作品获得了计算优势。我们的算法依赖于与条件梯度步骤结合使用的差异和平滑性，并伴随着严格的融合保证。提供了初步数值实验，以说明方法的实际性能。
We propose two novel conditional gradient-based methods for solving structured stochastic convex optimization problems with a large number of linear constraints. Instances of this template naturally arise from SDP-relaxations of combinatorial problems, which involve a number of constraints that is polynomial in the problem dimension. The most important feature of our framework is that only a subset of the constraints is processed at each iteration, thus gaining a computational advantage over prior works that require full passes. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees. Preliminary numerical experiments are provided for illustrating the practical performance of the methods.
