A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models
This work addresses a central challenge in high-dimensional statistics for researchers and practitioners, providing a unifying framework for analyzing computational bottlenecks in feature learning, though it appears incremental as it builds on existing models and concepts.
The paper tackles the problem of understanding when learning is statistically possible but computationally hard in high-dimensional statistics, specifically in single- and multi-index models, by showing that a Noise Sensitivity Exponent (NSE) governs the existence and magnitude of statistical-to-computational gaps in these 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.