Learning with Shallow Neural Networks on Cluster-Structured Features

• URL: http://arxiv.org/abs/2605.14927v1
• Date: Thu, 14 May 2026 15:02:24 GMT
• Title: Learning with Shallow Neural Networks on Cluster-Structured Features
• Abstract summary: We study how spatial correlations affect the sample complexity of learning with gradient descent on shallow neural networks.<n>We show that for a layerwise gradient-descent variant, the sample complexity scales with the number of hidden variables.<n>We empirically test our theoretical findings on both synthetic and real data.
• Score: 13.080485957000464
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Critical Percolation as a Synthetic Data Model for Interpretability [0.0]
  We introduce a family of synthetic datasets consisting of hierarchical functions defined on critical mean-field percolation clusters.<n>Latent variables modeling a taxonomic hierarchy generate each data point's target value.<n>We find that the model's ground-truth latent variables can be linearly decoded from neural network activations.
  arXiv  Detail & Related papers  (2026-06-18T15:15:57Z)
• Asymptotic Learning Curves for Diffusion Models with Random Features Score and Manifold Data [7.047721358838963]
  We study the theoretical behavior of denoising score matching.<n>We derive exact expressions for the test, train, and score errors in the high-dimensional limit.
  arXiv  Detail & Related papers  (2026-03-24T08:58:12Z)
• Unsupervised detection of semantic correlations in big data [47.201377047286215]
  We present a method to detect semantic correlations in high-dimensional data represented as binary numbers.<n>We estimate the binary intrinsic dimension of a dataset, which quantifies the minimum number of independent coordinates needed to describe the data.<n>The proposed algorithm is largely insensitive to the so-called curse of dimensionality, and can therefore be used in big data analysis.
  arXiv  Detail & Related papers  (2024-11-04T14:37:07Z)
• Learning with Hidden Factorial Structure [2.474908349649168]
  Recent advances suggest that text and image data contain such hidden structures, which help mitigate the curse of dimensionality.<n>We present a controlled experimental framework to test whether neural networks can indeed exploit such "hidden factorial structures"
  arXiv  Detail & Related papers  (2024-11-02T22:32:53Z)
• On Characterizing the Evolution of Embedding Space of Neural Networks using Algebraic Topology [9.537910170141467]
  We study how the topology of feature embedding space changes as it passes through the layers of a well-trained deep neural network (DNN) through Betti numbers. We demonstrate that as depth increases, a topologically complicated dataset is transformed into a simple one, resulting in Betti numbers attaining their lowest possible value.
  arXiv  Detail & Related papers  (2023-11-08T10:45:12Z)
• Gradient-Based Feature Learning under Structured Data [57.76552698981579]
  In the anisotropic setting, the commonly used spherical gradient dynamics may fail to recover the true direction. We show that appropriate weight normalization that is reminiscent of batch normalization can alleviate this issue. In particular, under the spiked model with a suitably large spike, the sample complexity of gradient-based training can be made independent of the information exponent.
  arXiv  Detail & Related papers  (2023-09-07T16:55:50Z)
• Homological Convolutional Neural Networks [4.615338063719135]
  We propose a novel deep learning architecture that exploits the data structural organization through topologically constrained network representations. We test our model on 18 benchmark datasets against 5 classic machine learning and 3 deep learning models.
  arXiv  Detail & Related papers  (2023-08-26T08:48:51Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  We introduce an energy constrained diffusion model which encodes a batch of instances from a dataset into evolutionary states. We provide rigorous theory that implies closed-form optimal estimates for the pairwise diffusion strength among arbitrary instance pairs. Experiments highlight the wide applicability of our model as a general-purpose encoder backbone with superior performance in various tasks.
  arXiv  Detail & Related papers  (2023-01-23T15:18:54Z)
• 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)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)
• Data-driven emergence of convolutional structure in neural networks [83.4920717252233]
  We show how fully-connected neural networks solving a discrimination task can learn a convolutional structure directly from their inputs. By carefully designing data models, we show that the emergence of this pattern is triggered by the non-Gaussian, higher-order local structure of the inputs.
  arXiv  Detail & Related papers  (2022-02-01T17:11:13Z)
• Multi-scale Feature Learning Dynamics: Insights for Double Descent [71.91871020059857]
  We study the phenomenon of "double descent" of the generalization error. We find that double descent can be attributed to distinct features being learned at different scales.
  arXiv  Detail & Related papers  (2021-12-06T18:17:08Z)

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.