Sublinearly Structured Deep Neural Networks Achieve Feature Learning Consistency for Compositional Functions

• URL: http://arxiv.org/abs/2606.23477v1
• Date: Mon, 22 Jun 2026 15:24:53 GMT
• Title: Sublinearly Structured Deep Neural Networks Achieve Feature Learning Consistency for Compositional Functions
• Abstract summary: Deep neural networks (DNNs) have achieved remarkable success on complex machine-learning tasks.<n>We show that sublinearly structured DNNs can attain feature-learning consistency comparable to that of classical models.<n>A structural audit indicates that widely used convolutional neural networks (CNNs), including AlexNet, VGGNet, ResNet, GoogLeNet, are sublinearly structured on their image classification benchmarks.
• Score: 14.326511406760822
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Over the past decade, deep neural networks (DNNs) have achieved remarkable success on complex machine-learning tasks, yet the theoretical foundations of their performance remain incomplete. From a statistical viewpoint, a natural question is: can DNNs attain feature-learning and prediction consistency comparable to that of classical models? While a full characterization is open, we provide positive results for a broad subclass. We establish feature-learning consistency guarantees for sublinearly structured DNNs-architectures whose input/output dimensions and number of hidden neurons grow sublinearly with the sample size-when learning hierarchically compositional target functions. Importantly, this consistency still holds even in the conventional "over-parameterized" regime where the total number of parameters exceeds the number of training samples. Empirically, sublinearly structured DNNs match or surpass wide DNNs in prediction. A structural audit further indicates that widely used convolutional neural networks (CNNs), including AlexNet, VGGNet, ResNet, GoogLeNet, are sublinearly structured on their image classification benchmarks. We further prove that the sublinearly structured DNNs achieve universal approximation for hierarchically compositional functions in the large-sample limit. Moreover, images exhibit an inherent hierarchical, compositional structure. Taken together, these results explain, through a statistical lens, why many large-scale deep learning models succeed after adequate training on massive image datasets.

Related papers

• Learning Sparse Compositional Functions with Norm-Constrained Neural Networks [8.967327976469653]
  We show that deep networks can exploit the compositional structure of the target functions, effectively avoiding the curse of dimensionality (CoD)<n>Our results have broad applicability since every function that is efficiently Turing computable admits sparse compositional representations.
  arXiv  Detail & Related papers  (2026-05-25T09:02:13Z)
• Compositional Sparsity as an Inductive Bias for Neural Architecture Design [35.06894725394093]
  We identify the structural priors that enable Deep Neural Networks to overcome the curse of dimensionality.<n>We present an interpretable pipeline in which abstraction emerges through hierarchical composition.<n>Across a broad suite of real-world datasets, HNNs consistently match or outperform dense baselines while using far fewer parameters.
  arXiv  Detail & Related papers  (2026-05-14T12:26:50Z)
• Generalization Bounds of Spiking Neural Networks via Rademacher Complexity [58.338455812259724]
  Spiking Neural Networks (SNNs) have garnered increasing attention as one of bio-inspired models due to their great potential in neuromorphic computing and computation.<n>Recent advances disclosed an excitation-dependent and architecture-related generalization bound such that the Rademacher complexity of SNNs with firing can be upper bounded by an exponential function.<n>We theoretically investigate the generalization bounds of SNNs with several integration-and-fire schemes via Rademacher complexity.
  arXiv  Detail & Related papers  (2026-04-26T14:24:48Z)
• KVNN: Learnable Multi-Kernel Volterra Neural Networks [6.550684951976901]
  kernelized Volterra Neural Network (kVNN)<n>Experiments on two representative tasks: video action recognition and image denoising.<n>Results are maintained even when trained from scratch without large-scale pretraining.
  arXiv  Detail & Related papers  (2026-04-16T15:18:48Z)
• Mathematical Modeling and Convergence Analysis of Deep Neural Networks with Dense Layer Connectivities in Deep Learning [1.5516092077598485]
  In deep learning, dense layer connectivity has become a key design principle in deep neural networks (DNNs)<n>In this work, we model densely connected DNNs mathematically and analyze their learning problems in the deep-layer limit.
  arXiv  Detail & Related papers  (2025-10-02T14:22:51Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• 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)
• PredRNN: A Recurrent Neural Network for Spatiotemporal Predictive Learning [109.84770951839289]
  We present PredRNN, a new recurrent network for learning visual dynamics from historical context. We show that our approach obtains highly competitive results on three standard datasets.
  arXiv  Detail & Related papers  (2021-03-17T08:28:30Z)
• Evolutionary Architecture Search for Graph Neural Networks [23.691915813153496]
  We propose a novel AutoML framework through the evolution of individual models in a large Graph Neural Networks (GNN) architecture space. To the best of our knowledge, this is the first work to introduce and evaluate evolutionary architecture search for GNN models.
  arXiv  Detail & Related papers  (2020-09-21T22:11:53Z)
• Neural Networks Enhancement with Logical Knowledge [83.9217787335878]
  We propose an extension of KENN for relational data. The results show that KENN is capable of increasing the performances of the underlying neural network even in the presence relational data.
  arXiv  Detail & Related papers  (2020-09-13T21:12:20Z)
• Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks [54.27962244835622]
  This paper proposes a new mean-field framework for over- parameterized deep neural networks (DNNs) In this framework, a DNN is represented by probability measures and functions over its features in the continuous limit. We illustrate the framework via the standard DNN and the Residual Network (Res-Net) architectures.
  arXiv  Detail & Related papers  (2020-07-03T01:37:16Z)

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.