Geodesic
On the power of adaption and randomization
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e152

Voir la notice de l'article provenant de la source Cambridge University Press

We present bounds on the maximal gain of adaptive and randomized algorithms over nonadaptive, deterministic ones for approximating linear operators on convex sets. If the sets are additionally symmetric, then our results are optimal. For nonsymmetric sets, we unify some notions of n-widths and s-numbers, and show their connection to minimal errors. We also discuss extensions to nonlinear widths and approximation based on function values, and conclude with a list of open problems. 
Krieg, David; Novak, Erich; Ullrich, Mario. On the power of adaption and randomization. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e152. doi: 10.1017/fms.2025.10101
@article{10_1017_fms_2025_10101,
     author = {Krieg, David and Novak, Erich and Ullrich, Mario},
     title = {On the power of adaption and randomization},
     journal = {Forum of Mathematics, Sigma},
     pages = {e152},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.10101},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10101/}
}
TY  - JOUR
AU  - Krieg, David
AU  - Novak, Erich
AU  - Ullrich, Mario
TI  - On the power of adaption and randomization
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e152
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10101/
DO  - 10.1017/fms.2025.10101
ID  - 10_1017_fms_2025_10101
ER  - 
%0 Journal Article
%A Krieg, David
%A Novak, Erich
%A Ullrich, Mario
%T On the power of adaption and randomization
%J Forum of Mathematics, Sigma
%D 2025
%P e152
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10101/
%R 10.1017/fms.2025.10101
%F 10_1017_fms_2025_10101

[1] Aleksandrov, P., Combinatorial Topology, Vol. 1 (Graylock Press, Rochester, NY, 1956). Google Scholar

[2] Bakhvalov, N. S., ‘On the optimality of linear methods for operator approximation in convex classes of functions’, USSR Comput. Maths. Math. Phys. 11 (1971), 244–249.10.1016/0041-5553(71)90017-6 Google Scholar | DOI

[3] Bakhvalov, N. S., ‘On the approximate calculation of multiple integrals’, J. Complexity 31 (2015), 502–516.10.1016/j.jco.2014.12.003 Google Scholar | DOI

[4] Bauhardt, W., ‘Hilbert-Zahlen von Operatoren in Banachräumen’, Math. Nachr. 79 (1977), 181–187.10.1002/mana.19770790114 Google Scholar | DOI

[5] Brandenberg, R., ‘Radii of regular polytopes’, Discrete Comput. Geom. 33 (2005), 43–55.10.1007/s00454-004-1127-1 Google Scholar | DOI

[6] Byrenheid, G., Kunsch, R. J. and Nguyen, V. K., ‘Monte Carlo methods for uniform approximation on periodic Sobolev spaces with mixed smoothness’, J. Complexity 46 (2018), 90–102.10.1016/j.jco.2017.12.002 Google Scholar | DOI

[7] Cohen, A., Devore, R., Petrova, G. and Wojtaszczyk, P., ‘Optimal stable nonlinear approximation’, Found. Comput. Math. 22 (2022), 607–648.10.1007/s10208-021-09494-z Google Scholar | DOI

[8] Cohen, A. and Dolbeault, M., ‘Optimal pointwise sampling for approximation’, J. Complexity 68 (2022), 101602. Google Scholar

[9] Creutzig, J. and Wojtaszczyk, P., ‘Linear vs. nonlinear algorithms for linear problems’, J. Complexity 20 (2004), 807–820.10.1016/j.jco.2004.05.003 Google Scholar | DOI

[10] Devore, R. A., Howard, R. and Micchelli, C., ‘Optimal nonlinear approximation’, Manuscripta Math. 63 (1989), 469–478.10.1007/BF01171759 Google Scholar | DOI

[11] Devore, R.A., Kyriazis, G., Leviatan, D. and Tikhomirov, V. M., ‘Wavelet compression and nonlinear n-widths’, Adv. Comput. Math. 1 (1993), 197–214.10.1007/BF02071385 Google Scholar | DOI

[12] Dolbeault, M., Krieg, D. and Ullrich, M., ‘A sharp upper bound for sampling numbers in ’, Appl. Comput. Harmon. Anal. 63 (2023), 113–134.10.1016/j.acha.2022.12.001 Google Scholar | DOI

