Probabilistic approach to analysis of information complexity of concret multivariate approximation problem

I. A. Limar

Zapiski Nauchnykh Seminarov POMI, Probability and statistics. Part 36, Tome 535 (2024), pp. 150-172

Résumé

Information complexity in the worst-case setting of multivariate approximation problem of functions from reproducing kernel Hilbert space with Gaussian kernel is considered. In the paper we obtain an upper estimate of information complexity for arbitrary error threshold and parametric dimension via probabilistic methods. The main result refines the logarithmic asymptotics of Khartov and Limar and complements the estimates by Fasshauer, Hickernell, and Woźniakowski.

Bibliographie

[1] N. Aronszajn, “Theory of reproducing kernels”, Trans. Amer. Math. Soc., 68 (1950), 337–404 | DOI | MR | Zbl

[2] J. Chen, H. Wang, “Average case tractability of multivariate approximation with Gaussian kernels”, J. Approx. Theory, 239 (2019), 51–71 | DOI | MR | Zbl

[3] C.-G. Esseen, “A moment inequality with an application to the central limit theorem”, Scand. Aktuarietidskr. J., 39 (1956), 160–170 | DOI | MR

[4] G. E. Fasshauer, F. J. Hickernell, H. Woźniakowski, “Average case approximation: convergence and tractability of Gaussian kernels”, Monte Carlo and Quasi-Monte Carlo 2010, eds. L. Plaskota, H. Woźniakowski, Springer, 2012, 329–345 | DOI | MR

[5] G. E. Fasshauer, F. J. Hickernell, H. Woźniakowski, “On dimension-independent rates of convergence for function approximation with Gaussian kernels”, SIAM J. Numer. Analysis, 50 (2012), 247–271 | DOI | MR | Zbl

[6] A. I. J. Forrester, A. Sóbester, A. J. Keane, Engineering Design via Surrogate Modelling: a Practical Guide, Wiley, Chichester, 2008

[7] T. Hastie, R. Tibshirani, J. Friedman, Elements of Statistical Learning: Data Mining, Inference, and Prediction, Springer Series in Statistics, second ed., Springer, New York, 2009 | DOI | MR | Zbl

[8] A. A. Khartov, “A simplified criterion for quasi-polynomial tractability of approximation of random elements and its applications”, J. Complexity, 34 (2016), 30–41 | DOI | MR | Zbl

[9] A. A. Khartov, I. A. Limar, “Asymptotic analysis in multivariate average case approximation with Gaussian kernels”, J. Complexity, 70 (2022), 101631 | DOI | MR | Zbl

[10] A. A. Khartov, I. A. Limar, “Asymptotic analysis in worst case approximation with Gaussian kernels”, J. Complexity, 82 (2024), 101838 | DOI | MR | Zbl

[11] E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, v. I, EMS Tracts Math., 6, Linear Information, EMS, Zürich, 2008 | DOI | MR | Zbl

[12] E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, v. II, EMS Tracts Math., 12, Standard Information for Functionals, EMS, Zürich, 2010 | DOI | MR | Zbl

[13] E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, v. III, EMS Tracts Math., 18, Standard Information for Operators, EMS, Zürich, 2012 | DOI | MR | Zbl

[14] C. E. Rasmussen, C. Williams, Gaussian Processes for Machine Learning, MIT Press, 2006 | MR | Zbl

[15] S. Pereverzyev, An Introduction to Artificial Intelligence Based on Reproducing Kernel Hilbert Spaces, Birkhäuser, 2022 | MR | Zbl

[16] B. Schölkopf, A. J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, Massachusetts, 2002

[17] I. Shevtsova, On the absolute constants in the Berry–Esseen type inequalities for identically distributed summands, 2011, arXiv: 1111.6554 | MR

[18] I. H. Sloan, H. Woźniakowski, “Multivariate approximation for analytic functions with Gaussian kernels”, J. Complexity, 45 (2018), 1–21 | DOI | MR | Zbl

[19] H. Wendland, Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, 2005 | MR | Zbl

[20] H. Zhu, C. K. I. Williams, R. J. Rohwer, M. Morciniec, “Gaussian Regression and Optimal Finite Dimensional Linear Models”, Neural Networks and Machine Learning, ed. C. M. Bishop, Springer, Berlin, 1998, 1–20

[21] A. A. Borovkov, Teoriya veroyatnostei, URSS, M., 2009

[22] M. Sh. Birman, M. Z Solomyak, Spektralnaya teoriya samosopryazhennykh operatorov v gilbertovom prostranstve, Lan, SPb., 2010

[23] M. A. Krasnoselskii, P. P. Zabreiko, E. I. Pustyrnik, P. E. Sobolevskii, Integralnye operatory v prostranstvakh summiruemykh funktsii, Nauka, M., 1966 | MR

[24] V. V. Petrov, Summy nezavisimykh sluchainykh velichin, Nauka, M., 1972

[25] P. K. Suetin, Klassicheskie ortogonalnye mnogochleny, Fizmatlit, M., 2007