cs.LGNov 26, 2025

SUPN: Shallow Universal Polynomial Networks for Efficient Function Approximation

Authors: Zachary Morrow, Michael Penwarden, Brian Chen, Aurya Javeed, Akil Narayan, John D. Jakeman

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Deep neural networks (DNNs) and Kolmogorov-Arnold networks (KANs) are flexible function approximators, but their accuracy can require substantial network depth, width, and trainable parameter counts. Beyond making the resulting networks less transparent, large parameter spaces can increase training cost and produce solutions that are sensitive to optimization and parameter initialization, leading to variability in generalization error. For these reasons, we propose Shallow Universal Polynomial Networks (SUPNs), which retain a single hidden layer while increasing the expressivity of each unit through a learnable multivariate polynomial inside each activation, which we refer to as a polynomial pre-activation. This construction trades architectural depth and width for greater expressivity within each hidden unit, reducing parameter counts and training cost while preserving a shallow computational graph. We establish two complementary universal approximation results: SUPNs are universal by increasing network width at fixed polynomial complexity, as in classical shallow-network approximation, and by increasing polynomial complexity at fixed finite width. We further prove that finite SUPNs can approach the best approximation attainable in a prescribed polynomial space to arbitrary relative tolerance, derive explicit quasi-optimal parameters, and establish corresponding convergence rates. We empirically evaluate SUPNs against DNNs, KANs, and polynomial projection on smooth, nonsmooth, and discontinuous function-approximation problems in one, two, and ten dimensions using more than 16,000 trained models. Across the target functions studied, SUPNs frequently achieve lower approximation error and variability than DNNs and KANs at comparable parameter counts while retaining lower training cost, supporting their use as efficient function approximators when the target structure is not known a priori.

Figures & tables

Figure 1: Illustration of function approximators considered in this work. Note that MLPs and KANs are shown in their single layer form for comparison, but are most often used in a deep (many-layer) configuration compared to SUPNs, which are always a single layer.
Figure 2: Two examples of lower sets, the total-degree space (left) and hyperbolic cross-section (right).
Figure 3: Training losses with Adam, BFGS, and a second-order trust-region method.
Figure 4: 1D target functions for approximation.
Figure 5: Relative L2L^{2} errors vs. trainable parameters using SUPN, DNN, KAN, and polynomial projection for fkf_{k} , k∈[5]k\in[5] .
Figure 6: Standard deviation of relative error over 5 realizations of initial network weights.
Figure 7: Top: Heat map of test errors for f6(x)f_{6}(x) over the hyperparameter sweep. Middle: Corresponding numbers of trainable parameters. Bottom: Time required to compute one backward pass for SUPNs, DNNs, and KANs, averaged over 5000 Adam and 1000 Newton–CG iterations for each architecture. Polynomial projection is omitted because it does not require iterative training, it also takes much less time than the neural networks to perform function approximation. Direct numerical comparisons are in Figure 5 . Compared to DNNs and KANs, SUPNs display continuous accuracy improvement in (N,M)(N,M) along with far lower parameter counts and relative errors.
Figure 8: Ablation study for KANs over grid size GG and spline order for fixed width of N=4N=4 and depth M=4M=4 . The colorbar extents are the same as in Figure 7 . The blue star indicates the default choice of G=5G=5 and third-order splines used in the other KAN results. There is no meaningful change in KAN accuracy over the parameter sweep for this problem.
Figure 9: Median L2L^{2} error (over network initialization) of finite-sampling experiments for different combinations of target function, best approximation accuracy, and sampling strategy. For the “uniform” results, the line is the median over 10 realizations of training data and 5 weight initializations, while the shaded region is the 10th to 90th percentile.
Figure 10: Convergence of SUPN and polynomial projection on Runge function for c=5,10,20c=5,10,20 . Lines of best fit are shown for SUPN.
Figure 11: Surrogate predictions on sinusoid example corresponding to median-error model.
Figure 12: Top: GP realizations. Bottom: Median relative L2L^{2} error over network initialization and GP draws.
Figure 13: 2D target functions for approximation.
Figure 14: Median L2L^{2} error versus number of trainable parameters PP for 2D examples ( fkf_{k} , k=7,8,9k=7,8,9 ).
Figure 15: Median relative L2L^{2} error on anisotropic target function with D=10D=10 input dimensions.
Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

DDInput dimensionL(⋅)\mathcal{L}(\cdot)Loss function
QQOutput dimensionθ\bm{\theta}Learnable parameters
PPParameter dimensionθ^\bm{\hat{\theta}}Best-approximation parameters
Ω\OmegaCompact subset of RD\mathbb{R}^{D}θ~\bm{\tilde{\theta}}Empirically trained parameters
TiT_{i}Chebyshev polynomial of deg. iiσ\sigmaActivation function
LiL_{i}Legendre polynomial of deg. iiBj,iB_{j,i}B-spline of deg. ii on partition jj
KKTraining set sizeϵ\epsilonGeneralization error
Appendix
Table 1: Symbols and notation.
Figure 16: Relative L∞L^{\infty} errors vs. trainable parameters using SUPN, DNN, KAN, and polynomial projection for fkf_{k} , k∈[6]k\in[6] .
 SUPNDNNKAN
