On efficiently computable functions, deep networks and sparse compositionality

2025/10/13 by Tomaso Poggio, Poggio, Tomaso
Computer Science · #Neural Networks and Applications #Computability, Logic, AI Algorithms

paper · pdf · doi:10.48550/arxiv.2510.11942

Abstract

We show that efficient Turing computability at any fixed input/output precision implies the existence of compositionally sparse (bounded-fan-in, polynomial-size) DAG representations and of corresponding neural approximants achieving the target precision. Concretely: if f:[0,1]^d→\R^m is computable in time polynomial in the bit-depths, then for every pair of precisions (n,m_out) there exists a bounded-fan-in Boolean circuit of size and depth \poly(n+m_out) computing the discretized map; replacing each gate by a constant-size neural emulator yields a deep network of size/depth \poly(n+m_out) that achieves accuracy ε=2^-m_out. We also relate these constructions to compositional approximation rates \citeMhaskarPoggio2016b,poggio_deep_shallow₂017,Poggio2017,Poggio2023HowDS and to optimization viewed as hierarchical search over sparse structures.

Citations

• Auto-Regressive Next-Token Predictors are Universal Learners
• Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review
• Benefits of depth in neural networks
• The Power of Depth for Feedforward Neural Networks

Related

• Position: A Theory of Deep Learning Must Include Compositional Sparsity
• Compressed Computation: Dense Circuits in a Toy Model of the Universal-AND Problem
• Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms
• PAC-learning gains of Turing machines over circuits and neural networks
• Optimal Approximation with Sparse Neural Networks and Applications