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

Felix Bartel

doi:10.5802/smai-jcm.96

Felix Bartel ¹

¹Chemnitz University of Technology, Faculty of Mathematics, 09107 Chemnitz, Germany

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

Abstract

Given $n$ samples of a function $f : D \to ℂ$ in random points drawn with respect to a measure $ϱ_{S}$ we develop theoretical analysis of the $L_{2} (D, ϱ_{T})$ -approximation error. For a parituclar choice of $ϱ_{S}$ depending on $ϱ_{T}$ , it is known that the weighted least squares method from finite dimensional function spaces $V_{m}$ , $dim (V_{m}) = 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 $ϱ_{S}$ and the target measure $ϱ_{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_{mix}^{2}$ . Overcoming numerical issues of this $H_{mix}^{2}$ basis, this gives a novel stable approximation method with quadratic error decay. Numerical experiments indicate the applicability of our results.

Article information
Cite this article

Published online: 2023-07-31

DOI: 10.5802/smai-jcm.96

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

Author's affiliations:

Felix Bartel ¹

¹ Chemnitz University of Technology, Faculty of Mathematics, 09107 Chemnitz, Germany

Felix Bartel. Error Guarantees for Least Squares Approximation with Noisy Samples in Domain Adaptation. The SMAI Journal of computational mathematics, Volume 9 (2023), pp. 95-120. doi: 10.5802/smai-jcm.96

@article{SMAI-JCM_2023__9__95_0,
     author = {Felix Bartel},
     title = {Error {Guarantees} for {Least} {Squares} {Approximation} with {Noisy} {Samples} in {Domain} {Adaptation}},
     journal = {The SMAI Journal of computational mathematics},
     pages = {95--120},
     year = {2023},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {9},
     doi = {10.5802/smai-jcm.96},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.96/}
}

TY  - JOUR
AU  - Felix Bartel
TI  - Error Guarantees for Least Squares Approximation with Noisy Samples in Domain Adaptation
JO  - The SMAI Journal of computational mathematics
PY  - 2023
SP  - 95
EP  - 120
VL  - 9
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.96/
DO  - 10.5802/smai-jcm.96
LA  - en
ID  - SMAI-JCM_2023__9__95_0
ER  -

%0 Journal Article
%A Felix Bartel
%T Error Guarantees for Least Squares Approximation with Noisy Samples in Domain Adaptation
%J The SMAI Journal of computational mathematics
%D 2023
%P 95-120
%V 9
%I Société de Mathématiques Appliquées et Industrielles
%U https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.96/
%R 10.5802/smai-jcm.96
%G en
%F SMAI-JCM_2023__9__95_0

References
Cited by

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

[2] B. Adcock; D. Huybrechs 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] B. Adcock; A. Iserles; S. P. Nørsett 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] Y. Baraud Model selection for regression on a random design, ESAIM, Probab. Stat., Volume 6 (2002), pp. 127-146 | DOI | MR | Numdam | Zbl

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

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

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

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

[9] A. Chkifa; A. Cohen; G. Migliorati; F. Nobile; R. Tempone 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] A. Cohen; M. A. Davenport; D. Leviatan On the stability and accuracy of least squares approximations, Found. Comput. Math., Volume 13 (2013) no. 5, pp. 819-834 | Zbl | MR | DOI

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

[12] R. Cools; F. Y. Kuo; D. Nuyens; G. Suryanarayana 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] J. Dick; D. Nuyens; F. Pillichshammer Lattice rules for nonperiodic smooth integrands, Numer. Math., Volume 126 (2014) no. 2, pp. 259-291 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

[22] J. Hampton; A. Doostan 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] A. Iserles; S. P. Nørsett 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] L. Kämmerer; T. Ullrich; T. Volkmer 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] M. G. Krein On a special class of differential operators, Dokl. Akad. Nauk SSSR, Volume 2 (1935), pp. 345-349

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

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

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

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

[30] S. Lu; P. Mathé; S. V. Pereverzev 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] G. Migliorati; F. Nobile; E. von Schwerin; R. Tempone Analysis of Discrete $L^{2}$ Projection on Polynomial Spaces with Random Evaluations, Found. Comput. Math. (2014) | MR | Zbl | DOI

[32] M. Moeller; T. Ullrich $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] N. Nagel; M. Schäfer; T. Ullrich A New Upper Bound for Sampling Numbers, Found. Comput. Math. (2021) | DOI

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

[35] R. Nasdala; D. Potts 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] S. J. Pan; Q. Yang A Survey on Transfer Learning, IEEE Trans. Knowl. Data Eng., Volume 22 (2010) no. 10, pp. 1345-1359 | DOI

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

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

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

[40] D. Potts; T. Volkmer 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] K. Pozharska; T. Ullrich 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] H. Rauhut; R. Ward Sparse Legendre expansions via $ℓ_{1}$ -minimization, J. Approx. Theory, Volume 164 (2012) no. 5, pp. 517-533 | DOI | MR

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

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

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

[46] G. Suryanarayana; D. Nuyens; R. Cools 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] V. N. Temlyakov 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] L. N. Trefethen Approximation theory and approximation practice, Society for Industrial and Applied Mathematics, 2013, viii+305 pages | DOI | MR

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

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

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

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

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

Cited by Sources: