Research map / Learning theory and algorithms / Sample complexity

Vocabulary for Universal Approximation: A Linguistic Perspective of Mapping Compositions

ICML 2024 · Learning theory and algorithms › Sample complexity · approach: Hardness of learning neural networks · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows constructively that a finite vocabulary of O(d^2) flow maps of ODEs (affine and leaky-ReLU flows) can compose to approximate any orientation-preserving diffeomorphism or continuous map on a compact domain, and models regular languages via flow grammars.

Problem

Whether finitely many mappings suffice, under composition, to achieve universal approximation of continuous functions, motivated by the analogy between sequence models/language and mapping compositions.

Approach

Constructs a finite set V of flow maps of autonomous ODEs (time-scaled ±e_i, ±E_ij x, leaky-ReLU flows with times 1 and sqrt(2)) using Lie product splitting and Kronecker's theorem, so any OP diffeomorphism (and by extension any continuous map in L^p) is approximated by a finite-word composition, with no learnable weights.

Key results

• Proves a finite vocabulary V of O(d^2) flow maps suffices for C-UAP over OP diffeomorphisms on compact domains, and for L^p-UAP over continuous maps for d>=2.
• Shows any DFA language is flowable via a flow grammar (CFSM), with dimension d>=2 independent of the number of DFA states.
• Gives a finite-vocabulary result for linear/vector/matrix spaces using Kronecker's theorem (V_0 = {lambda e_i : lambda in {±1, ±sqrt2}}).

Surprising findings

• A finite vocabulary of fixed-dimension flow maps suffices for universal approximation, so approximation power comes from composition length rather than parameter count.
• Under this construction the required sequence length may be extremely large; the constructed vocabulary is explicitly described as not optimal.

Limitations

• Results restricted to mappings on compact domains; unbounded domains not addressed.
• Constructed vocabulary is not optimal and the required composition length may be extremely large.
• Regular-language model is theoretical; the CFSM is not implemented or tested in practice.

Experimental setup

Baselines: compositional matrix-space model (CMSM) Word2Fun

Builds on: Lie product formula operator splitting Kronecker's approximation theorem neural ODEs compositional matrix-space models

Closest papers by meaning

• How Do Language Models Compose Functions? (NeurIPS 2026 · similarity 0.86)
• Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory (ICLR 2025 · similarity 0.85)
• Universality of Linear Recurrences Followed by Non-linear Projections: Finite-Width Guarantees and Benefits of Complex Eigenvalues (ICML 2024 · similarity 0.85)
• Neural-Symbolic Recursive Machine for Systematic Generalization (ICLR 2024 · similarity 0.85)
• Towards Universality: Studying Mechanistic Similarity Across Language Model Architectures (ICLR 2025 · similarity 0.84)
• Training Neural Networks as Recognizers of Formal Languages (ICLR 2025 · similarity 0.84)