{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T02:20:55Z","timestamp":1785550855816,"version":"3.56.0"},"reference-count":322,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T00:00:00Z","timestamp":1781827200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Numerica"],"published-print":{"date-parts":[[2026,7]]},"abstract":"<jats:p>We consider the approximation or recovery of functions based on a finite number of function evaluations. This is a well-studied problem in optimal recovery, machine learning and numerical analysis in general, but many fundamental insights were obtained only recently. We discuss different aspects of the information-theoretic limit that appears because of the limited data available, as well as algorithms and sampling strategies that come as close to it as possible.<\/jats:p>\n                  <jats:p>We also discuss (optimal) sampling in a broader sense, allowing other types of measurements that may be nonlinear, adaptive and random, and present several relations between the different settings in the spirit of information-based complexity. We hope that this article will provide both a basic introduction to the subject and a contemporary summary of the current state of research.<\/jats:p>","DOI":"10.1017\/s0962492925100287","type":"journal-article","created":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:58:58Z","timestamp":1781855938000},"page":"273-457","source":"Crossref","is-referenced-by-count":2,"title":["Approximation of functions: Optimal sampling and complexity"],"prefix":"10.1017","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8180-8906","authenticated-orcid":false,"given":"David","family":"Krieg","sequence":"first","affiliation":[{"name":"University of Passau"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1120-8467","authenticated-orcid":false,"given":"Mario","family":"Ullrich","sequence":"additional","affiliation":[{"name":"Johannes Kepler University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2026,6,19]]},"reference":[{"key":"S0962492925100287_r15","first-page":"3","article-title":"On the approximate calculation of multiple integrals","volume":"1959","author":"Bakhvalov","year":"1959","journal-title":"Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him."},{"key":"S0962492925100287_r128","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19841190109"},{"key":"S0962492925100287_r299","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2020.101484"},{"key":"S0962492925100287_r278","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-012-9153-3"},{"key":"S0962492925100287_r274","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2003.11.003"},{"key":"S0962492925100287_r237","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2008.11.002"},{"key":"S0962492925100287_r31","doi-asserted-by":"publisher","DOI":"10.1137\/23M1546671"},{"key":"S0962492925100287_r55","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2023.101819"},{"key":"S0962492925100287_r187","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2024.106056"},{"key":"S0962492925100287_r34","doi-asserted-by":"publisher","DOI":"10.4064\/fm-20-1-177-190"},{"key":"S0962492925100287_r132","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2022.101662"},{"key":"S0962492925100287_r92","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"S0962492925100287_r178","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2025.129873"},{"key":"S0962492925100287_r1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-025-09738-2"},{"key":"S0962492925100287_r54","first-page":"379","article-title":"Influential observations, high leverage points, and outliers in linear regression","volume":"1","author":"Chatterjee","year":"1986","journal-title":"Statist. Sci."},{"key":"S0962492925100287_r21","doi-asserted-by":"publisher","DOI":"10.1137\/130949117"},{"key":"S0962492925100287_r282","volume-title":"Orthogonal Polynomials","author":"Szeg\u0151","year":"1975"},{"key":"S0962492925100287_r231","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/17100"},{"key":"S0962492925100287_r304","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2013.04.003"},{"key":"S0962492925100287_r3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976885"},{"key":"S0962492925100287_r81","doi-asserted-by":"publisher","DOI":"10.1007\/s10092-017-0216-5"},{"key":"S0962492925100287_r286","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2018.02.001"},{"key":"S0962492925100287_r186","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2025.106216"},{"key":"S0962492925100287_r205","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09922-3"},{"key":"S0962492925100287_r26","volume-title":"Dynamic Programming","author":"Bellman","year":"1957"},{"key":"S0962492925100287_r203","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(91)90036-W"},{"key":"S0962492925100287_r221","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2010.08.001"},{"key":"S0962492925100287_r250","volume-title":"Eigenvalues and s-Numbers","volume":"13","author":"Pietsch","year":"1987"},{"key":"S0962492925100287_r137","doi-asserted-by":"publisher","DOI":"10.1002\/mana.201100128"},{"key":"S0962492925100287_r200","doi-asserted-by":"publisher","DOI":"10.1134\/S000143462560293X"},{"key":"S0962492925100287_r151","first-page":"334","article-title":"Diameters of some finite-dimensional sets and classes of smooth functions","volume":"41","author":"Kashin","year":"1977","journal-title":"Izv. Akad. Nauk SSSR Ser. Mat."},{"key":"S0962492925100287_r202","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(90)90011-2"},{"key":"S0962492925100287_r29","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(92)90259-Z"},{"key":"S0962492925100287_r2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1279459"},{"key":"S0962492925100287_r111","doi-asserted-by":"publisher","DOI":"10.1017\/S096249291500001X"},{"key":"S0962492925100287_r146","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2016.02.008"},{"key":"S0962492925100287_r33","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492924000011"},{"key":"S0962492925100287_r103","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2020.101503"},{"key":"S0962492925100287_r218","first-page":"1","article-title":"On regularized Radon\u2013Nikodym differentiation","volume":"25","author":"Nguyen","year":"2024","journal-title":"J. Mach. Learn. Res."},{"key":"S0962492925100287_r164","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-018-9428-4"},{"key":"S0962492925100287_r86","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492913000044"},{"key":"S0962492925100287_r207","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2009.08.006"},{"key":"S0962492925100287_r104","doi-asserted-by":"publisher","DOI":"10.1017\/9781009003933"},{"key":"S0962492925100287_r93","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-92240-9"},{"key":"S0962492925100287_r142","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2018.08.003"},{"key":"S0962492925100287_r276","first-page":"76","article-title":"Some geometric characteristics of the embedding map from \n\n\n${W}_p^a$\n\n\n\n to C","volume":"10","author":"Solomjak","year":"1967","journal-title":"Izv. Vys\u0161. U\u010debn. Zaved Mat."},{"key":"S0962492925100287_r136","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2008.02.003"},{"key":"S0962492925100287_r185","unstructured":"Kunsch, R. J. (2017), High-dimensional function approximation: Breaking the curse with Monte Carlo methods. PhD thesis. Available at arXiv:1704.08213."},{"key":"S0962492925100287_r264","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0063594"},{"key":"S0962492925100287_r224","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(92)90032-7"},{"key":"S0962492925100287_r119","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drm052"},{"key":"S0962492925100287_r176","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-026-10249-z"},{"key":"S0962492925100287_r12","volume-title":"Learning Theory from First Principles","author":"Bach","year":"2024"},{"key":"S0962492925100287_r113","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2010.07.001"},{"key":"S0962492925100287_r230","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-59762-6_5"},{"key":"S0962492925100287_r156","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1960-030-4"},{"key":"S0962492925100287_r108","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771685"},{"key":"S0962492925100287_r64","doi-asserted-by":"publisher","DOI":"10.5802\/smai-jcm.24"},{"key":"S0962492925100287_r116","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-99-01029-7"},{"key":"S0962492925100287_r257","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2019.101427"},{"key":"S0962492925100287_r288","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2021.101575"},{"key":"S0962492925100287_r173","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3763"},{"key":"S0962492925100287_r165","doi-asserted-by":"publisher","DOI":"10.1090\/bproc\/216"},{"key":"S0962492925100287_r321","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"},{"key":"S0962492925100287_r8","first-page":"135","article-title":"The path of hyperinterpolation: A survey","volume":"18","author":"An","year":"2025","journal-title":"Dolomites Res. Notes Approx."},{"key":"S0962492925100287_r315","doi-asserted-by":"publisher","DOI":"10.1016\/S0885-064X(03)00069-4"},{"key":"S0962492925100287_r36","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2011-02442-7"},{"key":"S0962492925100287_r23","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19770790114"},{"key":"S0962492925100287_r120","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-45282-1_11"},{"key":"S0962492925100287_r138","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2014-02855-X"},{"key":"S0962492925100287_r246","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-022-09576-3"},{"key":"S0962492925100287_r90","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-021-09558-x"},{"key":"S0962492925100287_r153","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2022.101653"},{"key":"S0962492925100287_r43","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.12.002"},{"key":"S0962492925100287_r316","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00300-4"},{"key":"S0962492925100287_r140","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2016.09.001"},{"key":"S0962492925100287_r66","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-021-09494-z"},{"key":"S0962492925100287_r112","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2021.12.002"},{"key":"S0962492925100287_r45","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2007.05.005"},{"key":"S0962492925100287_r311","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2012.05.016"},{"key":"S0962492925100287_r291","doi-asserted-by":"publisher","DOI":"10.1007\/BF01094364"},{"key":"S0962492925100287_r27","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/asr043"},{"key":"S0962492925100287_r229","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1999.0507"},{"key":"S0962492925100287_r52","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(81)90076-8"},{"key":"S0962492925100287_r41","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2021.01.004"},{"key":"S0962492925100287_r32","doi-asserted-by":"publisher","DOI":"10.1007\/s10092-023-00564-y"},{"key":"S0962492925100287_r241","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-002-0074-6"},{"key":"S0962492925100287_r309","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2004.06.011"},{"key":"S0962492925100287_r177","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/4148"},{"key":"S0962492925100287_r175","unstructured":"Krieg, D. , Novak, E. and Ullrich, M. (2026a), How many continuous measurements are needed to learn a vector? Available at arXiv:2412.06468. To appear in Proc. Amer. Math. Soc."},{"key":"S0962492925100287_r170","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-020-09481-w"},{"key":"S0962492925100287_r235","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.2000.0577"},{"key":"S0962492925100287_r174","doi-asserted-by":"publisher","DOI":"10.1017\/fms.2025.10101"},{"key":"S0962492925100287_r48","doi-asserted-by":"publisher","DOI":"10.1137\/151005099"},{"key":"S0962492925100287_r102","doi-asserted-by":"publisher","DOI":"10.1137\/10080138X"},{"key":"S0962492925100287_r160","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1994.1013"},{"key":"S0962492925100287_r167","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2018.08.002"},{"key":"S0962492925100287_r195","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2022.126457"},{"key":"S0962492925100287_r96","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-019-09894-w"},{"key":"S0962492925100287_r19","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2023.02.004"},{"key":"S0962492925100287_r123","first-page":"123","volume-title":"Functional Analysis","author":"Heinrich","year":"1994"},{"key":"S0962492925100287_r98","doi-asserted-by":"publisher","DOI":"10.2307\/1968516"},{"key":"S0962492925100287_r85","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2013.05.001"},{"key":"S0962492925100287_r97","doi-asserted-by":"publisher","DOI":"10.1007\/BF02066686"},{"key":"S0962492925100287_r144","volume-title":"Applications of Number Theory to Numerical Analysis","author":"Hua","year":"1981"},{"key":"S0962492925100287_r88","doi-asserted-by":"publisher","DOI":"10.1137\/23M160178X"},{"key":"S0962492925100287_r114","first-page":"3925","article-title":"Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series","volume":"151","author":"Goda","year":"2023","journal-title":"Proc. Amer. Math. Soc."},{"key":"S0962492925100287_r292","first-page":"1","volume-title":"Convex analysis, in Analysis II: Convex Analysis and Approximation Theory","author":"Tikhomirov","year":"1990"},{"key":"S0962492925100287_r295","doi-asserted-by":"publisher","DOI":"10.1007\/BF03024085"},{"key":"S0962492925100287_r4","doi-asserted-by":"publisher","DOI":"10.4171\/mems\/13"},{"key":"S0962492925100287_r47","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.885507"},{"key":"S0962492925100287_r57","doi-asserted-by":"publisher","DOI":"10.1051\/m2an\/2014050"},{"key":"S0962492925100287_r148","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2023.101786"},{"key":"S0962492925100287_r196","doi-asserted-by":"publisher","DOI":"10.4213\/rm10175e"},{"key":"S0962492925100287_r240","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2016.02.017"},{"key":"S0962492925100287_r39","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2015.05.079"},{"key":"S0962492925100287_r100","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2007.11.001"},{"key":"S0962492925100287_r300","doi-asserted-by":"publisher","DOI":"10.1007\/s43036-024-00386-x"},{"key":"S0962492925100287_r6","volume-title":"Combinatorial Topology","volume":"1","author":"Aleksandrov","year":"1956"},{"key":"S0962492925100287_r126","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2023.101821"},{"key":"S0962492925100287_r37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09477-9_5"},{"key":"S0962492925100287_r106","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-7169-3"},{"key":"S0962492925100287_r267","volume-title":"Spline Functions: Basic Theory","author":"Schumaker","year":"1981"},{"key":"S0962492925100287_r317","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2018.05.001"},{"key":"S0962492925100287_r75","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1955-0067351-1"},{"key":"S0962492925100287_r145","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492924000023"},{"key":"S0962492925100287_r181","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-015-9299-x"},{"key":"S0962492925100287_r244","volume-title":"Dimension Theory of General Spaces","author":"Pears","year":"1975"},{"key":"S0962492925100287_r7","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2026.117612"},{"key":"S0962492925100287_r194","doi-asserted-by":"publisher","DOI":"10.1111\/rssb.12096"},{"key":"S0962492925100287_r217","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(86)90016-X"},{"key":"S0962492925100287_r285","doi-asserted-by":"publisher","DOI":"10.1017\/9781108689687"},{"key":"S0962492925100287_r310","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-06-01944-2"},{"key":"S0962492925100287_r239","doi-asserted-by":"publisher","DOI":"10.4171\/116"},{"key":"S0962492925100287_r77","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2007.04.002"},{"key":"S0962492925100287_r319","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2014.10.016"},{"key":"S0962492925100287_r255","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511600814"},{"key":"S0962492925100287_r94","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2021.101571"},{"key":"S0962492925100287_r260","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2012.01.008"},{"key":"S0962492925100287_r280","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(78)90035-6"},{"key":"S0962492925100287_r134","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/8502"},{"key":"S0962492925100287_r9","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-007-0092-z"},{"key":"S0962492925100287_r226","doi-asserted-by":"publisher","DOI":"10.1006\/jath.1995.1025"},{"key":"S0962492925100287_r180","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2017.02.004"},{"key":"S0962492925100287_r30","first-page":"1025","article-title":"Sur la limitation des valeurs d\u2019un polyn\u00f4me Pn(x) de degr\u00e9 n sur tout un segment par ses valeurs en (n + 1) points du segment","volume":"1931","author":"Bernstein","year":"1931","journal-title":"Bull. Acad. Sci. URSS"},{"key":"S0962492925100287_r16","doi-asserted-by":"publisher","DOI":"10.5802\/smai-jcm.96"},{"key":"S0962492925100287_r149","doi-asserted-by":"publisher","DOI":"10.1007\/BF01106467"},{"key":"S0962492925100287_r223","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0079792"},{"key":"S0962492925100287_r20","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018977404843"},{"key":"S0962492925100287_r306","volume-title":"High-Dimensional Statistics: A Non-asymptotic Viewpoint","volume":"48","author":"Wainwright","year":"2019"},{"key":"S0962492925100287_r179","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-023-10021-7"},{"key":"S0962492925100287_r25","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492921000039"},{"key":"S0962492925100287_r157","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2015.01.003"},{"key":"S0962492925100287_r214","doi-asserted-by":"publisher","DOI":"10.1007\/s43036-025-00480-8"},{"key":"S0962492925100287_r46","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"S0962492925100287_r121","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(89)90032-4"},{"key":"S0962492925100287_r197","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60932-9"},{"key":"S0962492925100287_r127","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2023.101823"},{"key":"S0962492925100287_r247","doi-asserted-by":"publisher","DOI":"10.4064\/sm-51-3-201-223"},{"key":"S0962492925100287_r213","unstructured":"Moeller, M. , Neumayer, S. , Pozharska, K. , Sommerfeld, T. and Ullrich, T. (2025a), High-dimensional sparse recovery from function samples: Decoders, guarantees and instance optimality. Available at arXiv:2503.16209v2."},{"key":"S0962492925100287_r50","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9045-x"},{"key":"S0962492925100287_r73","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2021.109090"},{"key":"S0962492925100287_r192","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2008.01.011"},{"key":"S0962492925100287_r268","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492924000059"},{"key":"S0962492925100287_r150","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-021-09555-0"},{"key":"S0962492925100287_r184","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-33507-0_24"},{"key":"S0962492925100287_r78","doi-asserted-by":"publisher","DOI":"10.1007\/BF01171759"},{"key":"S0962492925100287_r243","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1995.1025"},{"key":"S0962492925100287_r293","volume-title":"Complexity and Information","author":"Traub","year":"1998"},{"key":"S0962492925100287_r283","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1993.1004"},{"key":"S0962492925100287_r70","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-06-08421-8"},{"key":"S0962492925100287_r101","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000069"},{"key":"S0962492925100287_r232","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90013-7"},{"key":"S0962492925100287_r216","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-04-01708-9"},{"key":"S0962492925100287_r159","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-6278-3"},{"key":"S0962492925100287_r284","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-018-9446-2"},{"key":"S0962492925100287_r65","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-013-9142-3"},{"key":"S0962492925100287_r220","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/12868"},{"key":"S0962492925100287_r79","doi-asserted-by":"publisher","DOI":"10.1007\/BF02071385"},{"key":"S0962492925100287_r313","volume-title":"Scattered Data Approximation","volume":"17","author":"Wendland","year":"2005"},{"key":"S0962492925100287_r305","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2020.107140"},{"key":"S0962492925100287_r275","first-page":"240","article-title":"Quadrature and interpolation formulas for tensor products of certain classes of functions","volume":"4","author":"Smolyak","year":"1963","journal-title":"Sov. Math. Dokl."},{"key":"S0962492925100287_r270","first-page":"387","article-title":"Smolyak\u2019s algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness","volume":"13","author":"Sickel","year":"2007","journal-title":"East J. Approx."},{"key":"S0962492925100287_r228","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1996.0015"},{"key":"S0962492925100287_r155","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176342810"},{"key":"S0962492925100287_r191","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-009-9075-x"},{"key":"S0962492925100287_r219","doi-asserted-by":"publisher","DOI":"10.1134\/S0081543813010173"},{"key":"S0962492925100287_r69","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-01-00923-5"},{"key":"S0962492925100287_r14","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3868"},{"key":"S0962492925100287_r281","first-page":"472","article-title":"Optimal numerical integration formulas for some classes of functions of several variables","volume":"20","author":"Sukharev","year":"1979","journal-title":"Dokl. Akad. Nauk"},{"key":"S0962492925100287_r249","doi-asserted-by":"publisher","DOI":"10.1007\/BF01364141"},{"key":"S0962492925100287_r204","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-014-9267-x"},{"key":"S0962492925100287_r258","doi-asserted-by":"publisher","DOI":"10.1137\/21M1410580"},{"key":"S0962492925100287_r312","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2011.03.004"},{"key":"S0962492925100287_r44","doi-asserted-by":"publisher","DOI":"10.1090\/btran\/12"},{"key":"S0962492925100287_r189","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2009.12.003"},{"key":"S0962492925100287_r59","unstructured":"Chkifa, A. , Dolbeault, M. , Krieg, D. and Ullrich, M. (2026), Constructive discretization and approximation in reproducing kernel Hilbert spaces. Available at arXiv:2602.18719v1."},{"key":"S0962492925100287_r53","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511897467"},{"key":"S0962492925100287_r62","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2016.03.018"},{"key":"S0962492925100287_r133","doi-asserted-by":"publisher","DOI":"10.1515\/9783110635461-004"},{"key":"S0962492925100287_r301","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2025.101992"},{"key":"S0962492925100287_r42","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543241"},{"key":"S0962492925100287_r314","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198535898.001.0001"},{"key":"S0962492925100287_r95","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2012.10.008"},{"key":"S0962492925100287_r109","first-page":"200","article-title":"On widths of the Euclidean ball","volume":"30","author":"Garnaev","year":"1984","journal-title":"Sov. Math. Dokl."},{"key":"S0962492925100287_r210","first-page":"419","article-title":"Analysis of discrete L2 projection on polynomial spaces with random evaluations","volume":"14","author":"Migliorati","year":"2014","journal-title":"Found. Comput. Math."},{"key":"S0962492925100287_r143","doi-asserted-by":"publisher","DOI":"10.2307\/3212956"},{"key":"S0962492925100287_r208","first-page":"1","volume-title":"Optimal Estimation in Approximation Theory","author":"Micchelli","year":"1978"},{"key":"S0962492925100287_r74","doi-asserted-by":"publisher","DOI":"10.1070\/RM9892"},{"key":"S0962492925100287_r206","doi-asserted-by":"publisher","DOI":"10.3150\/bj\/1161614945"},{"key":"S0962492925100287_r172","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-023-10021-7"},{"key":"S0962492925100287_r266","doi-asserted-by":"publisher","DOI":"10.1007\/BF01449770"},{"key":"S0962492925100287_r322","first-page":"1","article-title":"Adaptive learning of density ratios in RKHS","volume":"24","author":"Zellinger","year":"2023","journal-title":"J. Mach. Learn. Res."},{"key":"S0962492925100287_r158","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-023-09994-2"},{"key":"S0962492925100287_r67","doi-asserted-by":"publisher","DOI":"10.1142\/S0219530522400140"},{"key":"S0962492925100287_r198","first-page":"861","article-title":"A statistical perspective on algorithmic leveraging","volume":"16","author":"Ma","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"S0962492925100287_r252","doi-asserted-by":"publisher","DOI":"10.4064\/sm184-3-5"},{"key":"S0962492925100287_r296","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1992-00240-9"},{"key":"S0962492925100287_r84","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-09951-9"},{"key":"S0962492925100287_r318","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/13.1.13"},{"key":"S0962492925100287_r99","first-page":"192","article-title":"\u00dcber die interpolatorische Darstellung stetiger Funktionen","volume":"23","author":"Faber","year":"1914","journal-title":"Jahresber. Dtsch. Math.-Ver."},{"key":"S0962492925100287_r124","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45346-6_5"},{"key":"S0962492925100287_r80","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492921000052"},{"key":"S0962492925100287_r193","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18429-1"},{"key":"S0962492925100287_r13","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-013-9219-x"},{"key":"S0962492925100287_r201","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.182.1.8"},{"key":"S0962492925100287_r183","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-697560-4.50008-3"},{"key":"S0962492925100287_r277","doi-asserted-by":"publisher","DOI":"10.30970\/ana.2023.1.88"},{"key":"S0962492925100287_r60","volume-title":"Support Vector Machines","author":"Christmann","year":"2008"},{"key":"S0962492925100287_r83","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2025.101948"},{"key":"S0962492925100287_r169","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2024.106098"},{"key":"S0962492925100287_r262","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8095-4"},{"key":"S0962492925100287_r63","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492915000033"},{"key":"S0962492925100287_r38","doi-asserted-by":"publisher","DOI":"10.1137\/12086755X"},{"key":"S0962492925100287_r168","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drad014"},{"key":"S0962492925100287_r307","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(84)90063-4"},{"key":"S0962492925100287_r58","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3272"},{"key":"S0962492925100287_r222","doi-asserted-by":"publisher","DOI":"10.5802\/smai-jcm.117"},{"key":"S0962492925100287_r72","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2023.127570"},{"key":"S0962492925100287_r110","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2023.101790"},{"key":"S0962492925100287_r287","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2020.101545"},{"key":"S0962492925100287_r10","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1950-0051437-7"},{"key":"S0962492925100287_r49","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"S0962492925100287_r154","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1959.tb00338.x"},{"key":"S0962492925100287_r236","doi-asserted-by":"publisher","DOI":"10.4171\/026"},{"key":"S0962492925100287_r40","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-75934-0"},{"key":"S0962492925100287_r163","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.09.002"},{"key":"S0962492925100287_r245","first-page":"845","article-title":"Robust instance-optimal recovery of sparse signals at unknown noise levels","volume":"11","author":"Petersen","year":"2022","journal-title":"Inf. Inference"},{"key":"S0962492925100287_r279","first-page":"252","article-title":"Aleksandrov diameters of finite-dimensional sets and classes of smooth functions","volume":"16","author":"Stesin","year":"1975","journal-title":"Sov. Math. Dokl."},{"key":"S0962492925100287_r269","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-3758(00)00115-4"},{"key":"S0962492925100287_r161","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2025.110971"},{"key":"S0962492925100287_r105","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4948-7"},{"key":"S0962492925100287_r166","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2024.101840"},{"key":"S0962492925100287_r118","doi-asserted-by":"publisher","DOI":"10.1137\/18M1234151"},{"key":"S0962492925100287_r35","first-page":"26","article-title":"Fekete points as norming sets","volume":"11","author":"Bos","year":"2018","journal-title":"Dolomites Res. Notes Approx."},{"key":"S0962492925100287_r211","first-page":"397","article-title":"Approximation of functions in Lp and C on the torus","volume":"58","author":"Mityagin","year":"1962","journal-title":"Math. Notes"},{"key":"S0962492925100287_r227","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1995.1002"},{"key":"S0962492925100287_r131","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2020.101544"},{"key":"S0962492925100287_r24","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2025.101822"},{"key":"S0962492925100287_r298","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"S0962492925100287_r212","first-page":"97","article-title":"Inequalities between n-diameters","volume":"7","author":"Mityagin","year":"1963","journal-title":"Proc. Voronezh Seminar on Functional Analysis"},{"key":"S0962492925100287_r139","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2013.10.007"},{"key":"S0962492925100287_r130","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2016.05.011"},{"key":"S0962492925100287_r91","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2022.12.001"},{"key":"S0962492925100287_r82","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2014.03.015"},{"key":"S0962492925100287_r302","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2007.03.011"},{"key":"S0962492925100287_r253","doi-asserted-by":"publisher","DOI":"10.2989\/QM.2009.32.3.4.905"},{"key":"S0962492925100287_r190","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2007.11.006"},{"key":"S0962492925100287_r272","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0463"},{"key":"S0962492925100287_r28","volume-title":"Advances in Neural Information Processing Systems 19","author":"Ben-David","year":"2006"},{"key":"S0962492925100287_r251","volume-title":"History of Banach Spaces and Linear Operators","author":"Pietsch","year":"2007"},{"key":"S0962492925100287_r256","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2011.01.006"},{"key":"S0962492925100287_r125","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74496-2_26"},{"key":"S0962492925100287_r162","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2025.101958"},{"key":"S0962492925100287_r234","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-005-0612-y"},{"key":"S0962492925100287_r22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmva.2017.05.010"},{"key":"S0962492925100287_r147","doi-asserted-by":"publisher","DOI":"10.1070\/RM1974v029n03ABEH001287"},{"key":"S0962492925100287_r17","unstructured":"Bartel, F. and D\u0169ng, D. (2024), Sampling recovery in Bochner spaces and applications to parametric PDEs. Available at arXiv:2409.05050."},{"key":"S0962492925100287_r238","volume-title":"Tractability of Multivariate Problems","volume":"12","author":"Novak","year":"2010"},{"key":"S0962492925100287_r271","doi-asserted-by":"publisher","DOI":"10.1006\/jath.1995.1119"},{"key":"S0962492925100287_r71","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-023-09606-x"},{"key":"S0962492925100287_r5","doi-asserted-by":"publisher","DOI":"10.4064\/aa167-2-4"},{"key":"S0962492925100287_r263","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-008-9089-0"},{"key":"S0962492925100287_r117","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2020.105455"},{"key":"S0962492925100287_r273","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.11.001"},{"key":"S0962492925100287_r215","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-021-09504-0"},{"key":"S0962492925100287_r76","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002816"},{"key":"S0962492925100287_r122","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(92)90027-9"},{"key":"S0962492925100287_r56","first-page":"432","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)","author":"Cheraghchi","year":"2013"},{"key":"S0962492925100287_r265","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20227"},{"key":"S0962492925100287_r61","volume-title":"The Finite Element Method for Elliptic Problems","volume":"4","author":"Ciarlet","year":"1978"},{"key":"S0962492925100287_r152","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-023-09618-4"},{"key":"S0962492925100287_r129","doi-asserted-by":"publisher","DOI":"10.4064\/aa96-3-7"},{"key":"S0962492925100287_r225","doi-asserted-by":"publisher","DOI":"10.1006\/jath.1995.1071"},{"key":"S0962492925100287_r115","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2016.02.006"},{"key":"S0962492925100287_r254","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69894-1"},{"key":"S0962492925100287_r107","first-page":"1180","volume-title":"Proceedings of the 32nd International Conference on Machine Learning","volume":"37","author":"Ganin","year":"2015"},{"key":"S0962492925100287_r182","doi-asserted-by":"publisher","DOI":"10.1561\/2200000044"},{"key":"S0962492925100287_r188","doi-asserted-by":"publisher","DOI":"10.1137\/110845537"},{"key":"S0962492925100287_r294","volume-title":"A General Theory of Optimal Algorithms","author":"Traub","year":"1980"},{"key":"S0962492925100287_r135","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2014.03.012"},{"key":"S0962492925100287_r248","volume-title":"Operator Ideals","volume":"16","author":"Pietsch","year":"1978"},{"key":"S0962492925100287_r141","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2023.105919"},{"key":"S0962492925100287_r233","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-015-9282-6"},{"key":"S0962492925100287_r199","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-022-09568-3"},{"key":"S0962492925100287_r261","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2015.02.003"},{"key":"S0962492925100287_r259","volume-title":"Gaussian Processes for Machine Learning","author":"Rasmussen","year":"2006"},{"key":"S0962492925100287_r290","doi-asserted-by":"publisher","DOI":"10.1070\/RM1960v015n03ABEH004093"},{"key":"S0962492925100287_r297","volume-title":"Information-Based Complexity","author":"Traub","year":"1988"},{"key":"S0962492925100287_r51","doi-asserted-by":"publisher","DOI":"10.1017\/S0308210500015341"},{"key":"S0962492925100287_r89","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2021.101602"},{"key":"S0962492925100287_r87","article-title":"Addressing parameter choice issues in unsupervised domain adaptation by aggregation","author":"Dinu","year":"2023","journal-title":"The Eleventh International Conference on Learning Representations (ICLR 2023)"},{"key":"S0962492925100287_r11","first-page":"247","article-title":"About the approximation of periodic functions of many variable trigonometric polynomials","volume":"32","author":"Babenko","year":"1960","journal-title":"Dokl. Akad. Nauk"},{"key":"S0962492925100287_r209","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/draa023"},{"key":"S0962492925100287_r18","doi-asserted-by":"publisher","DOI":"10.5802\/smai-jcm.136"},{"key":"S0962492925100287_r308","doi-asserted-by":"publisher","DOI":"10.1007\/s102080010016"},{"key":"S0962492925100287_r289","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2022.105718"},{"key":"S0962492925100287_r320","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2022.105835"},{"key":"S0962492925100287_r171","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2021.101569"},{"key":"S0962492925100287_r242","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-015-9411-6"},{"key":"S0962492925100287_r68","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2004.05.003"},{"key":"S0962492925100287_r303","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2008.01.002"}],"container-title":["Acta Numerica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0962492925100287","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:59:47Z","timestamp":1781855987000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0962492925100287\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,19]]},"references-count":322,"alternative-id":["S0962492925100287"],"URL":"https:\/\/doi.org\/10.1017\/s0962492925100287","relation":{},"ISSN":["0962-4929","1474-0508"],"issn-type":[{"value":"0962-4929","type":"print"},{"value":"1474-0508","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,19]]}}}