Neural Networks With Dense Weights Are Not Universal Approximators
cs.LG, stat.ML
Submitted: 2026-02-07
Updated: 2026-09-24
Comments: NeurIPS 2026. Also presented at the GFM Workshop, ICML 2026
Code: https://github.com/levi776/Dense-Neural-Networks-are-not-Universal-Approximators
License: http://creativecommons.org/licenses/by/4.0/
The gist: We investigate the approximation capabilities of dense neural networks.
Terminology
Abstract
We investigate the approximation capabilities of dense neural networks. While universal approximation theorems establish that sufficiently large architectures can approximate arbitrary continuous functions if there are no restrictions on the weight values, we show that dense neural networks do not possess this universality. Our argument is based on a model compression approach, combining the weak regularity lemma with an interpretation of feedforward networks as message passing graph neural networks. We consider ReLU neural networks subject to natural constraints on weights and input and output dimensions, which model a notion of dense connectivity. Within this setting, we demonstrate the existence of Lipschitz continuous functions that cannot be approximated by such networks. This highlights intrinsic limitations of neural networks with dense layers and motivates the use of sparse connectivity as a necessary ingredient for achieving true universality.
Sources
- Sparse Double Descent: Where Network Pruning Aggravates Overfitting
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance
- Edge Directionality Improves Learning on Heterophilic Graphs
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks