Abstract

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. In order to control the long term behavior of the iterates, a stability result is needed in addition. To this end, the sequence of the iterates is seen as a homogeneous Feller Markov chain whose transition kernel is parameterized by the algorithm step size. The cluster points of the Markov chains invariant measures in the small step regime are invariant for the semiflow induced by the differential inclusion. Conclusions regarding the long run behavior of the iterates for small steps are drawn. It is shown that when the sum of the mean operators is demipositive, the probabilities that the iterates are away from the set of zeros of this sum are small in Cesàro mean. The ergodic behavior of these iterates is studied as well. Applications of the proposed algorithm are considered. In particular, a detailed analysis of the random proximal gradient algorithm with constant step is performed.

Author information

Contact details are reproduced from the original publication and may be historical.

Walid Hachem

CNRS / LIGM (UMR 8049), Université Paris-Est, 5 blvd. Descartes, Champs-sur-Marne, 77454 Marne-la-Vallée Cd. 2, France

walid.hachem@u-pem.fr

Keywords

  • Dynamical systems
  • narrow convergence of stochastic processes
  • random maximal monotone operators
  • stochastic approximation with constant step
  • stochastic forward-backward algorithm
  • stochastic proximal point algorithm

Mathematics Subject Classification

47H05, 47N10, 62L20, 34A60

