# A Closed-Form Formula for Consistent Lipschitz Regression on Metric Spaces with Sparse Neural Network Realizations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 115 references that are in the map.
- First posted on arXiv 2 Sep 2026.

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

- [Universal approximation property of Banach space-valued random feature models including random neural networks](https://mlsanity.com/paper/2312.08410/) (2023)
- [Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity](https://mlsanity.com/paper/2409.12335/) (2024)
- [An Approximation Theory for Metric Space-Valued Functions With A View Towards Deep Learning](https://mlsanity.com/paper/2304.12231/) (2023)
- [Generating Rectifiable Measures through Neural Networks](https://mlsanity.com/paper/2412.05109/) (2024)
- [Is In-Context Universality Enough? MLPs are Also Universal In-Context](https://mlsanity.com/paper/2502.03327/) (2025)
- [New universal operator approximation theorem for encoder-decoder architectures](https://mlsanity.com/paper/2503.24092/) (2025)
- [Approximation Rates in Besov Norms and Sample-Complexity of Kolmogorov-Arnold Networks with Residual Connections](https://mlsanity.com/paper/2504.15110/) (2025)
- [Do we really need the Rademacher complexities?](https://mlsanity.com/paper/2502.15118/) (2025)
- [Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Data](https://mlsanity.com/paper/2509.00924/) (2025)
- [Improving the matrix multiplication exponent with modern optimization and AlphaEvolve](https://mlsanity.com/paper/2608.16884/) (2026)
- [Adaptivity Under Realizability Constraints: Comparing In-Context and Agentic Learning](https://mlsanity.com/paper/2605.04995/) (2026)
- [Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling](https://mlsanity.com/paper/2605.08377/) (2026)

## Abstract (arXiv)

Several classical machine-learning methods, such as KRRs and SVRs, are both computationally and analytically tractable since their estimators either admit closed-form expressions or are obtained by minimizing convex training objectives; neither feature is generally available for deep neural networks. We address this by introducing a simple closed-form ``two-stage'' compositional formula hatf for reconstructing an unknown Lipschitz function f:X→ ℝ on a metric space (mathcal X,ρ) from N i.i.d. noisy observations. Our main result is a high-probability uniform (L∞) recovery guarantee that jointly controls approximation and statistical errors while enjoying an optimization error of zero; in particular, we do not assume oracle access to an approximate ERM. Our secondary main results establish the optimality of our formula in three complementary senses. 1) Function space: On Ahlfors-regular metric spaces, the hypothesis class parameterized by our formula attains the optimal fat-shattering dimension. 2) Parameter space: Its dependence on the parameters is maximally numerically stable, in the sense that a smaller approximation error cannot be achieved with a smaller Lipschitz dependence on the model parameters. 3) Forward pass: Its dependence on the input is maximally regular, matching the Lipschitz constant of the target function f. When mathcal X=[0,1]d is equipped with the ℓ^∞ norm, hatf admits algorithmic ReLU-MLP and exact ReLU-multi-head transformer realizations of depth O(log(N)) with O(N) nonzero parameters.