A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models

• URL: http://arxiv.org/abs/2603.17896v1
• Date: Wed, 18 Mar 2026 16:26:41 GMT
• Title: A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models
• Abstract summary: We show that a Noise Sensitivity Exponent (NSE) governs the existence and magnitude of statistical-to-computational gaps.<n>Our results identify the NSE as a unifying property linking noise robustness, computational hardness, and feature specialization in high-dimensional learning.
• Score: 28.495611422425238
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Meta-Statistical Learning: Supervised Learning of Statistical Inference [59.463430294611626]
  This work demonstrates that the tools and principles driving the success of large language models (LLMs) can be repurposed to tackle distribution-level tasks.<n>We propose meta-statistical learning, a framework inspired by multi-instance learning that reformulates statistical inference tasks as supervised learning problems.
  arXiv  Detail & Related papers  (2025-02-17T18:04:39Z)
• Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions [12.410304632874531]
  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.<n>We extend this result to a class of multi index models, namely sparse Boolean functions, also known as Juntas.
  arXiv  Detail & Related papers  (2025-02-10T13:19:30Z)
• USDRL: Unified Skeleton-Based Dense Representation Learning with Multi-Grained Feature Decorrelation [24.90512145836643]
  We introduce a Unified Skeleton-based Dense Representation Learning framework based on feature decorrelation.<n>We show that our approach significantly outperforms the current state-of-the-art (SOTA) approaches.
  arXiv  Detail & Related papers  (2024-12-12T12:20:27Z)
• How Feature Learning Can Improve Neural Scaling Laws [79.59705237659547]
  We develop a solvable model of neural scaling laws beyond the kernel limit.<n>We show how performance scales with model size, training time, and the total amount of available data.
  arXiv  Detail & Related papers  (2024-09-26T14:05:32Z)
• Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions [20.036783417617652]
  We investigate the training dynamics of two-layer shallow neural networks trained with gradient-based algorithms.<n>We show that a simple modification of the idealized single-pass gradient descent training scenario drastically improves its computational efficiency.<n>Our results highlight the ability of networks to learn relevant structures from data alone without any pre-processing.
  arXiv  Detail & Related papers  (2024-05-24T11:34:31Z)
• Max-Sliced Mutual Information [17.667315953598788]
  Quantifying the dependence between high-dimensional random variables is central to statistical learning and inference. Two classical methods are canonical correlation analysis (CCA), which identifies maximally correlated projected versions of the original variables, and Shannon's mutual information, which is a universal dependence measure. This work proposes a middle ground in the form of a scalable information-theoretic generalization of CCA, termed max-sliced mutual information (mSMI)
  arXiv  Detail & Related papers  (2023-09-28T06:49:25Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Balancing Explainability-Accuracy of Complex Models [8.402048778245165]
  We introduce a new approach for complex models based on the co-relation impact. We propose approaches for both scenarios of independent features and dependent features. We provide an upper bound of the complexity of our proposed approach for the dependent features.
  arXiv  Detail & Related papers  (2023-05-23T14:20:38Z)
• Dynamic Latent Separation for Deep Learning [67.62190501599176]
  A core problem in machine learning is to learn expressive latent variables for model prediction on complex data. Here, we develop an approach that improves expressiveness, provides partial interpretation, and is not restricted to specific applications.
  arXiv  Detail & Related papers  (2022-10-07T17:56:53Z)
• Adaptive Discrete Communication Bottlenecks with Dynamic Vector Quantization [76.68866368409216]
  We propose learning to dynamically select discretization tightness conditioned on inputs. We show that dynamically varying tightness in communication bottlenecks can improve model performance on visual reasoning and reinforcement learning tasks.
  arXiv  Detail & Related papers  (2022-02-02T23:54:26Z)
• Rank-R FNN: A Tensor-Based Learning Model for High-Order Data Classification [69.26747803963907]
  Rank-R Feedforward Neural Network (FNN) is a tensor-based nonlinear learning model that imposes Canonical/Polyadic decomposition on its parameters. First, it handles inputs as multilinear arrays, bypassing the need for vectorization, and can thus fully exploit the structural information along every data dimension. We establish the universal approximation and learnability properties of Rank-R FNN, and we validate its performance on real-world hyperspectral datasets.
  arXiv  Detail & Related papers  (2021-04-11T16:37:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.