PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral Convergence of Random Feature Method in Multiple Dimensions

Pingbing Ming, Hao Yu

arXiv:2609.03401v1math.NAcs.AIcs.LGmath.ST

TL;DR

The paper addresses multidimensional random feature methods for PDEs, including accuracy, convergence, and severe ill-conditioning. It develops target-uniform spectral approximation theory, transfers it to elliptic problems, and relates spectral accuracy to singular-value decay and conditioning.

  • Problem

    Learning-based PDE solvers face high computational costs, inconsistent accuracy improvement, and severe random feature matrix ill-conditioning in high-accuracy computations.

  • Method

    The analysis combines concentration of empirical feature operators, interpolation-scale estimates, effective-dimension bounds, and abstract strong- and weak-form solver estimates.

  • Results

    The paper proves high-probability spectral convergence from super-exponential to algebraic rates, target-uniform approximation on one event, PDE convergence estimates, and super-exponential or exponential singular-value decay for Fourier or tanh features.

  • Takeaways & Limitations

    A single sampled space and target-specific coefficient vector can deliver simultaneous spectral accuracy across admissible norms, while the same approximation mechanism drives severe ill-conditioning.

  • Takeaways & Limitations

    The theory requires a support assumption on the sampling measure, and further relaxation of coefficient and boundary regularity assumptions is beyond the paper’s scope.

Abstract

from arXiv · show

We first prove spectral convergence of the random feature method (RFM) for multidimensional targets in Sobolev, Gevrey, ultra-analytic, and bandlimited classes. The analysis establishes general high-probability approximation estimates in the interpolation scale generated by a kernel integral operator. On a single event determined only by the sampled features, one random space approximates every target in a prescribed source ball; moreover, for each target, a single coefficient vector defines an approximant that attains spectral accuracy simultaneously in all admissible error norms. For both regularity-adapted frequency distributions and uniform distributions on growing frequency windows, the resulting rates range from super-exponential to algebraic, depending on the regularity of the target. Second, we establish abstract error estimates for strong- and weak-form RFM discretizations, thereby converting the preceding approximation bounds into convergence estimates for multidimensional second-order elliptic boundary value and eigenvalue problems. Finally, for random feature matrices (RFMtxs), we prove super-exponential singular-value decay with Fourier features and exponential decay with $\tanh$ features, together with corresponding condition-number lower bounds. The analysis identifies a common mechanism: the same spectral approximation that yields high accuracy also drives severe ill-conditioning.

1. Introduction

The paper develops a multidimensional spectral-convergence theory for random feature methods, linking target regularity, uniform approximation, PDE discretization, and matrix ill-conditioning. It establishes rates from algebraic to super-exponential and explains why high accuracy coincides with severe conditioning problems.

  • Learning-based PDE solvers are meshfree and flexible, but still face high computational costs and inconsistent accuracy improvements.
  • Random feature methods reduce neural-network training to linear least squares by sampling hidden parameters and optimizing only output coefficients.
  • A single high-probability sampled space approximates every target in a source ball, while each target uses one coefficient vector across all admissible error norms.
  • Rates range from algebraic for Sobolev targets to stretched-exponential, exponential, and super-exponential for higher-regularity classes under adapted or growing-window sampling.The estimates also hold simultaneously in general Sobolev norms W^t,p(Ω), 1 ≤ p ≤ ∞.
  • The approximation bounds transfer to strong- and weak-form elliptic PDE and eigenvalue discretizations, while Fourier and tanh RFMtxs exhibit rapid singular-value decay and corresponding condition-number lower bounds.The paper attributes the ill-conditioning to the same spectral approximation mechanism that produces high accuracy.

2. Approximation in kernel interpolation spaces

