Kernel interpolation of high dimensional scattered data. (English) Zbl 07852678
Summary: Data sites selected from modeling high-dimensional problems often appear scattered in nonpaternalistic ways. Except for sporadic-clustering at some spots, they become relatively far apart as the dimension of the ambient space grows. These features defy any theoretical treatment that requires local or global quasi-uniformity of distribution of data sites. Incorporating a recently-developed application of integral operator theory in machine learning, we propose and study in the current article a new framework to analyze kernel interpolation of high-dimensional data, which features bounding stochastic approximation error by the spectrum of the underlying kernel matrix. Both theoretical analysis and numerical simulations show that spectra of kernel matrices are reliable and stable barometers for gauging the performance of kernel-interpolation methods for high-dimensional data.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 94A20 | Sampling theory in information and communication theory |
| 41A35 | Approximation by operators (in particular, by integral operators) |
Software:
ImageNetReferences:
| [1] | Baldi, P. and Hatfield, G. W., DNA Microarrays and Gene Expression: From Experiments to Data Analysis and Modeling, Cambridge University Press, Cambridge, 2011. |
| [2] | Ball, K. M., Invertibility of Euclidean distance matrices and radial basis interpolation, J. Approx. Theory, 68 (1992), pp. 74-82. · Zbl 0746.41002 |
| [3] | Belkin, M., Approximation Beats Concentration? An Approximation View on Inference with Smooth Radial Kernels, preprint, https://arxiv.org/abs/1801.03437, 2018. |
| [4] | Bhatia, R., Matrix Analysis, , Springer-Verlag, New York, 2013. |
| [5] | Buchholz, S., Kernel interpolation in Sobolev spaces is not consistent in low dimensions, in Proceedings of Thirty Fifth Conference on Learning Theory, , PMLR, 2022, pp. 3410-3440. |
| [6] | Caponnetto, A. and De Vito, E., Optimal rates for the regularized least-squares algorithm, Found. Comput. Math., 7 (2007), pp. 331-368. · Zbl 1129.68058 |
| [7] | Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L., Imagenet: A large-scale hierarchical image database, in Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition, , IEEE, 2009, pp. 248-255. |
| [8] | Fasshauer, G. E. and McCourt, M. J., Stable evaluation of Gaussian radial basis function interpolants, SIAM J. Sci. Comput., 34 (2012), pp. A737-A762, doi:10.1137/110824784. · Zbl 1252.65028 |
| [9] | Hangelbroek, T., Narcowich, F. J., Rieger, C., and Ward, J. D., Direct and inverse results on bounded domains for meshless methods via localized bases on manifolds, in Contemporary Computational Mathematics—A Celebration of the 80th Birthday of Ian Sloan, Springer, Cham, 2018, pp. 517-543. · Zbl 1405.41009 |
| [10] | Hangelbroek, T., Narcowich, F. J., Sun, X., and Ward, J. D., Kernel approximation on manifolds II: The \(L_{\infty }\) norm of the \(L_2\) projector, SIAM J. Math. Anal., 43 (2011), pp. 662-684, doi:10.1137/100795334. · Zbl 1232.41002 |
| [11] | Hangelbroek, T., Narcowich, F. J., and Ward, J. D., Kernel approximation on manifolds I: Bounding the Lebesgue constant, SIAM J. Math. Anal., 42 (2010), pp. 1732-1760, doi:10.1137/090769570. · Zbl 1219.41003 |
| [12] | Hangelbroek, T., Narcowich, F. J., and Ward, J. D., Polyharmonic and related kernels on manifolds: Interpolation and approximation, Found. Comput. Math., 12 (2012), pp. 625-670. · Zbl 1259.41005 |
| [13] | Karoui, E., The spectrum of kernel random matrices, Ann. Statist., 38 (2010), pp. 1-50. · Zbl 1181.62078 |
| [14] | Levesley, J. and Sun, X., Approximation in rough native spaces by shifts of smooth kernels on spheres, J. Approx. Theory, 133 (2005), pp. 269-283. · Zbl 1082.41018 |
| [15] | Liang, T. and Rakhlin, A., Just interpolate: Kernel “ridgeless” regression can generalize, Ann. Statist., 48 (2020), pp. 1329-1347. · Zbl 1453.68155 |
| [16] | Lin, S.-B., Guo, X., and Zhou, D.-X., Distributed learning with regularized least squares, J. Mach. Learn. Res., 18 (2017), pp. 3202-3232. · Zbl 1435.68273 |
| [17] | Lin, S.-B., Lei, Y., and Zhou, D.-X., Boosted kernel ridge regression: Optimal learning rates and early stopping, J. Mach. Learn. Res., 20 (2019), 46. · Zbl 1484.68189 |
| [18] | Lin, S.-B. and Zhou, D.-X., Distributed kernel-based gradient descent algorithms, Constr. Approx., 47 (2018), pp. 249-276. · Zbl 1390.68542 |
| [19] | Madych, W. and Nelson, S., Multivariate interpolation and conditionally positive definite functions II, Math. Comp., 54 (1990), pp. 211-230. · Zbl 0859.41004 |
| [20] | Maiorov, V., Representation of polynomials by linear combinations of radial basis functions, Constr. Approx., 37 (2013), pp. 283-293. · Zbl 1264.41023 |
| [21] | Mücke, N., Adaptivity for Regularized Kernel Methods by Lepskii’s Principle, preprint, https://arxiv.org/abs/1804.05433, 2018. |
| [22] | Narcowich, F. J., Sun, X., and Ward, J. D., Approximation power of RBFs and their associated SBFs: A connection, Adv. Comput. Math., 27 (2007), pp. 107-124. · Zbl 1119.41011 |
| [23] | Narcowich, F. J., Sun, X., Ward, J. D., and Wendland, H., Direct and inverse Sobolev error estimates for scattered data interpolation via spherical basis functions, Found. Comput. Math., 7 (2007), pp. 369-390. · Zbl 1348.41010 |
| [24] | Narcowich, F. J. and Ward, J. D., Norms of inverses and condition numbers for matrices associated with scattered data, J. Approx. Theory, 64 (1991), pp. 69-94. · Zbl 0724.41004 |
| [25] | Narcowich, F. J. and Ward, J. D., Scattered data interpolation on spheres: Error estimates and locally supported basis functions, SIAM J. Math. Anal., 33 (2002), pp. 1393-1410, doi:10.1137/S0036141001395054. · Zbl 1055.41007 |
| [26] | Narcowich, F. J. and Ward, J. D., Scattered-data interpolation on \(\mathbb{R}^n\): Error estimates for radial basis and band-limited functions, SIAM J. Math. Anal., 36 (2004), pp. 284-300, doi:10.1137/S0036141002413579. · Zbl 1081.41014 |
| [27] | Narcowich, F. J., Ward, J. D., and Wendland, H., Sobolev error estimates and a Bernstein inequality for scattered data interpolation via radial basis functions, Constr. Approx., 24 (2006), pp. 175-186. · Zbl 1120.41022 |
| [28] | Park, J. and Sandberg, I. W., Universal approximation using radial-basis-function networks, Neural Comput., 3 (1991), pp. 246-257. |
| [29] | Petrou, M. M. and Petrou, C., Image Processing: The Fundamentals, John Wiley & Sons, 2010. · Zbl 1191.68792 |
| [30] | Pinelis, I., Optimum bounds for the distributions of martingales in Banach spaces, Ann. Probab., (1994), pp. 1679-1706. · Zbl 0836.60015 |
| [31] | Schaback, R., Error estimates and condition numbers for radial basis function interpolation, Adv. Comput. Math., 3 (1995), pp. 251-264. · Zbl 0861.65007 |
| [32] | Schaback, R., A unified theory of radial basis functions: Native Hilbert spaces for radial basis functions II, J. Comput. Appl. Math., 121 (2000), pp. 165-177. · Zbl 0984.46014 |
| [33] | Schaback, R., Multivariate interpolation by polynomials and radial basis functions, Constr. Approx., 21 (2005), pp. 293-317. · Zbl 1076.41003 |
| [34] | Smale, S. and Zhou, D.-X., Shannon sampling and function reconstruction from point values, Bull. Amer. Math. Soc., 41 (2004), pp. 279-305. · Zbl 1107.94007 |
| [35] | Smale, S. and Zhou, D.-X., Shannon sampling II: Connections to learning theory, Appl. Comput. Harmon. Anal., 19 (2005), pp. 285-302. · Zbl 1107.94008 |
| [36] | Smale, S. and Zhou, D.-X., Learning theory estimates via integral operators and their approximations, Constr. Approx., 26 (2007), pp. 153-172. · Zbl 1127.68088 |
| [37] | Steinwart, I. and Christmann, A., Support Vector Machines, Springer, New York, 2008. · Zbl 1203.68171 |
| [38] | Steinwart, I., Hush, D. R., and Scovel, C., Optimal rates for regularized least squares regression, in Proceedings of the 22nd Conference on Learning Theory, , 2009, pp. 79-93. |
| [39] | Vershynin, R., High-Dimensional Probability: An Introduction with Applications in Data Science, , Cambridge University Press, Cambridge, 2018. · Zbl 1430.60005 |
| [40] | Wendland, H., Scattered Data Approximation, , Cambridge University Press, Cambridge, 2004. |
| [41] | Yang, Y., Pilanci, M., and Wainwright, M., Randomized sketches for kernels: Fast and optimal nonparametric regression, Ann. Statist., 45 (2017), pp. 991-1023. · Zbl 1371.62039 |
| [42] | Yao, Y., Rosasco, L., and Caponnetto, A., On early stopping in gradient descent learning, Constr. Approx., 26 (2007), pp. 289-315. · Zbl 1125.62035 |
| [43] | Zhang, Y., Duchi, J., and Wainwright, M., Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates, J. Mach. Learn. Res., 16 (2015), pp. 3299-3340. · Zbl 1351.62142 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
