Dynamical behavior of a stochastic forward-backward algorithm using random monotone operators. (English) Zbl 1360.47010
Summary: The purpose of this paper is to study the dynamical behavior of the sequence produced by a Forward-Backward algorithm, involving two random maximal monotone operators and a sequence of decreasing step sizes. Defining a mean monotone operator as an Aumann integral and assuming that the sum of the two mean operators is maximal (sufficient maximality conditions are provided), it is shown that with probability one, the interpolated process obtained from the iterates is an asymptotic pseudotrajectory in the sense of M. Benaïm and M. W. Hirsch [J. Dyn. Differ. Equations 8, No. 1, 141–176 (1996; Zbl 0878.58053)] of the differential inclusion involving the sum of the mean operators. The convergence of the empirical means of the iterates toward a zero of the sum of the mean operators is shown, as well as the convergence of the sequence itself to such a zero under a demipositivity assumption. These results find applications in a wide range of optimization problems or variational inequalities in random environments.
MSC:
| 47H05 | Monotone operators and generalizations |
| 47N10 | Applications of operator theory in optimization, convex analysis, mathematical programming, economics |
| 62L20 | Stochastic approximation |
| 34A60 | Ordinary differential inclusions |
Keywords:
dynamical systems; random maximal monotone operators; stochastic forward-backward algorithm; stochastic proximal point algorithmCitations:
Zbl 0878.58053References:
| [1] | Mercier, B.: Lectures on topics in finite element solution of elliptic problems, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 63. Tata Institute of Fundamental Research, Bombay (1979). With notes by G. Vijayasundaram · Zbl 0445.65100 |
| [2] | Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964-979 (1979) · Zbl 0426.65050 · doi:10.1137/0716071 |
| [3] | Benaïm, M., Hirsch, M.W.: Asymptotic pseudotrajectories and chain recurrent flows, with applications. J. Dyn. Differ. Equ. 8(1), 141-176 (1996) · Zbl 0878.58053 · doi:10.1007/BF02218617 |
| [4] | Benaïm, M., Hofbauer, J., Sorin, S.: Stochastic approximations and differential inclusions. SIAM J. Control Optim. 44(1), 328-348 (2005). (electronic) · Zbl 1087.62091 · doi:10.1137/S0363012904439301 |
| [5] | Aumann, R.J.: Integrals of set-valued functions. J. Math. Anal. Appl. 12, 1-12 (1965) · Zbl 0163.06301 · doi:10.1016/0022-247X(65)90049-1 |
| [6] | Aubin, J.P., Frankowska, H.: Set-Valued Analysis. Modern Birkhäuser Classics. Birkhäuser Boston Inc, Boston (2009). (Reprint of the 1990 edition) · doi:10.1007/978-0-8176-4848-0 |
| [7] | Bianchi, P.: Ergodic Convergence of a stochastic proximal point algorithm. arXiv:1504.05400 (2015) · Zbl 1315.65058 |
| [8] | Benaïm, M., Schreiber, S.J.: Ergodic properties of weak asymptotic pseudotrajectories for semiflows. J. Dyn. Differ. Equ. 12(3), 579-598 (2000) · Zbl 0998.37013 · doi:10.1023/A:1026463628355 |
| [9] | Bruck Jr., R.E.: Asymptotic convergence of nonlinear contraction semigroups in Hilbert space. J. Funct. Anal. 18, 15-26 (1975) · Zbl 0319.47041 · doi:10.1016/0022-1236(75)90027-0 |
| [10] | Brézis, H.: Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert. North-Holland mathematics studies. Elsevier Science, Burlington (1973) · Zbl 0252.47055 |
| [11] | Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York (2011) · Zbl 1218.47001 |
| [12] | Castaing, C., Valadier, M.: Convex Analysis and Measurable Multifunctions, vol. 580. Springer, Berlin (1977) · Zbl 0346.46038 |
| [13] | Hiai, F., Umegaki, H.: Integrals, conditional expectations, and martingales of multivalued functions. J. Multivar. Anal. 7(1), 149-182 (1977) · Zbl 0368.60006 · doi:10.1016/0047-259X(77)90037-9 |
| [14] | Attouch, H.: Familles d’opérateurs maximaux monotones et mesurabilité. Annali di Matematica Pura ed Appl. 120(1), 35-111 (1979). doi:10.1007/BF02411939 · Zbl 0416.47019 · doi:10.1007/BF02411939 |
| [15] | Hiriart-Urruty, J.B.: Contributions à la programmation mathématique: cas déterministe et stochastique. Université de Clermont-Ferrand II, Clermont-Ferrand (1977). Thèse présentée à l’Université de Clermont-Ferrand II pour obtenir le grade de Docteur ès Sciences Mathématiques. Série E, No. 247 |
| [16] | Aubin, J.P., Cellina, A.: Differential Inclusions, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 264. Springer, Berlin (1984). (Set-valued maps and viability theory) · Zbl 0538.34007 |
| [17] | Benaïm, M.: Dynamics of stochastic approximation algorithms. In: Séminaire de Probabilités, XXXIII, Lecture Notes in Math., vol. 1709, pp. 1-68. Springer, Berlin (1999) · Zbl 0955.62085 |
| [18] | Delyon, B.: Stochastic Approximation with Decreasing Gain: Convergence and Asymptotic Theory. Unpublished Lecture Notes, http://perso.univ-rennes1.fr/bernard.delyon/as_cours.ps (2000) · Zbl 0998.90088 |
| [19] | Bauschke, H.H., Borwein, J.M., Li, W.: Strong conical hull intersection property, bounded linear regularity, jamesons property (g), and error bounds in convex optimization. Math. Program. 86(1), 135-160 (1999) · Zbl 0998.90088 · doi:10.1007/s101070050083 |
| [20] | Peypouquet, J., Sorin, S.: Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time. J. Convex Anal. 17(3-4), 1113-1163 (2010) · Zbl 1214.47080 |
| [21] | Pazy, A.: On the asymptotic behavior of semigroups of nonlinear contractions in Hilbert space. J. Funct. Anal. 27(3), 292-307 (1978) · Zbl 0377.47045 · doi:10.1016/0022-1236(78)90010-1 |
| [22] | Rockafellar, R.T.: Measurable dependence of convex sets and functions on parameters. J. Math. Anal. Appl. 28, 4-25 (1969) · Zbl 0202.33804 · doi:10.1016/0022-247X(69)90104-8 |
| [23] | Rockafellar, R.T., Wets, R.J.B.: Variational Analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317. Springer, Berlin (1998) · Zbl 0888.49001 |
| [24] | Walkup, D.W., Wets, R.J.B.: Stochastic programs with recourse. II: on the continuity of the objective. SIAM J. Appl. Math. 17, 98-103 (1969) · Zbl 0169.51402 · doi:10.1137/0117010 |
| [25] | Kushner, H.J., Yin, G.G.: Stochastic Approximation and Recursive Algorithms and Applications, Applications of Mathematics (New York), vol. 35, 2nd edn. Springer, New York (2003). (Stochastic Modelling and Applied Probability) · Zbl 1026.62084 |
| [26] | Nedić, A.: Random algorithms for convex minimization problems. Math. Program. 129(2, Ser. B), 225-253 (2011) · Zbl 1229.90128 · doi:10.1007/s10107-011-0468-9 |
| [27] | Lee, S., Nedic, A.: Distributed random projection algorithm for convex optimization. IEEE J. Sel. Top. Signal Process. 7(2), 221-229 (2013). doi:10.1109/JSTSP.2013.2247023 · doi:10.1109/JSTSP.2013.2247023 |
| [28] | Bertsekas, D.P.: Incremental proximal methods for large scale convex optimization. Math. Program. 129(2, Ser. B), 163-195 (2011) · Zbl 1229.90121 · doi:10.1007/s10107-011-0472-0 |
| [29] | Wang, M., Bertsekas, D.P.: Incremental constraint projection-proximal methods for nonsmooth convex optimization. Tech. rep, Massachusetts Institute of Technology (2013) · Zbl 1087.62091 |
| [30] | Wang, M., Bertsekas, D.P.: Incremental constraint projection methods for variational inequalities. Math. Program. 150(2, Ser. A), 321-363 (2015) · Zbl 1315.65058 · doi:10.1007/s10107-014-0769-x |
| [31] | Kinderlehrer, D., Stampacchia, G.: An introduction to variational inequalities and their applications, Classics in Applied Mathematics, vol. 31. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2000). (Reprint of the 1980 original) · Zbl 0457.35001 |
| [32] | Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. J. Math. Anal. Appl. 72(2), 383-390 (1979) · Zbl 0428.47039 · doi:10.1016/0022-247X(79)90234-8 |
| [33] | Combettes, P., Pesquet, J.C.: Stochastic Approximations and Perturbations in Forward-backward Splitting for Monotone Operators. Pure and Applied Functional Analysis (2016). To appear · Zbl 1377.90109 |
| [34] | Atchade, Y.F., Fort, G., Moulines, E.: On perturbed proximal gradient algorithms. arXiv:1402.2365 (2014) · Zbl 1433.90199 |
| [35] | Rosasco, L., Villa, S., Vũ, B.C.: Convergence of stochastic proximal gradient algorithm. arXiv preprint arXiv:1403.5074 (2014) · Zbl 1465.90101 |
| [36] | Rosasco, L., Villa, S., Vũ, B.C.: A stochastic inertial forward-backward splitting algorithm for multivariate monotone inclusions. arXiv preprint arXiv:1507.00848 (2015) · Zbl 06587813 |
| [37] | Toulis, P., Tran, D., Airoldi, E.M.: Towards stability and optimality in stochastic gradient descent. arXiv:1505.02417 (2015) · Zbl 1332.62291 |
| [38] | Alvarez, F., Peypouquet, J.: Asymptotic equivalence and Kobayashi-type estimates for nonautonomous monotone operators in Banach spaces. Discrete Contin. Dyn. Syst. 25(4), 1109-1128 (2009) · Zbl 1177.47060 · doi:10.3934/dcds.2009.25.1109 |
| [39] | Alvarez, F., Peypouquet, J.: Asymptotic almost-equivalence of Lipschitz evolution systems in Banach spaces. Nonlinear Anal. Theory Methods Appl. 73(9), 3018-3033 (2010) · Zbl 1202.34084 · doi:10.1016/j.na.2010.06.070 |
| [40] | Álvarez, F., Peypouquet, J.: A unified approach to the asymptotic almost-equivalence of evolution systems without Lipschitz conditions. Nonlinear Anal. 74(11), 3440-3444 (2011) · Zbl 1219.34070 · doi:10.1016/j.na.2011.02.030 |
| [41] | Robbins, H., Siegmund, D.: A convergence theorem for non negative almost supermartingales and some applications. In: Optimizing Methods in Statistics, pp. 233-257. Academic Press, New York (1971) · Zbl 0286.60025 |
| [42] | Baillon, J.B., Brézis, H.: Une remarque sur le comportement asymptotique des semigroupes non linéaires. Houston J. Math. 2(1), 5-7 (1976) · Zbl 0318.47039 |
| [43] | Rockafellar, R.T., Wets, R.J.B.: On the interchange of subdifferentiation and conditional expectations for convex functionals. Stochastics 7(3), 173-182 (1982) · Zbl 0487.49006 · doi:10.1080/17442508208833217 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
