Universal Approximation

Latest papers 19

Sep 29, 2026cs.LG

Kolmogorov-Arnold Classifier Systems as Universal Approximators

As the input dimension nn grows, rule-based machine learning, such as Learning Classifier Systems (LCSs), faces a fundamental scalability bottleneck for function approximation: both rule count and parameter count grow exponentially with nn. Traditional LCSs partition the nn-dimensional input space directly, requiring O(mn)\mathcal{O}(m^n) rules for adequate coverage, where mm is the per-variable resolution. This article breaks from this paradigm by reorganizing rules dimension-wise, guided by the Kolmogorov-Arnold representation theorem: any continuous nn-dimensional function can be expressed as a finite superposition of one-dimensional functions. The proposed Kolmogorov-Arnold Classifier System (KACS) decomposes the target function into one-dimensional subproblems and assigns a dedicated ruleset to each, reducing the worst-case rule count from O(mn)\mathcal{O}(m^n) to O(mn2)\mathcal{O}(mn^2) and replacing nn-dimensional local models with one-dimensional models requiring only two parameters per rule, independent of nn. We also provide the first constructive proof that an LCS, namely KACS, is a universal approximator for continuous functions on compact domains. Evaluated against a direct nn-dimensional input space partitioning approach under otherwise identical conditions, KACS achieves competitive accuracy in many settings while using only 2% to 40% of the parameters. Our implementation is available at https://github.com/YNU-NakataLab/KACS.
Sep 28, 2026cs.LG

Universal Approximation of Measure-to-Measure Operators by Pushforwards

Many learning tasks map an input distribution to an output distribution. A natural way to model such an operator is to transform each input sample using a continuous function that may depend on the entire input distribution, and then take the distribution of the transformed samples. This defines a measure-dependent pushforward model and includes measure-theoretic formulations of transformers. We ask when such models can approximate arbitrary continuous operators between spaces of probability measures. We first show that universal approximation fails when atomic inputs are allowed: some continuous measure-to-measure operators that split or redistribute atomic mass cannot be approximated arbitrarily well by deterministic pushforward models. We then introduce the uniform level set condition, which requires a continuous measure-dependent scalarization whose shrinking level set neighborhoods carry uniformly vanishing mass over the input family. This condition is satisfied, in particular, by compact families of absolutely continuous measures. On every compact family satisfying this condition, we prove that any continuous measure-to-measure operator with outputs of finite pp-th moment can be uniformly approximated, in the pp-Wasserstein distance, by continuous measure-dependent pushforwards. Combining our theorem with existing approximation results for measure-dependent in-context maps yields universal approximation by measure-theoretic transformers. We also extend the framework to continuously-varying source measures, yielding a corresponding universality result for a class of pushforward models that are closely aligned with cross-attention architectures.
Sep 7, 2026cs.LG

Kolmogorov--Arnold stability for discontinuous functions

Here we investigate the stability of the Kolmogorov--Arnold representation theorem (KART) under adversarial reparameterisations of the hidden layer for multivariate discontinuous and unbounded functions. Our results provide a rigorous mathematical foundation for the structural robustness of modern deep learning architectures, such as Kolmogorov--Arnold Networks (KANs), under adversarial configurations.
Aug 11, 2026quant-ph

A Single Atom in Front of a Mirror is a Universal Reservoir Computer

Universal approximation in reservoir computing is typically associated with a class of reservoirs. We show that universality can be associated with a single reservoir, considering a minimal setup of a single atom in front of a mirror. In its linear-transducer limit, our reservoir is a universal approximator of fading-memory maps under an operating class of checkable conditions, with a rate constant measured at the operating point. A given reservoir can reach arbitrary accuracy by changing measurement settings. The proof gives an explicit recipe: for a target accuracy, it specifies the required physical resources and resonator modes. Enlarging the number of accessible modes increases the matchable kernel span without reducing capability. Beyond the linear limit, the atom's saturation replaces high-order polynomial readouts, and the device operates on real-world tasks alongside classical baselines. Our results highlight an example of universality with a minimal quantum setup.
Aug 5, 2026physics.optics

