Convergence bounds for empirical nonlinear least-squares

DOI10.1051/M2AN/2021070MaRDI QIDQ5034774zbMATH OpenOpenAlexFDO

Authors Martin Eigel, Reinhold Schneider, Philipp Trunschke

Publication date 21 February 2022

Published in ESAIM: Mathematical Modelling and Numerical Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2001.00639

zbMATH Keywords

convergence rateserror analysistensor networksweighted nonlinear least squaresweighted sparsity

Mathematics Subject Classification ID

Rate of convergence, degree of approximation (41A25) Approximation by other special function classes (41A30) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) General nonlinear regression (62J02)

Abstract: We consider best approximation problems in a nonlinear subset $mathcalM$ of a Banach space of functions $$. The norm is assumed to be a generalization of the $L^2$-norm for which only a weighted Monte Carlo estimate $$ can be computed. The objective is to obtain an approximation $vinmathcalM$ of an unknown function $uinmathcalV$ by minimizing the empirical norm $|u-v{|}_n$. We consider this problem for general nonlinear subsets and establish error bounds for the empirical best approximation error. Our results are based on a restricted isometry property (RIP) which holds in probability and is independent of the nonlinear least squares setting. Several model classes are examined where analytical statements can be made about the RIP and the results are compared to existing sample complexity bounds from the literature. We find that for well-studied model classes our general bound is weaker but exhibits many of the same properties as these specialized bounds. Notably, we demonstrate the advantage of an optimal sampling density (as known for linear spaces) for sets of functions with sparse representations.

Recommendations

• Adaptive sampling recovery and nonlinear approximations of multivariate functions in Besov-type spaces
• Optimal stable nonlinear approximation
• Nonlinear least-squares estimation
• Nonlinear least squares in \(\mathbb R^{N}\)
• Nonparametric least squares estimation of a regression function

Cites work

• A distribution-free theory of nonparametric regression
• An introduction to hierarchical (\(\mathcal H\)-) rank and TT-rank of tensors with examples
• Analysis of discrete L^2 projection on polynomial spaces with random evaluations
• Analysis of the generalization error: empirical risk minimization over deep artificial neural networks overcomes the curse of dimensionality in the numerical approximation of Black-Scholes partial differential equations
• Breaking the coherence barrier: a new theory for compressed sensing
• Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements
• Compressive sensing and structured random matrices
• Convergence estimates in probability and in expectation for discrete least squares with noisy evaluations at random points
• Discrete least squares polynomial approximation with random evaluations - application to parametric and stochastic elliptic PDEs
• scientific article; zbMATH DE number 1390319 (Why is no real title available?)
• Infinite-dimensional compressed sensing and function interpolation
• Interpolation via weighted \(\ell_{1}\) minimization
• Iterative methods based on soft thresholding of hierarchical tensors
• Learning Theory
• Low rank tensor recovery via iterative hard thresholding
• Necessary and Sufficient Conditions for the Uniform Convergence of Means to their Expectations
• New tight frames of curvelets and optimal representations of objects with piecewise C² singularities
• Numerical solution of the parametric diffusion equation by deep neural networks
• On tensor completion via nuclear norm minimization
• On the convergence rate of sparse grid least squares regression
• On the mathematical foundations of learning
• On the Minimax Risk of Dictionary Learning
• Optimal weighted least-squares methods
• Reproducing kernels of Sobolev spaces on \(\mathbb{R}^d\) and applications to embedding constants and tractability
• Shearlet approximation of functions with discontinuous derivatives
• Stable als approximation in the TT-format for rank-adaptive tensor completion
• Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all
• Stable signal recovery from incomplete and inaccurate measurements
• Tail bounds via generic chaining
• Tensor spaces and numerical tensor calculus
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• User-friendly tail bounds for sums of random matrices
• Variational Monte Carlo -- bridging concepts of machine learning and high-dimensional partial differential equations

Cited in

(6)

• Approximative policy iteration for exit time feedback control problems driven by stochastic differential equations using tensor train format
• Adaptive Nonintrusive Reconstruction of Solutions to High-Dimensional Parametric PDEs
• Sample complexity bounds for the local convergence of least squares approximation
• Optimal sampling for least-squares approximation
• Weighted sparsity and sparse tensor networks for least squares approximation
• Some thoughts on compositional tensor networks

Describes a project that uses

Uses Software

• DLMF

This page was built for publication: Convergence bounds for empirical nonlinear least-squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5034774)