On Explicit Super-Expressive Approximation for Neural Networks

• URL: http://arxiv.org/abs/2607.06781v1
• Date: Tue, 07 Jul 2026 20:21:57 GMT
• Title: On Explicit Super-Expressive Approximation for Neural Networks
• Abstract summary: We investigate the fixed-architecture neural network approximation with explicit parameter bounds and elementary activations.<n>While prior work demonstrated super-expressive approximation using fixed-size networks, they lack quantitative and non-asymptotic characterizations of parameter magnitude with respect to the approximation error.
• Score: 14.904203072235434
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we investigate the fixed-architecture neural network approximation with explicit parameter bounds and elementary activations. While prior work demonstrated super-expressive approximation using fixed-size networks, they lack quantitative and non-asymptotic characterizations of parameter magnitude with respect to the approximation error. We resolve this issue by introducing the Chinese Remainder Theorem as a constructive encoding mechanism. For Lipschitz continuous functions on $[0,1]^D$, we construct a width-$\max\{D,4\}$, depth-$5$ network with explicit parameter-error trade-offs. For Hölder-smooth functions in $C^{r,γ}_A\left([0,1]^D\right)$, our fixed network of width $\max\{2D,\ D+5N+1\}$ and depth $r + 9$ achieves the parameter magnitude $\mathcal{P}$ bounded by $\log_2 \mathcal{P}=\mathcal{O}\bigl(\varepsilon^{-2D/(r+γ)}\log(1/\varepsilon)\bigr)$. This is the dual result compared to those in the parameter-bounded and architecture-unbounded paradigm.

Related papers

• Sharp Approximation Rates for Neural Networks with Affine Latent Parameterizations [6.851715331085056]
  We study a tradeoff between the latent dimension $M$ and the network budget $P$.<n>We prove that the optimal worst-case uniform approximation error over the unit ball of $$-Hlder functions on $[0,1]d$, where $0leq1$, has the sharp order $ bigl(PminM,Pbigr)-/d.
  arXiv  Detail & Related papers  (2026-08-31T17:55:51Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$<n>We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network [11.66117393949175]
  We show that the repeated compositions of a single fixed-size ReLU network exhibit surprising expressive power. Our results reveal that a continuous-depth network generated via a dynamical system has immense approximation power even if its dynamics function is time-independent.
  arXiv  Detail & Related papers  (2023-01-29T04:12:58Z)
• Shallow neural network representation of polynomials [91.3755431537592]
  We show that $d$-variables of degreeR$ can be represented on $[0,1]d$ as shallow neural networks of width $d+1+sum_r=2Rbinomr+d-1d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1d-1[binomr+d-1d-1d-1d-1
  arXiv  Detail & Related papers  (2022-08-17T08:14:52Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• ReLU Network Approximation in Terms of Intrinsic Parameters [5.37133760455631]
  We study the approximation error of ReLU networks in terms of the number of intrinsic parameters. We design a ReLU network with only three intrinsic parameters to approximate H"older continuous functions with an arbitrarily small error.
  arXiv  Detail & Related papers  (2021-11-15T18:20:38Z)
• Neural networks with superexpressive activations and integer weights [91.3755431537592]
  An example of an activation function $sigma$ is given such that networks with activations $sigma, lfloorcdotrfloor$, integer weights and a fixed architecture is given. The range of integer weights required for $varepsilon$-approximation of H"older continuous functions is derived.
  arXiv  Detail & Related papers  (2021-05-20T17:29:08Z)
• Function approximation by deep neural networks with parameters $\{0,\pm \frac{1}{2}, \pm 1, 2\}$ [91.3755431537592]
  It is shown that $C_beta$-smooth functions can be approximated by neural networks with parameters $0,pm frac12, pm 1, 2$. The depth, width and the number of active parameters of constructed networks have, up to a logarithimc factor, the same dependence on the approximation error as the networks with parameters in $[-1,1]$.
  arXiv  Detail & Related papers  (2021-03-15T19:10:02Z)
• Optimal Approximation Rate of ReLU Networks in terms of Width and Depth [5.37133760455631]
  This paper concentrates on the approximation power of deep feed-forward neural networks in terms of width and depth. It is proved that ReLU networks with width $mathcalObig(maxdlfloor N1/drfloor,, N+2big)$ and depth $mathcalO(L)$ can approximate a H"older continuous function on $[0,1]d$ with an approximation rate $mathcalObig(lambdasqrtd (N2L2ln
  arXiv  Detail & Related papers  (2021-02-28T13:15:55Z)
• Neural Network Approximation: Three Hidden Layers Are Enough [4.468952886990851]
  A three-hidden-layer neural network with super approximation power is introduced. Network is built with the floor function ($lfloor xrfloor$), the exponential function ($2x$), the step function ($1_xgeq 0$), or their compositions as the activation function in each neuron.
  arXiv  Detail & Related papers  (2020-10-25T18:30:57Z)
• Deep Network Approximation for Smooth Functions [9.305095040004156]
  We show that deep ReLU networks of width $mathcalO(Nln N)$ and depth $mathcalO(L L)$ can approximate $fin Cs([0,1]d)$ with a nearly optimal approximation error. Our estimate is non-asymptotic in the sense that it is valid for arbitrary width and depth specified by $NinmathbbN+$ and $LinmathbbN+$, respectively.
  arXiv  Detail & Related papers  (2020-01-09T15:06:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.