Constructive Universal Approximation and Sure Convergence for Multi-Layer Neural Networks

• URL: http://arxiv.org/abs/2507.04779v2
• Date: Fri, 12 Sep 2025 03:29:11 GMT
• Title: Constructive Universal Approximation and Sure Convergence for Multi-Layer Neural Networks
• Authors: Chien-Ming Chi,
• Abstract summary: o1Neuro is a new neural network model built on sparse indicator activation neurons.<n>At the population level, a deep o1Neuro can approximate any measurable function of $boldsymbolX$.<n>At the sample level, the optimization of o1Neuro reaches an optimal model with probability approaching one after sufficiently many update rounds.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose o1Neuro, a new neural network model built on sparse indicator activation neurons, with two key statistical properties. (1) Constructive universal approximation: At the population level, a deep o1Neuro can approximate any measurable function of $\boldsymbol{X}$, while a shallow o1Neuro suffices for additive models with two-way interaction components, including XOR and univariate terms, assuming $\boldsymbol{X} \in [0,1]^p$ has bounded density. Combined with prior work showing that a single-hidden-layer non-sparse network is a universal approximator, this highlights a trade-off between activation sparsity and network depth in approximation capability. (2) Sure convergence: At the sample level, the optimization of o1Neuro reaches an optimal model with probability approaching one after sufficiently many update rounds, and we provide an example showing that the required number of updates is well bounded under linear data-generating models. Empirically, o1Neuro is compared with XGBoost, Random Forests, and TabNet for learning complex regression functions with interactions, demonstrating superior predictive performance on several benchmark datasets from OpenML and the UCI Machine Learning Repository with $n = 10000$, as well as on synthetic datasets with $100 \le n \le 20000$.

Related papers

• Neural Networks Learn Generic Multi-Index Models Near Information-Theoretic Limit [66.20349460098275]
  We study the gradient descent learning of a general Gaussian Multi-index model $f(boldsymbolx)=g(boldsymbolUboldsymbolx)$ with hidden subspace $boldsymbolUin mathbbRrtimes d$.<n>We prove that under generic non-degenerate assumptions on the link function, a standard two-layer neural network trained via layer-wise gradient descent can agnostically learn the target with $o_d(1)$ test error.
  arXiv  Detail & Related papers  (2025-11-19T04:46:47Z)
• Global Convergence and Rich Feature Learning in $L$-Layer Infinite-Width Neural Networks under $μ$P Parametrization [66.03821840425539]
  In this paper, we investigate the training dynamics of $L$-layer neural networks using the tensor gradient program (SGD) framework.<n>We show that SGD enables these networks to learn linearly independent features that substantially deviate from their initial values.<n>This rich feature space captures relevant data information and ensures that any convergent point of the training process is a global minimum.
  arXiv  Detail & Related papers  (2025-03-12T17:33:13Z)
• No Free Lunch From Random Feature Ensembles [23.661623767100384]
  Given a budget on total model size, one must decide whether to train a single, large neural network or to combine the predictions of many smaller networks.<n>We prove that when a fixed number of trainable parameters are partitioned among $K$ independently trained models, $K=1$ achieves optimal performance.<n>We identify conditions on the kernel and task eigenstructure under which ensembles can achieve near-optimal scaling laws.
  arXiv  Detail & Related papers  (2024-12-06T20:55:27Z)
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep ReLU Networks [0.0]
  We show that any dataset with $N$ distinct points in $mathbbRd$ and $M$ output classes can be exactly classified.<n>We also prove a universal approximation theorem in $Lp(Omega; mathbbRm)$ for any bounded domain.<n>Our results offer a unified and interpretable framework connecting controllability, expressivity, and training dynamics in deep neural networks.
  arXiv  Detail & Related papers  (2024-09-10T14:31:21Z)
• Neural-g: A Deep Learning Framework for Mixing Density Estimation [16.464806944964003]
  Mixing (or prior) density estimation is an important problem in machine learning and statistics. We propose neural-$g$, a new neural network-based estimator for $g$-modeling.
  arXiv  Detail & Related papers  (2024-06-10T03:00:28Z)
• The limitation of neural nets for approximation and optimization [0.0]
  We are interested in assessing the use of neural networks as surrogate models to approximate and minimize objective functions in optimization problems. Our study begins by determining the best activation function for approximating the objective functions of popular nonlinear optimization test problems.
  arXiv  Detail & Related papers  (2023-11-21T00:21:15Z)
• SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem [1.3597551064547502]
  We consider the optimization process of minibatch descent gradient (SGD) on a 2-layer neural network with data separated by a quadratic ground truth function. We prove that with data drawn from the $d$-dimensional Boolean hypercube labeled by the quadratic XOR'' function $y = -x_ix_j$, it is possible to train to a population error $o(1)$ with $d :textpolylog(d)$ samples.
  arXiv  Detail & Related papers  (2023-09-26T17:57:44Z)
• Efficient and Flexible Neural Network Training through Layer-wise Feedback Propagation [49.44309457870649]
  Layer-wise Feedback feedback (LFP) is a novel training principle for neural network-like predictors.<n>LFP decomposes a reward to individual neurons based on their respective contributions.<n>Our method then implements a greedy reinforcing approach helpful parts of the network and weakening harmful ones.
  arXiv  Detail & Related papers  (2023-08-23T10:48:28Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive Coding Networks [65.34977803841007]
  Predictive coding networks are neuroscience-inspired models with roots in both Bayesian statistics and neuroscience. We show how by simply changing the temporal scheduling of the update rule for the synaptic weights leads to an algorithm that is much more efficient and stable than the original one.
  arXiv  Detail & Related papers  (2022-11-16T00:11:04Z)
• Structured Optimal Variational Inference for Dynamic Latent Space Models [16.531262817315696]
  We consider a latent space model for dynamic networks, where our objective is to estimate the pairwise inner products plus the intercept of the latent positions. To balance posterior inference and computational scalability, we consider a structured mean-field variational inference framework.
  arXiv  Detail & Related papers  (2022-09-29T22:10:42Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Neural Inverse Transform Sampler [4.061135251278187]
  We show that when modeling conditional densities with a neural network, $Z$ can be exactly and efficiently computed. We introduce the textbfNeural Inverse Transform Sampler (NITS), a novel deep learning framework for modeling and sampling from general, multidimensional, compactly-supported probability densities.
  arXiv  Detail & Related papers  (2022-06-22T15:28:29Z)
• A Free Lunch with Influence Functions? Improving Neural Network Estimates with Concepts from Semiparametric Statistics [41.99023989695363]
  We explore the potential for semiparametric theory to be used to improve neural networks and machine learning algorithms. We propose a new neural network method MultiNet, which seeks the flexibility and diversity of an ensemble using a single architecture.
  arXiv  Detail & Related papers  (2022-02-18T09:35:51Z)
• Neural Capacitance: A New Perspective of Neural Network Selection via Edge Dynamics [85.31710759801705]
  Current practice requires expensive computational costs in model training for performance prediction. We propose a novel framework for neural network selection by analyzing the governing dynamics over synaptic connections (edges) during training. Our framework is built on the fact that back-propagation during neural network training is equivalent to the dynamical evolution of synaptic connections.
  arXiv  Detail & Related papers  (2022-01-11T20:53:15Z)
• Scalable Lipschitz Residual Networks with Convex Potential Flows [120.27516256281359]
  We show that using convex potentials in a residual network gradient flow provides a built-in $1$-Lipschitz transformation. A comprehensive set of experiments on CIFAR-10 demonstrates the scalability of our architecture and the benefit of our approach for $ell$ provable defenses.
  arXiv  Detail & Related papers  (2021-10-25T07:12:53Z)
• The Rate of Convergence of Variation-Constrained Deep Neural Networks [35.393855471751756]
  We show that a class of variation-constrained neural networks can achieve near-parametric rate $n-1/2+delta$ for an arbitrarily small constant $delta$. The result indicates that the neural function space needed for approximating smooth functions may not be as large as what is often perceived.
  arXiv  Detail & Related papers  (2021-06-22T21:28:00Z)
• 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)
• Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes [15.76663241036412]
  We prove for a large class of activation functions that, if the model memorizes even a fraction of the training, then its Sobolev-seminorm is lower-bounded. Experiments reveal for the first time, (iv) a multiple-descent phenomenon in the robustness of the min-norm interpolator.
  arXiv  Detail & Related papers  (2021-06-04T17:52:50Z)
• 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)
• Model Fusion via Optimal Transport [64.13185244219353]
  We present a layer-wise model fusion algorithm for neural networks. We show that this can successfully yield "one-shot" knowledge transfer between neural networks trained on heterogeneous non-i.i.d. data.
  arXiv  Detail & Related papers  (2019-10-12T22:07:15Z)

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.