This section develops an interpolation-scale framework for random-feature approximation, linking kernel operators, feature sampling, ridge regression, and error norms. Under concentration-based sampling conditions, the framework provides high-probability, simultaneous approximation guarantees for source-regular targets.

  • Kernel interpolation spaces: The interpolation scale is generated by the spectral decomposition of a positive kernel integral operator and connects L2 with RKHS-based spaces.The spaces H_a are defined through spectral powers of the operator, with H_0 = L2 and continuous embeddings H_a into H_b for a ≥ b.
  • Feature representation and ridge approximation: An RF representation factors the kernel through a feature operator, while sampled features define a finite-dimensional operator for ridge approximation.The kernel operator satisfies Σ = TT*, and the sampled RF operator maps coefficient vectors into functions on the input domain.
  • Feature sampling: Leverage-score sampling minimizes the relevant sampling bound among admissible feature densities.The normalized leverage-score density attains equality in the associated bound and is required to be positive wherever the leverage quantity is positive.
  • Abstract approximation estimate: Theorem 2.3 controls both RF approximation error and ridge-coefficient size for targets in H_s across admissible regression and error norms.The theorem covers 0 ≤ θ ≤ s ≤ 1 and p ≤ s under the stated spectral and penalty conditions, with probability at least 1 − δ.
  • Uniformity and norm dependence: A single feature-dependent high-probability event supports target-uniform approximation, while one coefficient vector per target works simultaneously across admissible error norms.When p ≤ θ, weaker error norms can share the same sampling event; rates saturate below the threshold max(p, 2θ − 1), while stronger norms require stronger regularization.
  • Proof mechanism and regularization: The ridge error proof reduces the problem to empirical-resolvent operator norms and controls them through a high-probability concentration event.The penalty threshold ς_N determines admissible regularization levels, and the coefficient norm can increase as λ approaches zero.

3. Uniform approximation of regularity classes by random Fourier features

The paper establishes high-probability spectral approximation for multidimensional regularity classes using random Fourier features, with one sampled space uniform over targets and one reconstruction per target uniform over admissible error norms. Regularity-adapted and growing-window frequency measures yield rates from algebraic to super-exponential.

  • Theorem 3.2 establishes spectral convergence for random Fourier features using regularity-adapted reference measures, leverage-score sampling, and simultaneous control of approximation error and coefficient norm.
  • With probability at least 1 −δ, every admissible target has coefficients whose approximation satisfies all stated error bounds, on an event determined only by the sampled features.
  • Sobolev targets achieve the algebraic rate L_N^−(s−t)/d, while stretched-exponential Fourier regularity gives exp(−cL_N^1/(sd)).
  • Super-exponential Fourier and bandlimited classes yield exp(−cL_N^1/d log L_N), super-exponential in the linear resolution scale L_N^1/d.
  • For each target, one coefficient vector attains the convergence estimates simultaneously across all admissible interpolation or Sobolev error norms, while the sampling event remains target-uniform.
  • The same twofold uniformity holds for uniform measures on growing frequency cubes, whose bandwidth laws adapt the construction to target regularity.

4. RFM discretizations of PDE and eigenvalue problems

The paper transfers random-feature approximation bounds to strong- and weak-form discretizations of elliptic boundary value and eigenvalue problems. PDE errors are controlled by trial-space approximation, while eigenvalue convergence is faster than eigenspace convergence.

  • Strong-form RFM: Strong-form RFM errors are bounded by the best approximation error in the random-feature trial space under smoothness, ellipticity, and regularity assumptions.For unique solutions, the estimate is ||u − uRF||_{H^{s+l+1/2}(Ω)} ≤ C inf_{w∈VRF} ||u − w||_{H^2(Ω)}.
  • Strong-form RFM: The strong-form framework accommodates Dirichlet, Neumann, and Robin boundary operators, including problems with nontrivial null spaces.The stated scope includes the Laplace equation with a Neumann boundary condition.
  • Weak-form RFM: Weak-form RFM inherits a Céa-type quasi-optimality estimate, with its error controlled by the best approximation error in the variational trial space.The estimate uses continuity and coercivity of the bilinear form.
  • Eigenvalue problems: For eigenvalue problems, sufficiently rich random-feature spaces produce the correct eigenvalue multiplicity and convergence of the associated discrete eigenspaces.The discrete problem has exactly q eigenvalues converging to the target eigenvalue, counted with multiplicity.
  • Eigenvalue problems: Eigenvalues converge at twice the rate of the corresponding eigenspaces, with max_{1≤j≤q}|λ−λRF,j| ≤ CηRF^2(E).The eigenspace convergence rate matches the best approximation error, whereas eigenvalues converge at its square.

