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

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.