Universal Function Approximation via Diffractive Optical Processors: Physical Limits, Error Bounds, and Learnability

We present a unified theoretical framework connecting classical universal approximation theory, Fourier-feature approximation, and diffractive optical processors. We show that phase-encoded diffractive processors implement finite Fourier-feature expansions whose mathematical completeness follows from Fourier/Stone-Weierstrass arguments, while their physical realizability is governed by finite coefficient synthesis through optimized spatially varying coherent point-spread functions (PSFs). Our analyses derive approximation-error bounds that separate Fourier truncation, PSF-synthesis, input phase error, optical hardware, readout, and noise contributions; establish scaling relationships linking approximation complexity to optical degrees of freedom and input/output space-bandwidth products; derive photon-budget and throughput limits imposed by photon statistics; formulate finite-class statistical learnability bounds for phase-quantized diffractive function approximators; and analyze the impact of spatially incoherent illumination. We further analyze coherent optical cascadability and show that quadratic feature expansion through coherent mixing and optical readout provides a mechanism for enhanced representation while remaining fundamentally distinct from the depth-separation results established for digital neural networks. Our analyses provide a rigorous theoretical foundation for diffractive nonlinear function approximation and establish quantitative relationships among mathematical expressivity, optical hardware resources, statistical learning, and physical performance limits, thereby offering general design principles for large-scale analog optical computing systems.
Jul 6, 2026cs.LG

Minimum Block Width for Universal Approximation by Residual Neural Networks with Inner Width One

In this paper, we study the universal approximation property of residual neural networks, and obtain some new results. For input and output dimensions dxd_x and dyd_y, and LeakyReLU, ReLU, ReLU-like activation functions, the upper and lower bounds of the minimum block width are established. To achieve LpL^p approximation (1≤p<+∞)(1\leq p <+\infty) on any compact domain, we show that the exact minimum block width is max⁡{dx,dy}\max\{d_x,d_y\} when each residual branch has inner width 1. Furthermore, we show that residual neural networks with block width min⁡{dx+dy,max⁡{2dx+1,dy}}\min\{d_x+d_y, \max\{2d_x+1,d_y\}\} can achieve uniform approximation on any compact domain under the constraint that each residual branch has inner width 1. Besides, for any activation function family, we prove that there exist functions that cannot be approximated by residual neural networks with block width less than max⁡{dx,dy}\max\{d_x, d_y\}, both in the LpL^p sense and the uniform sense, regardless of inner width.
Jun 25, 2026cs.LG

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

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 kk-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(ε−ck2)O(ε^{-c k^2}) Lipschitz-approximation scale, for a constant c>0.
Jun 22, 2026cs.LG

EML Trees Are Universal Approximators

The recently introduced EML (Exp-Minus-Log) function acts as continuous analogue of NAND gates, providing a compositional building block capable of representing elementary functions. In this work, we study the expressive power of tree-structured compositions of EML functions. We show that such trees enjoy a universal approximation property for functions in Wk,∞W^{k, \infty} for k∈Nk \in \mathbb N, drawing on classical neural network approximation arguments while exploiting the ability to explicitly construct EML trees that mimic polynomial representations. We further propose a learning algorithm for EML-type trees equipped with fitting parameters, and demonstrate its feasibility in practical optimization problems. Our results establish EML trees as a theoretically grounded framework for function approximation.
Jun 18, 2026cs.LG

Learning universal approximations for partial differential equations with Physics-Informed Broad Learning System

