Learning with Shallow Neural Networks on Cluster-Structured Features
Not on the map. Why?
Abstract (arXiv)
The success of deep learning in high-dimensional settings is often attributed to the presence of low-dimensional structure in real-world data. While standard theoretical models typically assume that this structure lies in the target function, projecting unstructured inputs onto a low-dimensional subspace, data such as images, text or genomic sequences exhibit strong spatial correlations within the input space itself. In this paper, we propose a tractable model to study how these correlations affect the sample complexity of learning with gradient descent on shallow neural networks. Specifically, we consider targets that depend on a small number of latent Boolean variables, and input features grouped into clusters and correlated with the latent variables. Under an identifiability assumption, we show that for a layerwise gradient-descent variant, the sample complexity scales with the number of hidden variables and, when the signal-to-noise ratio is sufficiently high, is independent of the input dimension, up to logarithmic terms. We empirically test our theoretical findings on both synthetic and real data.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 39 of its 61 references that are in the map. First posted on arXiv 14 May 2026.
Builds on
39 of 61 references.
References · 39
- 2018Estimating the intrinsic dimension of datasets by a minimal neighborhood informationcited by 246
- 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
- 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
- 2016Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Reviewcited by 155
- 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 146
- 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
- 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
- 2021Learning curves of generic features maps for realistic datasets with a teacher-student modelcited by 126
- 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
- 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
- 2024A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Datacited by 88
- 2020Learning Parities with Neural Networkscited by 77
27 more
- 2023How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Modelcited by 70
- 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 67
- 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 67
- 2020The role of regularization in classification of high-dimensional noisy Gaussian mixturecited by 63
- 2020Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classificationcited by 60
- 2023Identifiability of latent-variable and structural-equation models: from linear to nonlinearcited by 58
- 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
- 2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
- 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 39
- 2024Towards a theory of how the structure of language is acquired by deep neural networkscited by 38
- 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 36
- 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
- 2023Gradient-Based Feature Learning under Structured Datacited by 32
- 2024Probing the Latent Hierarchical Structure of Data via Diffusion Modelscited by 25
- 2025How Compositional Generalization and Creativity Improve as Diffusion Models are Trainedcited by 24
- 2016Deep Learning and Hierarchal Generative Modelscited by 23
- 2023A Mathematical Model for Curriculum Learning for Paritiescited by 19
- 2024How transformers learn structured data: insights from hierarchical filteringcited by 18
- 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 13
- 2024Sliding down the stairs: how correlated latent variables accelerate learning with neural networkscited by 12
- 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
- 2013When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsitycited by 7
- 2024Matching the Statistical Query Lower Bound for k-Sparse Parity Problems with Sign Stochastic Gradient Descentcited by 7
- 2025Learning single-index models via harmonic decompositioncited by 7
- 2026Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chainingcited by 5
- 2024Learning with Hidden Factorial Structurecited by 2
- 2026Deep Learning of Compositional Targets with Hierarchical Spectral Methodscited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.