Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration
Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration
复制标题
DOI：
--
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Kwang-Sung Jun;Ashok Cutkosky;Francesco Orabona
中科院分区：
文献类型：
--
作者：
Kwang-Sung Jun;Ashok Cutkosky;Francesco Orabona
本文研究再生核Hilbert空间中的非参数最小二乘回归问题。我们提出了一个新的随机算法，具有最佳的泛化误差界的平方损失，关闭长期存在的差距上限和下限。此外，我们表明，我们的算法具有更快的有限时间和渐近速率的问题，贝叶斯风险的平方损失是小的。我们使用标准的工具，从最小二乘回归RKHS理论，即相关的积分算子的特征值的衰减和通过积分算子测量的最佳预测的复杂性，我们的结果。
In this paper, we consider the nonparametric least square regression in a Reproducing Kernel Hilbert Space (RKHS). We propose a new randomized algorithm that has optimal generalization error bounds with respect to the square loss, closing a long-standing gap between upper and lower bounds. Moreover, we show that our algorithm has faster finite-time and asymptotic rates on problems where the Bayes risk with respect to the square loss is small. We state our results using standard tools from the theory of least square regression in RKHSs, namely, the decay of the eigenvalues of the associated integral operator and the complexity of the optimal predictor measured through the integral operator.