Partial differential equations (PDEs) play a central role in modeling complex physical, biological, and engineering systems. While traditional numerical solvers are robust, they often incur prohibitive computational costs due to mesh dependencies, whereas recent Physics-Informed Neural Networks (PINNs) offer a mesh-free alternative but frequently suffer from slow convergence and optimization instability. To bridge this gap, this article proposes the Physics-Informed Broad Learning System (PIBLS), a novel backpropagation-free framework that reformulates PDE solving as a direct least-squares optimization. We improved an algorithm within this framework to handle nonlinear PDEs efficiently and provide a rigorous mathematical proof establishing the universal approximation property of PIBLS for these equations. Experiments on linear and nonlinear PDEs demonstrate that PIBLS is one to three orders of magnitude faster than conventional PINNs while achieving significantly higher solution accuracy. This framework provides a computationally efficient paradigm for scientific machine learning, offering a practical, high-speed alternative for real-time simulation and design optimization tasks.
Jun 15, 2026stat.ML

Sobolev Approximation by Fixed-Size Neural Networks with Arbitrary Accuracy

In this work, we investigate new activation functions for achieving arbitrary-accuracy Sobolev approximation by fixed-size neural networks. We first show that any function in W2,∞((a,b)d)W^{2,\infty}((a,b)^d) can be approximated with arbitrary accuracy, measured in the W1,∞W^{1,\infty}-norm, by a fixed-size neural network using the Elementary Universal Activation Function (EUAF\mathrm{EUAF}). To extend this result to Ws,∞((a,b)d)W^{s,\infty}((a,b)^d) for s∈Ns\in\mathbb{N}, we introduce a smooth activation DUAF∞\mathrm{DUAF}_{\infty} from the family of Differentiable Universal Activation Functions (DUAFn\mathrm{DUAF}_n). We prove that any function in Ws,∞((a,b)d)W^{s,\infty}((a,b)^d) can be approximated with arbitrary accuracy in the Ws−1,∞W^{s-1,\infty}-norm by a fixed-size DUAF∞\mathrm{DUAF}_{\infty}-activated network. We further construct sigmoidal variants DUAF~n\widetilde{\mathrm{DUAF}}_n and show that, for every 1≤s≤n1\leq s\leq n, fixed-size DUAF~n\widetilde{\mathrm{DUAF}}_n-activated networks still approximate any f∈Ws,∞((a,b)d)f\in W^{s,\infty}((a,b)^d) with arbitrary accuracy in the Ws−1,∞W^{s-1,\infty}-norm. In all these results, the width and depth bounds are computed explicitly, and the proposed activations are elementary.
Jun 8, 2026math.FA

Weighted universal approximation of differentiable maps on infinite-dimensional manifolds

We generalize the universal approximation theorem for functional input neural networks (FNN) to differentiable maps by including the approximation of the derivatives. A FNN maps the input from a possibly infinite-dimensional weighted manifold to the real-valued hidden layer, on which a non-linear scalar activation function is applied, and then returns the output into a Banach space via some linear readouts. By proving a weighted Nachbin theorem, we establish a universal approximation theorem for differentiable maps, which goes beyond the usual formulation on compact sets and also includes the approximation of the derivatives. This leads us to approximation results for non-anticipative functionals including the horizontal and vertical derivatives. As a further application, we show that linear functions of the signature are able to approximate path space functionals including their directional derivatives.
May 27, 2026cs.LG

Expressive Power of Floating-Point Neural Networks with Arbitrary Reduction Orders and Inexact Activation Implementations

Most existing expressivity theories for neural networks assume exact real arithmetic, whereas practical neural networks are executed under finite-precision floating-point arithmetic with implementation-dependent execution semantics. Recent works have begun studying the expressive power of floating-point neural networks, but existing results are limited to highly restricted activation functions and idealized assumptions such as fixed left-to-right reduction orders and correctly rounded activation implementations. In this work, we study the expressive power of floating-point neural networks under generalized floating-point execution semantics, including arbitrary reduction orders and inexact activation implementations with bounded ulp errors. We investigate when floating-point neural networks can represent arbitrary functions between floating-point domains exactly. To this end, we introduce a general distinguishability framework and show that the ability to distinguish every pair of distinct inputs in the first layer is necessary for universal representability. This characterization yields broad classes of activation implementations that are not universal representators, extending previous isolated counterexamples such as the correctly rounded cosine activation. We further prove that a suitable form of distinguishability is also sufficient for universal representability under mild conditions on the activation implementation. Using this framework, we establish universal representability results for a broad class of practical activation functions, including implementations of Sigmoid\mathrm{Sigmoid}, tanh⁡\tanh, ReLU\mathrm{ReLU}, ELU\mathrm{ELU}, SeLU\mathrm{SeLU}, GeLU\mathrm{GeLU}, Swish\mathrm{Swish}, Mish\mathrm{Mish}, and sin⁡\sin, under significantly more realistic floating-point execution models than previously known.
May 22, 2026cs.LG

