arxiv_ml 80% Match Research Paper Theoretical computer scientists,Machine learning theorists,Researchers in deep learning foundations 3 weeks ago

On efficiently computable functions, deep networks and sparse compositionality

generative-ai › autoregressive

📄 Abstract

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

Authors (1)

Tomaso Poggio

Submitted

October 13, 2025

arXiv Category

cs.LG

arXiv PDF

Key Contributions

This paper demonstrates that efficient Turing computability implies the existence of compositionally sparse circuit representations and corresponding neural approximants. It shows that any efficiently computable function can be represented by a bounded-fan-in Boolean circuit and approximated by a deep neural network of polynomial size and depth.

Business Value

Provides fundamental theoretical insights into the capabilities of deep learning, potentially guiding the design of more efficient and powerful neural network architectures.

Paper Metadata

Innovation Type

Theoretical Result

Deployment Feasibility

N/A (theoretical result)

Limitations Addressed

The theoretical understanding of the relationship between computational complexity and the expressive power of deep neural networks, particularly concerning sparse and compositional structures.

Technical Tags

Efficient computabilityDeep networksSparse compositionalityBounded-fan-in circuitsNeural approximantsBoolean circuitsCompositional approximationHierarchical searchOptimization

Research Topics

Theoretical foundations of deep learningComputability theory and neural networksComplexity theoryCompositionality in AI

Methods & Architectures

Circuit complexityNeural network approximationCompositional analysis Deep neural networksBounded-fan-in Boolean circuits

Applications & Tasks

Theoretical Computer Science Machine Learning Theory Deep Learning Theory Relating computability to network structureUnderstanding the representational power of deep networksAnalyzing compositional approximationConnecting optimization to sparse structures Show existence of sparse circuit representationsConstruct corresponding neural approximantsAchieve target precisionRelate to compositional approximation rates

Related Fields

Theoretical Computer ScienceMachine Learning TheoryComputational ComplexityDeep Learning

Keywords

computabilitydeep networkssparsecompositionalitycircuitsneural networksapproximationcomplexityoptimizationtheorybounded-fan-inBoolean circuitshierarchical search

Academic Context

#Theoretical foundations of deep learning#Computability theory and neural networks#Complexity theory#Compositionality in AI

Commercial Potential

Competitive Edge

Offers a theoretical bridge between computability theory and deep learning, providing foundational understanding rather than a direct application.

Market Opportunity

N/A (theoretical)

Revenue Models

N/A (theoretical)

Resource Requirements

Compute Needs

N/A (theoretical)

Data Requirements

N/A (theoretical)

Deployment Constraints

N/A (theoretical)

Scalability

The theoretical results apply to networks of polynomial size and depth, implying scalability.

Production Readiness

Maturity Level

Theoretical

Time to Market

N/A (theoretical)

Patent Potential

Low, as it's a theoretical result.

View Full Paper Back to Papers