Convergence bounds for nonlinear least squares and applications to tensor recovery
Not on the map. Why?
Abstract (arXiv)
We consider the problem of approximating a function in general nonlinear subsets of L2 when only a weighted Monte Carlo estimate of the L2-norm can be computed. Of particular interest in this setting is the concept of sample complexity, the number of samples that are necessary to recover the best approximation. Bounds for this quantity have been derived in a previous work and depend primarily on the model class and are not influenced positively by the regularity of the sought function. This result however is only a worst-case bound and is not able to explain the remarkable performance of iterative hard thresholding algorithms that is observed in practice. We reexamine the results of the previous paper and derive a new bound that is able to utilize the regularity of the sought function. A critical analysis of our results allows us to derive a sample efficient algorithm for the model set of low-rank tensors. The viability of this algorithm is demonstrated by recovering quantities of interest for a classical high-dimensional random partial differential equation.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 10 of its 58 references that are in the map. First posted on arXiv 11 Aug 2021.
Builds on
10 of 58 references.
References · 10
- 2014On Tensor Completion via Nuclear Norm Minimizationcited by 32
- 2013A least-squares method for sparse low rank approximation of multivariate functionscited by 10
- 2020Tensor network approaches for learning non-linear dynamical lawscited by 7
- 2021Pricing high-dimensional Bermudan options with hierarchical tensor formatscited by 6
- 2020Learning with tree tensor networks: complexity estimates and model selectioncited by 5
- 2020The Restricted Isometry of ReLU Networks: Generalization through Norm Concentrationcited by 4
- 2020Approximative Policy Iteration for Exit Time Feedback Control Problems driven by Stochastic Differential Equations using Tensor Train formatcited by 4
- 2021A block-sparse Tensor Train Format for sample-efficient high-dimensional Polynomial Regressioncited by 3
- 2021PGD-based advanced nonlinear multiparametric regressions for constructing metamodels at the scarce-data limitcited by 2
- 2019Approximating the Stationary Bellman Equation by Hierarchical Tensor Productscited by 1
Built on by
Citing papers per year: 2023: 1; 2024: 1.
2 papers.