×

Monte Carlo with determinantal point processes. (English) Zbl 1491.65007

Summary: We show that repulsive random variables can yield Monte Carlo methods with faster convergence rates than the typical \(N^{-1/2}\), where \(N\) is the number of integrand evaluations. More precisely, we propose stochastic numerical quadratures involving determinantal point processes associated with multivariate orthogonal polynomials, and we obtain root mean square errors that decrease as \(N^{-(1+1/d)/2}\), where \(d\) is the dimension of the ambient space. First, we prove a central limit theorem (CLT) for the linear statistics of a class of determinantal point processes, when the reference measure is a product measure supported on a hypercube, which satisfies the Nevai-class regularity condition; a result which may be of independent interest. Next, we introduce a Monte Carlo method based on these determinantal point processes, and prove a CLT with explicit limiting variance for the quadrature error, when the reference measure satisfies a stronger regularity condition. As a corollary, by taking a specific reference measure and using a construction similar to importance sampling, we obtain a general Monte Carlo method, which applies to any measure with continuously derivable density. Loosely speaking, our method can be interpreted as a stochastic counterpart to Gaussian quadrature, which at the price of some convergence rate, is easily generalizable to any dimension and has a more explicit error term.

MSC:

65C05 Monte Carlo methods
42C05 Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis
60F05 Central limit and other weak theorems

References:

