A First-Order Stochastic Primal-Dual Algorithm with Correction Step |
| |
Authors: | Lorenzo Rosasco Silvia Villa Bằng Công Vũ |
| |
Institution: | 1. Laboratory for Computational and Statistical Learning, Istituto Italiano di Tecnologia, Genova, Italy;2. Massachusetts Institute of Technology, Cambridge, Massachusetts, USA;3. Department of Informatics, Bioengineering, Robotics, and Systems Engineering (DIBRIS), Università di Genova, Genova, Italylrosasco@mit.edu;5. Dipartimento di Matematica, Politecnico di Milano, Milano, Italy |
| |
Abstract: | In this article, we investigate the convergence properties of a stochastic primal-dual splitting algorithm for solving structured monotone inclusions involving the sum of a cocoercive operator and a composite monotone operator. The proposed method is the stochastic extension to monotone inclusions of a proximal method studied in the literature for saddle point problems. It consists in a forward step determined by the stochastic evaluation of the cocoercive operator, a backward step in the dual variables involving the resolvent of the monotone operator, and an additional forward step using the stochastic evaluation of the cocoercive operator introduced in the first step. We prove weak almost sure convergence of the iterates by showing that the primal-dual sequence generated by the method is stochastic quasi-Fejér-monotone with respect to the set of zeros of the considered primal and dual inclusions. Additional results on ergodic convergence in expectation are considered for the special case of saddle point models. |
| |
Keywords: | Cocoercive operator composite operator duality monotone inclusion maximal monotone operator operator splitting primal-dual algorithm stochastic errors |
|
|