Convergence bounds for empirical nonlinear least-squares and applications to tensor recovery

We consider best approximation problems in a nonlinear subset of a Banach space of functions. The norm is assumed to be a generalization of the L2-norm for which only a weighted Monte Carlo estimate can be computed. We establish error bounds for the empirical best approximation error in this general setting and use these bounds to derive a new, 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 random partial differential equation.