论文标题
RFN：一种基于随机功能的牛顿方法，用于繁殖内核希尔伯特空间中的经验风险最小化
RFN: A Random-Feature Based Newton Method for Empirical Risk Minimization in Reproducing Kernel Hilbert Spaces
论文作者
论文摘要
在使用内核方法的监督学习中，我们经常在复制的内核希尔伯特空间（RKHS）上遇到大规模的有限和最小化。可以使用牛顿方法的有效变体来解决大规模有限和问题，其中Hessian通过数据子样本近似。但是，在RKHS中，惩罚函数对内核的依赖性使标准的子采样方法不可应用，因为革兰氏矩阵不容易以低级别形式获得。在本文中，我们观察到，对于这类问题，人们可以自然使用内核近似来加快牛顿方法。为了关注内核近似的随机特征，我们提供了一种新型的二阶算法，该算法享受局部超级线性收敛和全局线性收敛（具有很高概率）。我们为近似的Hessian所需的随机特征的数量得出了理论下限，以便在规范意义上接近真正的Hessian。与几个基准相比，我们对现实世界数据的数值实验验证了我们方法的效率。
In supervised learning using kernel methods, we often encounter a large-scale finite-sum minimization over a reproducing kernel Hilbert space (RKHS). Large-scale finite-sum problems can be solved using efficient variants of Newton method, where the Hessian is approximated via sub-samples of data. In RKHS, however, the dependence of the penalty function to kernel makes standard sub-sampling approaches inapplicable, since the gram matrix is not readily available in a low-rank form. In this paper, we observe that for this class of problems, one can naturally use kernel approximation to speed up the Newton method. Focusing on randomized features for kernel approximation, we provide a novel second-order algorithm that enjoys local superlinear convergence and global linear convergence (with high probability). We derive the theoretical lower bound for the number of random features required for the approximated Hessian to be close to the true Hessian in the norm sense. Our numerical experiments on real-world data verify the efficiency of our method compared to several benchmarks.
