Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions
This work is significant for researchers and practitioners in high-dimensional statistics, as it provides new insights into the learnability of complex models under randomly biased distributions.
The authors tackled the problem of learning single index and multi index models, and found that introducing a small random perturbation to the data distribution makes high complexity cases rare, allowing for efficient learning of low-dimensional functions. This result applies to Gaussian single index models and sparse Boolean functions.
The problem of learning single index and multi index models has gained significant interest as a fundamental task in high-dimensional statistics. Many recent works have analysed gradient-based methods, particularly in the setting of isotropic data distributions, often in the context of neural network training. Such studies have uncovered precise characterisations of algorithmic sample complexity in terms of certain analytic properties of the target function, such as the leap, information, and generative exponents. These properties establish a quantitative separation between low and high complexity learning tasks. In this work, we show that high complexity cases are rare. Specifically, we prove that introducing a small random perturbation to the data distribution--via a random shift in the first moment--renders any Gaussian single index model as easy to learn as a linear function. We further extend this result to a class of multi index models, namely sparse Boolean functions, also known as Juntas.