×

Multilevel Monte Carlo approximation of functions. (English) Zbl 1490.65023

Summary: Many applications across sciences and technologies require a careful quantification of nondeterministic effects to a system output, for example, when evaluating the system’s reliability or when gearing it towards more robust operation conditions. At the heart of these considerations lies an accurate characterization of uncertain system outputs. In this work we introduce and analyze novel multilevel Monte Carlo techniques for an efficient characterization of an uncertain system output’s distribution. These techniques rely on accurately approximating general parametric expectations, i.e., expectations that depend on a parameter, uniformly on an interval. Applications of interest include, for example, the approximation of the characteristic function and of the cumulative distribution function of an uncertain system output. A further important consequence of the introduced approximation techniques for parametric expectations (i.e., for functions) is that they allow us to construct multilevel Monte Carlo estimators for various robustness indicators, such as for a quantile (also known as value-at-risk) and for the conditional value-at-risk. These robustness indicators cannot be expressed as moments and are thus not usually easily accessible. In fact, here we provide a framework that allows us to simultaneously estimate a cumulative distribution function, a quantile, and the associated conditional value-at-risk of an uncertain system output at the cost of a single multilevel Monte Carlo simulation, while each estimated quantity satisfies a prescribed tolerance goal.

MSC:

65D15 Algorithms for approximation of functions
65C05 Monte Carlo methods
60H35 Computational methods for stochastic equations (aspects of stochastic analysis)
65C20 Probabilistic models, generic numerical methods in probability and statistics
65Y20 Complexity and performance of numerical algorithms
60E10 Characteristic functions; other transforms
91G70 Statistical methods; risk measures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Asmussen and P. W. Glynn, {\it Stochastic Simulation: Algorithms and Analysis}, Springer, New York, 2007, . · Zbl 1126.65001
[2] S. Asmussen, J. L. Jensen, and L. Rojas-Nandayapa, {\it On the Laplace transform of the lognormal distribution}, Methodol. Comput. Appl. Probab., 18 (2016), pp. 441-458, . · Zbl 1386.60066
[3] S.-K. Au and J. L. Beck, {\it Estimation of small failure probabilities in high dimensions by subset simulation}, Probabilist. Eng. Mech., 16 (2001), pp. 263-277, .
[4] R. Avikainen, {\it On irregular functionals of SDEs and the Euler scheme}, Finance Stoch., 13 (2009), pp. 381-401, . · Zbl 1199.60198
[5] V. Barthelmann, E. Novak, and K. Ritter, {\it High dimensional polynomial interpolation on sparse grids}, Adv. Comput. Math., 12 (2000), pp. 273-288, . · Zbl 0944.41001
[6] C. Bierig and A. Chernov, {\it Convergence analysis of multilevel Monte Carlo variance estimators and application for random obstacle problems}, Numer. Math., 130 (2015), pp. 579-613, . · Zbl 1432.65006
[7] C. Bierig and A. Chernov, {\it Approximation of probability density functions by the multilevel Monte Carlo maximum entropy method}, J. Comput. Phys., 314 (2016), pp. 661-681, . · Zbl 1349.65007
[8] C. Bierig and A. Chernov, {\it Estimation of arbitrary order central statistical moments by the multilevel Monte Carlo method}, Stoch. Partial Differ. Equ. Anal. Comput., 4 (2016), pp. 3-40, . · Zbl 1375.65011
[9] S. C. Brenner and L. R. Scott, {\it The Mathematical Theory of Finite Element Methods}, 3rd ed., Springer, New York, 2008, . · Zbl 1135.65042
[10] C. Canuto, M. Y. Hussainif, A. Quarteroni, and T. A. Zang, {\it Spectral Methods: Fundamentals in Single Domains}, Springer, New York, 2011.
[11] K. A. Cliffe, M. B. Giles, R. Scheichl, and A. L. Teckentrup, {\it Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients}, Comput. Vis. Sci., 14 (2011), pp. 3-15, . · Zbl 1241.65012
[12] C. de Boor, {\it A Practical Guide to Splines}, Springer, New York, 2001. · Zbl 0987.65015
[13] S. Dereich and T. Mueller-Gronbach, {\it General Multilevel Adaptations for Stochastic Approximation Algorithms}, Preprint, arXiv:1506.05482 [math.PR], 2015, . · Zbl 1464.62366
[14] D. Elfverson, D. J. Estep, F. Hellman, and A. M\ralqvist, {\it Uncertainty quantification for approximate \(p\)-quantiles for physical models with stochastic inputs}, SIAM/ASA J. Uncertain. Quantif., 2 (2014), pp. 826-850, . · Zbl 1311.65003
[15] D. Feldman and H. G. Tucker, {\it Estimation of non-unique quantiles}, Ann. Math. Statist., 37 (1966), pp. 451-457, . · Zbl 0152.36907
[16] N. Frikha, {\it Multi-level stochastic approximation algorithms}, Ann. Appl. Probab., 26 (2016), pp. 933-985, . · Zbl 1344.93111
[17] M. B. Giles, {\it Multilevel Monte Carlo path simulation}, Oper. Res., 56 (2008), pp. 607-617, . · Zbl 1167.65316
[18] M. B. Giles, {\it Multilevel Monte Carlo methods}, Acta Numer., 24 (2015), pp. 259-328, . · Zbl 1316.65010
[19] M. B. Giles and A.-L. Haji-Ali, {\it Multilevel Nested Simulation for Efficient Risk Estimation}, Preprint, [Q-Fin.CP], 2018, . · Zbl 1457.91416
[20] M. B. Giles, T. Nagapetyan, and K. Ritter, {\it Multilevel Monte Carlo approximation of distribution functions and densities}, SIAM/ASA J. Uncertain. Quantif., 3 (2015), pp. 267-295, . · Zbl 1322.65014
[21] M. B. Giles, T. Nagapetyan, and K. Ritter, {\it Adaptive Multilevel Monte Carlo Approximation of Distribution Functions}, Preprint, [math.PR], 2017, . · Zbl 1322.65014
[22] N. K. Govil and R. N. Mohapatra, {\it Markov and Bernstein type inequalities for polynomials}, J. Inequal. Appl., 3 (1999), pp. 349-387, . · Zbl 0933.30003
[23] C. A. Hall and W. W. Meyer, {\it Optimal error bounds for cubic spline interpolation}, J. Approx. Theory, 16 (1976), pp. 105-122, . · Zbl 0316.41007
[24] S. Heinrich, {\it Monte Carlo complexity of global solution of integral equations}, J. Complexity, 14 (1998), pp. 151-175, . · Zbl 0920.65090
[25] S. Heinrich, {\it Multilevel Monte Carlo methods}, in Large-Scale Scientific Computing, Springer, Berlin, Heidelberg, 2001, pp. 58-67, . · Zbl 1031.65005
[26] P. Holgate, {\it The lognormal characteristic function}, Comm. Statist. Theory Methods, 18 (1989), pp. 4539-4548, . · Zbl 0721.60012
[27] P. E. Kloeden and E. Platen, {\it Numerical Solution of Stochastic Differential Equations}, Applications of Mathematics 23, Springer, New York, 1992, . · Zbl 0752.60043
[28] M. Ledoux and M. Talagrand, {\it Probability in Banach Spaces}, Springer, New York, 1991, . · Zbl 0748.60004
[29] V. Linde and A. Pietsch, {\it Mappings of Gaussian cylindrical measures in Banach spaces}, Theory Probab. Appl., 19 (1974), pp. 445-460, . · Zbl 0312.60005
[30] M. Pisaroni, S. Krumscheid, and F. Nobile, {\it Quantifying Uncertain System Outputs via the Multilevel Monte Carlo Method - Part I: Central Moment Estimation}, MATHICSE Technical report 23.2017, École Polytechnique Fédérale de Lausanne, Switzerland, 2017. · Zbl 1440.65008
[31] M. Pisaroni, S. Krumscheid, and F. Nobile, {\it Quantifying uncertain system outputs via the multilevel Monte Carlo method - Part II: Distribution and robustness measures}, manuscript, 2018. · Zbl 1440.65008
[32] R. T. Rockafellar and S. Uryasev, {\it Conditional value-at-risk for general loss distributions}, J. Bank. Financ., 26 (2002), pp. 1443-1471, .
[33] A. L. Teckentrup, R. Scheichl, M. B. Giles, and E. Ullmann, {\it Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients}, Numer. Math., 125 (2013), pp. 569-600, . · Zbl 1306.65009
[34] L. N. Trefethen, {\it Approximation Theory and Approximation Practice}, Society for Industrial and Applied Mathematics, Philadelphia, 2013. · Zbl 1264.41001
[35] E. Ullmann and I. Papaioannou, {\it Multilevel estimation of rare events}, SIAM/ASA J. Uncertain. Quantif., 3 (2015), pp. 922-953, . · Zbl 1327.65246
[36] A. W. van der Vaart, {\it Asymptotic Statistics}, Cambridge University Press, Cambridge, UK, 2000. · Zbl 0910.62001
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.