Influence of sampling on the convergence rates of greedy algorithms for parameter-dependent random variables

Blel, Mohamed-Raed; Ehrlacher, Virginie; Lelièvre, Tony

doi:10.1090/mcom/3979

Influence of sampling on the convergence rates of greedy algorithms for parameter-dependent random variables
HTML articles powered by AMS MathViewer

by Mohamed-Raed Blel, Virginie Ehrlacher and Tony Lelièvre;

Math. Comp. 94 (2025), 863-908

DOI: https://doi.org/10.1090/mcom/3979

Published electronically: August 2, 2024

HTML | PDF

Abstract:

The main focus of this article is to provide a mathematical study of greedy algorithms for the construction of reduced bases so as to approximate a collection of parameter-dependent random variables. For each value of the parameter, the associated random variable belongs to some Hilbert space (say the space of square-integrable random variates for instance). But carrying out an exact greedy algorithm in this context would require the computation of exact expectations or variances of parameter-dependent random variates, which cannot be done in practice. Instead, expectations and variances can only be computed approximately via empirical means and empirical variances involving a finite number of Monte-Carlo samples. The aim of this work is precisely to study the effect of finite Monte-Carlo sampling on the theoretical properties of greedy algorithms. In particular, using concentration inequalities for the empirical measure in Wasserstein distance proved by Fournier and Guillin [Probab. Theory Related Fields 162 (2015), pp. 707–738], we provide sufficient conditions on the number of samples used for the computation of empirical variances at each iteration of the greedy procedure to guarantee that the resulting method algorithm is a weak greedy algorithm with high probability. Let us mention here that such an algorithm has initially been proposed by Boyaval and Lelièvre [Commun. Math. Sci. 8 (2010), pp. 735–762] with the aim to design a variance reduction technique for the computation of parameter-dependent expectations via the use of control variates constructed using a reduced basis paradigm. The theoretical results we prove here are not fully practical and we therefore propose a heuristic procedure to choose the number of Monte-Carlo samples at each iteration, inspired from this theoretical study, which provides satisfactory results on several numerical test cases.

References

