Error Guarantees for Least Squares Approximation with Noisy Samples in Domain Adaptation

Bartel, Felix

The SMAI Journal of computational mathematics, Tome 9 (2023), pp. 95-120

Given $n$ samples of a function $f:D\to ℂ$ in random points drawn with respect to a measure ${\varrho }_S$ we develop theoretical analysis of the $L_2(D,{\varrho }_T)$-approximation error. For a parituclar choice of ${\varrho }_S$ depending on ${\varrho }_T$, it is known that the weighted least squares method from finite dimensional function spaces $V_m$, $dim\left(V_m\right)=m<\infty$ has the same error as the best approximation in $V_m$ up to a multiplicative constant when given exact samples with logarithmic oversampling. If the source measure ${\varrho }_S$ and the target measure ${\varrho }_T$ differ we are in the domain adaptation setting, a subfield of transfer learning. We model the resulting deterioration of the error in our bounds.

Further, for noisy samples, our bounds describe the bias-variance trade off depending on the dimension $m$ of the approximation space $V_m$. All results hold with high probability.

For demonstration, we consider functions defined on the $d$-dimensional cube given in unifom random samples. We analyze polynomials, the half-period cosine, and a bounded orthonormal basis of the non-periodic Sobolev space $H_{\mathrm{mix}}^2$. Overcoming numerical issues of this $H_{\mathrm{mix}}^2$ basis, this gives a novel stable approximation method with quadratic error decay. Numerical experiments indicate the applicability of our results.

Classification : 41A10, 41A25, 41A60, 41A63, 42C10, 65TXX, 65F22, 65D15, 94A20
Keywords: domain adaptation, individual function approximation, least squares, sampling theory, transfer learning, unit cube, polynomial approximation

[1] Adcock, B. Multivariate modified Fourier series and application to boundary value problems, Numer. Math., Volume 115 (2010) no. 4, pp. 511-552 | MR | DOI | Zbl

[2] Adcock, B.; Huybrechs, D. Multivariate modified Fourier expansions, Spectral and high order methods for partial differential equations (Lecture Notes in Computational Science and Engineering), Volume 76, Springer, 2011, pp. 85-92 | Zbl | MR | DOI

[3] Adcock, B.; Iserles, A.; Nørsett, S. P. From high oscillation to rapid approximation II: expansions in Birkhoff series, IMA J. Numer. Anal., Volume 32 (2012) no. 1, pp. 105-140 | MR | DOI | Zbl

[4] Baraud, Y. Model selection for regression on a random design, ESAIM, Probab. Stat., Volume 6 (2002), pp. 127-146 | DOI | MR | Numdam | Zbl

[5] Bartel, F.; Hielscher, R. Concentration inequalities for cross-validation in scattered data approximation, J. Approx. Theory, Volume 277 (2022), 105715, 17 pages | DOI | MR | Zbl

[6] Bartel, F.; Hielscher, R.; Potts, D. Fast Cross-validation in Harmonic Approximation, Appl. Comput. Harmon. Anal., Volume 49 (2020) no. 2, pp. 415-437 | DOI | MR | Zbl

[7] Bartel, F.; Schäfer, M.; Ullrich, T. Constructive subsampling of finite frames with applications in optimal function recovery, Appl. Comput. Harmon. Anal. (2023) (to appear) | DOI | MR | Zbl