[1] Ameur, Y., Hedenmalm, H. and Makarov, N. (2011). Fluctuations of eigenvalues of random normal matrices. Duke Math. J. 159 31-81. · Zbl 1225.15030 · doi:10.1215/00127094-1384782
[2] Ameur, Y., Hedenmalm, H. and Makarov, N. (2015). Random normal matrices and Ward identities. Ann. Probab. 43 1157-1201. · Zbl 1388.60020 · doi:10.1214/13-AOP885
[3] Bach, F., Lacoste-Julien, S. and Obozinski, G. (2012). On the equivalence between herding and conditional gradient algorithms. In Proceedings of the International Conference on Machine Learning (ICML).
[4] Belloni, A. and Chernozhukov, V. (2009). On the computational complexity of MCMC-based estimators in large samples. Ann. Statist. 37 2011-2055. · Zbl 1175.65015 · doi:10.1214/08-AOS634
[5] Berman, R. J. (2009). Bergman kernels for weighted polynomials and weighted equilibrium measures of \(\mathbb{C}^n \). Indiana Univ. Math. J. 58 1921-1946. · Zbl 1175.32002
[6] Berman, R. J. (2009). Bergman kernels and equilibrium measures for line bundles over projective manifolds. Amer. J. Math. 131 1485-1524. · Zbl 1191.32008 · doi:10.1353/ajm.0.0077
[7] Berman, R. J. (2012). Sharp asymptotics for Toeplitz determinants and convergence towards the Gaussian free field on Riemann surfaces. Int. Math. Res. Not. IMRN 22 5031-5062. · Zbl 1262.60043 · doi:10.1093/imrn/rnr229
[8] Berman, R. J. (2014). Determinantal point processes and fermions on complex manifolds: Large deviations and bosonization. Comm. Math. Phys. 327 1-47. · Zbl 1337.60093 · doi:10.1007/s00220-014-1891-6
[9] Berman, R. J. (2018). Kähler-Einstein metrics, canonical random point processes and birational geometry. In Algebraic Geometry: Salt Lake City 2015. Proc. Sympos. Pure Math. 97 29-73. Amer. Math. Soc., Providence, RI. · Zbl 1446.32017
[10] Bogaert, I. (2014). Iteration-free computation of Gauss-Legendre quadrature nodes and weights. SIAM J. Sci. Comput. 36 A1008-A1026. · Zbl 1297.65025 · doi:10.1137/140954969
[11] Brass, H. and Petras, K. (2011). Quadrature Theory: The Theory of Numerical Integration on a Compact Interval. Mathematical Surveys and Monographs 178. Amer. Math. Soc., Providence, RI. · Zbl 1231.65059
[12] Breuer, J. and Duits, M. (2016). Universality of mesoscopic fluctuations for orthogonal polynomial ensembles. Comm. Math. Phys. 342 491-531. · Zbl 1360.42014 · doi:10.1007/s00220-015-2514-6
[13] Breuer, J. and Duits, M. (2017). Central limit theorems for biorthogonal ensembles and asymptotics of recurrence coefficients. J. Amer. Math. Soc. 30 27-66. · Zbl 1351.15022 · doi:10.1090/jams/854
[14] Briol, F.-X., Oates, C., Girolami, M. and Osborne, M. A. (2015). Frank-Wolfe Bayesian quadrature: Probabilistic integration with theoretical guarantees. In Advances in Neural Information Processing Systems (NIPS) 1162-1170.
[15] Briol, F.-X., Oates, C. J., Girolami, M., Osborne, M. A. and Sejdinovic, D. (2019). Probabilistic integration: A role in statistical computation? Statist. Sci. 34 1-22. · Zbl 1420.62135 · doi:10.1214/18-STS660
[16] Chen, Y., Welling, M. and Smola, A. (2010). Super-samples from kernel herding. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI).
[17] Daley, D. J. and Vere-Jones, D. (1988). An Introduction to the Theory of Point Processes. Springer Series in Statistics. Springer, New York. · Zbl 0657.60069
[18] Davis, P. J. and Rabinowitz, P. (1984). Methods of Numerical Integration, 2nd ed. Computer Science and Applied Mathematics. Academic Press, Orlando, FL. · Zbl 0537.65020
[19] Delyon, B. and Portier, F. (2016). Integral approximation by kernel smoothing. Bernoulli 22 2177-2208. · Zbl 1345.60013 · doi:10.3150/15-BEJ725
[20] Diaconis, P. and Evans, S. N. (2001). Linear functionals of eigenvalues of random matrices. Trans. Amer. Math. Soc. 353 2615-2633. · Zbl 1008.15013 · doi:10.1090/S0002-9947-01-02800-8
[21] Dick, J., Kuo, F. Y. and Sloan, I. H. (2013). High-dimensional integration: The quasi-Monte Carlo way. Acta Numer. 22 133-288. · Zbl 1296.65004 · doi:10.1017/S0962492913000044
[22] Dick, J. and Pillichshammer, F. (2010). Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge Univ. Press, Cambridge. · Zbl 1282.65012
[23] Douc, R., Moulines, E. and Stoffer, D. S. (2014). Nonlinear Time Series: Theory, Methods, and Applications with R Examples. Chapman & Hall/CRC Texts in Statistical Science Series. CRC Press/CRC, Boca Raton, FL. · Zbl 1306.62026
[24] Fink, M., Niederer, S. A., Cherry, E. M., Fenton, F. H., Koivumäki, J. T., Seemann, G., Thul, R., Zhang, H., Sachse, F. B. et al. (2011). Cardiac cell modelling: Observations from the heart of the cardiac physiome project. Prog. Biophys. Mol. Biol. 104 2-21.
[25] Gauss, C. F. (1815). Methodus Nova Integralium Valores per Approximationem Inveniendi. Heinrich Dietrich, Göttingen.
[26] Gautier, G., Bardenet, R. and Valko, M. (2018). DPPy: Sampling determinantal point processes with Python. Preprint. Available at arXiv:1809.07258.
[27] Gautschi, W. (2004). Orthogonal Polynomials: Computation and Approximation. Numerical Mathematics and Scientific Computation. Oxford Univ. Press, New York. · Zbl 1130.42300
[28] Gautschi, W. (2009/10). How sharp is Bernstein’s inequality for Jacobi polynomials? Electron. Trans. Numer. Anal. 36 1-8. · Zbl 1189.33016
[29] Gautschi, W. and Varga, R. S. (1983). Error bounds for Gaussian quadrature of analytic functions. SIAM J. Numer. Anal. 20 1170-1186. · Zbl 0545.41040 · doi:10.1137/0720087
[30] Glaser, A., Liu, X. and Rokhlin, V. (2007). A fast algorithm for the calculation of the roots of special functions. SIAM J. Sci. Comput. 29 1420-1438. · Zbl 1145.65015 · doi:10.1137/06067016X
[31] Glynn, P. W. and Szechtman, R. (2002). Some new perspectives on the method of control variates. In Monte Carlo and Quasi-Monte Carlo Methods, 2000 (Hong Kong) 27-49. Springer, Berlin. · Zbl 1002.65016
[32] Golub, G. H. and Van Loan, C. F. (2013). Matrix Computations, 4th ed. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins Univ. Press, Baltimore, MD. · Zbl 1268.65037
[33] Hale, N. and Townsend, A. (2013). Fast and accurate computation of Gauss-Legendre and Gauss-Jacobi quadrature nodes and weights. SIAM J. Sci. Comput. 35 A652-A674. · Zbl 1270.65017 · doi:10.1137/120889873
[34] Hardy, A. (2015). Average characteristic polynomials of determinantal point processes. Ann. Inst. Henri Poincaré Probab. Stat. 51 283-303. · Zbl 1332.60023 · doi:10.1214/13-AIHP572
[35] Hough, J. B., Krishnapur, M., Peres, Y. and Virág, B. (2006). Determinantal processes and independence. Probab. Surv. 3 206-229. · Zbl 1189.60101 · doi:10.1214/154957806000000078
[36] Huszár, F. and Duvenaud, D. (2012). Optimally-weighted herding is Bayesian quadrature. In Uncertainty in Artificial Intelligence (UAI).
[37] Johansson, K. (1997). On random matrices from the compact classical groups. Ann. of Math. (2) 145 519-545. · Zbl 0883.60010 · doi:10.2307/2951843
[38] Johansson, K. (1998). On fluctuations of eigenvalues of random Hermitian matrices. Duke Math. J. 91 151-204. · Zbl 1039.82504 · doi:10.1215/S0012-7094-98-09108-6
[39] Johansson, K. (2006). Random matrices and determinantal processes. In Mathematical Statistical Physics 1-55. Elsevier, Amsterdam. · Zbl 1411.60144
[40] Johansson, K. and Lambert, G. (2018). Gaussian and non-Gaussian fluctuations for mesoscopic linear statistics in determinantal processes. Ann. Probab. 46 1201-1278. · Zbl 1429.60011 · doi:10.1214/17-AOP1178
[41] Kallenberg, O. (1997). Foundations of Modern Probability. Probability and Its Applications (New York). Springer, New York. · Zbl 0892.60001
[42] Killip, R. and Nenciu, I. (2004). Matrix models for circular ensembles. Int. Math. Res. Not. 50 2665-2701. · Zbl 1255.82004 · doi:10.1155/S1073792804141597
[43] König, W. (2005). Orthogonal polynomial ensembles in probability theory. Probab. Surv. 2 385-447. · Zbl 1189.60024
[44] Kriecherbauer, T. and Shcherbina, M. (2010). Fluctuations of eigenvalues of matrix models and their applications. Preprint. Available at arXiv:1003.6121.
[45] Kuijlaars, A. B. J., McLaughlin, K. T.-R., Van Assche, W. and Vanlessen, M. (2004). The Riemann-Hilbert approach to strong asymptotics for orthogonal polynomials on \([-1,1]\). Adv. Math. 188 337-398. · Zbl 1082.42017 · doi:10.1016/j.aim.2003.08.015
[46] Kulesza, A. and Taskar, B. (2012). Determinantal Point Processes for Machine Learning. Foundations and Trends in Machine Learning. · Zbl 1278.68240 · doi:10.1561/2200000044
[47] Lambert, G. (2015). CLT for biorthogonal ensembles and related combinatorial identities. Preprint. Available at arXiv:1511.06121.
[48] Lambert, G. (2018). Mesoscopic fluctuations for unitary invariant ensembles. Electron. J. Probab. 23 Paper No. 7. · Zbl 1387.60012
[49] Lavancier, F., Møller, J. and Rubak, E. (2015). Determinantal point process models and statistical inference. J. R. Stat. Soc. Ser. B. Stat. Methodol. 77 853-877. · Zbl 1414.62403 · doi:10.1111/rssb.12096
[50] Liu, Q. and Lee, J. D. (2017). Black-box importance sampling. Proc. Mach. Learn. Res. 54 952-961.
[51] Lyons, R. (2003). Determinantal probability measures. Publ. Math. Inst. Hautes Études Sci. 98 167-212. · Zbl 1055.60003 · doi:10.1007/s10240-003-0016-0
[52] Lyons, R. and Peres, Y. (2016). Probability on Trees and Networks. Cambridge Series in Statistical and Probabilistic Mathematics 42. Cambridge Univ. Press, New York.
[53] Macchi, O. (1975). The coincidence approach to stochastic point processes. Adv. in Appl. Probab. 7 83-122. · Zbl 0366.60081 · doi:10.2307/1425855
[54] Møller, J., Nielsen, M., Porcu, E. and Rubak, E. (2015). Determinantal point process models on the sphere. Research Report 13, Centre for Stochastic Geometry and Advanced Bioimaging. · Zbl 1429.60050
[55] O’Hagan, A. (1991). Bayes-Hermite quadrature. J. Statist. Plann. Inference 29 245-260. · Zbl 0829.65024 · doi:10.1016/0378-3758(91)90002-V
[56] Oates, C. and Girolami, M. (2016). Control functionals for quasi-Monte Carlo integration. In Proceeddings of the International Conference on Artificial Intelligence and Statistics. · Zbl 1411.62088 · doi:10.1111/rssb.12185
[57] Oates, C. J., Girolami, M. and Chopin, N. (2017). Control functionals for Monte Carlo integration. J. R. Stat. Soc. Ser. B. Stat. Methodol. 79 695-718. · Zbl 1411.62088 · doi:10.1111/rssb.12185
[58] Olver, S., Nadakuditi, R. R. and Trogdon, T. (2015). Sampling unitary ensembles. Random Matrices Theory Appl. 4 1550002. · Zbl 1333.65010 · doi:10.1142/S2010326315500021
[59] Owen, A. B. (1997). Scrambled net variance for integrals of smooth functions. Ann. Statist. 25 1541-1562. · Zbl 0886.65018 · doi:10.1214/aos/1031594731
[60] Owen, A. B. (2008). Local antithetic sampling with scrambled nets. Ann. Statist. 36 2319-2343. · Zbl 1157.65006 · doi:10.1214/07-AOS548
[61] Pastur, L. (2006). Limiting laws of linear eigenvalue statistics for Hermitian matrix models. J. Math. Phys. 47 103303. · Zbl 1112.82022 · doi:10.1063/1.2356796
[62] Peet, M. M. (2009). Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions. IEEE Trans. Automat. Control 54 979-987. · Zbl 1367.93442 · doi:10.1109/TAC.2009.2017116
[63] Popescu, I. (2009). General tridiagonal random matrix models, limiting distributions and fluctuations. Probab. Theory Related Fields 144 179-220. · Zbl 1165.82012 · doi:10.1007/s00440-008-0145-y
[64] Purves, D., Scharlemann, J. P. W., Harfoot, M., Newbold, T., Tittensor, D. P., Hutton, J. and Emmott, S. (2013). Ecosystems: Time to model all life on Earth. Nature 493 295-297.
[65] Rasmussen, C. E. and Williams, C. K. I. (2006). Gaussian Processes for Machine Learning. Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA. · Zbl 1177.68165
[66] Rider, B. and Virág, B. (2007). The noise in the circular law and the Gaussian free field. Int. Math. Res. Not. IMRN 2 Art. ID rnm006. · Zbl 1130.60030
[67] Robert, C. P. and Casella, G. (2004). Monte Carlo Statistical Methods, 2nd ed. Springer Texts in Statistics. Springer, New York. · Zbl 1096.62003
[68] Saff, E. B. and Totik, V. (1997). Logarithmic Potentials with External Fields. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 316. Springer, Berlin. · Zbl 0881.31001
[69] Scardicchio, A., Zachary, C. E. and Torquato, S. (2009). Statistical properties of determinantal point processes in high-dimensional Euclidean spaces. Phys. Rev. E (3) 79 041108.
[70] Schervish, M. J. (1995). Theory of Statistics. Springer Series in Statistics. Springer, New York. · Zbl 0834.62002
[71] Shcherbina, M. (2013). Fluctuations of linear eigenvalue statistics of \(\beta\) matrix models in the multi-cut regime. J. Stat. Phys. 151 1004-1034. · Zbl 1273.15042 · doi:10.1007/s10955-013-0740-x
[72] Simon, B. (2011). Szegő’s Theorem and Its Descendants: Spectral Theory for \(L^2\) Perturbations of Orthogonal Polynomials. M. B. Porter Lectures. Princeton Univ. Press, Princeton, NJ. · Zbl 1230.33001
[73] Soshnikov, A. (2000). Determinantal random point fields. Russian Math. Surveys 55 923-975. · Zbl 0991.60038 · doi:10.1070/RM2000v055n05ABEH000321
[74] Soshnikov, A. (2002). Gaussian limit for determinantal random point fields. Ann. Probab. 30 171-187. · Zbl 1033.60063 · doi:10.1214/aop/1020107764
[75] Stahl, H. and Totik, V. (1992). General Orthogonal Polynomials. Encyclopedia of Mathematics and Its Applications 43. Cambridge Univ. Press, Cambridge.
[76] Szegő, G. (1975). Orthogonal Polynomials, 4th ed. Colloquium Publications, XXIII. Amer. Math. Soc., Providence, RI. · Zbl 0305.42011
[77] Torquato, S., Scardicchio, A. and Zachary, C. E. (2008). Point processes in arbitrary dimension from fermionic gases, random matrix theory, and number theory. J. Stat. Mech. Theory Exp. 11 P11019. · Zbl 1456.82079 · doi:10.1088/1742-5468/2008/11/P11019
[78] Trotta, R. (2008). Bayes in the sky: Bayesian inference and model selection in cosmology. Contemp. Phys. 49 71-104.
[79] Xiang, S. (2016). An improved error bound on Gauss quadrature. Appl. Math. Lett. 58 42-48. · Zbl 1336.41012 · doi:10.1016/j.aml.2016.01.015
[80] Xiang, S. and Bornemann, F. (2012). On the convergence rates of Gauss and Clenshaw-Curtis quadrature for functions of limited regularity. SIAM J. Numer. Anal. 50 2581-2587. · Zbl 1259.65059 · doi:10.1137/120869845
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.