Convergence bounds for nonlinear least squares and applications to tensor recovery
This work addresses the sample complexity issue in nonlinear least squares for practitioners in computational mathematics and machine learning, offering an incremental improvement over worst-case bounds.
The paper tackles the problem of approximating functions in nonlinear subsets using weighted Monte Carlo estimates, deriving a new bound that leverages function regularity to improve sample complexity, and applies this to develop a sample-efficient algorithm for low-rank tensor recovery, demonstrating its effectiveness on a high-dimensional random PDE.
We consider the problem of approximating a function in general nonlinear subsets of $L^2$ when only a weighted Monte Carlo estimate of the $L^2$-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.