https://www.arxiv.org/abs/2109.00190
Analyzes the L2 approximation properties of deep ReLU convolutional neural networks on two-dimensional space. Using the decomposition of convolutional kernels, show the universal approximation.
https://www.arxiv.org/abs/2106.14997
Provide a lower bound on the approximation rates for shallow neural networks, which are obtained by lower bounding the L2 metric entropy of the convex hull of the neural network basis functions.
Deep Neural Networks with ReLU-Sine-Exponential Activations Break Curse of Dimensionality on Hoelder Class
https://www.arxiv.org/abs/2103.00542
For general continuous f on d dimensional box with continuity modulus, construct networks with sufficient approximation rate. This requires d^3/2 width, showing that this networks overcome the curse of dimensionality on Holder functions.
https://www.arxiv.org/abs/2109.11354
Prove that operator NNs of bounded width and arbitrary depth are universal approximators for continuous nonlinear operators.
https://www.arxiv.org/abs/2106.14997
Prove sharp lower bounds on the approximation rates for shallow neural networks, obtained by lower bounding L2 metric entropy of the convex hull of basis functions.
https://www.arxiv.org/abs/2001.03040
Prove that multivariate polynomials can be approximated by deep ReLU networks of with small enough approximation error, then through local Taylor expansions, show that deep ReLU networks can approximate C^s functions.
A proof that deep artificial neural networks overcome the curse of dimensionality in the numerical approximation of Komogorov partial differential equations with constant diffusion and nonlinear drift coefficients
https://www.arxiv.org/abs/1809.07321
Prove that the number of parameters used to describe the employed DNN grows at most polynomially in both the PDE dimension d and the reciprocal of the prescribed approximation accuracy.
https://www.arxiv.org/abs/1911.09647
Develop the techniques to obtain error estimates between solutions of PDEs and approximating ANNs in the uniform L infty sense. Prove that the number of parameters of an ANN to uniformly approximate the classical solution of the heat equation in a region [a,b]^d for a fixed time point T grows at most polynomially in the dimension d and the reciprocal of the approximation precision.
https://www.arxiv.org/abs/1910.09293
Prove that a shallow neural network with some activation functions can arbitrarily well approximate any Lp integrable functions defined on R * [0,1]^n, and moreover integrable function on the Euclidean plane.
https://www.arxiv.org/abs/2111.00215
Show that ResNets are able to approximate solutions of Kolmogorov PDEs with constant diffusion and possibly nonlinear drift coefficients without suffering the curse of dimensionality.
Deep Learning in High Dimension: Neural Network Approximation of Analytic Functions in L2(R^d, gamma_d)
https://www.arxiv.org/abs/2111.07080
Prove expression rates for analytic function, L2 in the gaussian product measure, show the exponential convergence rate. The rate only depend on quantified holomorphy of F, to a product of strips in C^d.
https://www.arxiv.org/abs/2110.03673
Extend the previous work using Radon transform, define Radon-based semi-norms, that function admits an infinite-width neural network representation on a bounded open set when its norm is finite. Derive sparse finite width neural network approximation bounds, and show that infinite width representations are not unique.
https://www.arxiv.org/abs/2103.00502
Construct ReLU networks approximating Hoelder continuous function on [0,1]^d, which is optimal up to constant.
https://www.arxiv.org/abs/2112.12555
Establish universal lower bounds for classification under regularity of decision boundary, and show that for locally Barron-regular decision boundary, the optimal estimation rate are independent of underlying dimension and can be realized by empirical risk minimization.
https://www.arxiv.org/abs/2112.14877
Design a framework for proving universality of activation, using it show various activations including Mish, SiLU, ELU, GELU and some new activation's universality.
https://www.arxiv.org/abs/2201.00217
For nonparametric estimation of Lipscitz operators with deep neural networks, prove non-asymptotic upper bound for generalization error. With the assumption that the target operator exhibits a low dimensional structure, the error bound decays as sample size increases, where rate is determined by intrinsic dimension.
https://www.arxiv.org/abs/2106.10911
For measure preserving neural networks like NICE and RevNets, if there is compact set in R^n > 1, it is able to approximate any measure preserving map which is bounded and injective in the Lp norm.
https://www.arxiv.org/abs/2012.03016
Prove that not only continuous functions, but also all discontinuous functions can be implemented by three-layer networks.
https://www.arxiv.org/abs/1904.05263
Prove that GD can find global minimum exponentially fast, with generalization error established. If the target function is contained in RKHS induced by activation and initialization distribution, there exist generalizable early stopping solution in GD path.
https://www.arxiv.org/abs/2011.02256
Derive the generalization error of a DNN with optimal convergence rate on estimation on non smooth functions with singularities on hypersurfaces. Show that there is a phase where DNNs outperform other standard methods.
https://www.arxiv.org/abs/2202.03841
Show that any target network with inputs in d dimension can be approximated by a width O(d) network, with linearly over parameterized.
Approximation error of single hidden layer neural networks with fixed weights
https://www.arxiv.org/abs/2202.03289
Provides an explicit formula fo the approximation error of single hidden layer neural networks with two fixed weights.
https://www.arxiv.org/abs/2204.06233
For Lipscitz contrained network, ReLU networks have provable disadvantage. Propose learnable spline activation function, and show that this choise is optimal among all component-wise 1-Lipscitz activation functions, in the sense that no other weight constrained architectures can approximate a larger class of functions.
https://www.arxiv.org/abs/2105.02095
Study two-layer neural network with both domain and ranges are Banach spaces with separable preduals. For the lattice operation of taking positive part, prove the inverse and direct approximation theorems with Monte-Carlo rates.
https://www.arxiv.org/abs/2109.08844
Consider the problem of learning the function in second-order Radon-domain bounded variation space, and derive a minimax lower bound for the estimation problem for this function space, and show that the NN estimators are minimax optimal up to logarithmic factors, which do not depend on the curse of dimensionality.
https://www.arxiv.org/abs/2101.12353
Prove that neural networks can transform a low-dimensional source distribution to a distribution that is arbitrarily close to a high-dimensional target distribution, when the closeness are measured by Wasserstein distances and maximum mean discrepancy.
https://www.arxiv.org/abs/1603.00162
Describe a construction based on generalized tensor decompositions that transforms convolutional arithmetic circuits into convolutional rectifier networks, then use tools from the world of arithmetic circuits. Show that convolutional rectifier networks are universal with max pooling but not with average pooling. Also show that depth efficiency is weaker with convolutional rectifier networks than convolutional arithmetic circuits.
https://www.arxiv.org/abs/2206.00934
Show that there exists a neural network that is robust to noise approximation of the finite-dimensional operator with Lipscitz-continuous inverse.
https://www.arxiv.org/abs/2005.11949
Study the expressive power of deep ReLU NNs for approximating functions in dilated shift-invariant spaces, with approximate error bounds w.r.t. width and depth, for the Sobolev spaces and Besov spaces. Also give lower bounds of the Lp approximation error for Sobolev spaces.
https://www.arxiv.org/abs/2105.04156
Show that the approximation scheme of ReLU DNN for x^2 and xy are composition versions of the hierarchical basis approximation in finite element methods, which gives interpretation and proof of approximation of polynomial.
https://www.arxiv.org/abs/2207.08306
Considering the modified ReLU-net which sparsifies the network parameters, show that these class of networks with regularization attain the minimax rate of prediction of unknown beta-smooth functions.
https://www.arxiv.org/abs/2101.12365
Gives an upper bound for non-linear approximation rates, metric entropy, and n-widths of their absolute convex hull, for smoothly parameterized dictionary. Then apply these result for dictionaries of ridge functions that correspond to shallow neural networks. Also provides the lower bound of the metric entropy and n-widths, which gives sharp lower bound on approximation rate for the ReLU^k activations and sigmoidal acitvation, with bounded variatiation.
https://www.arxiv.org/abs/2111.08117
Characterize the class of functions that are representable by linear threshold activation functions, and show that 2 hidden layer is necessary and sufficient. Also give precise bound on the sizes of neural networks to represent any function in the class.
https://www.arxiv.org/abs/2204.11231
Construct the refinement of the usual topology on locally integrable function spaces, where compactly-supported functions can only be approximated in L1-norm by functions with matchine discretized support. Then establish the universality of ReLU-NN with bilinear pooling in this topology.
https://www.arxiv.org/abs/2208.03211
Prove that deep neural netwroks with all non-negative weights are not universal approximators.
Deep ReLU neural networks overcome the curse of dimensionality for partil integrodifferential equations
https://www.arxiv.org/abs/2102.11707
Show that the DNNs with ReLU activation functions are able to express viscosity solutions of linear PIDEs, which arises from a class of jump diffusions.
Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
https://www.arxiv.org/abs/1602.05897
Show that initial representations generated by common random initializations are sufficiently rich to express all functions in the dual kernel space.
https://www.arxiv.org/abs/1610.09887
Prove that various types of simple and natural functions, including indicators of balls and ellipses, non-linear radial functions, smooth non-linear functions, can be better approximated using deeper networks than shallower ones, even if the shallower networks are much larger.
https://www.arxiv.org/abs/2105.14835
Using techniques from mixed-integer optimization, polyhedral theory, tropical geometry, provide a counterbalance to the universal approximation theorem which suggest that a single hidden layer is sufficient for learning tasks. Inverstigate whether the class of exactly representablew functions strictly increases by adding more layers. Also present upper bounds on the sizes of neural networks required to represent functions in these neural hypothesis classes.
https://www.arxiv.org/abs/2208.08138
Show that d-variate polynomials of degree R on interval can be represented as shallow neural networks with fixed width, and use this approximation to minimax optimal rate of convergence of unknown univariate regression function.
Neural Network Approximation of Lipschitz Functions in High Dimensions with Applications to Inverse Problems
https://www.arxiv.org/abs/2208.13305
Assuming the existence of a linear Johnson-Lindenstrauss embedding of a high dimensional set to low dimensional cube, the Lipschitz function from high dimension can be represented by Lipschitz function from low dimension. Using this, show that the neural network can approximate a function with high dimensional input without exponential scale, using JL-embedding as first layer.
Solving parametric partial differential equations with deep rectified quadratic unit neural networks
https://www.arxiv.org/abs/2203.06973
Derive an upper bound on the size of deep ReQU network for learning parameteric PDE, while taking full advantage of the inherent low-dimensionality of the solution manifolds. This upper bound is lower than the lower bound of ReLU network's complexity-bound.
Extending the Universal Approximation Theorem for a Broad Class of Hypercomplex-Valued Neural Networks
https://www.arxiv.org/abs/2203.02456
Introduce the concept of non-degenerate hypercomplex algebra which includes complex numbers, quaternions, and tessariances, and state the universal approximation theorem for the hypercomplex-valued neural networks.
https://www.arxiv.org/abs/2209.01432
First show that the solution to Poisson equation can be numerically approximated by Monte Carlo methods which slightly change the walk on the spheres algorithm, which is efficient w.r.t. approximation error without the curse of dimensionality. Then show that this Monte Carlo solver renders ReLU DNN solutions to Poisson problem, showing that the random DNN provides a small approximation error and low polynomial complexity in the dimension.
https://www.arxiv.org/abs/2104.02095
Show that neural networks with absolute value activation function and the path norm, depth, width having logarithmic dependence on 1/eps can eps-approximate functions that are analytic on certain regions of complex numbers.
Optimal bump functions for shallow ReLU networks: Weight decay, depth separation and the curse of dimensionality
https://www.arxiv.org/abs/2209.01173
Consider the data from radially symmetric distribution with target label 1 at the origin, 0 outside the unit ball, otherwise unknown. With weight decay regularization and in infinite neuron, infinite data limit, prove that a unique radially symmetric minimizer exists, with decay regularizer grow as input dimension. Show that the regularizer decrease exponentially in input dimension if target label is on smaller ball rather than origin. And show that NN with two hidden layers can approximate the target function without this curse of dimensionality.
https://www.arxiv.org/abs/2209.11395
Consider neural networks with an arbitrary set of activation functions, show that both continuous and Lp UAP on compact domain share a universal lower bound of max(dx, dy). The proof is based on the approximation power of neural ODE and ability to approximate it by neural network.
https://www.arxiv.org/abs/2210.02671
Show that any transformer neural network can be translated into an equivlaent fixed-size first-order logic formula which may also use majority quantifiers.
https://www.arxiv.org/abs/2210.10443
Show that the value function and continuation value of an optimal stopping time of high dimensional discrete time Markov process can be approximated with error at most epsilon, with polynomial on dimension.
https://www.arxiv.org/abs/2210.10264
Propose new activation named 'DLU', and show that it has competitive performance for approximation to ReLU and rational network, while having several advantages.
Simultaneous approximation of a smooth function and its derivatives by deep neural networks with piecewise-polynomial activations
https://www.arxiv.org/abs/2206.09527
Derive the required depth, width, and sparsity of the deep neural network to approximate any Hoelder smooth function in Hoelder norm, when all weights are bounded by 1.
https://www.arxiv.org/abs/2212.02223
Prove the Carl's type ineuqalities for the error of approximation of compact sets by deep and shallow neural networks, which gives lower bound on how well we can approximate the functions in K.
https://www.arxiv.org/abs/2206.04360
Show that the approximation of space F by space G in Lp norm can be described with the packing number and range of F, and fat-shattering dimension of G. Using this result, show the lower bound for special function classes like Hoelder balls or multivariate monotonic functions that matches with upper bound up to log factors.
https://www.arxiv.org/abs/2205.13401
Show that the general relative positional encoding based Transformer is not universal approximator as absolute positional encoding, because the softmax attention always generate the right stochastic matrix. Derive sufficient condition for universal approximation, and derive URPE attention that satisfy this condition which multiplies single Toeplitz matrix.
https://www.arxiv.org/abs/2010.12217
Prove the exponential expressivity with ReLU NN in H1 function space, that is locally analytic but admits point singularities and edge singularities, for dimension 2 and 3. This imply the exponential expressivity for the elliptic boundary and eigenvalue problems.
https://www.arxiv.org/abs/2205.14421
Establish the approximation error of the neural network to approximate functional, which are mapping from infinite dimensional space to finite dimension space, which scales as O(1/sqrt(m)), with m as the width, overcoming the curse of dimensionality. The key idea is using Barron spectral space of functionals.
https://www.arxiv.org/abs/2301.04605
Consider deep neural network with intermediate neurons connected by multiplication operation. Consider two classes of target functions, generalized bandlimited functions and Sobolev-type balls. Show that the multiplicative NN achieves fewer layers and neuron compared to ReLU neural networks.
https://www.arxiv.org/abs/2301.12353
Show that the repeated composition of single fixed-size ReLU network with linear map at before and after networks, can approximate any 1-Lipschitz continuous functions with an error O(r^(-1/d)), and for continuous function with error characterized by the modulus of continuity.
https://www.arxiv.org/abs/2301.13091
Show that the neural network with ReLU and x^2 as activation function, can approximate any analytic function and functions in Sobolev space, with constant depth and arbitrary accuracy. Then show how to leverage low local dimensionality to overcome the curse of dimensionality, giving approximation rate that is optimal for unknown lower-dimensional subspace.
https://www.arxiv.org/abs/2008.08427
Show that for the networks with hidden parameter are distributed in a bounded domain, the network may not achieve zero approximation error, and derive a nontrivial approximation error lower bound via ridgelet analysis.
The necessity of depth for artificial neural networks to approximate certain classes of smooth and bounded functions without the curse of dimensionality
https://www.arxiv.org/abs/2301.08284
Show that the product of inputs coordinates or its sign value can neither be approximated without the curse of dimensionality, with shallow or insufficiently deep ReLU NNs, but can be approximated without curse of dimensionality with DNNs.
https://www.arxiv.org/abs/2302.00834
Show that for the N data that are separated by distance d, needs Omega(N) parameters when d is exponentially small in N, which is sharp result in this regime.
https://www.arxiv.org/abs/2302.07937
Show that for random ReLU network with fine-tuning the normalization layer only, can reconstruct any target network that is O(sqrt(width)) smaller.
https://www.arxiv.org/abs/2303.03544
Analyze the number of neurons to approximate multivariate monomial, showing the exponential lower bound for shallow neural network. This lower bound do not hold for normalized lipschiz monomials, so the shallow ReLU network suffer curse of dimensionality when Lipschiz parameter scales with the dimension.
https://www.arxiv.org/abs/2211.00335
Formulate the generic recurrent neural network, and provide the approximation error bounds for filtering in non-compact domains, and strong time-uniform approximation error bounds.
https://www.arxiv.org/abs/2303.11247
Show that the memorization of n points can be done with conditional ReLU network with O(log n) operations, where ReLU NNs need O(sqrt(n)) operations. Show that this is best possible.
https://www.arxiv.org/abs/2303.12147
Show the universal approximation of HDNNs, and prove that a portion of the flow of HDNNs can approximate arbitrary well any continuous functions.
https://www.arxiv.org/abs/2211.13866
Prove the universality of deep narrow RNNs and show the upper bound of the minimum width can be independent to the length of data.
https://www.arxiv.org/abs/2303.16813
Show that shallow complex neural networks can approximate any function in complex cube, and Ck function with error m^(-k/2n) where m is number of neurons, and n is the dimension of space, when activation is smooth but not polyharmonics. Also show that the weight selection is continuous w.r.t. target function, and prove the derived approximation rate is optimal for this selection.
https://www.arxiv.org/abs/2201.09418
Prove the upper and lower bounds on the weight norm constrained networks for smooth function classes, where lower bound is derived via Rademacher complexity. Apply these bounds to show the convergence rate for regression with norm constrained neural networks and distribution estimation of GANs.
https://www.arxiv.org/abs/2304.01880
Study the approximation properties with weights varying on finitely many directions and thresholds from an open interval. Obtain a necessary and sufficient measure theoretic condition for density of such networks in the space of continuous functions. Prove a density result for specifically constructed activation and a fixed number of neurons.
Optimal rates of approximation by shallow ReLU^k neural networks and applications to nonparametric regression
https://www.arxiv.org/abs/2304.01561
Study the approximation of ReLU^k neural networks, and show that sufficiently smooth functions with finite variation norms are approximable. For those with less smoothness, the approximation rate in terms of variation norm is presented.
https://www.arxiv.org/abs/2304.02220
Consider the RBF neural network with smoothing factor replaced with shift, and prove that certain condition on the activation function allow these neural network to approximate any continuous multivariate function on any compact subset.
https://www.arxiv.org/abs/2305.02582
Interpret LayerNorm as projection to d-1 space and scale to have same norm. Using this, show that projection allow the attention to have query that attends to all keys equally, and scaling allow each key to receive the highest attention, preventing the un-select-able keys.
https://www.arxiv.org/abs/2304.13221
Introduce class of neural operators between different geometry, which includes FNO as a special case. Show that this architecture with computation of a spatial average benefits from universal approximation.
A Transfer Principle: Universal Approximators Between Metric Spaces From Euclidean Universal Approximators
https://www.arxiv.org/abs/2304.12231
Construct the universal approximation between arbitrary Polish metric space, using universal approximators between euclidean space, where the approximator returns discrete probability measure. Then prove quantitative guarantee for Hoelder-like maps, including finite graph, rough differential equation between Carnot group, and continuous non-linear operators between Banach space.
https://www.arxiv.org/abs/2210.10264
Consider the activation named as SignReLU, show that these activations outperform rational and ReLU networks in terms of approximation.
https://www.arxiv.org/abs/2305.08753
Introduce the abstract class of neural oscillators, and prove that they are universal to approximate any continuous and casual operator mapping.
Learning on Manifolds: Universal Approximations Properties using Geometric Controllability Conditions for Neural ODEs
https://www.arxiv.org/abs/2305.08849
Design new neural ODE that leave a given manifold invariant, and show that any flow of a manifold-constrained dynamical system can also be approximated using the flow of manifold-constrained neural ODE when controllability condition is satisfied. Also show that this theory works for finite width infinite deep network.
https://www.arxiv.org/abs/2303.03544
Establish an exponential lower bound on the compleixty of any shallow network approximating the product function, and show that lower bound doesn't apply to normalized Lipschitz monomials. This implies that shallow ReLU nets suffer the curse of dimensionality when Lipschitz parameter scales with dimension.
Universal Approximation Properties for an ODENet and a ResNet: Mathematical Analysis and Numerical Experiments
https://www.arxiv.org/abs/2101.10229
Prove a universal approximation for ODENet, that ODENet with width input dim + output dim and nonpolynomial activation function can approximate any continuous function, and ResNet also.
https://www.arxiv.org/abs/2211.14047
Prove that convolutional networks and continuous counterpart can achieve universal approximation with with symmetry at constant channel width, and show non-residual variant with at least two channel and kernel size two.
https://www.arxiv.org/abs/2305.16910
Find the descriptions of activations that finite width infintie depth complex-valued neural networks are universal, that is neight holomorphic nor antiholomorphic, nor R-affine.