A Look at the Effect of Sample Design on Generalization through the Lens of Spectral Analysis
This provides a foundational framework for understanding and designing sampling methods to improve generalization in machine learning, applicable across various architectures and algorithms.
The paper tackles the problem of how training data sampling affects generalization error by proposing a spectral analysis framework, showing that optimal sampling patterns can be derived from high-dimensional geometry and providing error bounds and convergence rates for state-of-the-art patterns.
This paper provides a general framework to study the effect of sampling properties of training data on the generalization error of the learned machine learning (ML) models. Specifically, we propose a new spectral analysis of the generalization error, expressed in terms of the power spectra of the sampling pattern and the function involved. The framework is build in the Euclidean space using Fourier analysis and establishes a connection between some high dimensional geometric objects and optimal spectral form of different state-of-the-art sampling patterns. Subsequently, we estimate the expected error bounds and convergence rate of different state-of-the-art sampling patterns, as the number of samples and dimensions increase. We make several observations about generalization error which are valid irrespective of the approximation scheme (or learning architecture) and training (or optimization) algorithms. Our result also sheds light on ways to formulate design principles for constructing optimal sampling methods for particular problems.