Primal-dual stochastic gradient method for convex programs with many functional constraints

Yangyang Xu

Numerical Linear Algebra mathscidoc:1912.43152

arXiv preprint arXiv:1802.02724, 2018.2
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 (1/\sqrt {k}) rate for strongly convex case. Numerical experiments on quadratically constrained quadratic programming are conducted to demonstrate its efficiency.
No keywords uploaded!
[ Download ] [ 2019-12-21 11:26:04 uploaded by Yangyang_Xu ] [ 244 downloads ] [ 0 comments ]
@inproceedings{yangyang2018primal-dual,
  title={Primal-dual stochastic gradient method for convex programs with many functional constraints},
  author={Yangyang Xu},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191221112604925852712},
  booktitle={arXiv preprint arXiv:1802.02724},
  year={2018},
}
Yangyang Xu. Primal-dual stochastic gradient method for convex programs with many functional constraints. 2018. In arXiv preprint arXiv:1802.02724. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191221112604925852712.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved