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

arXiv: https://arxiv.org/abs/2606.26705 · HTML: https://mlsanity.com/paper/2606.26705/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 210 references that are in the map.
- First posted on arXiv 25 Jun 2026.

## Builds on (most cited first, 15 of 15)

- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness](https://mlsanity.com/paper/2401.08514/) (2024)
- [Mathematical theory of deep learning](https://mlsanity.com/paper/2407.18384/) (2024)
- [Neural Bipartite Matching](https://mlsanity.com/paper/2005.11304/) (2020)
- [Position: A Theory of Deep Learning Must Include Compositional Sparsity](https://mlsanity.com/paper/2507.02550/) (2025)
- [Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity](https://mlsanity.com/paper/2409.12335/) (2024)
- [Generative Neural Operators of Log-Complexity Can Simultaneously Solve Infinitely Many Convex Programs](https://mlsanity.com/paper/2508.14995/) (2025)
- [Analysis of Deep Neural Networks with Quasi-optimal polynomial approximation rates](https://mlsanity.com/paper/1912.02302/) (2019)
- [One model to solve them all: 2BSDE families via neural operators](https://mlsanity.com/paper/2511.01125/) (2025)
- [Transferability of Graph Neural Networks using Graphon and Sampling Theories](https://mlsanity.com/paper/2307.13206/) (2023)
- [Higher-Order Transformer Derivative Estimates for Explicit Pathwise Learning Guarantees](https://mlsanity.com/paper/2405.16563/) (2024)
- [Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms](https://mlsanity.com/paper/2508.18526/) (2025)
- [Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity](https://mlsanity.com/paper/2605.07097/) (2026)
- [Deep greedy unfolding: Sorting out argsorting in greedy sparse recovery algorithms](https://mlsanity.com/paper/2505.15661/) (2025)
- [Certifiable Boolean Reasoning Is Universal](https://mlsanity.com/paper/2602.05120/) (2026)

## Built on by (most cited first, 1 of 1)

- [Into the danger zone: stable extrapolation in high-dimensional function and operator learning](https://mlsanity.com/paper/2609.36709/) (2026)

## Abstract (arXiv)

Feedforward neural network (NN) expressivity is typically studied by emulating optimal basis-expansion schemes. While powerful, this perspective is incomplete: it primarily captures complexity through regularity, and therefore does not distinguish intuitively simple and complicated objects with comparable regularity, such as the square-root function and a typical Brownian path. The guiding message is that neural networks should be viewed not only as flexible basis functions, but also as models of computation. If a function is computable by a real-valued circuit over a prescribed elementary gate language, then it can be computed to comparable accuracy by an NN with explicit depth, width, and non-zero-parameter bounds controlled by the depth, width, gate count, and gate structure. Thus, neural-network complexity is not governed by regularity alone, but also by algorithmic complexity. We then show that any definable NN model satisfying a natural parallelization condition, allowing possibly multivariate non-linearities such as attention or layer normalization, is a universal approximator if and only if it contains a non-affine nonlinearity. The scope of our theory is illustrated by deducing universal approximation guarantees for continuous functions, minimax-optimal approximation guarantees for Besov classes, logarithmic-error complexity for holomorphic functions, and by showing that NNs can emulate numerical algorithms such as Newton-Raphson root finding and power iteration without architecture-specific arguments. Its precision is illustrated by shortest-path computation on k-vertex graphs: compiling the tropical dynamic-programming circuit yields NNs with O(log(1/ε)) non-zero parameters, exponentially improving in 1/ε over the generic O(ε-c k2) Lipschitz-approximation scale, for a constant c>0.