Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity

• URL: http://arxiv.org/abs/2605.07097v1
• Date: Fri, 08 May 2026 01:26:25 GMT
• Title: Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity
• Abstract summary: 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.
• Score: 15.786915433105868
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that, in a precise sense, a broad class of feedforward neural networks learn (have finite sample complexity) in the PAC model: every fixed finite feedforward architecture whose layers are definable in an o-minimal structure has finite sample complexity in the agnostic PAC setting, even with unbounded parameters. This covers standard fixed-size MLPs, CNNs, GNNs, and transformers with fixed sequence length, together with the operations and layers typically used in such architectures, including linear projections, residual connections, attention mechanisms, pooling layers, normalization layers, and admissible positional encodings. Hence, distribution-free learnability for modern non-recurrent architectures is not an exceptional property of particular activations or architecture-specific VC arguments, but a consequence of tame feedforward computation. Our results reposition finite-sample PAC learnability as a baseline rather than a differentiator: they shift the focus of architectural comparison toward inductive biases, symmetries and geometric priors, scalability, and optimization behaviour.

Related papers

• Convergence of Gradient Descent for General Neural Network Architectures Beyond the NTK Regime [24.053364183688874]
  Training dynamics is central to understanding neural networks.<n>We propose a convergence framework for analyzing gradient descent dynamics under a broad family of neural network architectures.
  arXiv  Detail & Related papers  (2026-06-22T14:00:26Z)
• 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)
• Invariant-Stratified Propagation for Expressive Graph Neural Networks [9.192992900110983]
  Graph Neural Networks (GNNs) face fundamental limitations in expressivity and capturing structural heterogeneity.<n>We introduce Invariant-Stratified Propagation (ISP), a framework comprising both a novel WL variant (ISP-WL) and its efficient neural network implementation (ISPGNN)<n>ISP stratifies nodes according to graph invariants, processing them in hierarchical strata that reveal structural distinctions invisible to 1-WL.<n>ISP quantifies differences in nodes' structural positions within higher-order patterns, distinguishing interactions where participants occupy different roles from those with uniform participation.
  arXiv  Detail & Related papers  (2026-03-02T02:34:40Z)
• Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Bounds [63.47271262149291]
  We propose a unified framework for PAC-Bayesian norm-based generalization.<n>The key to our approach is a sensitivity matrix that quantifies the network outputs with respect to structured weight perturbations.<n>We derive a family of generalization bounds that recover several existing PAC-Bayesian results as special cases.
  arXiv  Detail & Related papers  (2026-01-13T00:42:22Z)
• The Neural Differential Manifold: An Architecture with Explicit Geometric Structure [8.201374511929538]
  This paper introduces the Neural Differential Manifold (NDM), a novel neural network architecture that explicitly incorporates geometric structure into its fundamental design.<n>We analyze the theoretical advantages of this approach, including its potential for more efficient optimization, enhanced continual learning, and applications in scientific discovery and controllable generative modeling.
  arXiv  Detail & Related papers  (2025-10-29T02:24:27Z)
• Identifiability of Deep Polynomial Neural Networks [1.7510408568923366]
  Polynomial Neural Networks (PNNs) possess a rich algebraic and geometric structure.<n>Their identifiability -- a key property for ensuring interpretability -- remains poorly understood.<n>We present a comprehensive analysis of the identifiability of deep PNNs.
  arXiv  Detail & Related papers  (2025-06-20T15:58:46Z)
• 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)
• DepGraph: Towards Any Structural Pruning [68.40343338847664]
  We study general structural pruning of arbitrary architecture like CNNs, RNNs, GNNs and Transformers. We propose a general and fully automatic method, emphDependency Graph (DepGraph), to explicitly model the dependency between layers and comprehensively group parameters for pruning. In this work, we extensively evaluate our method on several architectures and tasks, including ResNe(X)t, DenseNet, MobileNet and Vision transformer for images, GAT for graph, DGCNN for 3D point cloud, alongside LSTM for language, and demonstrate that, even with a
  arXiv  Detail & Related papers  (2023-01-30T14:02:33Z)
• Equivariant Architectures for Learning in Deep Weight Spaces [54.61765488960555]
  We present a novel network architecture for learning in deep weight spaces. It takes as input a concatenation of weights and biases of a pre-trainedvariant. We show how these layers can be implemented using three basic operations.
  arXiv  Detail & Related papers  (2023-01-30T10:50:33Z)
• Efficient Micro-Structured Weight Unification and Pruning for Neural Network Compression [56.83861738731913]
  Deep Neural Network (DNN) models are essential for practical applications, especially for resource limited devices. Previous unstructured or structured weight pruning methods can hardly truly accelerate inference. We propose a generalized weight unification framework at a hardware compatible micro-structured level to achieve high amount of compression and acceleration.
  arXiv  Detail & Related papers  (2021-06-15T17:22:59Z)
• 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)
• Adversarially Robust Neural Architectures [43.74185132684662]
  This paper aims to improve the adversarial robustness of the network from the architecture perspective with NAS framework. We explore the relationship among adversarial robustness, Lipschitz constant, and architecture parameters. Our algorithm empirically achieves the best performance among all the models under various attacks on different datasets.
  arXiv  Detail & Related papers  (2020-09-02T08:52:15Z)
• A Tree Architecture of LSTM Networks for Sequential Regression with Missing Data [0.0]
  We introduce a novel tree architecture based on the Long Short-Term Memory (LSTM) networks. In our architecture, we employ a variable number of LSTM networks, which use only the existing inputs in the sequence. We achieve significant performance improvements with respect to the state-of-the-art methods for the well-known financial and real life datasets.
  arXiv  Detail & Related papers  (2020-05-22T18:57:47Z)

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.