On the Sample Complexity of Subspace Learning

Abstract

A large number of algorithms in machine learning, from principal component analysis (PCA), and its non-linear (kernel) extensions, to more recent spectral embedding and support estimation methods, rely on estimating a linear subspace from samples. In this paper we introduce a general formulation of this problem and derive novel learning error estimates. Our results rely on natural assumptions on the spectral properties of the covariance operator associated to the data distribu- tion, and hold for a wide class of metrics between subspaces. As special cases, we discuss sharp error estimates for the reconstruction properties of PCA and spectral support estimation. Key to our analysis is an operator theoretic approach that has broad applicability to spectral learning methods.

Extendend Version of conference paper

Cited by in corpus (9)

• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Less is More: Nyström Computational Regularization
• Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off
• Kernel regression in high dimensions: Refined analysis beyond double descent
• Interpolation and Learning with Scale Dependent Kernels
• Gain with no Pain: Efficient Kernel-PCA by Nyström Sampling
• Learning Output Embeddings in Structured Prediction
• Statistical Optimality and Computational Efficiency of Nyström Kernel PCA
• Large-scale Kernel Methods and Applications to Lifelong Robot Learning