Abstract

We study the convergence of random function iterations for finding an invariant measure of the corresponding Markov operator. We call the problem of finding such an invariant measure the stochastic fixed point problem. This generalizes earlier work of the authors [Random function iterations for consistent stochastic feasibility, Numer. Funct. Analysis Opt. 40/4 (2019) 386–420] studying the stochastic feasibility problem, namely, to find points that are, with probability 1, fixed points of the random functions. When no such points exist, the stochastic feasibility problem is called inconsistent, but still under certain assumptions, the more general stochastic fixed point problem has a solution and the random function iteration converges to an invariant measure for the corresponding Markov operator. We show how common structures in deterministic fixed point theory can be exploited to establish existence of invariant measures and convergence in distribution of the Markov chain. This framework specializes to many applications of current interest including, for instance, stochastic algorithms for large-scale distributed computation, and deterministic iterative procedures with computational error. The theory developed in this study provides a solid basis for describing the convergence of simple computational methods without the assumption of infinite precision arithmetic or vanishing computational errors.

Author information

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

Keywords

  • Averaged mappings
  • nonexpansive mappings
  • stochastic feasibility
  • inconsistent stochastic fixed point problem
  • iterated random functions
  • convergence of Markov chain

Mathematics Subject Classification

60J05, 46N10, 46N30, 65C40, 49J55; 49J53, 65K05