Any-Dimensional Invariant Universality

Several machine learning models are defined for inputs of any size, such as graphs with different numbers of nodes and point clouds containing varying numbers of points. The universality properties of such any-dimensional models remain poorly understood, as universality is traditionally studied for models accepting inputs of a fixed size, defined on a compact subset of their domain. In sharp contrast, any-dimensional models can be viewed as sequences of functions defined on growing-sized inputs, and it is not clear in which sense they can be universal. We develop a systematic approach to establish any-dimensional universality, by identifying any-dimensional functions with a unique function taking inputs in a suitable infinite-dimensional limit space containing inputs of all finite sizes as well as their limits. Using the symmetries of these inputs and relations between inputs of different sizes, we show that this limit space admits a natural topology with rich families of compact sets on which any-dimensional universality can be established. We illustrate our approach by showing that several existing architectures fail to be universal, and we propose simple modifications that restore universality.
May 20, 2026cs.LG

Approximation Theory for Neural Networks: Old and New

Universal approximation theorems provide a mathematical explanation for the expressive power of neural networks. They assert that, under mild conditions on the activation function, feedforward neural networks are dense in broad function classes, such as continuous functions on compact subsets of Rd\mathbb{R}^d, LpL^p spaces, or Sobolev spaces. Over the past four decades, these qualitative universality results have evolved into a rich quantitative theory addressing approximation rates, parameter efficiency, and the role of architectural features such as depth and width. This survey presents several glimpses into this theory. We review classical density results for single-hidden-layer networks, as well as quantitative bounds that relate approximation error to network size and smoothness assumptions on target functions. Particular emphasis is placed on depth--width trade-offs and on results demonstrating that deeper architectures can achieve superior parameter efficiency for structured function classes. In addition to standard feedforward neural networks, we also review recent developments on Kolmogorov--Arnold Networks (KANs), which offer an alternative architectural paradigm and whose approximation-theoretic properties have begun to attract significant theoretical attention.
May 8, 2026cs.LG

Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling

In many practical applications it is important to build symmetries into neural network architectures. Consider the important case of permutation symmetry on point clouds consisting of nn points in dd dimensions. In this case the network learns a function on a set of nn points in Rd\mathbb{R}^d, and a natural paradigm for constructing invariant networks is Janossy pooling, which generalizes the popular Deep Sets architecture. We study the universality of this approach, in particular the important question of how large the embedding dimension must be to guarantee universality of this architecture. Specifically, using a novel technique, we prove new lower bounds on the required size of this embedding dimension. For Deep Sets, this gives the correct minimal dimension up to a constant factor for all d>1d > 1. For kk-ary Janossy pooling, we prove the first non-trivial lower bound on the required embedding dimension when k>1k > 1.
Apr 27, 2026cs.LG

Progressive Approximation in Deep Residual Networks: Theory and Validation

The Universal Approximation Theorem (UAT) guarantees universal function approximation but does not explain how residual models distribute approximation across layers. We reframe residual networks as a layer-wise approximation process that builds an approximation trajectory from input to target, and prove the existence of progressive trajectories where error decreases monotonically with depth. It reveals that residual networks can implement structured, step-by-step refinement rather than end-to-end (E2E) black-box mapping. Building on this, we propose Layer-wise Progressive Approximation (LPA), a theoretically grounded training principle that explicitly aligns each layer with its residual target to realize such trajectories. LPA is architecture-agnostic: we observe progressive behavior in residual FNNs, ResNets, and Transformers across tasks including complex surface fitting, image classification, and NLP with LLMs for generation and classification. Crucially, this enables ``train once, use NN models": a single network yields useful predictions at every depth, supporting efficient shallow inference without retraining. Our work unifies approximation theory with practical deep learning, providing a new lens on representation learning and a flexible framework for multi-depth deployment. The source code will be released unpon acceptance at https://(open_upon_acceptance).
Apr 26, 2026cs.LG