[8] Bellec, P. C. Concentration of quadratic forms under a Bernstein moment assumption (2019) (https://arxiv.org/abs/1901.08736)

[9] Chkifa, A.; Cohen, A.; Migliorati, G.; Nobile, F.; Tempone, R. Discrete least squares polynomial approximation with random evaluations—application to parametric and stochastic elliptic PDEs, ESAIM, Math. Model. Numer. Anal., Volume 49 (2015) no. 3, pp. 815-837 | MR | DOI | Zbl | Numdam

[10] Cohen, A.; Davenport, M. A.; Leviatan, D. On the stability and accuracy of least squares approximations, Found. Comput. Math., Volume 13 (2013) no. 5, pp. 819-834 | Zbl | MR | DOI

[11] Cohen, A.; Migliorati, G. Optimal weighted least-squares methods, SMAI J. Comput. Math., Volume 3 (2017), pp. 181-203 | Numdam | Zbl | MR | DOI

[12] Cools, R.; Kuo, F. Y.; Nuyens, D.; Suryanarayana, G. Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions, J. Complexity, Volume 36 (2016), pp. 166-181 | DOI | MR | Zbl

[13] Dick, J.; Nuyens, D.; Pillichshammer, F. Lattice rules for nonperiodic smooth integrands, Numer. Math., Volume 126 (2014) no. 2, pp. 259-291 | DOI | MR | Zbl

[14] Dolbeault, M.; Cohen, A. Optimal pointwise sampling for $L^2$ approximation, J. Complexity, Volume 68 (2022), 101602 | DOI | MR | Zbl

[15] Dolbeault, M.; Cohen, A. Optimal sampling and Christoffel functions on general domains, Constr. Approx., Volume 56 (2022) no. 1, pp. 121-163 | MR | Zbl | DOI

[16] Dolbeault, M.; Krieg, D.; Ullrich, M. A sharp upper bound for sampling numbers in $L_2$, Appl. Comput. Harmon. Anal., Volume 63 (2023), pp. 113-134 | MR | DOI

[17] Foucart, S.; Rauhut, H. A mathematical introduction to compressive sensing, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, 2013, xviii+625 pages | MR | DOI

[18] Gizewski, E. R.; Mayer, L.; Moser, B. A.; Nguyen, D. H.; Pereverzyev, S.; Pereverzyev, S. V.; Shepeleva, N.; Zellinger, W. On a regularization of unsupervised domain adaptation in RKHS, Appl. Comput. Harmon. Anal., Volume 57 (2022), pp. 201-227 | DOI | MR | Zbl

[19] Greenbaum, A. Iterative methods for solving linear systems, Frontiers in Applied Mathematics, 17, Society for Industrial and Applied Mathematics, 1997, xiv+220 pages | DOI | MR

[20] Györfi, L.; Kohler, M.; Krzyżak, A.; Walk, H. A distribution-free theory of nonparametric regression, Springer Series in Statistics, Springer, 2002, xvi+647 pages | MR | DOI

[21] Haberstich, C.; Nouy, A.; Perrin, G. Boosted optimal weighted least-squares, Math. Comput. (2022) | DOI | MR | Zbl

[22] Hampton, J.; Doostan, A. Coherence motivated sampling and convergence analysis of least squares polynomial Chaos regression, Comput. Methods Appl. Mech. Eng., Volume 290 (2015), pp. 73-97 | Zbl | MR | DOI

[23] Iserles, A.; Nørsett, S. P. From high oscillation to rapid approximation. I. Modified Fourier expansions, IMA J. Numer. Anal., Volume 28 (2008) no. 4, pp. 862-887 | Zbl | MR | DOI

[24] Kämmerer, L.; Ullrich, T.; Volkmer, T. Worst-case recovery guarantees for least squares approximation using random samples, Constr. Approx., Volume 54 (2021) no. 2, pp. 295-352 | Zbl | MR | DOI

[25] Krein, M. G. On a special class of differential operators, Dokl. Akad. Nauk SSSR, Volume 2 (1935), pp. 345-349

[26] Krieg, D.; Ullrich, M. Function values are enough for $L_2$-approximation, Found. Comput. Math., Volume 21 (2021) no. 4, pp. 1141-1151 | Zbl | MR | DOI

[27] Kuo, F. Y.; Migliorati, G.; Nobile, F.; Nuyens, D. Function integration, reconstruction and approximation using rank-1 lattices, Math. Comput., Volume 90 (2021) no. 330, pp. 1861-1897 | Zbl | MR | DOI

[28] Limonova, I.; Temlyakov, V. N. On sampling discretization in $L_2$, J. Math. Anal. Appl., Volume 515 (2022) no. 2, 126457, 14 pages | Zbl | MR | DOI

[29] Lippert, L.; Potts, D.; Ullrich, T. Fast Hyperbolic Wavelet Regression meets ANOVA (2021) (https://arxiv.org/abs/2108.13197, to appear in Numer. Math.) | DOI

[30] Lu, S.; Mathé, P.; Pereverzev, S. V. Balancing principle in supervised learning for a general regularization scheme, Appl. Comput. Harmon. Anal., Volume 48 (2020) no. 1, pp. 123-148 | Zbl | MR | DOI

[31] Migliorati, G.; Nobile, F.; von Schwerin, E.; Tempone, R. Analysis of Discrete $L^2$ Projection on Polynomial Spaces with Random Evaluations, Found. Comput. Math. (2014) | MR | Zbl | DOI

[32] Moeller, M.; Ullrich, T. $L_2$-norm sampling discretization and recovery of functions from RKHS with finite trace, Sampl. Theory Signal Process. Data Anal., Volume 19 (2021) no. 2, 13, 31 pages | Zbl | MR | DOI

[33] Nagel, N.; Schäfer, M.; Ullrich, T. A New Upper Bound for Sampling Numbers, Found. Comput. Math. (2021) | DOI

[34] Narayan, A.; Jakeman, J. D.; Zhou, T. A Christoffel function weighted least squares algorithm for collocation approximations, Math. Comput., Volume 86 (2017) no. 306, pp. 1913-1947 | Zbl | MR | DOI

[35] Nasdala, R.; Potts, D. A note on transformed Fourier systems for the approximation of non-periodic signals, Monte Carlo and quasi-Monte Carlo methods (Springer Proceedings in Mathematics & Statistics), Volume 387, Springer, 2022, pp. 253-271 | MR | DOI

[36] Pan, S. J.; Yang, Q. A Survey on Transfer Learning, IEEE Trans. Knowl. Data Eng., Volume 22 (2010) no. 10, pp. 1345-1359 | DOI

[37] Pereverzyev, S. V.; Lu, S. Regularization Theory for Ill-Posed Problems. Selected Topics, Walter de Gruyter, 2013, 287 pages | DOI

[38] Plonka, G.; Potts, D.; Steidl, G.; Tasche, M. Numerical Fourier analysis, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, 2018, xvi+168 pages | MR | DOI

[39] Potts, D.; Schmischke, M. Learning multivariate functions with low-dimensional structures using polynomial bases, J. Comput. Appl. Math., Volume 403 (2022), 113821, 19 pages | DOI | MR | Zbl

[40] Potts, D.; Volkmer, T. Fast and exact reconstruction of arbitrary multivariate algebraic polynomials in Chebyshev form, 2015 International Conference on Sampling Theory and Applications (SampTA) (2015), pp. 392-396 | DOI

[41] Pozharska, K.; Ullrich, T. A Note on Sampling Recovery of Multivariate Functions in the Uniform Norm, SIAM J. Numer. Anal., Volume 60 (2022) no. 3, pp. 1363-1384 | DOI | MR | Zbl

[42] Rauhut, H.; Ward, R. Sparse Legendre expansions via ${\ell }_1$-minimization, J. Approx. Theory, Volume 164 (2012) no. 5, pp. 517-533 | DOI | MR

[43] Rudelson, M.; Vershynin, R. Hanson-Wright inequality and sub-gaussian concentration, Electron. Commun. Probab., Volume 18 (2013), 82, 9 pages | DOI | MR | Zbl

[44] Shen, J.; Tang, T.; Wang, L. Spectral methods. Algorithms, analysis and applications, Springer Series in Computational Mathematics, 41, Springer, 2011, xvi+470 pages | DOI | MR

[45] Steinwart, I.; Christmann, A. Support vector machines, Information Science and Statistics, Springer, 2008, xvi+601 pages | MR

[46] Suryanarayana, G.; Nuyens, D.; Cools, R. Reconstruction and collocation of a class of non-periodic functions by sampling along tent-transformed rank-1 lattices, J. Fourier Anal. Appl., Volume 22 (2016) no. 1, pp. 187-214 | MR | Zbl | DOI

[47] Temlyakov, V. N. On approximate recovery of functions with bounded mixed derivative, J. Complexity, Volume 9 (1993) no. 1, pp. 41-59 (Festschrift for Joseph F. Traub, Part I) | DOI | MR | Zbl

[48] Trefethen, L. N. Approximation theory and approximation practice, Society for Industrial and Applied Mathematics, 2013, viii+305 pages | DOI | MR

[49] Triebel, H. Theory of function spaces, Modern Birkhäuser Classics, Birkhäuser, 2010, 285 pages | MR

[50] Triebel, Hans Theory of function spaces. II, Monographs in Mathematics, 84, Birkhäuser, 1992, viii+370 pages | DOI | MR

[51] Tropp, J. A. User-friendly tail bounds for sums of random matrices, Found. Comput. Math., Volume 12 (2012) no. 4, pp. 389-434 | DOI | MR | Zbl

[52] Wang, H. New error bounds for Legendre approximations of differentiable functions (2021) (https://arxiv.org/abs/2111.03833) | DOI

[53] Werschulz, A. G.; Woźniakowski, H. Tractability of Multivariate Approximation over a Weighted Unanchored Sobolev Space, Constr. Approx., Volume 30 (2009) no. 3, pp. 395-421 | DOI | Zbl | MR