Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
复制标题
DOI：
10.1137/18m1229869
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Yangyang Xu
中科院分区：
文献类型：
--
作者：
Yangyang Xu
随机梯度法（SG法）是一种求解目标函数为随机函数或多个函数的平均值的优化问题的方法。大多数现有的工作SG假设的基本问题是无约束的或有一个易于项目的约束集。在本文中，我们考虑的问题，有一个随机的目标，也有许多功能的限制。对于这样的问题，它可能是非常昂贵的投影点的可行集，甚至计算次梯度和/或所有约束函数的函数值。为了解决这些问题，我们提出了一种新的SG方法的基础上增广拉格朗日函数。在每次迭代中，它查询目标的随机次梯度，一个随机采样约束函数的次梯度和函数值，以及另一个采样约束函数的函数值。因此，每次迭代的复杂度很低。我们建立了它的收敛速度的凸和强凸问题。对于凸情况，它可以达到最佳$O（1/\sqrt{k}）$收敛速度，对于强凸情况，它可以达到接近最佳$O\big（（\log k）/k\big）$速度。对二次约束二次规划问题的数值实验表明了该算法的有效性。
Stochastic gradient (SG) method has been popularly applied to solve optimization problems with objective that is stochastic or an average of many functions. Most existing works on SG assume that the underlying problem is unconstrained or has an easy-to-project constraint set. In this paper, we consider problems that have a stochastic objective and also many functional constraints. For such problems, it could be extremely expensive to project a point to the feasible set, or even compute subgradient and/or function value of all constraint functions. To find solutions of these problems, we propose a novel SG method based on the augmented Lagrangian function. Within every iteration, it inquires a stochastic subgradient of the objective, a subgradient and function value of one randomly sampled constraint function, and function value of another sampled constraint function. Hence, the per-iteration complexity is low. We establish its convergence rate for convex and also strongly convex problems. It can achieve the optimal $O(1/\sqrt{k})$ convergence rate for convex case and nearly optimal $O\big((\log k)/k\big)$ rate for strongly convex case. Numerical experiments on quadratically constrained quadratic programming are conducted to demonstrate its efficiency.