cs.LGFeb 7, 2026

Neural Networks With Dense Computational Graphs Are Not Universal Approximators

Authors: Levi Rauchwerger, Stefanie Jegelka, Ron Levie

Organizations: Princeton University, Dept of CS · MIT, Dept of EECS and CSAIL · TUM, School of CIT, MCML, MDSI · Technion – IIT, Faculty of Mathematics

Abstract

We investigate the approximation capabilities of dense neural networks. While universal approximation theorems establish that sufficiently large architectures can approximate arbitrary continuous functions when there are no restrictions on the weights, 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.

Figures & tables

Explore similar work

CardsList
  1. Approximation Theory for Neural Networks: Old and New

    May 20, 2026Soumendu Sundar Mukherjee, Himasish TalukdarUniversal ApproximationNeural Network Approximation Theory

  2. Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation

    Jun 25, 2026Anastasis Kratsios, Simone Brugiapaglia, Bum Jun Kim +2Universal ApproximationNeural Network Approximation Theory