{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T05:39:21Z","timestamp":1776836361285,"version":"3.51.2"},"reference-count":46,"publisher":"American Mathematical Society (AMS)","issue":"338","license":[{"start":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T00:00:00Z","timestamp":1691539200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["F5513-N26"],"award-info":[{"award-number":["F5513-N26"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["F5513-N26"],"award-info":[{"award-number":["F5513-N26"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["F5513-N26"],"award-info":[{"award-number":["F5513-N26"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["F5513-N26"],"award-info":[{"award-number":["F5513-N26"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We study\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper L Subscript q\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>L<\/mml:mi>\n                            <mml:mi>q<\/mml:mi>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">L_q<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -approximation and integration for functions from the Sobolev space\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper W Subscript p Superscript s Baseline left-parenthesis normal upper Omega right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:msubsup>\n                              <mml:mi>W<\/mml:mi>\n                              <mml:mi>p<\/mml:mi>\n                              <mml:mi>s<\/mml:mi>\n                            <\/mml:msubsup>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi mathvariant=\"normal\">\n                              \u03a9\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">W^s_p(\\Omega )<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    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\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"p equals q equals normal infinity\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>p<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mi>q<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mi mathvariant=\"normal\">\n                              \u221e\n                              \n                            <\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">p=q=\\infty<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , where a logarithmic loss cannot be avoided.\n                  <\/p>","DOI":"10.1090\/mcom\/3763","type":"journal-article","created":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T09:21:28Z","timestamp":1654075288000},"page":"2715-2738","source":"Crossref","is-referenced-by-count":6,"title":["Recovery of Sobolev functions restricted to iid sampling"],"prefix":"10.1090","volume":"91","author":[{"given":"David","family":"Krieg","sequence":"first","affiliation":[]},{"given":"Erich","family":"Novak","sequence":"additional","affiliation":[]},{"given":"Mathias","family":"Sonnleitner","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2022,8,9]]},"reference":[{"issue":"4","key":"1","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1016\/j.jco.2014.12.003","article-title":"On the approximate calculation of multiple integrals [translation of 0115275]","volume":"31","author":"Bakhvalov, Nikolai Sergeevich","year":"2015","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"2","unstructured":"N. S. Bakhvalov, On the rate of convergence of indeterministic integration processes within the functional classes \ud835\udc4a^{(\ud835\udc59)}_{\ud835\udc5d}, Theor. Probab. Appl. 7 (1962), 227."},{"key":"3","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1017\/9781009025096.002"},{"key":"4","series-title":"Studies in Mathematics and its Applications, Vol. 4","isbn-type":"print","volume-title":"The finite element method for elliptic problems","author":"Ciarlet, Philippe G.","year":"1978","ISBN":"https:\/\/id.crossref.org\/isbn\/0444850287"},{"key":"5","doi-asserted-by":"publisher","first-page":"Paper No. 101602, 12","DOI":"10.1016\/j.jco.2021.101602","article-title":"Optimal pointwise sampling for \ud835\udc3f\u00b2 approximation","volume":"68","author":"Dolbeault, Matthieu","year":"2022","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"6","doi-asserted-by":"crossref","unstructured":"M. Dolbeault, D. Krieg, and M. Ullrich, A sharp upper bound for sampling numbers in \ud835\udc3f\u2082, Preprint,  arXiv:2204.12621, 2022.","DOI":"10.2139\/ssrn.4132094"},{"issue":"150","key":"7","doi-asserted-by":"publisher","first-page":"441","DOI":"10.2307\/2006095","article-title":"Polynomial approximation of functions in Sobolev spaces","volume":"34","author":"Dupont, Todd","year":"1980","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"8","series-title":"Advanced Courses in Mathematics. CRM Barcelona","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-92240-9","volume-title":"Hyperbolic cross approximation","author":"D\u0169ng, Dinh","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319922393"},{"issue":"6","key":"9","doi-asserted-by":"publisher","first-page":"1203","DOI":"10.1007\/s11222-019-09894-w","article-title":"Optimal Monte Carlo integration on closed manifolds","volume":"29","author":"Ehler, Martin","year":"2019","journal-title":"Stat. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0960-3174","issn-type":"print"},{"key":"10","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1017\/S096249291500001X","article-title":"Multilevel Monte Carlo methods","volume":"24","author":"Giles, Michael B.","year":"2015","journal-title":"Acta Numer.","ISSN":"https:\/\/id.crossref.org\/issn\/0962-4929","issn-type":"print"},{"key":"11","isbn-type":"print","first-page":"123","article-title":"Random approximation in numerical analysis","author":"Heinrich, Stefan","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0824790669"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/978-3-540-74496-2_26","article-title":"Randomized approximation of Sobolev embeddings","author":"Heinrich, Stefan","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540744955"},{"issue":"5","key":"13","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/j.jco.2009.04.003","article-title":"Randomized approximation of Sobolev embeddings. II","volume":"25","author":"Heinrich, Stefan","year":"2009","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"5","key":"14","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/j.jco.2009.04.002","article-title":"Randomized approximation of Sobolev embeddings. III","volume":"25","author":"Heinrich, Stefan","year":"2009","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"12","key":"15","doi-asserted-by":"publisher","first-page":"8691","DOI":"10.1090\/tran\/8502","article-title":"Random sections of ellipsoids and the power of random information","volume":"374","author":"Hinrichs, Aicke","year":"2021","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"key":"16","doi-asserted-by":"crossref","unstructured":"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\u201354.","DOI":"10.1515\/9783110635461-004"},{"key":"17","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.matcom.2019.01.011","article-title":"Faster estimates of the mean of bounded random variables","volume":"161","author":"Huber, Mark","year":"2019","journal-title":"Math. Comput. Simulation","ISSN":"https:\/\/id.crossref.org\/issn\/0378-4754","issn-type":"print"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s00365-018-9428-4","article-title":"Optimal Monte Carlo methods for \ud835\udc3f\u00b2-approximation","volume":"49","author":"Krieg, David","year":"2019","journal-title":"Constr. Approx.","ISSN":"https:\/\/id.crossref.org\/issn\/0176-4276","issn-type":"print"},{"issue":"4","key":"19","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1007\/s10208-016-9307-y","article-title":"A universal algorithm for multivariate integration","volume":"17","author":"Krieg, David","year":"2017","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"20","unstructured":"D. Krieg and M. Sonnleitner, Random points are optimal for the approximation of Sobolev functions, Preprint,  arXiv:2009.11275, 2020."},{"key":"21","unstructured":"D. Krieg and M. Sonnleitner, Function recovery on manifolds using scattered data, Preprint,  arXiv:2109.04106, 2021."},{"issue":"4","key":"22","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1007\/s10208-020-09481-w","article-title":"Function values are enough for \ud835\udc3f\u2082-approximation","volume":"21","author":"Krieg, David","year":"2021","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"23","doi-asserted-by":"publisher","first-page":"Paper No. 101569, 14","DOI":"10.1016\/j.jco.2021.101569","article-title":"Function values are enough for \ud835\udc3f\u2082-approximation: Part II","volume":"66","author":"Krieg, David","year":"2021","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"24","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.jco.2018.10.007","article-title":"Solvable integration problems and optimal sample size selection","volume":"53","author":"Kunsch, Robert J.","year":"2019","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"5-6","key":"25","doi-asserted-by":"publisher","first-page":"3095","DOI":"10.1007\/s10444-019-09728-3","article-title":"Optimal confidence for Monte Carlo integration of smooth functions","volume":"45","author":"Kunsch, Robert J.","year":"2019","journal-title":"Adv. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1019-7168","issn-type":"print"},{"key":"26","doi-asserted-by":"publisher","first-page":"Paper No. 101618, 22","DOI":"10.1016\/j.jco.2021.101618","article-title":"On the power of standard information for tractability for \ud835\udc3f\u2082-approximation in the average case setting","volume":"70","author":"Lu, Wanting","year":"2022","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"5","key":"27","doi-asserted-by":"publisher","first-page":"1145","DOI":"10.1007\/s10208-019-09427-x","article-title":"Mean estimation and regression under heavy-tailed distributions: a survey","volume":"19","author":"Lugosi, G\u00e1bor","year":"2019","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"3","key":"28","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0885-064X(91)90036-W","article-title":"Random approximation of Sobolev embeddings","volume":"7","author":"Math\u00e9, Peter","year":"1991","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"29","series-title":"Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15564-2","volume-title":"Sobolev spaces with applications to elliptic partial differential equations","volume":"342","author":"Maz\u2019ya, Vladimir","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642155635","edition":"2"},{"key":"30","doi-asserted-by":"publisher","first-page":"Paper No. 105706, 30","DOI":"10.1016\/j.jat.2022.105706","article-title":"Stable high-order randomized cubature formulae in arbitrary dimension","volume":"275","author":"Migliorati, Giovanni","year":"2022","journal-title":"J. Approx. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9045","issn-type":"print"},{"issue":"2","key":"31","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s10208-021-09504-0","article-title":"A new upper bound for sampling numbers","volume":"22","author":"Nagel, Nicolas","year":"2022","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"250","key":"32","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1090\/S0025-5718-04-01708-9","article-title":"Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting","volume":"74","author":"Narcowich, Francis J.","year":"2005","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"33","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0079792","volume-title":"Deterministic and stochastic error bounds in numerical analysis","volume":"1349","author":"Novak, Erich","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/3540503684"},{"key":"34","doi-asserted-by":"publisher","first-page":"101458","DOI":"10.1016\/j.jco.2020.101458","article-title":"Algorithms and complexity for functions on general domains","volume":"61","author":"Novak, Erich","year":"2020","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"35","series-title":"EMS Tracts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.4171\/116","volume-title":"Tractability of multivariate problems. Volume III: Standard information for operators","volume":"18","author":"Novak, Erich","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783037191163"},{"issue":"3","key":"36","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s00365-005-0612-y","article-title":"Function spaces in Lipschitz domains and optimal rates of convergence for sampling","volume":"23","author":"Novak, Erich","year":"2006","journal-title":"Constr. Approx.","ISSN":"https:\/\/id.crossref.org\/issn\/0176-4276","issn-type":"print"},{"issue":"19","key":"37","doi-asserted-by":"publisher","first-page":"6065","DOI":"10.1093\/imrn\/rnv342","article-title":"The covering radius of randomly distributed points on a manifold","author":"Reznikov, A.","year":"2016","journal-title":"Int. Math. Res. Not. IMRN","ISSN":"https:\/\/id.crossref.org\/issn\/1073-7928","issn-type":"print"},{"key":"38","doi-asserted-by":"crossref","unstructured":"Sh. Shalev-Shwartz and Sh. Ben-David, Understanding Machine Learning, Cambridge University Press, 2014.","DOI":"10.1017\/CBO9781107298019"},{"key":"39","series-title":"Princeton Mathematical Series, No. 30","volume-title":"Singular integrals and differentiability properties of functions","author":"Stein, Elias M.","year":"1970"},{"key":"40","series-title":"Information Science and Statistics","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-77242-4","volume-title":"Support vector machines","author":"Steinwart, Ingo","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387772417"},{"key":"41","doi-asserted-by":"publisher","first-page":"Paper No. 101545, 11","DOI":"10.1016\/j.jco.2020.101545","article-title":"On optimal recovery in \ud835\udc3f\u2082","volume":"65","author":"Temlyakov, V.","year":"2021","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"3","key":"42","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1137\/16M1075557","article-title":"A Monte Carlo method for integration of multivariate smooth functions","volume":"55","author":"Ullrich, Mario","year":"2017","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"43","doi-asserted-by":"publisher","first-page":"101484","DOI":"10.1016\/j.jco.2020.101484","article-title":"On the worst-case error of least squares algorithms for \ud835\udc3f\u2082-approximation with high probability","volume":"60","author":"Ullrich, Mario","year":"2020","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"44","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1093\/imanum\/21.1.285","article-title":"Local polynomial reproduction and moving least squares approximation","volume":"21","author":"Wendland, Holger","year":"2001","journal-title":"IMA J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0272-4979","issn-type":"print"},{"key":"45","series-title":"Cambridge Monographs on Applied and Computational Mathematics","isbn-type":"print","volume-title":"Scattered data approximation","volume":"17","author":"Wendland, Holger","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521843355"},{"issue":"5","key":"46","doi-asserted-by":"publisher","first-page":"Paper No. e1539, 23","DOI":"10.1002\/wics.1539","article-title":"Modern Monte Carlo methods for efficient uncertainty quantification and propagation: a survey","volume":"13","author":"Zhang, Jiaxin","year":"2021","journal-title":"Wiley Interdiscip. Rev. Comput. Stat.","ISSN":"https:\/\/id.crossref.org\/issn\/1939-5108","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-338\/S0025-5718-2022-03763-7\/mcom3763_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-338\/S0025-5718-2022-03763-7\/S0025-5718-2022-03763-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:42:22Z","timestamp":1776832942000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-338\/S0025-5718-2022-03763-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,9]]},"references-count":46,"journal-issue":{"issue":"338","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["S0025-5718-2022-03763-7"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3763","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2022,8,9]]}}}