Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions

Elisabetta Cornacchia, Dan Mikulincer, Elchanan Mossel
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1331-1365, 2025.

Abstract

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 analyzed gradient-based methods, particularly in the setting of isotropic data distributions, often in the context of neural network training. Such studies have uncovered precise characterizations 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-cornacchia25a, title = {Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions}, author = {Cornacchia, Elisabetta and Mikulincer, Dan and Mossel, Elchanan}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {1331--1365}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/cornacchia25a/cornacchia25a.pdf}, url = {https://proceedings.mlr.press/v291/cornacchia25a.html}, abstract = {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 analyzed gradient-based methods, particularly in the setting of isotropic data distributions, often in the context of neural network training. Such studies have uncovered precise characterizations 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.} }
Endnote
%0 Conference Paper %T Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions %A Elisabetta Cornacchia %A Dan Mikulincer %A Elchanan Mossel %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-cornacchia25a %I PMLR %P 1331--1365 %U https://proceedings.mlr.press/v291/cornacchia25a.html %V 291 %X 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 analyzed gradient-based methods, particularly in the setting of isotropic data distributions, often in the context of neural network training. Such studies have uncovered precise characterizations 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.
APA
Cornacchia, E., Mikulincer, D. & Mossel, E.. (2025). Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:1331-1365 Available from https://proceedings.mlr.press/v291/cornacchia25a.html.

Related Material