NN (width)3, 5, 9, 18,2, 3, 5, 9, 12[6]
27, 35, 40
MM (depth)3, 5, 9, 18,2, 3, 5, 9, 12[5]
27, 35, 40
Appendix
Table 2: Network architectures for 1D examples.
Figure 17: Relative L∞L^{\infty} errors in 2D.
Figure 18: Standard deviation of relative error over 5 realizations of initial network weights for 2D examples. To reduce clutter, only the better-performing of ΛTD\Lambda_{\textrm{TD}} and ΛHC\Lambda_{\textrm{HC}} are shown for SUPN.
Figure 19: Finite-sampling error on the 2D examples.
 SUPN (HC)SUPN (TD)DNNKAN
NN (width)1, 3, 5, 7,1, 3, 5, 7,[10][5]
9, 11, 13, 159, 11, 13, 15
LL (depth)0, 3, 7, 11,0, 2, 4, 6,[10][5]
16, 22, 28, 348, 10, 12, 14
Appendix
Table 3: Network architectures for 2D examples.
 SUPN (HC)DNNKAN
NN (width)5, 10, 15, 2020, 40, 605, 10, 15
LL (depth)[7][4][5]
Appendix
Table 4: Network architectures for 10D example.
Figure 20: Accuracy from training on noisy data.
Figure 21: Plot of best approximation with SUPN on the step functions over (N,M)(N,M) hyperparameter sweep.
Figure 22: Plot of best approximation with DNN on the step functions over (Width,Depth)(Width,Depth) hyperparameter sweep.
Figure 23: Plot of best approximation with KAN on the step functions over (N,M)(N,M) hyperparameter sweep.
Figure 24: Plot of best approximation with polynomial projection on the step functions over (N,M)(N,M) hyperparameter sweep.
Figure 25: Plot of zoomed in discontinuity at x=−0.375x=-0.375 for the step function target. The network approximations shown are drawn from the 5th largest width/depth or M/N models shown in Figures 21 , 22 , and 23 , i.e., along the diagonal, for three different model initializations.
Figure 26: Plot of zoomed in discontinuity at x=−0.375x=-0.375 for the step function target. The network approximations shown are drawn from the 3rd largest width/depth or M/N models shown in Figures 21 , 22 , and 23 , i.e., along the diagonal, for three different model initializations.
Figure 27: Plot of zoomed in discontinuity at x=−0.375x=-0.375 for the step function target. The network approximations shown are drawn from the largest width/depth or M/N models shown in Figures 21 , 22 , and 23 , i.e., along the diagonal, for three different model initializations.
Figure 28: Plot of best approximation with SUPN on the continuous Rastrigin function over (N,M)(N,M) hyperparameter sweep.
Figure 29: Plot of best approximation with DNN on the continuous Rastirgin function over (Width,Depth)(Width,Depth) hyperparameter sweep.
Figure 30: Plot of best approximation with KAN on the continuous Rastirgin function over (Width,Depth)(Width,Depth) hyperparameter sweep.
Figure 31: Plot of best approximation with polynomial projection on the continuous Rastrigin function over (N,M)(N,M) hyperparameter sweep. Each grid cell uses N(M+1)N(M+1) terms, i.e. the same as an SUPN.
More in this topic

Polynomial Neural Networks

Polynomial neural networks use polynomial activations or learned polynomial bases to model nonlinear functions for approximation, scientific computing, and efficient inference.

See all 23 papers

Explore similar work

CardsList
May 20, 2026

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.

Soumendu Sundar Mukherjee, Himasish Talukdar

Statistics and Mathematics Unit, Indian Statistical Institute, Kolkata

Universal ApproximationNeural Network Approximation TheoryFeedforward Neural NetworksNeural Network ExpressivityFunction Approximation
AskPDF
Apr 26, 2026

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.

Vugar Ismailov

Kolmogorov-Arnold NetworksUniversal ApproximationNeural Network Approximation TheoryNeural Network Expressivity
AskPDF
Jun 25, 2026

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.

Anastasis Kratsios, Simone Brugiapaglia, Bum Jun Kim +2

McMaster University & Vector Institute, Toronto, ON, Canada · Concordia University, Montréal, QC, Canada · University of Tokyo, Tokyo, Japan +2

Universal ApproximationNeural Network Approximation TheoryFeedforward Neural NetworksNeural Network ExpressivityFunction Approximation
AskPDF