References

  1. D. Ariza-Ruiz, L. Leuştean, G. López-Acedo: Firmly nonexpansive mappings in classes of geodesic spaces, Trans. Amer. Math. Soc. 366/8 (2014) 4299–4322.https://doi.org/10.1090/S0002-9947-2014-05968-0Google Scholar
  2. D. Ariza-Ruiz, G. López-Acedo, A. Nicolae: The asymptotic behavior of the composition of firmly nonexpansive mappings, J. Optim. Theory Appl. 167 (2015) 409–429.https://doi.org/10.1007/s10957-015-0710-3Google Scholar
  3. J.-B. Baillon, R. E. Bruck: The rate of asymptotic regularity is o( √ n), in: Theory and Applications of Nonlinear Operators of Accretive and Monotone Type, A. G. Kartsatos (ed.), Lecture Notes in Pure and Applied Mathematics 178, Marcel Dekker, New York (1996) 51–81.Google Scholar
  4. J. B. Baillon, R. E. Bruck, S. Reich: On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces, Houston J. Math. 4/1 (1978) 1–9.Google Scholar
  5. J.-B. Baillon, G. Haddad: Quelques propriétés des opérateurs angle-bornés et n-cycliquement monotones, Israel J. Math. 26 (1977) 137–150.https://doi.org/10.1007/BF03007664Google Scholar
  6. C. Baldassi, C. Borgs, J. T. Chayes, A. Ingrosso, C. Lucibello, L. Saglietti, R. Zecchina: Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes, Proc. National Acad. Sciences 113/48 (2016) E7655–E7662.https://doi.org/10.1073/pnas.1608103113Google Scholar
  7. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., CMS Books in Mathematics, Springer, New York (2017).https://doi.org/10.1007/978-3-319-48311-5Google Scholar
  8. A. Bërdëllima, F. Lauster, D. R. Luke: α-firmly nonexpansive operators on metric spaces, J. Fixed Point Theory Appl. 24/1 (2022), art. no. 14.https://doi.org/10.1007/s11784-021-00919-4Google Scholar
  9. P. Billingsley: Convergence of Probability Measures, 2nd ed., Wiley, Chichester (1999).https://doi.org/10.1002/9780470316962Google Scholar
  10. S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein: Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learning 3/1 (2011) 1–122.https://doi.org/10.1561/2200000016Google Scholar
  11. L. M. Briceño-Arias, G. Chierchia, E. Chouzenoux, J.-C. Pesquet: A random block-coordinate Douglas–Rachford splitting method with low computational complexity for binary logistic regression, Comp. Optim. Appl. 72 (2019) 707–726.https://doi.org/10.1007/s10589-019-00060-6Google Scholar
  12. F. E. Browder: Convergence theorems for sequences of nonlinear operators in Banach spaces, Math. Zeitschrift 100 (1967) 201–225.https://doi.org/10.1007/BF01109805Google Scholar
  13. D. Butnariu: The expected-projection method: Its behavior and applications to linear operator equations and convex optimization, J. Appl. Analysis 1/1 (1995) 93–108.https://doi.org/10.1515/JAA.1995.93Google Scholar
  14. D. Butnariu, Y. Censor, S. Reich: Iterative averaging of entropic projections for solving stochastic convex feasibility problems, Comp. Optim. Appl. 8 (1997) 21–39.https://doi.org/10.1023/A:1008654413997Google Scholar
  15. D. Butnariu, S. D. Flåm: Strong convergence of expected-projection methods in Hilbert spaces, Numer. Funct. Anal. Optim. 16/5-6 (1995) 601–636.https://doi.org/10.1080/01630569508816635Google Scholar
  16. D. Butnariu, A. N. Iusem, R. S. Burachik: Iterative methods of solving stochastic convex feasibility problems and applications, Comp. Optim. Appl. 15 (2000) 269–307.https://doi.org/10.1023/A:1008795702124Google Scholar
  17. D. Butnariu, S. Reich, A. J. Zaslavski: Asymptotic behavior of inexact orbits for a class of operators in complete metric spaces, J. Appl. Analysis 13/1 (2007) 1–11.https://doi.org/10.1515/JAA.2007.1Google Scholar
  18. V. Cevher, B. C. Vũ, A. Yurtsever: Stochastic forward Douglas-Rachford splitting method for monotone inclusions, in: Large-Scale and Distributed Optimization, P. Giselsson et al. (eds.), Workshop Lund 2017, Lecture Notes in Mathematics 2227, Springer, Cham (2018) 149–179.https://doi.org/10.1007/978-3-319-97478-1_7Google Scholar
  19. W. Cheney, A. A. Goldstein: Proximity maps for convex sets, Proc. Amer. Math. Soc. 10/3 (1959) 448–450.https://doi.org/10.1090/S0002-9939-1959-0105008-8Google Scholar
  20. P. L. Combettes, J. Eckstein: Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions, Math. Programming 168/1 (2018) 645–672.https://doi.org/10.1007/s10107-016-1044-0Google Scholar
  21. P. L. Combettes, S. Salzo, S. Villa: Consistent learning by composite proximal thresholding, Math. Programming Ser. B 167/1 (2018) 99–127.https://doi.org/10.1007/s10107-017-1133-8Google Scholar
  22. R. Cominetti, J. A. Soto, J. Vaisman: On the rate of convergence of Krasnosel’skiǐ-Mann iterations and their connection with sums of Bernoullis, Israel J. Math. 199, Part B (2014) 757–772.https://doi.org/10.1007/s11856-013-0045-4Google Scholar
  23. P. Diaconis, D. Freedman: Iterated random functions, SIAM Review 41/1 (1999) 45–76.https://doi.org/10.1137/S0036144598338446Google Scholar
  24. A. Dieuleveut, A. Durmus, F. Bach: Bridging the gap between constant step size stochastic gradient descent and Markov chains, Ann. Stat. 48/3 (2020) 1348–1382.https://doi.org/10.1214/19-AOS1850Google Scholar
  25. C. Geiersbach, G. Ch. Pflug: Projected stochastic gradients for convex constrained problems in Hilbert spaces, SIAM J. Optim. 29/3 (2019) 2079–2099.https://doi.org/10.1137/18M1200208Google Scholar
  26. R. M. Gower, P. Richtárik: Randomized iterative methods for linear systems, SIAM J. Matrix Analysis Appl. 36/4 (2015) 1660–1690.https://doi.org/10.1137/15M1025487Google Scholar
  27. M. Hairer: Convergence of Markov Processes, Lecture Notes, University of Warwick, (2016).Google Scholar
  28. M. Hardt, T. Ma, B. Recht: Gradient descent learns linear dynamical systems, J. Mach. Learn. Res. 19 (2018), art. no. 29, 44 p.Google Scholar
  29. N. Hermer: Random Functions Iterations for Stochastic Feasibility Problems, PhD thesis, University of Göttingen (2019).https://doi.org/10.1080/01630563.2018.1535507Google Scholar
  30. N. Hermer, D. R. Luke, A. Sturm: Random function iterations for consistent stochastic feasibility, Numer. Funct. Anal. Opt. 40/4 (2019) 386–420.https://doi.org/10.1080/01630563.2018.1535507Google Scholar
  31. O. Hernández-Lerma, J. B. Lasserre: Markov Chains and Invariant Probabilities, Birkhäuser, Basel (2003).https://doi.org/10.1007/978-3-0348-8024-4Google Scholar
  32. A. N. Iusem, T. Pennanen, B. F. Svaiter: Inexact variants of the proximal point algorithm without monotonicity, SIAM J. Optimization 13/4 (2003) 1080–1097.https://doi.org/10.1137/S1052623401399587Google Scholar
  33. O. Kallenberg: Foundations of Modern Probability, Probability and Its Applications, Springer, New York (1997).Google Scholar
  34. L. Kuipers, H. Niederreiter: Uniform Distribution of Sequences, Pure and Applied Mathematics, Wiley, New York (1974).Google Scholar
  35. M. N. Lam, H. N. Phuong, P. Richtárik, K. Scheinberg, M. Takáč, M. van Dijk: New convergence aspects of stochastic gradient algorithms, J. Mach. Learn. Res. 20 (2019), art. no. 176, 49 p.Google Scholar
  36. A. Lasota, T. Szarek: Lower bound technique in the theory of a stochastic differential equation, J. Diff. Equations 231/2 (2006) 513–533.https://doi.org/10.1016/j.jde.2006.04.018Google Scholar
  37. F. Lauster, D. R. Luke: Convergence of proximal splitting algorithms in CAT(κ) spaces and beyond, Fixed Point Theory Alg. Sci. Eng. (2021), art. no. 13, 21 p.https://doi.org/10.1186/s13663-021-00698-0Google Scholar
  38. P. L. Lions, B. Mercier: Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16 (1979) 964–979.https://doi.org/10.1137/0716071Google Scholar
  39. D. R. Luke, R. Shefi: A globally linearly convergent method for pointwise quadratically supportable convex-concave saddle point problems, J. Math. Analysis Appl. 457/2 (2018) 1568–1590.https://doi.org/10.1016/j.jmaa.2017.02.068Google Scholar
  40. D. R. Luke, N. H. Thao, M. K. Tam: Quantitative convergence analysis of iterated expansive, set-valued mappings, Math. Oper. Res. 43/4 (2018) 1143–1176.https://doi.org/10.1287/moor.2017.0898Google Scholar
  41. P. Mattila: Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability, Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge (1995).https://doi.org/10.1017/CBO9780511623813Google Scholar
  42. S. Meyn, R. L. Tweedie: Markov Chains and Stochastic Stability, Cambridge University Press, Cambridge (2009).https://doi.org/10.1017/CBO9780511626630Google Scholar
  43. J. J. Moreau: Proximité et dualité dans un espace Hilbertian, Bull. Soc. Math. France 93/3 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  44. A. Nedić: Random algorithms for convex minimization problems, Math. Programming 129/2 (2011) 225–253.https://doi.org/10.1007/s10107-011-0468-9Google Scholar
  45. K. R. Parthasarathy: Probability Measures on Metric Spaces, reprint of the 1967 original, AMS Chelsea Publishing, Providence (2005).https://doi.org/10.1090/chel/352Google Scholar
  46. G. Ch. Pflug: Stochastic minimization with constant step-size: asymptotic laws, SIAM J. Control Optimization 24/4 (1986) 655–666.https://doi.org/10.1137/0324039Google Scholar
  47. D. Preiss: Dimension of metrics and differentiation of measures, in: General Topology and its Relations to Modern Analysis and Algebra V, Proc. 5th Prague Topol. Symp. 1981, Sigma Series in Pure Mathematics Vol. 3, Heldermann, Berlin (1983) 565–568.Google Scholar
  48. Yu. V. Prokhorov: Convergence of random processes and limit theorems in probability theory, Teor. Veroyatn. Primen. 1 (1956) 177–238.https://doi.org/10.1137/1101016Google Scholar
  49. L. Rey-Bellet: Ergodic properties of Markov processes, in: Open Quantum Systems. II: The Markovian Approach, S. Attal et al. (eds.), Summer School Grenoble 2003, Lecture Notes in Mathematics 1881, Springer, Berlin (2006) 1–39.https://doi.org/10.1007/3-540-33966-3_1Google Scholar
  50. P. Richtárik, M. Takáč: Distributed coordinate descent method for learning with big data, J. Mach. Learn. Res. 17 (2016), art. no. 75, 25 p.Google Scholar
  51. H. E. Robbins, S. Monro: A stochastic approximation method, Ann. Math. Statistics 22 (1951) 400–407.https://doi.org/10.1214/aoms/1177729586Google Scholar
  52. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control. Optim. 14 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  53. L. Rosasco, S. Villa, B. C. Vũ: Convergence of stochastic proximal gradient algorithm, Appl. Math. Optim. 82/3 (2019) 891–917.https://doi.org/10.1007/s00245-019-09617-7Google Scholar
  54. M. V. Solodov, B. F. Svaiter: A hybrid approximate extragradient–proximal point algorithm using the enlargement of a maximal monotone operator, Set-Valued Analysis 7 (1999) 323–345.https://doi.org/10.1023/A:1008777829180Google Scholar
  55. V. Strassen: The existence of probability measures with given marginals, Ann. Math. Statistics 36/2 (1965) 423–439.https://doi.org/10.1214/aoms/1177700153Google Scholar
  56. D. W. Stroock: Probability Theory: An Analytic View, Cambridge University Press, Cambridge (2010).https://doi.org/10.1017/CBO9780511974243Google Scholar
  57. T. Szarek: Feller processes on nonlocally compact spaces, Ann. Probab. 34/5 (2006) 1849–1863.https://doi.org/10.1214/009117906000000313Google Scholar
  58. C. Villani: Optimal Transport: Old and New, Grundlehren der Mathematischen Wissenschaften 338, Springer, Berlin (2009).https://doi.org/10.1007/978-3-540-71050-9Google Scholar
  59. J. von Neumann: Functional Operators. Vol II: The Geometry of Orthogonal Spaces, Annals of Mathematical Studies Vol. 22, Princeton University Press, Princeton (1950).https://doi.org/10.1515/9781400881895Google Scholar
  60. P. Walters: An Introduction to Ergodic Theory, Graduate Texts in Mathematics Vol. 79, Springer, New York (2000).Google Scholar
  61. D. Worm: Semigroups on Spaces of Measures, PhD thesis, Universiteit Leiden (2010).Google Scholar

Suggested citation

N. Hermer, D. R. Luke, A. Sturm. “Nonexpansive Markov Operators and Random Function Iterations for Stochastic Fixed Point Problems.” Journal of Convex Analysis 30 (2023), No. 4, 1073–1114. https://doi.org/10.68381/jca30049

Download BibTeXPublished by Heldermann Verlag.

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