Learning Sparse Compositional Functions with Norm-Constrained Neural Networks

• URL: http://arxiv.org/abs/2605.25608v1
• Date: Mon, 25 May 2026 09:02:13 GMT
• Title: Learning Sparse Compositional Functions with Norm-Constrained Neural Networks
• Abstract summary: 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.
• Score: 8.967327976469653
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The ability of deep neural networks to learn hierarchical features is widely regarded as a key mechanism underlying their success in high-dimensional learning. Existing theory partially supports this view by establishing approximation rates based on parameter counts and sample complexity guarantees for compositional models without incurring the curse of dimensionality (CoD). To study overparameterized regimes, where the number of parameters exceeds the sample size, we develop a framework that measures complexity via the parameter norm. Within this approach, we establish approximation rates and excess risk bounds for learning sparse compositional functions whose compositional structure is represented by directed acyclic graphs (DAGs), using Frobenius norm-constrained deep neural networks. Our results have broad applicability since every function that is efficiently Turing computable admits sparse compositional representations. In particular, we cover a range of representative models, including multi-index models, binary tree structures, and general compositional architectures. The rates we derive show that deep networks can exploit the compositional structure of the target functions, effectively avoiding the CoD through hierarchical representations.

Related papers

• Sublinearly Structured Deep Neural Networks Achieve Feature Learning Consistency for Compositional Functions [14.326511406760822]
  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.
  arXiv  Detail & Related papers  (2026-06-22T15:24:53Z)
• 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)
• Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity [15.786915433105868]
  We show that a broad class of feedforward neural networks learn (have finite sample complexity) in the PAC model.<n>Our results reposition finite-sample PAC learnability as a baseline rather than a differentiator.
  arXiv  Detail & Related papers  (2026-05-08T01:26:25Z)
• 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)
• Deep Hierarchical Learning with Nested Subspace Networks [53.71337604556311]
  We propose Nested Subspace Networks (NSNs) for large neural networks.<n>NSNs enable a single model to be dynamically and granularly adjusted across a continuous spectrum of compute budgets.<n>We show that NSNs can be surgically applied to pre-trained LLMs and unlock a smooth and predictable compute-performance frontier.
  arXiv  Detail & Related papers  (2025-09-22T15:13:14Z)
• Instruction-Guided Autoregressive Neural Network Parameter Generation [49.800239140036496]
  We propose IGPG, an autoregressive framework that unifies parameter synthesis across diverse tasks and architectures.<n>By autoregressively generating neural network weights' tokens, IGPG ensures inter-layer coherence and enables efficient adaptation across models and datasets.<n>Experiments on multiple datasets demonstrate that IGPG consolidates diverse pretrained models into a single, flexible generative framework.
  arXiv  Detail & Related papers  (2025-04-02T05:50:19Z)
• Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
  This paper defines upper and lower bounds for neural network widths, which are informed by the polytope structure of the dataset in question. We develop an algorithm to investigate a converse situation where the polytope structure of a dataset can be inferred from its corresponding trained neural networks. It is established that popular datasets such as MNIST, Fashion-MNIST, and CIFAR10 can be efficiently encapsulated using no more than two polytopes with a small number of faces.
  arXiv  Detail & Related papers  (2024-02-04T08:57:42Z)
• How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model [47.617093812158366]
  We introduce the Random Hierarchy Model: a family of synthetic tasks inspired by the hierarchical structure of language and images. We find that deep networks learn the task by developing internal representations invariant to exchanging equivalent groups. Our results indicate how deep networks overcome the curse of dimensionality by building invariant representations.
  arXiv  Detail & Related papers  (2023-07-05T09:11:09Z)
• Reframing Neural Networks: Deep Structure in Overcomplete Representations [41.84502123663809]
  We introduce deep frame approximation, a unifying framework for representation learning with structured overcomplete frames. We quantify structural differences with the deep frame potential, a data-independent measure of coherence linked to representation uniqueness and stability. This connection to the established theory of overcomplete representations suggests promising new directions for principled deep network architecture design.
  arXiv  Detail & Related papers  (2021-03-10T01:15:14Z)
• Dual-constrained Deep Semi-Supervised Coupled Factorization Network with Enriched Prior [80.5637175255349]
  We propose a new enriched prior based Dual-constrained Deep Semi-Supervised Coupled Factorization Network, called DS2CF-Net. To ex-tract hidden deep features, DS2CF-Net is modeled as a deep-structure and geometrical structure-constrained neural network. Our network can obtain state-of-the-art performance for representation learning and clustering.
  arXiv  Detail & Related papers  (2020-09-08T13:10:21Z)
• Generalising Recursive Neural Models by Tensor Decomposition [12.069862650316262]
  We introduce a general approach to model aggregation of structural context leveraging a tensor-based formulation. We show how the exponential growth in the size of the parameter space can be controlled through an approximation based on the Tucker decomposition. By this means, we can effectively regulate the trade-off between expressivity of the encoding, controlled by the hidden size, computational complexity and model generalisation.
  arXiv  Detail & Related papers  (2020-06-17T17:28:19Z)
• When Residual Learning Meets Dense Aggregation: Rethinking the Aggregation of Deep Neural Networks [57.0502745301132]
  We propose Micro-Dense Nets, a novel architecture with global residual learning and local micro-dense aggregations. Our micro-dense block can be integrated with neural architecture search based models to boost their performance.
  arXiv  Detail & Related papers  (2020-04-19T08:34:52Z)
• Supervised Learning for Non-Sequential Data: A Canonical Polyadic Decomposition Approach [85.12934750565971]
  Efficient modelling of feature interactions underpins supervised learning for non-sequential tasks. To alleviate this issue, it has been proposed to implicitly represent the model parameters as a tensor. For enhanced expressiveness, we generalize the framework to allow feature mapping to arbitrarily high-dimensional feature vectors.
  arXiv  Detail & Related papers  (2020-01-27T22:38:40Z)

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.