[13] Edmunds, D. E. and Lang, J., ‘Gelfand numbers and widths’, J. Approx. Theory 166 (2013), 78–84.10.1016/j.jat.2012.10.008 Google Scholar | DOI

[14] Fang, G. and Duan, L., ‘The complexity of function approximation on Sobolev spaces with bounded mixed derivative by linear Monte Carlo methods’, J. Complexity 24 (2008), 398–409.10.1016/j.jco.2007.11.001 Google Scholar | DOI

[15] Gal, S. and Micchelli, C. A., ‘Optimal sequential and non-sequential procedures for evaluating a functional’, Appl. Anal. 10 (1980), 105–120.10.1080/00036818008839292 Google Scholar | DOI

[16] Geng, J. and Wang, H., ‘On the power of standard information for tractability for approximation of periodic functions in the worst case setting’, J. Complexity 80 (2024), 101790.10.1016/j.jco.2023.101790 Google Scholar | DOI

[17] Karvonen, T. and Suzuki, Y., ‘Approximation in Hilbert spaces of the Gaussian and related analytic kernels’, Preprint (2022), . Google Scholar | arXiv

[18] Merino, B. González, ‘On the ratio between successive radii of a symmetric convex body’, Math. Ineq. Appl. 16 (2013), 569–576. Google Scholar

[19] Merino, B. González, ‘Improving bounds for the Perel’man–Pukhov quotient for inner and outer radii’, J. Convex Anal. 24 (2017), 1099–1116. Google Scholar

[20] Heinrich, S., ‘On the relation between linear n-widths and approximation numbers’, J. Approx. Theory 58 (1989), 315–333.10.1016/0021-9045(89)90032-4 Google Scholar | DOI

[21] Heinrich, S., ‘Lower bounds for the complexity of Monte Carlo function approximation’, J. Complexity 8 (1992), 277–300.10.1016/0885-064X(92)90027-9 Google Scholar | DOI

[22] Heinrich, S., ‘Randomized complexity of parametric integration and the role of adaption I. Finite dimensional case’, J. Complexity 81 (2024), 101821. Google Scholar

[23] Heinrich, S., ‘Randomized complexity of parametric integration and the role of adaption II. Sobolev spaces’, J. Complexity 82 (2024), 101823.10.1016/j.jco.2023.101823 Google Scholar | DOI

[24] Heinrich, S., ‘Randomized complexity of vector-valued approximation’, in Hinrichs, A., Kritzer, P. and Pillichshammer, F. (eds), Monte Carlo and Quasi-Monte Carlo Methods. MCQMC 2022, Springer Proc. Math. Statist., Vol. 460 (Springer, Cham, 2022). Google Scholar

[25] Heinrich, S., ‘Randomized complexity of mean computation and the adaption problem’, J. Complexity 85 (2024), 101872.10.1016/j.jco.2024.101872 Google Scholar | DOI

[26] Ismagilov, R. S., ‘Diameters of sets in normed linear spaces and approximation of functions by trigonometric polynomials’, Russ. Math. Surveys 29(3) (1974), 169–186.10.1070/RM1974v029n03ABEH001287 Google Scholar | DOI

[27] Kadets, M. and Snobar, S., ‘Certain functionals on the Minkowski compactum’, Math. Notes 10 (1971), 694–696.10.1007/BF01106467 Google Scholar | DOI

[28] Kon, M. A. and Novak, E., ‘The adaption problem for approximating linear operators’, Bull. Amer. Math. Soc. 23 (1990), 159–165.10.1090/S0273-0979-1990-15924-5 Google Scholar | DOI

[29] Krieg, D., ‘Optimal Monte Carlo methods for -approximation’, Constr. Approx. 49 (2019), 385–403.10.1007/s00365-018-9428-4 Google Scholar | DOI

[30] Krieg, D., Novak, E. and Ullrich, M., ‘How many continuous measurements are needed to learn a vector?’, Preprint (2025), . Google Scholar | arXiv

[31] Krieg, D., Pozharska, K., Ullrich, M. and Ullrich, T., ‘Sampling recovery in and other norms’, to appear in Math. Comp., Preprint (2025), . Google Scholar | arXiv

[32] Krieg, D., Pozharska, K., Ullrich, M. and Ullrich, T., ‘Sampling projections in the uniform norm’, J. Math. Anal. Appl. 553(2) (2026), 129873.10.1016/j.jmaa.2025.129873 Google Scholar | DOI