Necessary and sufficient conditions for universality of Kolmogorov-Arnold networks

We analyze the universal approximation property of Kolmogorov-Arnold Networks (KANs) in terms of their edge functions. If these functions are all affine, then universality clearly fails. How many non-affine functions are needed, in addition to affine ones, to ensure universality? We show that a single one suffices. More precisely, we prove that deep KANs in which all edge functions are either affine or equal to a fixed continuous function σσ are dense in C(K)C(K) for every compact set K⊂RnK\subset\mathbb{R}^n if and only if σσ is non-affine. In contrast, for KANs with exactly two hidden layers, universality holds if and only if σσ is nonpolynomial. We further show that the full class of affine functions is not required; it can be replaced by a finite set without affecting universality. In particular, in the nonpolynomial case, a fixed family of five affine functions suffices when the depth is arbitrary. More generally, for every continuous non-affine function σσ, there exists a finite affine family AσA_σ such that deep KANs with edge functions in Aσ∪{σ}A_σ\cup\{σ\} remain universal. We also prove that KANs with the spline-based edge parameterization introduced by Liu et al.~\cite{Liu2024} are universal approximators in the classical sense, even when the spline degree and knot sequence are fixed in advance.
Dec 18, 2025math.PR

Global universal approximation with Brownian signatures

We establish LpL^p-universal approximation theorems for general path-dependent and non-anticipative functionals on suitable rough path spaces, showing that linear functionals acting on signatures of time-extended rough paths are dense with respect to the LpL^p-distance. To that end, we derive global universal approximation theorems for weighted rough path spaces. We demonstrate that these LpL^p-universal approximation theorems apply to Gaussian processes, in particular, to fractional Brownian motion. As a consequence, linear functionals on the signature of the time-extended Brownian motion can approximate any pp-integrable stochastic process adapted to the Brownian filtration, including solutions to stochastic differential equations.
Date pendingcs.LG

Autonomous-Flow-Based Generation

We show that using autonomous-flow-based generation, one can universally approximate orientation-preserving diffeomorphisms defined on the cube by Neural ODEs with rate O(P−1/d)\mathcal{O}(P^{-1/d}) with PP parameters. On the other hand, we show that by using only a single autonomous flow, the class of Neural ODEs is nowhere dense on the cube in dimension d≥2d \ge 2 . Under a compact-supportid_\mathrm{id} condition on (0,1)d(0,1)^d, we show that using autonomous-flow-based generation, one can universally approximate compactly supportedid_\mathrm{id} diffeomorphisms on (0,1)d(0,1)^d for any dimension with rate O((Plog⁡P)−2/d)\mathcal{O}((\frac{P}{\log P})^{-2/d}) with PP parameters and for compactly supportedid_\mathrm{id} homeomorphisms on (0,1)d(0,1)^d in dimension d≥5d \geq 5 with rate O(P−1/(d+1))\mathcal{O}(P^{-1/(d+1)}) with PP parameters and by a composition of at most IdI_d autonomous Neural ODEs with the same supportid_\mathrm{id}, where IdI_d depends only on the dimension. Moreover, we show that the class of single autonomous flows compactly supportedid_\mathrm{id} on (0,1)d(0,1)^d is meagre in the space of compactly supportedid_\mathrm{id} homeomorphisms on (0,1)d(0,1)^d for d≥2d\ge 2. By linearly lifting the domain into one higher dimension, we obtain a universal approximation result for Lipschitz functions compactly supported on (0,1)d(0,1)^d with rate O(P−1/(d+1))\mathcal{O}(P^{-1/(d+1)}) with PP parameters.