5. Singular values and exponential ill-conditioning of RFMtxs

The section analyzes singular-value decay and condition-number growth in random feature matrices used for collocation. Fourier features exhibit super-exponential decay, while tanh features exhibit exponential decay, linking high approximation accuracy to severe ill-conditioning.

  • RFM matrix construction: The RFM collocation matrix is formed by applying the interior differential operator and boundary operator to each feature at sampled collocation points.The coefficients solve a linear least-squares system Ψα = F.
  • Tanh features: Tanh-feature RFM matrices have exponential singular-value decay, with aT(d,S) > 0 chosen explicitly in terms of dimension and frequency-window size.The tanh result assumes bounded frequencies and feature parameters as specified in the theorem.
  • Mechanism and implications: The common mechanism is simultaneous approximation of all feature columns in a low-dimensional trial space, followed by the min–max characterization of singular values.Spectral approximation makes the residual exponentially or super-exponentially small.
  • Mechanism and implications: Increasing dimension can slow singular-value decay because the decay exponents scale with M^{1/d}, while localization and preconditioning are identified as possible remedies.The dimensional trend is supported by numerical experiments and the stated bounds.

6. Conclusion

The paper develops multidimensional random-feature approximation theory, transfers it to elliptic PDEs and eigenvalue problems, and analyzes the resulting matrix conditioning. Its central conclusion is that spectral accuracy and severe ill-conditioning arise from the same approximation mechanism.

  • Conclusion: The framework establishes high-probability RFM convergence from super-exponential to algebraic rates across target regularity classes and sampling strategies.The rates depend on target regularity and apply under both regularity-adapted and growing-window uniform sampling.
  • Conclusion: A single target-independent event supports approximation of an entire source ball, while each target has one coefficient vector working across all admissible error norms.The construction provides simultaneous spectral accuracy in the interpolation scale.
  • Conclusion: The abstract approximation estimates yield convergence estimates for strong- and weak-form elliptic boundary value problems and their eigenvalue problems.The same interpolation-scale theory underlies these PDE discretization results.
  • Conclusion: Fourier and tanh RFM matrices respectively show super-exponential and exponential high-index singular-value decay, together with condition-number lower bounds.These results quantitatively explain severe ill-conditioning in high-accuracy RFM computations.
  • Conclusion: Extending the framework to other activations requires control of kernel interpolation spaces, source conditions, and effective dimensions.The singular-value argument additionally requires uniform spectral approximation of derivatives needed by the PDE operator.

Appendix A. Proofs for approximation in interpolation spaces

The appendix proves the interpolation-space approximation theorem by reducing error and coefficient control to random-operator bounds, then establishing empirical-operator concentration and resolvent comparisons.

  • Operator reduction: The proof represents the empirical integral operators and rewrites approximation error and coefficient norms through regularized operator resolvents.The empirical operator is N^-1ΦΦ* and the preconditioned operator is defined from Σ and the feature map.
  • Theorem proof: The resulting bounds separately control uniform approximation error and coefficient norm, preserving the parameterized interpolation-scale structure.The framework allows independent source regularity, regression norm, and error norm choices within admissible ranges.
  • Concentration: A preconditioned empirical concentration lemma gives high-probability control and resolvent comparison on one event.The event has probability at least 1−δ and supports the stated comparison for every a∈[0,1/2].
  • Concentration: The concentration proof uses Cordes’ inequality for fractional resolvent comparison and Minsker’s Bernstein inequality for intrinsic-dimension operator tails.The tail bound depends on the effective rank of the variance operator rather than ambient dimension.
  • Theorem proof: The theorem proof applies the concentration estimate at admissible penalty levels and passes to the critical level by continuity and limiting arguments.The same strategy controls both approximation error and the solution coefficient norm.