[33] Krieg, D., Siedlecki, P., Ullrich, M. and Woźniakowski, H., ‘Exponential tractability of -approximation with function values’, Adv. Comput. Math. 49 (2023), 18.10.1007/s10444-023-10021-7 Google Scholar | DOI

[34] Krieg, D. and Ullrich, M., ‘Function values are enough for -approximation’, Found. Comput. Math. 21(4) (2021), 1141–1151.10.1007/s10208-020-09481-w Google Scholar | DOI

[35] Krieg, D. and Ullrich, M., ‘Function values are enough for -approximation: Part II’, J. Complexity 66 (2021), 101569.10.1016/j.jco.2021.101569 Google Scholar | DOI

[36] Kunsch, R. J., ‘Bernstein Numbers and Lower Bounds for the Monte Carlo Error’, in Cools, R. and Nuyens, D. (eds), Monte Carlo and Quasi-Monte Carlo Methods, Springer Proc. Math. Statist., Vol. 163 (Springer, Cham, 2016).10.1007/978-3-319-33507-0_24 Google Scholar | DOI

[37] Kunsch, R. J., High-dimensional Function Approximation: Breaking the Curse with Monte Carlo Methods, Ph. D. dissertation, Preprint (2017), . Google Scholar | arXiv

[38] Kunsch, R. J., Novak, E. and Wnuk, M., ‘Randomized approximation of summable sequences – adaptive and non-adaptive’, J. Approx. Theory 304 (2024), 106056.10.1016/j.jat.2024.106056 Google Scholar | DOI

[39] Kunsch, R. J. and Wnuk, M., ‘Uniform approximation of vectors using adaptive randomized information’, Preprint (2024), . Google Scholar | arXiv

[40] Lorentz, G. G., Golitschek, M. V. and Makovoz, Yu., Constructive Approximation, Advanced Problems, Grundlehren 304 (Springer, Berlin, 1996).10.1007/978-3-642-60932-9 Google Scholar | DOI

[41] Mathé, P., ‘s-numbers in Information-Based Complexity’, J. Complexity 6 (1990), 41–66.10.1016/0885-064X(90)90011-2 Google Scholar | DOI

[42] Mathé, P., ‘Random approximation of Sobolev embeddings’, J. Complexity 7 (1991), 261–281.10.1016/0885-064X(91)90036-W Google Scholar | DOI

[43] Mityagin, B. S. and Henkin, G. M., ‘Inequalities between n-diameters’, in Proc. Seminar on Functional Analysis 7 (Voronezh, 1963), 97–103. Google Scholar

[44] Nagel, N., Schäfer, M. and Ullrich, T., ‘A new upper bound for sampling numbers’, Found. Comput. Math. 22(2) (2022), 445–468.10.1007/s10208-021-09504-0 Google Scholar | DOI

[45] Novak, E., Deterministic and Stochastic Error Bounds in Numerical Analysis, Lecture Notes in Mathematics, Vol. 1349 (Springer, Berlin, 1988).10.1007/BFb0079792 Google Scholar | DOI

[46] Novak, E., ‘Optimal linear randomized methods for linear operators in Hilbert spaces’, J. Complexity 8(1) (1992), 22–36.10.1016/0885-064X(92)90032-7 Google Scholar | DOI

[47] Novak, E., ‘Optimal recovery and n-widths for convex classes of functions’, J. Approx. Theory 80 (1995), 390–408.10.1006/jath.1995.1025 Google Scholar | DOI

[48] Novak, E., ‘The adaption problem for nonsymmetric convex sets’, J. Approx. Theory 82 (1995), 123–134.10.1006/jath.1995.1071 Google Scholar | DOI

[49] Novak, E., ‘On the power of adaption’, J. Complexity 12 (1996), 199–237.10.1006/jcom.1996.0015 Google Scholar | DOI

[50] Novak, E. and Ritter, K., ‘A stochastic analog to Chebyshev centers and optimal average case algorithms’, J. Complexity 5 (1989), 60–79.10.1016/0885-064X(89)90013-7 Google Scholar | DOI

[51] Novak, E. and Woźniakowski, H., Tractability of Multivariate Problems. Volume I: Linear Information, EMS Tracts in Mathematics, Vol. 6 (European Mathematical Society, Zürich, 2008).10.4171/026 Google Scholar | DOI

