A first-order stochastic primal-dual algorithm with correction step

DOI10.1080/01630563.2016.1254243zbMATH Open1369.47074arXiv1602.07872OpenAlexW2964040277MaRDI QIDQ5357019FDOQ5357019

Băng Công Vũ, Silvia Villa, Lorenzo Rosasco

Publication date: 13 September 2017

Published in: Numerical Functional Analysis and Optimization (Search for Journal in Brave)

Abstract: 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 {em Y. Drori, S. Sabach, and M. Teboulle, A simple algorithm for a class of nonsmooth convex-concave saddle-point problems, 2015} and {em I. Loris and C. Verhoeven, On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty, 2011} 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 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'er-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.

Full work available at URL: https://arxiv.org/abs/1602.07872

Recommendations

• Stochastic approximations and perturbations in forward-backward splitting for monotone operators
• Stochastic forward Douglas-Rachford splitting method for monotone inclusions
• Convergence analysis of the stochastic reflected forward-backward splitting algorithm
• Stochastic primal dual fixed point method for composite optimization
• A fully stochastic primal-dual algorithm

zbMATH Keywords

operator splittingweak convergencedualityergodic convergencemaximal monotone operatorprimal-dual algorithmcomposite operatormonotone inclusioncocoercive operatorstochastic errors

Mathematics Subject Classification ID

Convex programming (90C25) Monotone operators and generalizations (47H05) Variational and other types of inclusions (47J22) Iterative procedures involving nonlinear operators (47J25) Decomposition methods (49M27) Numerical methods involving duality (49M29)

Cited In (9)

• Variable smoothing for convex optimization problems using stochastic gradients
• A regularization interpretation of the proximal point method for weakly convex functions
• Convergence of stochastic proximal gradient algorithm
• Modified Fejér sequences and applications
• Convergence analysis of the stochastic reflected forward-backward splitting algorithm
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• A fully stochastic primal-dual algorithm
• A stochastic variance reduction algorithm with Bregman distances for structured composite problems
• An improved first-order primal-dual algorithm with a new correction step

This page was built for publication: A first-order stochastic primal-dual algorithm with correction step

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5357019)