References

  1. Y. F. Atchadé, G. Fort, E. Moulines: On stochastic proximal gradient algorithms, J. Machine Learning Res. 18 (2017) 1–33.Google Scholar
  2. H. Attouch: Familles d’opérateurs maximaux monotones et mesurabilité, Ann. Mat. Pura Applicata 120(1) (1979) 35–111.https://doi.org/10.1007/BF02411939Google Scholar
  3. J.-P. Aubin, A. Cellina: Differential Inclusions, Grundlehren der Mathematischen Wissenschaften 264, Springer, Berlin et al. (1984).https://doi.org/10.1007/978-3-642-69512-4Google Scholar
  4. H. H. Bauschke, J. M. Borwein: Legendre functions and the method of random Bregman projections, J. Convex Analysis 4(1) (1997) 27–67.https://doi.org/10.68381/jca04002Google Scholar
  5. H. H. Bauschke, J. M. Borwein, W. Li: Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization, Math. Programming 86(1) (1999) 135–160.https://doi.org/10.1007/s101070050083Google Scholar
  6. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics, Springer, New York et al. (2011).https://doi.org/10.1007/978-1-4419-9467-7Google Scholar
  7. M. Benaïm: Dynamics of stochastic approximation algorithms, in: Séminaire de Probabilités XXXIII, Lecture Notes in Mathematics 1709, Springer, Berlin et al. (1999) 1–68.https://doi.org/10.1007/BFb0096509Google Scholar
  8. M. Benaïm, M. W. Hirsch: Stochastic approximation algorithms with constant step size whose average is cooperative, Ann. Appl. Probab. 9(1) 1999) 216–241.https://doi.org/10.1214/aoap/1029962603Google Scholar
  9. M. Benaïm, J. Hofbauer, S. Sorin: Stochastic approximations and differential inclusions, SIAM J. Control Optim. 44(1) (2005) 328–348 (electronic).https://doi.org/10.1137/S0363012904439301Google Scholar
  10. D. P. Bertsekas: Incremental proximal methods for large scale convex optimization, Math. Programming, Ser. B 129(2) (2011) 163–195.https://doi.org/10.1007/s10107-011-0472-0Google Scholar
  11. P. Bianchi: Ergodic convergence of a stochastic proximal point algorithm, SIAM J. Optimization 26(4) (2016) 2235–2260.https://doi.org/10.1137/15M1017909Google Scholar
  12. P. Bianchi, W. Hachem: Dynamical behavior of a stochastic Forward-Backward algorithm using random monotone operators, J. Optimization Theory Appl 171(1) (2016) 90–120.https://doi.org/10.1007/s10957-016-0978-yGoogle Scholar
  13. P. Bianchi, W. Hachem, A. Salim: Constant step stochastic approximations involving differential inclusions: stability, long-run convergence and applications, Stochastics (2018) 1–33.https://doi.org/10.1080/17442508.2018.1539086Google Scholar
  14. J. M. Borwein, A. S. Lewis: Convex Analysis and Nonlinear Optimization, CMS Books in Mathematics 3, 2nd edition, Springer, New York et al. (2006).https://doi.org/10.1007/978-0-387-31256-9Google Scholar
  15. H. Brézis: Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert, North-Holland Mathematics Studies, Elsevier, Burlington (1973).Google Scholar
  16. R. E. Bruck, Jr.: Asymptotic convergence of nonlinear contraction semigroups in Hilbert space, J. Funct. Analysis 18 (1975) 15–26.https://doi.org/10.1016/0022-1236(75)90027-0Google Scholar
  17. C. Castaing, M. Valadier: Convex Analysis and Measurable Multifunctions, Lecture Notes in Mathematics 580, Springer, Berlin et al. (1977).https://doi.org/10.1007/BFb0087685Google Scholar
  18. P. L. Combettes, J.-C. Pesquet: Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping, SIAM J. Optimization 25(2) (2015) 1221–1248.https://doi.org/10.1137/140971233Google Scholar
  19. P. L. Combettes, J.-C. Pesquet: Stochastic approximations and perturbations in forward-backward splitting for monotone operators, Pure Appl. Funct. Analysis 1(1) (2016) 13–37.Google Scholar
  20. J. de Vries: Elements of Topological Dynamics, Mathematics and its Applications 257, Kluwer, Dordrecht (1993).https://doi.org/10.1007/978-94-015-8171-4Google Scholar
  21. A. Dieuleveut, A. Durmus, F. Bach: Bridging the gap between constant step size stochastic gradient descent and Markov chains, arXiv: 1707.06386 (2017).Google Scholar
  22. M. Faure, G. Roth: Stochastic approximations of set-valued dynamical systems: convergence with positive probability to an attractor, Math. Oper. Res. 35(3) (2010) 624–640.https://doi.org/10.1287/moor.1100.0455Google Scholar
  23. J.-C. Fort, G. Pagès: Asymptotic behavior of a Markovian stochastic algorithm with constant step, SIAM J. Control Optimization 37(5) (1999) 1456–1482 (electronic).https://doi.org/10.1137/S0363012997328610Google Scholar
  24. R. Z. Ha’sminskii: The average principle for parabolic and elliptic differential equations and Markov processes with small diffusions, Theor. Probab. Appl. 8 (1963) 1–21.https://doi.org/10.1137/1108001Google Scholar
  25. F. Hiai, H. Umegaki: Integrals, conditional expectations, and martingales of multivalued functions, J. Multivariate Analysis 7(1) (1977) 149–182.https://doi.org/10.1016/0047-259X(77)90037-9Google Scholar
  26. J.-B. Hiriart-Urruty: About properties of the mean value functional and of the continuous infimal convolution in stochastic convex analysis, in: Optimization Techniques Modeling and Optimization in the Service of Man, Part 2, Optimization Techniques 1975, J. Cea (ed.), Lecture Notes in Computer Science 41, Springer, Berlin et al. (1975) 763–789.https://doi.org/10.1007/3-540-07623-9_324Google Scholar
  27. J.-B. Hiriart-Urruty: Contributions à la Programmation Mathématique: Cas Déterministe et Stochastique, Thèse, Série E 247, Université de Clermont-Ferrand II, Clermont-Ferrand (1977).Google Scholar
  28. H. J. Kushner, G. G. Yin: Stochastic Approximation and Recursive Algorithms and Applications, Applications of Mathematics 35, 2nd edition, Springer, New York et al. (2003).Google Scholar
  29. P.-J. Laurent: Approximation et optimisation, Collection Enseignement des Sciences 13, Hermann, Paris (1972).Google Scholar
  30. I. Molchanov: Theory of Random Sets, Probability and its Applications, Springer, London et al. (2005).Google Scholar
  31. J. Neveu: Bases Mathématiques du Calcul des Probabilités, Masson, Paris (1964).Google Scholar
  32. J. Peypouquet, S. Sorin: Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time, J. Convex Analysis 17(3-4) (2010) 1113–1163.https://doi.org/10.68381/jca17068Google Scholar
  33. R. R. Phelps: Lectures on maximal monotone operators, Extracta Math. 12(3) (1997) 193–230.Google Scholar
  34. R. T. Rockafellar: Measurable dependence of convex sets and functions on parameters, J. Math. Anal. Appl. 28 (1969) 4–25.https://doi.org/10.1016/0022-247X(69)90104-8Google Scholar
  35. R. T. Rockafellar: Convex Analysis, Princeton Mathematical Series 28, Princeton University Press, Princeton (1970).Google Scholar
  36. R. T. Rockafellar, R. J.-B. Wets: On the interchange of subdifferentiation and conditional expectations for convex functionals, Stochastics 7(3) (1982) 173–182.https://doi.org/10.1080/17442508208833217Google Scholar
  37. L. Rosasco, S. Villa, B. C. Vũ: Convergence of stochastic proximal gradient algorithm, (2014) arXiv: 1403.5074.Google Scholar
  38. L. Rosasco, S. Villa, B. C. Vũ: A stochastic inertial forward-backward splitting algorithm for multivariate monotone inclusions, Optimization 65(6) (2016) 1293–1314.https://doi.org/10.1080/02331934.2015.1127371Google Scholar
  39. G. Roth, W. H. Sandholm: Stochastic approximations with constant step size and differential inclusions, SIAM J. Control Optimization 51(1) (2013) 525–555.https://doi.org/10.1137/110844192Google Scholar
  40. D. W. Walkup, R. J.-B. Wets: Stochastic programs with recourse II: on the continuity of the objective, SIAM J. Appl. Math. 17 (1969) 98–103.https://doi.org/10.1137/0117010Google Scholar

Suggested citation

P. Bianchi, W. Hachem, A. Salim. “A Constant Step Forward-Backward Algorithm Involving Random Maximal Monotone Operators.” Journal of Convex Analysis 26 (2019), No. 2, 397–436. https://doi.org/10.68381/jca26021

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2019. Rights now held by Banach Press.