[52] Perel’Man, G. Ya, ‘On the k-radii of a convex body’, Siberian Math. J. 28 (1987), 665–666.10.1007/BF00973857 Google Scholar | DOI

[53] Pietsch, A., ‘s-numbers of operators in Banach spaces’, Studia Math. 51 (1974), 201–223.10.4064/sm-51-3-201-223 Google Scholar | DOI

[54] Pietsch, A., Operator Ideals, North-Holland Mathematical Library, Vol. 20 (Elsevier, Amsterdam, 1980). Google Scholar

[55] Pietsch, A., Eigenvalues and s-Numbers, Cambridge Studies in Advanced Mathematics, Vol. 13 (Cambridge University Press, Cambridge, 1987). Google Scholar

[56] Pietsch, A., History of Banach Spaces and Linear Operators (Birkhäuser, Boston, MA, 2007). Google Scholar

[57] Pietsch, A., ‘Long-standing open problems of Banach space theory: My personal top ten’, Quaest. Math. 32(3) (2009), 321–337.10.2989/QM.2009.32.3.4.905 Google Scholar | DOI

[58] Pinkus, A., n-Widths in Approximation Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (Springer, Berlin, 1985).10.1007/978-3-642-69894-1 Google Scholar | DOI

[59] Pukhov, S. V., ‘Inequalities for the Kolmogorov and Bernstein widths in Hilbert space’, Math. Notes 25 (1979), 320–326. [Translated from Mat. Zametki 25(4) (1979), 619–628.]10.1007/BF01688487 Google Scholar | DOI

[60] Pukhov, S. V., ‘Kolmogorov diameters of a regular simplex’, Moscow Univ. Math. Bull. 35 (1980), 38–41. Google Scholar

[61] Siegel, J. W., ‘Sharp lower bounds on the manifold widths of Sobolev and Besov spaces’, J. Complexity 85 (2024), 101884.10.1016/j.jco.2024.101884 Google Scholar | DOI

[62] Solomjak, M. E. and Tichomirov, V. M., ‘Some geometric characteristics of the embedding map from to ’, Izv. Vyssh. Uchebn. Zaved. Mat. 10 (1967), 76–82. Google Scholar

[63] Stesin, M. I., ‘On Aleksandrov diameters of balls’, Dokl. Akad. Nauk SSSR 217(1) (1974), 31–33. Google Scholar

[64] Stesin, M. I., ‘Aleksandrov diameters of finite-dimensional sets and classes of smooth functions’, Dokl. Akad. Nauk SSSR 220(6) (1975), 1278–1281. Google Scholar

[65] Temlyakov, V. N., ‘On optimal recovery in ’, J. Complexity 65 (2021), 101545.10.1016/j.jco.2020.101545 Google Scholar | DOI

[66] Tikhomirov, V. M., ‘Diameters of sets in function spaces and the theory of best approximations’, Russ. Math. Surveys 15(3) (1960), 75–111.10.1070/RM1960v015n03ABEH004093 Google Scholar | DOI

[67] Traub, J. and Woźniakowski, H., A General Theory of Optimal Algorithms (Academic Press, New York, 1980). Google Scholar

[68] Traub, J., Wasilkowski, G. and Woźniakowski, H., Information-Based Complexity (Academic Press, Boston, MA, 1988). Google Scholar

[69] Ullrich, M., ‘On the worst-case error of least squares algorithms for -approximation with high probability’, J. Complexity 60 (2020), 1–14.10.1016/j.jco.2020.101484 Google Scholar | DOI

[70] Ullrich, M., ‘On inequalities between s-numbers’, Adv. Oper. Theory 9 (2024), 82.10.1007/s43036-024-00386-x Google Scholar | DOI

[71] Ullrich, M., ‘Sampling and entropy numbers in the uniform norm’, to appear in J. Complexity. Google Scholar

[72] Wasilkowski, G.W. and Woźniakowski, H., ‘The power of standard information for multivariate approximation in the randomized setting’, Math. Comp. 76 (2007), 965–988.10.1090/S0025-5718-06-01944-2 Google Scholar | DOI

[73] Yarotsky, D., ‘Error bounds for approximations with deep ReLU networks’, Neural Networks 94 (2017), 103–114.10.1016/j.neunet.2017.07.002 Google Scholar PubMed | DOI

Cité par Sources :