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

arXiv: https://arxiv.org/abs/2507.04779 · HTML: https://mlsanity.com/paper/2507.04779/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 60 references that are in the map.
- First posted on arXiv 7 Jul 2025.

## Builds on (most cited first, 27 of 27)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [TabNet: Attentive Interpretable Tabular Learning](https://mlsanity.com/paper/1908.07442/) (2019)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Tabular Data: Deep Learning is Not All You Need](https://mlsanity.com/paper/2106.03253/) (2021)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [When Do Neural Nets Outperform Boosted Trees on Tabular Data?](https://mlsanity.com/paper/2305.02997/) (2023)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [A Kernel-Based View of Language Model Fine-Tuning](https://mlsanity.com/paper/2210.05643/) (2022)
- [Adam Can Converge Without Any Modification On Update Rules](https://mlsanity.com/paper/2208.09632/) (2022)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Convergence rates for the stochastic gradient descent method for non-convex objective functions](https://mlsanity.com/paper/1904.01517/) (2019)
- [FreezeOut: Accelerate Training by Progressively Freezing Layers](https://mlsanity.com/paper/1706.04983/) (2017)
- [The gap between theory and practice in function approximation with deep neural networks](https://mlsanity.com/paper/2001.07523/) (2020)
- [A Selective Overview of Deep Learning](https://mlsanity.com/paper/1904.05526/) (2019)
- [Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces](https://mlsanity.com/paper/2104.02746/) (2021)
- [A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functions](https://mlsanity.com/paper/2108.04620/) (2021)
- [Non-convergence to global minimizers for Adam and stochastic gradient descent optimization and constructions of local minimizers in the training of artificial neural networks](https://mlsanity.com/paper/2402.05155/) (2024)
- [Optimization by gradient boosting](https://mlsanity.com/paper/1707.05023/) (2017)

## Abstract (arXiv)

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 boldsymbolX, while a shallow o1Neuro suffices for additive models with two-way interaction components, including XOR and univariate terms, assuming boldsymbolX ∈ [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 ≤ n ≤ 20000.