2017

A constant step Forward-Backward algorithm involving random maximal monotone operators

Bianchi, Pascal, Hachem, Walid, Salim, Adil

Understand

A stochastic Forward-Backward algorithm with a constant step is studied.

At each time step, this algorithm involves an independent copy of a couple of random maximal monotone operators.
Defining a mean operator as a selection integral, the differential inclusion built from the sum of the two mean operators is considered.
As a first result, it is shown that the interpolated process obtained from the iterates converges narrowly in the small step regime to the solution of this differential inclusion.

Built on

The average principle for parabolic and elliptic differential equations and Markov processes with small diffusions
R.Z. Ha’sminskii · 1963
Earlier work this paper cites.
Bases mathématiques du calcul des probabilités
J. Neveu · 1964
Earlier work this paper cites.
Measurable dependence of convex sets and functions on parameters
R. T. Rockafellar · 1969
Earlier work this paper cites.
Stochastic programs with recourse. II: On the continuity of the objective
D. W. Walkup and R. J.-B. Wets · 1969
Earlier work this paper cites.
Convex analysis
R. T. Rockafellar · 1970
Earlier work this paper cites.
Approximation et optimisation
P.-J. Laurent · 1972
Earlier work this paper cites.
Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert
H. Brézis · 1973
Earlier work this paper cites.
Asymptotic convergence of nonlinear contraction semigroups in Hilbert space
R. E. Bruck, Jr · 1975
Earlier work this paper cites.
About properties of the mean value functional and of the continuous infimal convolution in stochastic convex analysis
J.-B. Hiriart-Urruty · 1976
Earlier work this paper cites.
Convex analysis and measurable multifunctions
C. Castaing and M. Valadier · 1977
Earlier work this paper cites.
Integrals, conditional expectations, and martingales of multivalued functions
F. Hiai and H. Umegaki · 1977
Earlier work this paper cites.
Contributions à la programmation mathématique: cas déterministe et stochastique
J.-B. Hiriart-Urruty · 1977
Earlier work this paper cites.
Familles d’opérateurs maximaux monotones et mesurabilité
H. Attouch · 1979
Earlier work this paper cites.
On the interchange of subdifferentiation and conditional expectations for convex functionals
R. T. Rockafellar and R. J.-B. Wets · 1982
Earlier work this paper cites.

Similar

Differential inclusions
J.-P. Aubin and A. Cellina · 1984
Cited alongside, same era.
Elements of topological dynamics
J. de Vries · 1993
Cited alongside, same era.
Legendre functions and the method of random bregman projections
H. H. Bauschke and J. M. Borwein · 1997
Cited alongside, same era.
Lectures on maximal monotone operators
R. R. Phelps · 1997
Cited alongside, same era.
Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization
H. H. Bauschke, J. M. Borwein, and W. Li · 1999
Cited alongside, same era.
Dynamics of stochastic approximation algorithms
M. Benaïm · 1999
Cited alongside, same era.
Stochastic approximation algorithms with constant step size whose average is cooperative
M. Benaïm and M. W. Hirsch · 1999
Cited alongside, same era.
Asymptotic behavior of a Markovian stochastic algorithm with constant step
J.-C. Fort and G. Pagès · 1999
Cited alongside, same era.
Stochastic approximation and recursive algorithms and applications
H. J. Kushner and G. G. Yin · 2003
Cited alongside, same era.
Stochastic approximations and differential inclusions
M. Benaïm, J. Hofbauer, and S. Sorin · 2005
Cited alongside, same era.
Theory of random sets
I. Molchanov · 2005
Cited alongside, same era.
Convex analysis and nonlinear optimization
J. M. Borwein and A. S. Lewis · 2006
Cited alongside, same era.

Then

Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time
J. Peypouquet and S. Sorin · 2010
Later among the works it cites.
Convex analysis and monotone operator theory in Hilbert spaces
H. H. Bauschke and P. L. Combettes · 2011
Later among the works it cites.
Incremental proximal methods for large scale convex optimization
D. P. Bertsekas · 2011
Later among the works it cites.
Stochastic approximations with constant step size and differential inclusions
G. Roth and W. H. Sandholm · 2013
Later among the works it cites.
On stochastic proximal gradient algorithms
Y. F. Atchade, G. Fort, and E. Moulines · 2014
Later among the works it cites.
Convergence of stochastic proximal gradient algorithm
Original
L. Rosasco, S. Villa, and B. C. Vũ · 2014
Later among the works it cites.
Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping
P. L. Combettes and J.-C. Pesquet · 2015
Later among the works it cites.
Ergodic convergence of a stochastic proximal point algorithm
P. Bianchi · 2016
Later among the works it cites.
Dynamical behavior of a stochastic Forward-Backward algorithm using random monotone operators
P. Bianchi and W. Hachem · 2016
Later among the works it cites.
Constant step stochastic approximations involving differential inclusions: Stability, long-run convergence and applications
Original
P. Bianchi, W. Hachem, and A. Salim · 2016
Later among the works it cites.
Stochastic approximations and perturbations in forward-backward splitting for monotone operators
P. L. Combettes and J.-C. Pesquet · 2016
Later among the works it cites.
A stochastic inertial forward–backward splitting algorithm for multivariate monotone inclusions
L. Rosasco, S. Villa, and B. C. Vũ · 2016
Later among the works it cites.
Bridging the gap between constant step size stochastic gradient descent and markov chains
Original
A. Dieuleveut, A. Durmus, and F. Bach · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…