Convergence for adaptive resampling of random Fourier features

• URL: http://arxiv.org/abs/2509.03151v1
• Date: Wed, 03 Sep 2025 09:03:28 GMT
• Title: Convergence for adaptive resampling of random Fourier features
• Authors: Xin Huang, Aku Kammonen, Anamika Pandey, Mattias Sandberg, Erik von Schwerin, Anders Szepessy, Raúl Tempone,
• Abstract summary: The machine learning random Fourier feature method for data in high dimension is computationally and theoretically attractive since the optimization is based on a convex standard least squares problem and independent sampling of frequencies.<n>This work proves of a data adaptive method based on resampling the frequencies optimally, as the number of nodes and amount of data tend to infinity.<n> Numerical results based on reconjugate gradient and adaptive random walk steps together with approximations of the least squares problem by iterations confirm the analysis for regression and classification problems.
• Score: 8.67484158637974
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The machine learning random Fourier feature method for data in high dimension is computationally and theoretically attractive since the optimization is based on a convex standard least squares problem and independent sampling of Fourier frequencies. The challenge is to sample the Fourier frequencies well. This work proves convergence of a data adaptive method based on resampling the frequencies asymptotically optimally, as the number of nodes and amount of data tend to infinity. Numerical results based on resampling and adaptive random walk steps together with approximations of the least squares problem by conjugate gradient iterations confirm the analysis for regression and classification problems.

Related papers

• Scale-Adaptive Generative Flows for Multiscale Scientific Data [20.583125441867434]
  Flow-based generative models can face challenges when modeling scientific data with multiscale Fourier spectra.<n>Key insight is that the noise should not be smoother than the target data, to ensure bounded drift fields near the initial time.<n>We show that spectrum-matched noise improves numerical efficiency compared to standard white-noise approaches.
  arXiv  Detail & Related papers  (2025-09-03T03:17:49Z)
• LSCD: Lomb-Scargle Conditioned Diffusion for Time series Imputation [55.800319453296886]
  Time series with missing or irregularly sampled data are a persistent challenge in machine learning.<n>We introduce a different Lombiable--Scargle layer that enables a reliable computation of the power spectrum of irregularly sampled data.
  arXiv  Detail & Related papers  (2025-06-20T14:48:42Z)
• Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models [55.07411490538404]
  We propose a novel parallel sampling method that improves adaptive complexity dependence on dimension $d$.<n>Our approach builds on parallel simulation techniques from scientific computing.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Score-based Diffusion Models in Function Space [137.70916238028306]
  Diffusion models have recently emerged as a powerful framework for generative modeling.<n>This work introduces a mathematically rigorous framework called Denoising Diffusion Operators (DDOs) for training diffusion models in function space.<n>We show that the corresponding discretized algorithm generates accurate samples at a fixed cost independent of the data resolution.
  arXiv  Detail & Related papers  (2023-02-14T23:50:53Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Diffusion Posterior Sampling for General Noisy Inverse Problems [50.873313752797124]
  We extend diffusion solvers to handle noisy (non)linear inverse problems via approximation of the posterior sampling. Our method demonstrates that diffusion models can incorporate various measurement noise statistics.
  arXiv  Detail & Related papers  (2022-09-29T11:12:27Z)
• Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data [7.513100214864646]
  We show the worst-case complexity of convergence $tildeO(t-1/4)$ and MoreautildeO(vareps-4)$ for smooth non- optimization. We obtain first online nonnegative matrix factorization algorithms for dependent data based on projected gradient methods with adaptive step sizes and optimal convergence.
  arXiv  Detail & Related papers  (2022-03-29T17:59:10Z)
• On Sparse High-Dimensional Graphical Model Learning For Dependent Time Series [12.94486861344922]
  We consider the problem of inferring the conditional independence graph (CIG) of a sparse, high-dimensional stationary time series. A sparse-group lasso-based frequency-domain formulation of the problem is presented. We also empirically investigate selection of the tuning parameters based on Bayesian information criterion.
  arXiv  Detail & Related papers  (2021-11-15T16:52:02Z)
• Large-Scale Learning with Fourier Features and Tensor Decompositions [3.6930948691311007]
  We exploit the tensor product structure of deterministic Fourier features, which enables us to represent the model parameters as a low-rank tensor decomposition. We demonstrate by means of numerical experiments how our low-rank tensor approach obtains the same performance of the corresponding nonparametric model.
  arXiv  Detail & Related papers  (2021-09-03T14:12:53Z)
• Wind Field Reconstruction with Adaptive Random Fourier Features [0.0]
  We investigate the use of spatial methods for reconstructing the horizontal near-surface wind field given a sparse set of measurements. We include a physically motivated divergence penalty term $|nabla cdot beta(pmb x)|2$, as well as a penalty on the Sobolev norm. We devise an adaptive-Hastings algorithm for sampling the frequencies of the optimal distribution.
  arXiv  Detail & Related papers  (2021-02-04T01:42:08Z)
• Denoising Score Matching with Random Fourier Features [11.60130641443281]
  We derive analytical expression for the Denoising Score matching using the Kernel Exponential Family as a model distribution. The obtained expression explicitly depends on the noise variance, so the validation loss can be straightforwardly used to tune the noise level.
  arXiv  Detail & Related papers  (2021-01-13T18:02:39Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)

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.