Recovery of Sobolev functions restricted to iid sampling

Krieg, David; Novak, Erich; Sonnleitner, Mathias

doi:10.1090/mcom/3763

Recovery of Sobolev functions restricted to iid sampling
HTML articles powered by AMS MathViewer

by David Krieg, Erich Novak and Mathias Sonnleitner;

Math. Comp. 91 (2022), 2715-2738

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

Published electronically: August 9, 2022

HTML | PDF

Abstract:

We study $L_q$-approximation and integration for functions from the Sobolev space $W^s_p(\Omega )$ and compare optimal randomized (Monte Carlo) algorithms with algorithms that can only use identically distributed (iid) sample points, uniformly distributed on the domain. The main result is that we obtain the same optimal rate of convergence if we restrict to iid sampling, a common assumption in learning and uncertainty quantification. The only exception is when $p=q=\infty$, where a logarithmic loss cannot be avoided.

References

Nikolai Sergeevich Bakhvalov, On the approximate calculation of multiple integrals [translation of 0115275], J. Complexity 31 (2015), no. 4, 502–516. MR 3348079, DOI 10.1016/j.jco.2014.12.003
N. S. Bakhvalov, On the rate of convergence of indeterministic integration processes within the functional classes $W^{(l)}_p$, Theor. Probab. Appl. 7 (1962), 227.
J. Berner, Ph. Grohs, G. Kutyniok, and Ph. Petersen, The modern mathematics of deep learning, Theory of Deep Learning, Cambridge University Press, Preprint, arXiv:2105:04026, 2022.
Philippe G. Ciarlet, The finite element method for elliptic problems, Studies in Mathematics and its Applications, Vol. 4, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. MR 520174
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
M. Dolbeault, D. Krieg, and M. Ullrich, A sharp upper bound for sampling numbers in $L_2$, Preprint, arXiv:2204.12621, 2022.
Todd Dupont and Ridgway Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comp. 34 (1980), no. 150, 441–463. MR 559195, DOI 10.1090/S0025-5718-1980-0559195-7
Dinh Dũng, Vladimir Temlyakov, and Tino Ullrich, Hyperbolic cross approximation, Advanced Courses in Mathematics. CRM Barcelona, Birkhäuser/Springer, Cham, 2018. Edited and with a foreword by Sergey Tikhonov. MR 3887571, DOI 10.1007/978-3-319-92240-9
Martin Ehler, Manuel Gräf, and Chris. J. Oates, Optimal Monte Carlo integration on closed manifolds, Stat. Comput. 29 (2019), no. 6, 1203–1214. MR 4026666, DOI 10.1007/s11222-019-09894-w
Michael B. Giles, Multilevel Monte Carlo methods, Acta Numer. 24 (2015), 259–328. MR 3349310, DOI 10.1017/S096249291500001X
Stefan Heinrich, Random approximation in numerical analysis, Functional analysis (Essen, 1991) Lecture Notes in Pure and Appl. Math., vol. 150, Dekker, New York, 1994, pp. 123–171. MR 1241675
Stefan Heinrich, Randomized approximation of Sobolev embeddings, Monte Carlo and quasi-Monte Carlo methods 2006, Springer, Berlin, 2008, pp. 445–459. MR 2479239, DOI 10.1007/978-3-540-74496-2_{2}6
Stefan Heinrich, Randomized approximation of Sobolev embeddings. II, J. Complexity 25 (2009), no. 5, 455–472. MR 2555511, DOI 10.1016/j.jco.2009.04.003
Stefan Heinrich, Randomized approximation of Sobolev embeddings. III, J. Complexity 25 (2009), no. 5, 473–507. MR 2555512, DOI 10.1016/j.jco.2009.04.002
Aicke Hinrichs, David Krieg, Erich Novak, Joscha Prochno, and Mario Ullrich, Random sections of ellipsoids and the power of random information, Trans. Amer. Math. Soc. 374 (2021), no. 12, 8691–8713. MR 4337926, DOI 10.1090/tran/8502
A. Hinrichs, D. Krieg, E. Novak, J. Prochno, and M. Ullrich, On the power of random information, Multivariate Algorithms and Information-Based Complexity, De Gruyter, Berlin/Boston, 2020, pp. 43–54.
Mark Huber and Bo Jones, Faster estimates of the mean of bounded random variables, Math. Comput. Simulation 161 (2019), 93–101. MR 3926801, DOI 10.1016/j.matcom.2019.01.011
David Krieg, Optimal Monte Carlo methods for $L^2$-approximation, Constr. Approx. 49 (2019), no. 2, 385–403. MR 3922250, DOI 10.1007/s00365-018-9428-4
David Krieg and Erich Novak, A universal algorithm for multivariate integration, Found. Comput. Math. 17 (2017), no. 4, 895–916. MR 3682216, DOI 10.1007/s10208-016-9307-y
D. Krieg and M. Sonnleitner, Random points are optimal for the approximation of Sobolev functions, Preprint, arXiv:2009.11275, 2020.
D. Krieg and M. Sonnleitner, Function recovery on manifolds using scattered data, Preprint, arXiv:2109.04106, 2021.
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
David Krieg and Mario Ullrich, Function values are enough for $L_2$-approximation: Part II, J. Complexity 66 (2021), Paper No. 101569, 14. MR 4292366, DOI 10.1016/j.jco.2021.101569
Robert J. Kunsch, Erich Novak, and Daniel Rudolf, Solvable integration problems and optimal sample size selection, J. Complexity 53 (2019), 40–67. MR 3953086, DOI 10.1016/j.jco.2018.10.007
Robert J. Kunsch and Daniel Rudolf, Optimal confidence for Monte Carlo integration of smooth functions, Adv. Comput. Math. 45 (2019), no. 5-6, 3095–3122. MR 4047026, DOI 10.1007/s10444-019-09728-3
Wanting Lu and Heping Wang, On the power of standard information for tractability for $L_2$-approximation in the average case setting, J. Complexity 70 (2022), Paper No. 101618, 22. MR 4388510, DOI 10.1016/j.jco.2021.101618
Gábor Lugosi and Shahar Mendelson, Mean estimation and regression under heavy-tailed distributions: a survey, Found. Comput. Math. 19 (2019), no. 5, 1145–1190. MR 4017683, DOI 10.1007/s10208-019-09427-x
Peter Mathé, Random approximation of Sobolev embeddings, J. Complexity 7 (1991), no. 3, 261–281. MR 1128021, DOI 10.1016/0885-064X(91)90036-W
Vladimir Maz’ya, Sobolev spaces with applications to elliptic partial differential equations, Second, revised and augmented edition, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 342, Springer, Heidelberg, 2011. MR 2777530, DOI 10.1007/978-3-642-15564-2
Giovanni Migliorati and Fabio Nobile, Stable high-order randomized cubature formulae in arbitrary dimension, J. Approx. Theory 275 (2022), Paper No. 105706, 30. MR 4371125, DOI 10.1016/j.jat.2022.105706
Nicolas Nagel, Martin Schäfer, and Tino Ullrich, A new upper bound for sampling numbers, Found. Comput. Math. 22 (2022), no. 2, 445–468. MR 4407748, DOI 10.1007/s10208-021-09504-0
Francis J. Narcowich, Joseph D. Ward, and Holger Wendland, Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting, Math. Comp. 74 (2005), no. 250, 743–763. MR 2114646, DOI 10.1090/S0025-5718-04-01708-9
Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255, DOI 10.1007/BFb0079792
Erich Novak, Algorithms and complexity for functions on general domains, J. Complexity 61 (2020), 101458, 11. MR 4149210, DOI 10.1016/j.jco.2020.101458
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume III: Standard information for operators, EMS Tracts in Mathematics, vol. 18, European Mathematical Society (EMS), Zürich, 2012. MR 2987170, DOI 10.4171/116
Erich Novak and Hans Triebel, Function spaces in Lipschitz domains and optimal rates of convergence for sampling, Constr. Approx. 23 (2006), no. 3, 325–350. MR 2201470, DOI 10.1007/s00365-005-0612-y
A. Reznikov and E. B. Saff, The covering radius of randomly distributed points on a manifold, Int. Math. Res. Not. IMRN 19 (2016), 6065–6094. MR 3567267, DOI 10.1093/imrn/rnv342
Sh. Shalev-Shwartz and Sh. Ben-David, Understanding Machine Learning, Cambridge University Press, 2014.
Elias M. Stein, Singular integrals and differentiability properties of functions, Princeton Mathematical Series, No. 30, Princeton University Press, Princeton, NJ, 1970. MR 290095
Ingo Steinwart and Andreas Christmann, Support vector machines, Information Science and Statistics, Springer, New York, 2008. MR 2450103
V. Temlyakov, On optimal recovery in $L_2$, J. Complexity 65 (2021), Paper No. 101545, 11. MR 4264807, DOI 10.1016/j.jco.2020.101545
Mario Ullrich, A Monte Carlo method for integration of multivariate smooth functions, SIAM J. Numer. Anal. 55 (2017), no. 3, 1188–1200. MR 3648970, DOI 10.1137/16M1075557
Mario Ullrich, On the worst-case error of least squares algorithms for $L_2$-approximation with high probability, J. Complexity 60 (2020), 101484, 6. MR 4123742, DOI 10.1016/j.jco.2020.101484
Holger Wendland, Local polynomial reproduction and moving least squares approximation, IMA J. Numer. Anal. 21 (2001), no. 1, 285–300. MR 1812276, DOI 10.1093/imanum/21.1.285
Holger Wendland, Scattered data approximation, Cambridge Monographs on Applied and Computational Mathematics, vol. 17, Cambridge University Press, Cambridge, 2005. MR 2131724
Jiaxin Zhang, Modern Monte Carlo methods for efficient uncertainty quantification and propagation: a survey, Wiley Interdiscip. Rev. Comput. Stat. 13 (2021), no. 5, Paper No. e1539, 23. MR 4311091, DOI 10.1002/wics.1539