A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spaces

By Lorenzo Rosasco, Silvia Villa, Bang Công Vu. 2014

19 citations recorded by the source corpus.

We propose and analyze the convergence of a novel stochastic forward-backward splitting algorithm for solving monotone inclusions given by the sum of a maximal monotone operator and a single-valued maximal monotone cocoercive operator. This latter framework has a number of interesting special cases, including variational inequalities and convex minimization problems, while stochastic approaches are practically relevant to account for perturbations in the data. The algorithm we propose is a stochastic extension of the classical deterministic forward-backward method, and is obtained considering the composition of the resolvent of the maximal monotone operator with a forward step based on a stochastic estimate of the single-valued operator. Our study provides a non-asymptotic error analysis in expectation for the strongly monotone case, as well as almost sure convergence under weaker assumptions. The approach we consider allows to avoid averaging, a feature critical when considering methods based on sparsity, and, for minimization problems, it allows to obtain convergence rates matching those obtained by stochastic extensions of so called accelerated methods. Stochastic quasi Fejer's sequences are a key technical tool to prove almost sure convergence.

Subfields: Computational Theory and Mathematics, Mathematical Physics, Numerical Analysis, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Mathematical Physics

In Numerical Analysis

In Mathematical Optimization

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, neutral): “Without variance reduction, some work establishes last-iterate convergence results with a slow (sublinear) rate [Rosasco et al., 2014, Mishchenko et al., 2020].”
Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, background): “3 Existing stochastic algorithms Forward-backward algorithms have been studied with added n oise [22], leading to a convergence rate inO(1/t) after t iterations for strongly-convex-concave problems.”
A Variational Inequality Perspective on Generative Adversarial Nets (2018, background): “It has been studied with additive noise by Rosasco et al. (2014) in the general context of monotone inclusion and by Nemirovski et al. (2009) in the context of stochastic saddle point optimization.”