Spectral Convergence of Random Feature Method in Multiple Dimensions

• URL: http://arxiv.org/abs/2609.03401v1
• Date: Thu, 03 Sep 2026 06:01:00 GMT
• Title: Spectral Convergence of Random Feature Method in Multiple Dimensions
• Abstract summary: We first prove spectral convergence of the random feature method (RFM) for multidimensional targets in Sobolev, Gevrey, ultra-analytic, and bandlimited classes.<n>The analysis identifies a common mechanism: the same spectral approximation that yields high accuracy also drives severe ill-conditioning.
• Score: 5.361030050051251
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Hierarchical Fourier Approximation for Variational Quantum Distribution Learning [0.0]
  We study quantum distribution learning through a hierarchy of Walsh-Fourier approximations on the Boolean cube.<n>We prove an end-to-end expected learning guarantee where the approximation term is determined by the omitted Fourier mass.<n>We identify the conditions under which low-to-high spectral training admits approximation-estimation-optimization analysis.
  arXiv  Detail & Related papers  (2026-09-05T23:34:49Z)
• Spectrum Estimation is Almost as Hard as Tomography [1.7205106391379026]
  We prove a sample complexity lower bound of $(d2-)$ for spectrum estimation to constant sorted total-variation error.<n>Our hard instances are constructed from sandwiched products of Haar-random projectors.
  arXiv  Detail & Related papers  (2026-07-31T17:57:03Z)
• Regularized Variational and Spectral Log-Density-Ratio Estimation in the Gaussian Location Model [0.554780083433538]
  We study ridge-regularized log-density-ratio estimation in the Gaussian location model.<n>The variational estimator is the empirical Kullback-Leibler (KL) log-normalized fit with a squared L2-penalty on its nonconstant coefficient.
  arXiv  Detail & Related papers  (2026-07-02T08:46:52Z)
• Inference for High-Dimensional Sparse Spectral Precision Matrices [3.260049048085003]
  Inference on the spectral precision matrix at a fixed frequency enables tests of frequency-specific conditional associations.<n>Existing approaches do not provide full likelihood-based inference for the discrete Fourier lasso.<n>We propose a high-dimensional inference framework for sparse spectral precision matrices.
  arXiv  Detail & Related papers  (2026-06-06T05:27:35Z)
• Regular Fourier Features for Nonstationary Gaussian Processes [0.0]
  Spectral methods treat the spectral density as a probability distribution for Monte Carlo approximation.<n>We propose regular Fourier features for harmonizable processes that avoid this limitation.<n>We demonstrate the method on locally stationary kernels and on harmonizable mixture kernels with complex-valued spectral densities.
  arXiv  Detail & Related papers  (2026-02-26T13:50:28Z)
• Universality of General Spiked Tensor Models [9.454986540713655]
  We study the rank-one spiked tensor model in the high-dimensional regime.<n>We show that their high-dimensional spectral behavior and statistical limits are robust to non-Gaussian noise.
  arXiv  Detail & Related papers  (2026-02-04T11:59:30Z)
• Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussian [48.340460104014]
  We study gradient descent for training models to learn a single Gaussian distribution.<n>We prove a global convergence result for gradient descent under multiple regimes.<n>This is the first work to establish global convergence guarantees for Gaussian mixtures with at least three components under the score matching framework.
  arXiv  Detail & Related papers  (2025-11-27T03:41:48Z)
• Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
  Two estimators of linear functionals of $mu_phi $ based on the discretized Markov process are considered.<n>Error bounds are derived for sampling and estimation using a discretization of an intrinsically defined Langevin diffusion.
  arXiv  Detail & Related papers  (2023-12-22T18:01:11Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.