Appendix B. Proofs for uniform approximation by random Fourier features

Appendix B establishes the Fourier-specific spectral ingredients behind uniform approximation: injectivity, effective-dimension bounds across four frequency-decay regimes, and identifications between Fourier-defined target spaces and kernel interpolation or Sobolev spaces.

  • Spectral injectivity: Injectivity of the kernel integral operator follows by extending f by zero, using analyticity of its Fourier transform, and invoking the identity theorem.The argument concludes ker Σ = {0}, so the positive spectral subspace is all of L2(Ω).
  • Operator comparison: Translation-invariant operator comparisons reduce multidimensional spectral estimates to pointwise Fourier-multiplier inequalities.If 0 ≤ K2(ξ) ≤ K1(ξ) almost everywhere, then T2 ⪯ T1.
  • Effective dimension: Effective-dimension estimates are derived for polynomial, subexponential or exponential, super-exponential, and bandlimited frequency decay.The four cases use Fourier-multiplier comparisons and eigenvalue asymptotics.
  • Effective dimension: For polynomial decay, the comparison operator has eigenvalues λj(Σs) ≲d,s,Ω j^-2s/d for sufficiently large j.This estimate is inserted into the effective-dimension series to obtain the polynomial-regime bound.
  • Space identifications: The appendix identifies weighted Fourier target classes and bandlimited spaces with corresponding translation-invariant RKHSs and interpolation spaces.The bandlimited characterization gives HkS(Rd) = PWS, the space of functions whose Fourier transforms are supported in QS.

B.3. Proof of the uniform approximation theorem.

The uniform approximation theorem is obtained from a sampling condition controlled by effective dimension, yielding a feature-dependent high-probability event that is uniform over a source-space unit ball.

  • Probabilistic implication: A sufficient sampling condition follows from d(λ; θ, γ) ≤ M and the logarithmic size requirement involving M and δ.The proof then applies the sampling theorem at the selected penalty scale.
  • Probabilistic implication: Both feature representations induce the same kernel integral operator and therefore the same effective dimension.The optimal sampling density for either representation satisfies dmax(q*) = d(λ; θ, γ) ≤ M.

k. On this event, let f ∈Hσ

On the common sampling event, the proofs specialize the abstract approximation theorem to regularity classes and representations, obtaining uniform estimates and coefficient bounds across admissible norms.

  • Representations: The real cosine–sine realization preserves the coefficient identity because |aj|^2 + |bj|^2 equals the complex coefficient magnitude squared.This permits the complex-exponential estimates to yield real-valued approximants.
  • Uniformity across norms: The sampling event, coefficients, and approximants are independent of the error indices t and p, so estimates hold simultaneously for all admissible Sobolev norms.The deterministic embeddings transfer whole-space estimates to the domain.
  • Regularity-adapted classes: For exponential and Gevrey targets, effective-dimension choices are converted into approximation rates through λ scales involving exp(−aλM^(1/(sd))).The proof then combines the abstract estimate with restriction and interpolation embeddings.

B.5. Proof of the growing-bandwidth leverage estimate.

The growing-bandwidth proof controls effective dimension through time-frequency concentration eigenvalues, then combines that control with Sobolev embeddings to obtain simultaneous error estimates and coefficient bounds.

  • Norm conversion: The bandlimited Sobolev embedding introduces a factor (π/S)^{d(1−a)/2}(1 + dS^2)^{(2t+d+1)/4} in the error norm.This is the deterministic norm conversion used after the approximation estimate.
  • Uniformity and coefficients: Combining the approximation estimate with the embedding cancels the powers of π/S associated with a and 1 − a.The sampling event and approximants remain independent of t and p, and the coefficient bound has zero λJ,S power.

B.6. Proof of the growing uniform reference measure theorem.

