用随机准蒙特卡洛方法改进核函数近似，误差更小且稳定性更强。
Randomized Quasi-Monte Carlo Features for Kernel Approximation
- 引入RQMC替代传统蒙特卡洛，提升核近似误差收敛速度。
- 理论证明误差可降至O(1/M)，并降低对高维的敏感性。
- 适合需要高效稳定核学习的场景，如低至中等维度数据。
本文研究随机准蒙特卡洛（RQMC）方法在核函数随机特征近似中的应用。相比经典蒙特卡洛（MC）方法，RQMC将确定性逼近误差界从 $O_P(1/\ oot{2}{M})$ 改进至 $O(1/M)$（含对数因子），达到与准蒙特卡洛（QMC）相当的收敛速率。除确定性误差界外，还建立了若干平均误差界：部分假设更弱，另一些显著降低了对数因子的指数。在核岭回归中，RQMC特征在保持相同统计误差率的同时，具备计算优势。实验表明，RQMC在低维和中等高维场景下性能稳定，而传统QMC随维度增加表现明显下降。
原文摘要 · Abstract (English)
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{M})$ 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。