Sample complexity bounds for the local convergence of least squares approximation

We consider the problem of approximating a function in a general nonlinear subset of [Formula: see text], when only a weighted Monte Carlo estimate of the [Formula: see text]-norm is accessible. The concept of sample complexity, i.e. the number of sample points necessary to achieve a prescribed error with high probability, is of particular interest in this setting. Reasonable worst-case bounds for this quantity exist only for particular model classes, like linear spaces or sets of sparse vectors. However, the existing bounds are very pessimistic for more general sets, like tensor networks or neural networks. Restricting the model class to a neighborhood of the best approximation allows us to derive improved worst-case bounds for the sample complexity. When the considered neighborhood is a manifold with positive local reach, its sample complexity can be estimated through the sample complexities of the tangent and normal spaces and the manifold’s curvature.