Stochastic monotone inclusion with closed loop distributions

Hamza Ennaji; Jalal Fadili; Hedy Attouch

doi:10.3934/eect.2025022

Article Contents

2026, Volume 17: 140-172. Doi: 10.3934/eect.2025022

This volume Previous Article Optimal boundary control of the Bulk-surface Coupled Cahn-Hilliard-diffusion system for lipid raft formation Next Article An optimal control problem driven by iterative integro-differential inclusion

Stochastic monotone inclusion with closed loop distributions

1.
Univ. Grenoble Alpes, CNRS, Grenoble INP*, LJK, 38000 Grenoble, France
2.
ENSICAEN, Normandie Université, CNRS, GREYC, France
3.
IMAG, Université Montpellier, CNRS, France

^*Corresponding author: Hamza Ennaji
^*Corresponding author: Hamza Ennaji

Dedicated to the memory of Hedy Attouch, outstanding mathematician and beloved collaborator.

Received: September 2024

Revised: January 2025

Early access: February 24, 2025

Published online: February 24, 2025

Our work is supported by the ANR-DFG joint project TRINOM-DS, under number ANR-20-CE92-0037-01.

Abstract / Introduction Full Text(HTML) Figure(1) / Table(1) Related Papers Cited by

Abstract

In this paper, we study in a Hilbertian setting the first and second-order monotone inclusions related to stochastic optimization problems with decision-dependent distributions. The studied dynamics are formulated as monotone inclusions governed by Lipschitz perturbations of maximally monotone operators where the concept of equilibrium plays a central role. We discuss the relationship between the $ \mathbb{W}_1 $-Wasserstein Lipschitz behavior of the distribution and the so-called coarse Ricci curvature. As an application, we consider the monotone inclusions associated with stochastic optimization problems involving the sum of a smooth function with Lipschitz gradient, a proximable function, and a composite term.

Keywords:

Mathematics Subject Classification: 34G25, 37N40, 46N10, 47H05, 49M30, 60J20.

Citation:

Full Text(HTML)

Figure 1. Illustration of the ORC

Download: Full-size image PowerPoint slide

Table 1. Relation between the values of $ \tau $ and $ \kappa_ \mathsf{m} $

Values of $ \tau $ $ 0 $ <1 $ \leq 1 $

