Source-linked AI summary
Resolution-Consistent Greedy Neural Approximation on Infinite-Dimensional Spaces
Pablo M. Berná, Antonio Falcó, Diego Mondéjar
TL;DR
The paper addresses the lack of constructive, finite-data guarantees for neural approximation of infinite-dimensional inputs observed through finitely many coordinates. It introduces a parameter-weighted neural variation framework with greedy approximation and fully-corrective empirical learning, obtaining statistical complexity uniform in retained resolution and extending to Hilbert-valued outputs. The dimension-free statements concern statistical complexity, while continuous neuron selection remains computationally nonconvex.
Problem
Existing infinite-dimensional universal approximation results do not by themselves provide neuron-selection rules, width convergence rates, or statistical guarantees from finite data.
Method
The paper uses a parameter-normalized neural dictionary, weighted variation class, greedy approximation, and fully-corrective empirical regression for finite-resolution inputs.
Results
Statistical complexity is uniform in retained input resolution and, for Hilbert-valued responses, has no explicit dependence on output dimension.
Takeaways & Limitations
Within the weighted variation class, approximation and learning errors separate into coordinate-resolution, finite-width, and statistical contributions.
Takeaways & Limitations
The dimension-free guarantee is statistical, not computational: continuous neuron selection remains a nonconvex optimization problem whose cost can grow with retained resolution.
Abstract
from arXiv · showhide
We develop constructive approximation and learning guarantees for shallow neural models with infinite-dimensional inputs observed through finitely many coordinates. The analysis is based on a parameter-normalized neural dictionary and its associated weighted variation class. Within this class, the approximation error separates into a distribution-dependent coordinate-truncation term and a greedy finite-width term. For empirical regression, a fully-corrective greedy procedure yields population guarantees whose statistical complexity is uniform in the retained input resolution. The same framework extends to Hilbert-valued responses without an explicit dependence on the output dimension. The dimension-free statements are statistical, not computational: selecting a new neuron still requires solving a nonconvex parameter-search problem. The quasi-Polish construction underlying recent infinite-dimensional universal approximation results provides a motivating example, and synthetic experiments illustrate the predicted resolution, width, and sample-size regimes.
1 Introduction
The paper develops quantitative, constructive guarantees for greedy neural learning from infinite-dimensional inputs represented at finite resolution. Its weighted variation framework separates resolution, width, and sampling effects while keeping statistical complexity uniform in retained resolution.
- Motivation: Infinite-dimensional inputs require finite-resolution representations before neural models can be trained, introducing coordinate-truncation error alongside width and sampling error.The theory targets functional observations, trajectories, fields, probability measures, and PDE solutions.
- Motivation: Prior universal approximation results establish density on suitable infinite-dimensional and quasi-Polish spaces but do not provide neuron-selection rules, width rates, or finite-data guarantees.The paper turns this qualitative foundation into a quantitative theory.
- Framework: A parameter-weighted neural variation class links coordinate truncation and statistical complexity, while imposing an explicit regularity restriction on admissible targets.The weighted class is not equivalent to the full unweighted span and excludes increasingly sharp examples from fixed-radius balls.
- Guarantees: The population bound decomposes into resolution error + finite-width error + statistical error, with the statistical contribution having no explicit dependence on retained coordinates.In the motivating quasi-Polish example, the first two terms show inverse-resolution and inverse-width behavior, while the statistical term has square-root sample-size dependence up to logarithmic factors.
- Scope: The dimension-uniform result is statistical rather than computational because selecting each new neuron still requires a nonconvex parameter search whose cost may grow with resolution.Experiments therefore use a finite candidate dictionary to illustrate theoretical regimes rather than solve the continuous selection problem efficiently.
- Framework: Greedy selection yields approximation bounds separating resolution and finite-width terms; fully-corrective empirical updates provide an end-to-end population guarantee.The fully-corrective procedure controls the complexity of successive approximants.
- Extensions and evaluation: The statistical argument extends to Hilbert-valued responses without explicit dependence on either retained input dimension or output dimension.Synthetic experiments separately illustrate resolution, width, sample-size, and weighted-versus-unweighted variation effects.
2 Minimal measurable setting
The framework assumes measurable scalar coordinates controlled by a square-summable envelope, with finite-resolution truncation represented by projection onto the first N coordinates.
- Measurable coordinates h_j map the input space into an ℓ2 representation controlled by an envelope α∈ℓ2.
- Finite-resolution observation retains the first N coordinates through the projection P_N, leaving a discarded coordinate tail.
- The analysis distinguishes a distribution-dependent tail from a uniform tail for quantifying truncation.
- The bias is incorporated as an additional Hilbert coordinate, and the envelope supplies a uniform radius for the embedded inputs.
- Quasi-Polish topology and separating-coordinate assumptions motivate density results but are not required for the quantitative estimates.
3 Normalized neural atoms and weighted variation
The paper defines parameter-normalized neural atoms and a weighted variation class whose finite-radius geometry is more restrictive than the corresponding unweighted class, while preserving the dictionary span.
- The bounded activation ρ is 1-Lipschitz and is used to construct normalized neural atoms from internal parameters and bias.
- Under quasi-Polish separating assumptions, weighted atoms are dense in L2(µ), but density does not supply a uniform radius or quantitative universal-approximation rate.
- Parameter normalization preserves the linear span of the neural dictionary but does not preserve fixed-radius variation balls.
- The weighted variation class assigns parameter-dependent costs to neural representations, while the unweighted seminorm omits those costs.
- Weighted variation controls a Lipschitz seminorm relative to the embedding-induced pseudometric.
- For the threshold family, sharper boundaries have weighted variation growing linearly with sharpness while unweighted variation remains uniformly bounded.
4 Quantitative coordinate truncation
Coordinate truncation replaces an infinite-dimensional target by a finite-resolution comparator whose error is controlled by the discarded embedding tail while retaining bounded weighted representation cost.
- The discarded component (I−P_N)H(x) is the embedding tail beyond coordinate N.
- A normalized atom admits a pointwise finite-resolution truncation estimate for every parameter, resolution N, and input x.
- If f has weighted representation cost at most V, its finite-resolution comparator f_N retains normalized representation cost at most V.
5 Population greedy approximation
Population greedy approximation is analyzed in a Hilbert space using normalized dictionaries, yielding a width-dependent residual bound combined with finite-resolution comparison error.
- The Hilbert-space setup uses a symmetric dictionary with atoms bounded by unit norm and measures targets through the atomic gauge K_1(D).
- The recursion inversion gives a 1/(m+3)-type decay bound for the greedy residual sequence.
- Weak greedy selection guarantees a residual correlation proportional to the excess squared error above the comparator error.
- Orthogonal projection onto the enlarged selected span makes residual errors non-increasing and yields a quadratic recursion for the excess error.
- The deterministic width–resolution theorem combines the finite-resolution comparator with the greedy approximation analysis.
6 Rademacher complexity without an explicit resolution factor
The paper establishes Rademacher-complexity bounds for normalized neural dictionaries that remain uniform in the retained input resolution. A separability argument makes the continuum-indexed suprema measurable without introducing an explicit resolution factor.
- Measurability: Continuity in the parameter θ permits replacement of continuum suprema by countable dense subsets, resolving the relevant measurability questions.This applies both to fixed-sample Rademacher suprema and to sample-dependent empirical-process maps.
- Dimension-uniform complexity: The dimension-uniform normalized-dictionary bound has no explicit dependence on the input resolution N.The result applies for every n ≥ 2, every N, and every sample, with an explicit universal constant.
- Proof mechanism: Dyadic shelling combines bounded shell classes with a finite-union inequality to control the full normalized dictionary.The proof uses contraction for the bounded activation and explicitly includes both signs in the shell dictionary.
- Shell decomposition: Each fixed parameter-norm shell has Rademacher complexity O(K/√n) uniformly in N.The doubly logarithmic factor in the full bound comes from the elementary dyadic union argument.
7 Fully-corrective empirical greedy regression
The empirical method uses fully-corrective greedy regression under a fixed weighted variation budget. Its optimization analysis gives a finite-width rate, while the correction constraint preserves statistical control of the iterates.
- Algorithm: Fully-corrective greedy regression selects atoms through a linear minimization oracle and refits active coefficients under the weighted variation budget.The feasible class is convex and has radius at most V and diameter at most 2V.
- Statistical control: The empirical correction is constrained because nearly dependent selected atoms can otherwise make variation-norm coefficients arbitrarily large.Population approximation can use an unconstrained orthogonal refit, but empirical learning requires least squares within the fixed weighted budget.
- Optimization guarantee: The exact-oracle optimization error satisfies Δ_k ≤ 16V^2/(k + 3).The induction uses a first-step bound and step sizes α = 2/(k + 4) thereafter.
- Computational caveat: An inexact oracle with additive accuracy ξ_k = O(V^2/k) preserves an O(V^2/m) optimization rate.The continuous oracle remains a nonconvex optimization problem in N + 1 variables whose cost may grow with N.
- Scope: The same proof does not cover positively homogeneous ReLU because parameter normalization does not produce the required shrinking dyadic tails.The stated complexity lemma relies on bounded activation functions.
8 End-to-end statistical guarantee
The end-to-end theorem transfers approximation and greedy optimization into a population regression guarantee under bounded responses. Its sampling terms contain no explicit dependence on the retained coordinate resolution.
- Theorem 8.1: Theorem 8.1 gives a high-probability population guarantee for the fully-corrective greedy estimator with an exact linear oracle.The theorem assumes |Y| ≤ B almost surely and uses universal constants C1 and C2.
- Resolution dependence: The sampling terms contain no explicit dependence on the coordinate resolution N.This is the paper’s dimension-uniform statistical conclusion for the retained input representation.
- Error decomposition: The final bound combines coordinate-truncation error, finite-width optimization error, and statistical sampling terms.The comparator f_N contributes the resolution approximation term, while Proposition 7.1 supplies the greedy term.
- Canonical envelope: For the canonical envelope |h_j| ≤ 1/j, choosing N ≍ m ≍ √n matches the deterministic squared-error contributions to the global n^−1/2 sampling scale up to logarithmic factors.This gives the stated heuristic balance between resolution, width, and sample size.
9 Synthetic experiments
Finite-candidate experiments separately probe resolution, width, and sample-size effects, then compare weighted and unweighted variation constraints. The experiments illustrate the theory but do not establish tractability of the continuous oracle.
- Experimental design: The experiments use finite candidate dictionaries to isolate coordinate resolution, greedy width, sampling, and weighted-versus-unweighted effects.Their purpose is illustrative rather than validation of theorem constants or a continuous optimization claim.
- Resolution sweep: Increasing retained coordinates monotonically decreases test error in the noiseless resolution sweep, with a sharp drop at N = 48.The dashed N^−1 curve is only a worst-case squared-error reference, and the final drop reflects inclusion of all true atoms.
- Width sweep: Increasing greedy width reduces test error by more than three orders of magnitude, reaching nearly numerical error at m = 20.The target is a 20-atom combination contained in the finite candidate pool, making the endpoint intentionally easy.
- Sample-size sweep: The noisy sample-size sweep is consistent with an approximately n^−1/2 global-complexity scale across the tested range.The experiment uses bounded observation noise and makes no asymptotic claim from the small experiment.
- Weighted versus unweighted variation: Under matched budget V = 8, the unweighted fit remains near numerical accuracy while the weighted fit deteriorates rapidly as sharpness λ exceeds the fixed budget.The theoretical distinction is that the unweighted ball contains the raw atom, whereas the weighted ball excludes f_λ when λ > 8.
- Computational limitation: The finite candidate experiments do not certify that projected-gradient optimization finds the best continuum representation at a given budget.This limitation concerns the numerical optimizer, while the class-separation result is independent of the candidate pool.
10 Hilbert-valued targets
The Hilbert-valued extension retains coordinate-truncation and greedy-learning guarantees while avoiding explicit dependence on output dimension. An analytic linear oracle eliminates the output direction, leaving scalar parameter search.
- Vector-valued variation class: The framework models Hilbert-valued targets using vector atoms with measurable output directions bounded by one.The response space may be finite- or infinite-dimensional, including ℓ2.
- Greedy oracle: The linear oracle reduces neuron selection to a search over the scalar parameter θ, with the optimal output direction obtained in closed form.The direction is recovered by normalizing the Hilbert-valued correlation when it is nonzero.
- Statistical complexity: The dimension-uniform complexity argument uses Hilbert-space duality and does not require an output coordinate basis.The resulting statistical term is independent of both N and dim(Y).
- Statistical guarantee: The fully-corrective vector-valued greedy method achieves a statistical bound with no explicit dependence on retained resolution N or Hilbert dimension dim(Y).The result assumes bounded outputs and a target in the weighted vector variation class.
- Approximation and optimization: The population approximation error combines input coordinate truncation with finite-width approximation for Hilbert-valued targets.Truncating input atoms yields a comparator whose L2 error is bounded by VηN(µ).
- Interpretation: The extension removes output truncation by exploiting the rank-one structure of vector atoms directly.This preserves the coordinate-truncation argument because truncation acts only on the scalar input atom.
Discussion and Conclusion
The discussion places the guarantees inside a weighted regularity class, emphasizes distribution-dependent resolution and computational limits, and identifies Hilbert-valued responses as dimension-uniform statistically. The conclusion separates truncation, width, and sampling errors while retaining explicit scope boundaries.
- Scope and assumptions: The theorem applies to a weighted variation class, not every L2 target covered by an infinite-dimensional universal approximation result.The weighted ball is more restrictive than the unweighted variation ball.
- Scope and assumptions: Fixed weighted balls can exclude increasingly sharp thresholds, so normalization changes the admissible regularity class despite preserving the generated span.In the threshold example, the weighted norm is bounded between λ and 1 + λ while the unweighted norm stays at most one.
- Resolution: The natural resolution measure is the distribution-dependent tail ηN(µ), which can be smaller than the uniform envelope bound for concentrated input laws.This supports data-distribution-dependent resolution choices without changing the statistical-complexity argument.
- Computational boundary: The statistical theorem is uniform in N, but selecting neurons remains a computationally hard nonlinear parameter-search problem.The experiments replace the continuous oracle with a finite candidate pool.
- Extensions: The vector-valued extension suggests nonlinear operator or score learning while already removing explicit output-dimension dependence from the statistical term.A tractable nonlinear neuron oracle and realistic applications remain open requirements.
- Conclusion: The framework separates coordinate truncation, finite greedy width, and finite sampling errors using an ℓ2 coordinate embedding with resolution-independent Hilbert radius.The conclusion also highlights the restrictiveness of the weighted ball and the unresolved nonlinear oracle.