The proof combines representation-wise sampling, bandlimited truncation, and parameter conversion to establish the stated approximation rates for growing uniform frequency windows. A single feature-dependent event and approximant provide simultaneity across target regularity and error parameters.

  • Representation-wise sampling: A single sampling event depends only on the sampled features and supports the approximation estimate uniformly over all admissible bandlimited targets.The event is uniform over the target ball, while the construction fixes one approximant independent of t and p.
  • Sobolev targets: One fixed approximant can achieve the Sobolev approximation bounds simultaneously for all 1 ≤ p ≤ ∞ and 0 ≤ t ≤ s.The proof applies the representation theorem to a bandlimited target and then uses Sobolev embedding and Plancherel estimates.
  • Regularity-adapted rates: For Gevrey regularity s ≥ 1, choosing S_J = J/(4R*) yields an algebraic rate proportional to J^{-(s−t)}, including the endpoint s = 1.The remaining J-dependent factor is bounded, so the second term is controlled by a constant multiple of J^{-(s−t)}.
  • Regularity-adapted rates: For ultra-analytic targets, choosing S_J = (J log J)^{1/s}/(4R*) produces exponential decay in J log J after algebraic prefactors are absorbed.The proof bounds the truncation contribution by C∥u∥e^{-cJ log J} and reduces the exponential constant to absorb remaining factors.
  • Conversion to N: The sample-size conversion sets L = N/log(N/δ) and J = floor(c0L^{1/d}), yielding the stated N-dependent rates.For sufficiently large N, J is comparable to L^{1/d} and log J is comparable to log L.

Appendix D. Proofs for RFM solvers

The appendix derives stability and continuity estimates for RFM solvers and combines them with the minimality of the numerical solution. The resulting theorem bounds solver error by the best approximation error over the random-feature trial space.

  • Stability estimates: A boundary-value operator estimate controls the error in terms of interior and boundary residual norms, with constants independent of u and u_N.The proof applies the operator estimate to w = u − u_N and uses the embedding of L2(Ω) into the interior data space.
  • Continuity estimates: Trace and coefficient bounds provide the continuity estimates needed for the differential operator, boundary operator, and bilinear forms.The first estimate follows from operator definitions and the trace theorem; the second follows from Assumption 4.1.
  • RFM solver error: The RFM solution is bounded by the best residual achievable in the random-feature space because its defining minimality is combined with the stability estimates.Taking the infimum over all w in the trial space yields the theorem.

Appendix E. Proofs for singular-value estimates and condition-number lower bounds

The appendix proves singular-value decay by reducing matrix control to mutual feature approximation, then constructs Fourier and tanh approximants under a common sampling event. It also develops low-frequency polynomial approximations and high-frequency column bounds for condition-number estimates.

  • Fourier decay: Low-frequency Fourier features admit Taylor-polynomial approximations whose factorial remainder yields super-exponential singular-value decay.The proof compares factorial decay with the explicit rate constant and obtains an exponential-in-M^{1/d} log M bound.
  • Singular-value reduction: Singular-value control is reduced to approximating transformed features in W^{2,∞}(Ω), producing a large coefficient subspace on which the matrix action is small.This reduction minimizes dependence on collocation points, the domain, and the differential equation.
  • Fourier features: For Fourier features, a single sampled frequency–phase realization yields approximants for all 2N target functions in one common K-dimensional real trial space.The event has positive probability and is uniform over the target ball; fixing one realization gives the matrix estimate.
  • tanh features: For tanh features, uniform analytic norm bounds and the same common-event argument provide approximants satisfying the corresponding singular-value estimate.The constants depend on dimension and the frequency-window size through κ_T and a_T(d,S).
  • Condition-number bounds: The condition-number argument combines singular-value upper bounds with feature-column or low-frequency polynomial constructions to establish severe ill-conditioning.The low- and high-frequency cases are handled separately, including a direct construction for the low-frequency Fourier case.
  • tanh decay and conditioning: High-frequency tanh features are controlled through lower bounds on individual columns, separating low- and high-frequency sets at the threshold ρ_T.The high-frequency case uses interior preactivation bounds and the resulting column estimates.
Loading 2609.03401v1…