Randomized Quasi-Monte Carlo Features for Kernel Approximation

• URL: http://arxiv.org/abs/2503.06041v1
• Date: Sat, 08 Mar 2025 03:38:28 GMT
• Title: Randomized Quasi-Monte Carlo Features for Kernel Approximation
• Authors: Yian Huang, Zhen Huang,
• Abstract summary: We investigate the application of randomized quasi-Monte Carlo (RQMC) methods in random feature approximations for kernel-based learning.<n>Compared to the classical Monte Carlo (MC) approach citeprahimirandom, RQMC improves the deterministic approximation error bound.<n>We show that RQMC methods maintain stable performance in both low and moderately high-dimensional settings.
• Score: 3.105656247358225
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We investigate the application of randomized quasi-Monte Carlo (RQMC) methods in random feature approximations for kernel-based learning. Compared to the classical Monte Carlo (MC) approach \citep{rahimi2007random}, RQMC improves the deterministic approximation error bound from $O_P(1/\sqrt{n})$ to $O(1/M)$ (up to logarithmic factors), matching the rate achieved by quasi-Monte Carlo (QMC) methods \citep{huangquasi}. Beyond the deterministic error bound guarantee, we further establish additional average error bounds for RQMC features: some requiring weaker assumptions and others significantly reducing the exponent of the logarithmic factor. In the context of kernel ridge regression, we show that RQMC features offer computational advantages over MC features while preserving the same statistical error rate. Empirical results further show that RQMC methods maintain stable performance in both low and moderately high-dimensional settings, unlike QMC methods, which suffer from significant performance degradation as dimension increases.

Related papers

• Quantum Speedups for Markov Chain Monte Carlo Methods with Application to Optimization [12.054017903540194]
  We propose quantum algorithms that provide provable speedups for Markov Chain Monte Carlo methods. By introducing novel techniques for gradient estimation, our algorithms improve the complexities of classical samplers.
  arXiv  Detail & Related papers  (2025-04-04T17:44:22Z)
• Uncertainty quantification for Markov chains with application to temporal difference learning [63.49764856675643]
  We develop novel high-dimensional concentration inequalities and Berry-Esseen bounds for vector- and matrix-valued functions of Markov chains. We analyze the TD learning algorithm, a widely used method for policy evaluation in reinforcement learning.
  arXiv  Detail & Related papers  (2025-02-19T15:33:55Z)
• Randomized Physics-Informed Machine Learning for Uncertainty Quantification in High-Dimensional Inverse Problems [49.1574468325115]
  We propose a physics-informed machine learning method for uncertainty quantification in high-dimensional inverse problems. We show analytically and through comparison with Hamiltonian Monte Carlo that the rPICKLE posterior converges to the true posterior given by the Bayes rule.
  arXiv  Detail & Related papers  (2023-12-11T07:33:16Z)
• Model-Based Reparameterization Policy Gradient Methods: Theory and Practical Algorithms [88.74308282658133]
  Reization (RP) Policy Gradient Methods (PGMs) have been widely adopted for continuous control tasks in robotics and computer graphics. Recent studies have revealed that, when applied to long-term reinforcement learning problems, model-based RP PGMs may experience chaotic and non-smooth optimization landscapes. We propose a spectral normalization method to mitigate the exploding variance issue caused by long model unrolls.
  arXiv  Detail & Related papers  (2023-10-30T18:43:21Z)
• Robust Uncertainty Quantification Using Conformalised Monte Carlo Prediction [6.86690482279886]
  Uncertainty quantification (UQ) methods estimate the model's confidence per prediction. We introduce MC-CP, a novel hybrid UQ method that combines a new adaptive Monte Carlo (MC) dropout method with conformal prediction (CP) We show that MC-CP delivers significant improvements over advanced UQ methods, like MC dropout, RAPS and CQR, both in classification and regression benchmarks.
  arXiv  Detail & Related papers  (2023-08-18T16:07:01Z)
• Reverse Diffusion Monte Carlo [19.35592726471155]
  We propose a novel Monte Carlo sampling algorithm called reverse diffusion Monte Carlo (rdMC) rdMC is distinct from the Markov chain Monte Carlo (MCMC) methods.
  arXiv  Detail & Related papers  (2023-07-05T05:42:03Z)
• Convergence Analysis of Stochastic Gradient Descent with MCMC Estimators [8.493584276672971]
  gradient descent (SGD) and its variants is essential for machine learning. In this paper, we consider the SGD algorithm that employ the Markov Chain Monte Carlo (MCMC) estimator to compute the gradient. It is shown that MCMC-SGD escapes from saddle points and reaches $(epsilon,epsilon1/4)$ approximate second order stationary points.
  arXiv  Detail & Related papers  (2023-03-19T08:29:49Z)
• Monte Carlo Neural PDE Solver for Learning PDEs via Probabilistic Representation [59.45669299295436]
  We propose a Monte Carlo PDE solver for training unsupervised neural solvers. We use the PDEs' probabilistic representation, which regards macroscopic phenomena as ensembles of random particles. Our experiments on convection-diffusion, Allen-Cahn, and Navier-Stokes equations demonstrate significant improvements in accuracy and efficiency.
  arXiv  Detail & Related papers  (2023-02-10T08:05:19Z)
• Policy Gradient for Rectangular Robust Markov Decision Processes [62.397882389472564]
  We introduce robust policy gradient (RPG), a policy-based method that efficiently solves rectangular robust Markov decision processes (MDPs) Our resulting RPG can be estimated from data with the same time complexity as its non-robust equivalent.
  arXiv  Detail & Related papers  (2023-01-31T12:40:50Z)
• Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic [61.968469104271676]
  We propose an RL methodology attuned to the mixing time by employing a multi-level Monte Carlo estimator for the critic, the actor, and the average reward embedded within an actor-critic (AC) algorithm. We experimentally show that these alleviated restrictions on the technical conditions required for stability translate to superior performance in practice for RL problems with sparse rewards.
  arXiv  Detail & Related papers  (2023-01-28T04:12:56Z)
• Convergence analysis of a quasi-Monte Carlo-based deep learning algorithm for solving partial differential equations [0.0]
  We propose to apply quasi-Monte Carlo (QMC) methods to the Deep Ritz Method (DRM) for solving the Neumann problems for the Poisson equation and the static Schr"odinger equation. For error estimation, we decompose the error of using the deep learning algorithm to solve PDEs into the generalization error, the approximation error and the training error. Numerical experiments show that the proposed method converges faster in all cases and the variances of the gradient estimators of randomized QMC-based DRM are much smaller than those of DRM.
  arXiv  Detail & Related papers  (2022-10-28T15:06:57Z)
• High-dimensional Inference and FDR Control for Simulated Markov Random Fields [1.9458156037869137]
  This article explores statistical inference for simulated Markov random fields in high-dimensional settings. We introduce a methodology based on Maximum Chain Monte Carlo Likelihood Estimation with Elastic-net regularization.
  arXiv  Detail & Related papers  (2022-02-11T13:49:08Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)

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.