Oleg Balabanov and Anthony Nouy, Randomized linear algebra for model reduction. Part I: Galerkin methods and error estimation, Adv. Comput. Math. 45 (2019), no. 5-6, 2969–3019. MR 4047024, DOI 10.1007/s10444-019-09725-6
Oleg Balabanov and Anthony Nouy, Randomized linear algebra for model reduction—part II: minimal residual methods and dictionary-based approximation, Adv. Comput. Math. 47 (2021), no. 2, Paper No. 26, 54. MR 4237488, DOI 10.1007/s10444-020-09836-5
Maxime Barrault, Yvon Maday, Ngoc Cuong Nguyen, and Anthony T. Patera, An ‘empirical interpolation’ method: application to efficient reduced-basis discretization of partial differential equations, C. R. Math. Acad. Sci. Paris 339 (2004), no. 9, 667–672 (English, with English and French summaries). MR 2103208, DOI 10.1016/j.crma.2004.08.006
Peter Binev, Albert Cohen, Wolfgang Dahmen, Ronald DeVore, Guergana Petrova, and Przemyslaw Wojtaszczyk, Convergence rates for greedy algorithms in reduced basis methods, SIAM J. Math. Anal. 43 (2011), no. 3, 1457–1472. MR 2821591, DOI 10.1137/100795772
François Bolley, Arnaud Guillin, and Cédric Villani, Quantitative concentration inequalities for empirical measures on non-compact spaces, Probab. Theory Related Fields 137 (2007), no. 3-4, 541–593. MR 2280433, DOI 10.1007/s00440-006-0004-7
Sébastien Boyaval and Tony Lelièvre, A variance reduction method for parametrized stochastic differential equations using the reduced basis paradigm, Commun. Math. Sci. 8 (2010), no. 3, 735–762. MR 2730329, DOI 10.4310/CMS.2010.v8.n3.a7
Annalisa Buffa, Yvon Maday, Anthony T. Patera, Christophe Prud’homme, and Gabriel Turinici, A priori convergence of the greedy algorithm for the parametrized reduced basis method, ESAIM Math. Model. Numer. Anal. 46 (2012), no. 3, 595–603. MR 2877366, DOI 10.1051/m2an/2011056
K. A. Cliffe, M. B. Giles, R. Scheichl, and A. L. Teckentrup, Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients, Comput. Vis. Sci. 14 (2011), no. 1, 3–15. MR 2835612, DOI 10.1007/s00791-011-0160-x
Albert Cohen, Wolfgang Dahmen, Ronald DeVore, and James Nichols, Reduced basis greedy selection using random training sets, ESAIM Math. Model. Numer. Anal. 54 (2020), no. 5, 1509–1524. MR 4123669, DOI 10.1051/m2an/2020004
Albert Cohen, Mark A. Davenport, and Dany Leviatan, On the stability and accuracy of least squares approximations, Found. Comput. Math. 13 (2013), no. 5, 819–834. MR 3105946, DOI 10.1007/s10208-013-9142-3
Albert Cohen and Giovanni Migliorati, Optimal weighted least-squares methods, SMAI J. Comput. Math. 3 (2017), 181–203. MR 3716755, DOI 10.5802/smai-jcm.24
Ronald DeVore, Guergana Petrova, and Przemyslaw Wojtaszczyk, Greedy algorithms for reduced bases in Banach spaces, Constr. Approx. 37 (2013), no. 3, 455–466. MR 3054611, DOI 10.1007/s00365-013-9186-2
Ronald A. DeVore, Nonlinear approximation, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 51–150. MR 1689432, DOI 10.1017/S0962492900002816
Ronald A. DeVore, The theoretical foundation of reduced basis methods, Model reduction and approximation, Comput. Sci. Eng., vol. 15, SIAM, Philadelphia, PA, 2017, pp. 137–168. MR 3672147, DOI 10.1137/1.9781611974829.ch3
Matthieu Dolbeault and Albert Cohen, Optimal pointwise sampling for $L^2$ approximation, J. Complexity 68 (2022), Paper No. 101602, 12. MR 4343734, DOI 10.1016/j.jco.2021.101602
Alireza Doostan and Gianluca Iaccarino, A least-squares approximation of partial differential equations with high-dimensional random inputs, J. Comput. Phys. 228 (2009), no. 12, 4332–4345. MR 2531901, DOI 10.1016/j.jcp.2009.03.006
Virginie Ehrlacher, Damiano Lombardi, Olga Mula, and François-Xavier Vialard, Nonlinear model reduction on metric spaces. Application to one-dimensional conservative PDEs in Wasserstein spaces, ESAIM Math. Model. Numer. Anal. 54 (2020), no. 6, 2159–2197. MR 4169690, DOI 10.1051/m2an/2020013
Nicolas Fournier and Arnaud Guillin, On the rate of convergence in Wasserstein distance of the empirical measure, Probab. Theory Related Fields 162 (2015), no. 3-4, 707–738. MR 3383341, DOI 10.1007/s00440-014-0583-7
Michael B. Giles, Multilevel Monte Carlo methods, Acta Numer. 24 (2015), 259–328. MR 3349310, DOI 10.1017/S096249291500001X
N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev. 53 (2011), no. 2, 217–288. MR 2806637, DOI 10.1137/090771806
Jan S. Hesthaven, Gianluigi Rozza, and Benjamin Stamm, Certified reduced basis methods for parametrized partial differential equations, SpringerBriefs in Mathematics, Springer, Cham; BCAM Basque Center for Applied Mathematics, Bilbao, 2016. BCAM SpringerBriefs. MR 3408061, DOI 10.1007/978-3-319-22470-1
Lutz Kämmerer, Tino Ullrich, and Toni Volkmer, Worst-case recovery guarantees for least squares approximation using random samples, Constr. Approx. 54 (2021), no. 2, 295–352. MR 4321776, DOI 10.1007/s00365-021-09555-0
David Krieg and Mario Ullrich, Function values are enough for $L_2$-approximation, Found. Comput. Math. 21 (2021), no. 4, 1141–1151. MR 4298242, DOI 10.1007/s10208-020-09481-w
Yvon Maday, Anthony T. Patera, and Gabriel Turinici, A priori convergence theory for reduced-basis approximations of single-parameter elliptic partial differential equations, Proceedings of the Fifth International Conference on Spectral and High Order Methods (ICOSAHOM-01) (Uppsala), 2002, pp. 437–446. MR 1910581, DOI 10.1023/A:1015145924517
Benjamin Peherstorfer, Karen Willcox, and Max Gunzburger, Survey of multifidelity methods in uncertainty propagation, inference, and optimization, SIAM Rev. 60 (2018), no. 3, 550–591. MR 3841157, DOI 10.1137/16M1082469
Alfio Quarteroni, Andrea Manzoni, and Federico Negri, Reduced basis methods for partial differential equations, Unitext, vol. 92, Springer, Cham, 2016. An introduction; La Matematica per il 3+2. MR 3379913, DOI 10.1007/978-3-319-15431-2
Kathrin Smetana and Olivier Zahm, Randomized residual-based error estimators for the proper generalized decomposition approximation of parametrized problems, Internat. J. Numer. Methods Engrg. 121 (2020), no. 23, 5153–5177. MR 4171465, DOI 10.1002/nme.6339
Kathrin Smetana, Olivier Zahm, and Anthony T. Patera, Randomized residual-based error estimators for parametrized equations, SIAM J. Sci. Comput. 41 (2019), no. 2, A900–A926. MR 3932628, DOI 10.1137/18M120364X
K. Veroy and A. T. Patera, Certified real-time solution of the parametrized steady incompressible Navier-Stokes equations: rigorous reduced-basis a posteriori error bounds, Internat. J. Numer. Methods Fluids 47 (2005), no. 8-9, 773–788. MR 2123791, DOI 10.1002/fld.867
F. Vidal-Codina, N. C. Nguyen, M. B. Giles, and J. Peraire, A model and variance reduction method for computing statistical outputs of stochastic elliptic partial differential equations, J. Comput. Phys. 297 (2015), 700–720. MR 3361685, DOI 10.1016/j.jcp.2015.05.041