Search papers, labs, and topics across Lattice.
This paper investigates statistical-to-computational gaps in single- and multi-index models, demonstrating that a Noise Sensitivity Exponent (NSE) governs the emergence and size of these gaps. They show the NSE fully characterizes the computational bottleneck in single-index models with large additive noise. Furthermore, the same exponent controls statistical-computational gaps in multi-index models during specialization and dictates the optimal computational rate in hierarchical models.
A single Noise Sensitivity Exponent (NSE) dictates when learning becomes computationally intractable in high-dimensional single- and multi-index models.
Understanding when learning is statistically possible yet computationally hard is a central challenge in high-dimensional statistics. In this work, we investigate this question in the context of single- and multi-index models, classes of functions widely studied as benchmarks to probe the ability of machine learning methods to discover features in high-dimensional data. Our main contribution is to show that a Noise Sensitivity Exponent (NSE) - a simple quantity determined by the activation function - governs the existence and magnitude of statistical-to-computational gaps within a broad regime of these models. We first establish that, in single-index models with large additive noise, the onset of a computational bottleneck is fully characterized by the NSE. We then demonstrate that the same exponent controls a statistical-computational gap in the specialization transition of large separable multi-index models, where individual components become learnable. Finally, in hierarchical multi-index models, we show that the NSE governs the optimal computational rate in which different directions are sequentially learned. Taken together, our results identify the NSE as a unifying property linking noise robustness, computational hardness, and feature specialization in high-dimensional learning.
