A First-Order Stochastic Primal-Dual Algorithm with Correction Step

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

MATHEMATICS SUBJECT CLASSIFICATION:

• 47H05
• 49M29
• 49M27
• 90C25