A Quantifier-Reversal Approximation Paradigm for Recurrent Neural Networks

• URL: http://arxiv.org/abs/2511.15326v1
• Date: Wed, 19 Nov 2025 10:43:48 GMT
• Title: A Quantifier-Reversal Approximation Paradigm for Recurrent Neural Networks
• Abstract summary: This paper introduces a fundamentally different approximation paradigm that reverses the quantifier order.<n>For each target function $f$, we construct a single recurrent neural network (RNN) with fixed topology and fixed weights that approximates $f$ to within any prescribed tolerance $> 0$ when run for sufficiently many time steps.<n>Our RNN constructions emulate the structural underlying deep feed-forward ReLU network approximation theory.
• Score: 1.096028999747108
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Classical neural network approximation results take the form: for every function $f$ and every error tolerance $ε> 0$, one constructs a neural network whose architecture and weights depend on $ε$. This paper introduces a fundamentally different approximation paradigm that reverses this quantifier order. For each target function $f$, we construct a single recurrent neural network (RNN) with fixed topology and fixed weights that approximates $f$ to within any prescribed tolerance $ε> 0$ when run for sufficiently many time steps. The key mechanism enabling this quantifier reversal is temporal computation combined with weight sharing: rather than increasing network depth, the approximation error is reduced solely by running the RNN longer. This yields exponentially decaying approximation error as a function of runtime while requiring storage of only a small, fixed set of weights. Such architectures are appealing for hardware implementations where memory is scarce and runtime is comparatively inexpensive. To initiate the systematic development of this novel approximation paradigm, we focus on univariate polynomials. Our RNN constructions emulate the structural calculus underlying deep feed-forward ReLU network approximation theory -- parallelization, linear combinations, affine transformations, and, most importantly, a clocked mechanism that realizes function composition within a single recurrent architecture. The resulting RNNs have size independent of the error tolerance $ε$ and hidden-state dimension linear in the degree of the polynomial.

Related papers

• Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks [0.6153038651687485]
  We study binary classification problems whose decision sets are given by definable sets in o-minimal expansions of the real field.<n>Motivated by cell decomposition of definable sets, we introduce traceable sets as a classical proxy for definable decision regions and analyze their approximation by ReLU neural networks.
  arXiv  Detail & Related papers  (2026-06-29T20:44:20Z)
• Recurrent neural networks approximate continuous functions [1.096028999747108]
  We study the opposite possibility: can the network be chosen once and for all, and can accuracy be bought only by letting it run longer?<n>We prove that this is possible for every continuous function on [-1,1].<n>The mechanism behind the construction is a new intermediate Turing machine with a recurrent neural network (TMNU)
  arXiv  Detail & Related papers  (2026-06-18T15:03:42Z)
• Kronecker-Factored Approximate Curvature for Modern Neural Network Architectures [85.76673783330334]
  Two different settings of linear weight-sharing layers motivate two flavours of Kronecker-Factored Approximate Curvature (K-FAC) We show they are exact for deep linear networks with weight-sharing in their respective setting. We observe little difference between these two K-FAC variations when using them to train both a graph neural network and a vision transformer.
  arXiv  Detail & Related papers  (2023-11-01T16:37:00Z)
• The Onset of Variance-Limited Behavior for Networks in the Lazy and Rich Regimes [75.59720049837459]
  We study the transition from infinite-width behavior to this variance limited regime as a function of sample size $P$ and network width $N$. We find that finite-size effects can become relevant for very small datasets on the order of $P* sim sqrtN$ for regression with ReLU networks.
  arXiv  Detail & Related papers  (2022-12-23T04:48:04Z)
• Neural Network Approximation of Continuous Functions in High Dimensions with Applications to Inverse Problems [6.84380898679299]
  Current theory predicts that networks should scale exponentially in the dimension of the problem. We provide a general method for bounding the complexity required for a neural network to approximate a H"older (or uniformly) continuous function.
  arXiv  Detail & Related papers  (2022-08-28T22:44:07Z)
• Theory of Deep Convolutional Neural Networks III: Approximating Radial Functions [7.943024117353317]
  We consider a family of deep neural networks consisting of two groups of convolutional layers, a down operator, and a fully connected layer. The network structure depends on two structural parameters which determine the numbers of convolutional layers and the width of the fully connected layer.
  arXiv  Detail & Related papers  (2021-07-02T08:22:12Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  Modern machine learning models often employ a huge number of parameters and are typically optimized to have zero training loss. We examine how these benign overfitting phenomena occur in a two-layer neural network setting. We show that it is possible for the two-layer ReLU network interpolator to achieve a near minimax-optimal learning rate.
  arXiv  Detail & Related papers  (2021-06-06T19:08:53Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Random Vector Functional Link Networks for Function Approximation on Manifolds [8.535815777849786]
  We show that single layer neural-networks with random input-to-hidden layer weights and biases have seen success in practice. We further adapt this randomized neural network architecture to approximate functions on smooth, compact submanifolds of Euclidean space.
  arXiv  Detail & Related papers  (2020-07-30T23:50:44Z)
• The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training [10.72393527290646]
  We study phenomena in the context of two-layers neural networks in the neural tangent (NT) regime. We prove that as soon as $Ndgg n$, the test error is well approximated by one of kernel ridge regression with respect to the infinite-width kernel. The latter is in turn well approximated by the error ridge regression, whereby the regularization parameter is increased by a self-induced' term related to the high-degree components of the activation function.
  arXiv  Detail & Related papers  (2020-07-25T01:51:13Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  We study a distributed variable for large-scale AUC for a neural network as with a deep neural network. Our model requires a much less number of communication rounds and still a number of communication rounds in theory. Our experiments on several datasets show the effectiveness of our theory and also confirm our theory.
  arXiv  Detail & Related papers  (2020-05-05T18:08:23Z)
• Interpretable Deep Recurrent Neural Networks via Unfolding Reweighted $\ell_1$-$\ell_1$ Minimization: Architecture Design and Generalization Analysis [19.706363403596196]
  This paper develops a novel deep recurrent neural network (coined reweighted-RNN) by the unfolding of a reweighted minimization algorithm. To the best of our knowledge, this is the first deep unfolding method that explores reweighted minimization. The experimental results on the moving MNIST dataset demonstrate that the proposed deep reweighted-RNN significantly outperforms existing RNN models.
  arXiv  Detail & Related papers  (2020-03-18T17:02: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.