Values of $ \kappa_ \mathsf{m} $ $ 1 $ $ ]0,1] $ $ [0,1] $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	F. Alvarez, On the minimizing property of a second order dissipative system in Hilbert spaces, SIAM J. Control Optim., 38 (2000), 1102-1119. doi: 10.1137/S0363012998335802.
[2]	F. Alvarez and H. Attouch, An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Anal., 9 (2001), 3-11.
[3]	F. Alvarez, H. Attouch, J. Bolte and P. Redont, A second-order gradient-like dissipative dynamical system with hessian-driven damping: Application to optimization and mechanics, Journal de Mathématiques Pures et Appliquées, 81 (2002), 747-779. doi: 10.1016/S0021-7824(01)01253-3.
[4]	L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures, Basel: Birkhäuser, 2nd ed. edition, 2008.
[5]	V. Apidopoulos, J.-F. Aujol and C. Dossal, Convergence rate of inertial forward–backward algorithm beyond Nesterov's rule, Mathematical Programming, 180 (2020), 137-156. doi: 10.1007/s10107-018-1350-9.
[6]	H. Attouch, G. Buttazzo and G. Michaille, Variational Analysis in Sobolev and BV Spaces, volume 17 of MOS-SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, second edition, 2014. Applications to PDEs and optimization.
[7]	H. Attouch, A. Cabot and P. Redont, The dynamics of elastic shocks via epigraphical regularization of a differential inclusion, barrier and penalty approximations, Adv. Math. Sci. Appl., 12 (2002), 273-306.
[8]	H. Attouch, Z. Chbani, J. Fadili and H. Riahi, Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics, J. Optim. Theory Appl., 193 (2022), 704-736. doi: 10.1007/s10957-021-01859-2.
[9]	H. Attouch, Z. Chbani, J. Fadili and H. Riahi, First-order optimization algorithms via inertial systems with Hessian driven damping, Math. Program., 193 (2022), 113-155. doi: 10.1007/s10107-020-01591-1.
[10]	H. Attouch, Z. Chbani, J. Peypouquet and P. Redont, Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity, Mathematical Programming, 168 (2018), 123-175. doi: 10.1007/s10107-016-0992-8.
[11]	H. Attouch, Z. Chbani and H. Riahi, Rate of convergence of the nesterov accelerated gradient method in the subcritical case $\alpha\leq3$, ESAIM: Control, Optimisation and Calculus of Variations, 25 (2019).
[12]	H. Attouch and S. Csaba László, Continuous Newton-like inertial dynamics for monotone inclusions, Set-Valued Var. Anal., 29 (2021), 555-581. doi: 10.1007/s11228-020-00564-y.
[13]	H. Attouch and A. Damlamian, On multivalued evolution equations in hilbert spaces, Israel Journal of Mathematics, 12 (1972), 373-390. doi: 10.1007/BF02764629.
[14]	H. Attouch, J. Fadili and V. Kungurtsev, On the effect of perturbations in first-order optimization methods with inertia and Hessian driven damping, Evol. Equ. Control Theory, 12 (2023), 71-117. doi: 10.3934/eect.2022022.
[15]	H. Attouch, X. Goudou and P. Redont, The heavy ball with friction method, i. the continuous dynaamical system: global exploration of the local minima of a real-valued function by asymptotic analysis of a dissipative dynamical system, Communications in Contemporary Mathematics, 2 (2000), 1-34. doi: 10.1142/S0219199700000025.
[16]	H. Attouch and J. Peypouquet, The rate of convergence of nesterov's accelerated forward-backward method is actually faster than $1/k^2$, SIAM Journal on Optimization, 26 (2016), 1824-1834. doi: 10.1137/15M1046095.
[17]	H. Attouch and J. Peypouquet, Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators, Math. Program., 174 (2019), 391-432. doi: 10.1007/s10107-018-1252-x.
[18]	H. Attouch, J. Peypouquet and P. Redont, A dynamical approach to an inertial forward-backward algorithm for convex minimization, SIAM Journal on Optimization, 24 (2014), 232-256. doi: 10.1137/130910294.
[19]	H. Attouch, J. Peypouquet and P. Redont, Fast convex optimization via inertial dynamics with hessian driven damping, Journal of Differential Equations, 261 (2016), 5734-5783. doi: 10.1016/j.jde.2016.08.020.
[20]	H. Bahouri, J.-Y. Chemin and R. Danchin, Fourier Analysis and Nonlinear Partial Differential Equations, volume 343 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer, Heidelberg, 2011.
[21]	J. Baillon and H. Brézis, Une remarque sur le comportement asymptotique des semigroupes non linéaires, Houston J. Math., 2 (1976), 5-7.
[22]	V. Barbu, Nonlinear Differential Equations of Monotone Types in Banach Spaces, Springer Monographs in Mathematics, Springer, New York, 2010.
[23]	H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2011. With a foreword by Hédy Attouch.
[24]	P. Bianchi, W. Hachem and A. Salim, A fully stochastic primal-dual algorithm, Optimization Letters, 15 (2021), 701-710. doi: 10.1007/s11590-020-01614-y.
[25]	R. I. Boţ, E. R. Csetnek and S. C. László, Tikhonov regularization of a second order dynamical system with Hessian driven damping, Math. Program., 189 (2021), 151-186. doi: 10.1007/s10107-020-01528-8.
[26]	H. Brézis, Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert, North-Holland Mathematics Studies, No. 5. North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973.
[27]	H. Brézis, Functional Analysis, SObolev Spaces and Partial Differential Equations, Universitext. Springer, New York, 2011.
[28]	R. E. Bruck Jr, Asymptotic convergence of nonlinear contraction semigroups in hilbert space, Journal of Functional Analysis, 18 (1975), 15-26. doi: 10.1016/0022-1236(75)90027-0.
[29]	A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of mathematical imaging and vision, 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.
[30]	L. Condat, A primal–dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms, Journal of optimization theory and applications, 158 (2013), 460-479. doi: 10.1007/s10957-012-0245-9.
[31]	J. Cutler, M. Díaz and D. Drusvyatskiy, Stochastic approximation with decision-dependent distributions: Asymptotic normality and optimality, Mach. Learn. Res., 25 (2024), Paper No. 90, 49 pp.
[32]	A. Derrow-Pinion, J. She, D. Wong, O. Lange, T. Hester, L. Perez, M. Nunkesser, S. Lee, X. Guo, B. Wiltshire, P. W. Battaglia, V. Gupta, A. Li, Z. Xu, A. Sanchez-Gonzalez, Y. Li and P. Velickovic, Eta prediction with graph neural networks in google maps, in Proceedings of the 30th ACM International Conference on Information & Knowledge Management, CIKM '21, 3767-3776, New York, NY, USA, 2021. Association for Computing Machinery.
[33]	R. Douc, E. Moulines, P. Priouret and P. Soulier, Markov Chains, Springer Series in Operations Research and Financial Engineering, Springer, Cham, 2018.
[34]	D. Drusvyatskiy and L. Xiao, Stochastic optimization with decision-dependent distributions, Mathematics of Operations Research, 48 (2023), 954–998.
[35]	X. He, R. Hu and Y. Fang, A second order primalâ-dual dynamical system for a convex-concave bilinear saddle point problem, Applied Mathematics & Optimization, 89 (2024), 30.
[36]	O. Hernández-Lerma and J. B. Lasserre, Markov Chains and Invariant Probabilities, volume 211 of Prog. Math., Basel: Birkhäuser, 2003.
[37]	D. Kim, Accelerated proximal point method for maximally monotone operators, Mathematical Programming, 190 (2021), 57-87. doi: 10.1007/s10107-021-01643-0.
[38]	S. C. László, Convergence rates for an inertial algorithm of gradient type associated to a smooth non-convex minimization, Mathematical Programming, 190 (2021), 285-329. doi: 10.1007/s10107-020-01534-w.
[39]	T. Lin and M. I. Jordan, A control-theoretic perspective on optimal high-order optimization, Mathematical Programming, 195 (2022), 929–975.
[40]	J. Macfarlane, Your navigation app is making traffic unmanageable, IEEE Spectrum, 19, 2019.
[41]	J. M. Mazón, M. Solera-Diana and J. Toledo-Melero, Variational and Diffusion Problems in Random Walk Spaces, Progress in Nonlinear Differential Equations and Their Applications, Springer Nature Switzerland, 2023.
[42]	C. Mendler-Dünner, J. C. Perdomo, T. Zrnic and M. Hardt, Stochastic optimization for performative prediction, in Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc.
[43]	Y. E. Nesterov, A method for solving the convex programming problem with convergence rate o(1/k^2), Dokl. Akad. Nauk SSSR., 269 (1983), 543-547.
[44]	Y. Ollivier, Ricci curvature of Markov chains on metric spaces, J. Funct. Anal., 256 (2009), 810-864. doi: 10.1016/j.jfa.2008.11.001.
[45]	Y. Ollivier, A survey of Ricci curvature for metric spaces and markov chains, in Probabilistic approach to geometry, Mathematical Society of Japan, 57 (2010), 343-381.
[46]	J. Perdomo, T. Zrnic, C. Mendler-Dünner and M. Hardt, Performative prediction, in H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research, 119 (2020), 7599-7609. PMLR.
[47]	B. T. Polyak, Some methods of speeding up the convergence of iteration methods, Ussr computational mathematics and mathematical physics, 4 (1964), 1-17. doi: 10.1016/0041-5553(64)90137-5.
[48]	H. Raguet, J. Fadili and G. Peyré, A generalized forward-backward splitting, SIAM Journal on Imaging Sciences, 6 (2013), 1199-1226. doi: 10.1137/120872802.
[49]	B. Shi, S. S. Du, M. I. Jordan and W. J. Su, Understanding the acceleration phenomenon via high-resolution differential equations, Mathematical Programming, 195 (2022), 79–148.
[50]	W. Su, S. Boyd and E. J. Candès, A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights, J. Mach. Learn. Res., 17 (2016), Paper No. 153, 43 pp.
[51]	B. C. Vũ, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Advances in Computational Mathematics, 38 (2013), 667-681. doi: 10.1007/s10444-011-9254-8.
[52]	K. Wood and E. Dall'Anese, Stochastic saddle point problems with decision-dependent distributions, SIAM Journal on Optimization, 33 (2023), 1943-1967. doi: 10.1137/22M1488077.