Statistical Optimality and Computational Efficiency of Nyström Kernel PCA
Statistical Optimality and Computational Efficiency of Nyström Kernel PCA
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Nicholas Sterge;Bharath K. Sriperumbudur
中科院分区：
文献类型：
--
作者：
Nicholas Sterge;Bharath K. Sriperumbudur
核方法为从简单的线性方法开发非线性学习算法提供了一个优雅的框架。尽管这些方法在一些实际数据应用中具有优越的经验性能，但它们的实用性受到大样本情况下产生的巨大计算负担的限制。文献中已经提出了各种近似方案来缓解这些计算问题，并且近似核机被证明保留了经验性能。然而，人们对这些近似内核机器的理论特性还不太了解。在这项工作中，我们从理论上研究了 Nystrom 近似核主成分分析 (KPCA) 中计算复杂性和统计精度之间的权衡，其中我们表明 Nystrom 近似 KPCA 与（非近似）KPCA 的统计性能相匹配，同时保持计算上的优势。此外，我们还表明，当应用于 KPCA 时，Nystrom 近似 KPCA 优于另一种流行的近似方案（随机特征近似）的统计行为。
Kernel methods provide an elegant framework for developing nonlinear learning algorithms from simple linear methods. Though these methods have superior empirical performance in several real data applications, their usefulness is inhibited by the significant computational burden incurred in large sample situations. Various approximation schemes have been proposed in the literature to alleviate these computational issues, and the approximate kernel machines are shown to retain the empirical performance. However, the theoretical properties of these approximate kernel machines are less well understood. In this work, we theoretically study the trade-off between computational complexity and statistical accuracy in Nystrom approximate kernel principal component analysis (KPCA), wherein we show that the Nystrom approximate KPCA matches the statistical performance of (non-approximate) KPCA while remaining computationally beneficial. Additionally, we show that Nystrom approximate KPCA outperforms the statistical behavior of another popular approximation scheme, the random feature approximation, when applied to KPCA.