# Convergence bounds for nonlinear least squares and applications to tensor recovery

arXiv: https://arxiv.org/abs/2108.05237 · HTML: https://mlsanity.com/paper/2108.05237/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 58 references that are in the map.
- First posted on arXiv 11 Aug 2021.

## Builds on (most cited first, 10 of 10)

- [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014)
- [A least-squares method for sparse low rank approximation of multivariate functions](https://mlsanity.com/paper/1305.0030/) (2013)
- [Tensor network approaches for learning non-linear dynamical laws](https://mlsanity.com/paper/2002.12388/) (2020)
- [Pricing high-dimensional Bermudan options with hierarchical tensor formats](https://mlsanity.com/paper/2103.01934/) (2021)
- [Learning with tree tensor networks: complexity estimates and model selection](https://mlsanity.com/paper/2007.01165/) (2020)
- [The Restricted Isometry of ReLU Networks: Generalization through Norm Concentration](https://mlsanity.com/paper/2007.00479/) (2020)
- [Approximative Policy Iteration for Exit Time Feedback Control Problems driven by Stochastic Differential Equations using Tensor Train format](https://mlsanity.com/paper/2010.04465/) (2020)
- [A block-sparse Tensor Train Format for sample-efficient high-dimensional Polynomial Regression](https://mlsanity.com/paper/2104.14255/) (2021)
- [PGD-based advanced nonlinear multiparametric regressions for constructing metamodels at the scarce-data limit](https://mlsanity.com/paper/2103.05358/) (2021)
- [Approximating the Stationary Bellman Equation by Hierarchical Tensor Products](https://mlsanity.com/paper/1911.00279/) (2019)

## Built on by (most cited first, 2 of 2)

- [Optimal sampling for least-squares approximation](https://mlsanity.com/paper/2409.02342/) (2024)
- [From continuous-time formulations to discretization schemes: tensor trains and robust regression for BSDEs and parabolic PDEs](https://mlsanity.com/paper/2307.15496/) (2023)

## 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.