Nystrom Subsampling Method for Coefficient-Based Regularized Regression
Nystrom Subsampling Method for Coefficient-Based Regularized Regression
复制标题
基于系数的正则回归的 Nystrom 子采样方法
DOI：
10.1088/1361-6420/ab129e
复制
发表时间：
2019
期刊：
影响因子：
2.1
通讯作者：
Zongmin Wu
中科院分区：
文献类型：
--
作者：
Longda Ma;Lei Shi;Zongmin Wu
核方法在数据分析中很有吸引力，因为它们可以对观测值之间的非线性相似性进行建模，并提供丰富的表示方法，这两者对于一般领域的回归问题都很有用。尽管它们很受欢迎，但它们有两个主要的固有缺点。但核函数的正定性要求限制了核函数在真实的数据分析中的应用。另一个缺点是它们在海量数据场景中的可扩展性差。在本文中，我们的目标是通过考虑基于系数的正则化回归（或简称Nyström CRR）的Nyström子采样方法来解决这两个问题。Nyström子采样是一种通过列子采样构造原始核矩阵的低秩近似来降低空间和时间复杂度的有效方法。基于系数的正则化回归可以为设计不定核方法提供一个简单的范例。我们表明，这两个计划的组合不仅是计算效率，而且统计上一致的最小-最大的最佳收敛速度。我们明确地确定了作为样本大小的函数的子采样水平的下限，这样可以保持最小最大最优收敛速度。根据我们的分析，子采样水平在NyströmCRR的计算和渐近行为之间起着权衡的作用，因此对算法性能至关重要。为了选择合适的二次抽样水平，我们开发了一个增量NyströmCRR嵌套二次抽样集。该算法可以大大降低交叉验证的成本，甚至允许计算整个解决方案的路径，通过所有可能的子采样水平。基于我们的实证研究，增量Nyström CRR可以执行有效的模型选择，并在合成和真实的数据集上实现最先进的结果。
Kernel methods are attractive in data analysis as they can model nonlinear similarities between observations and provide means to rich representations, both of which are useful for the regression problems in general domains. Despite their popularity, they suffer from two primary inherent drawbacks. One drawback is the positive definiteness requirement of the kernel functions, which greatly restricts their applications to some real data analysis. The other drawback is their poor scalability in massive data scenarios. In this paper, we aim to address these two problems by considering the Nyström subsampling approach for coefficient-based regularized regression (or Nyström CRR for short). Nyström subsampling is an effective approach to reduce the space and time complexity by constructing a low-rank approximation of the original kernel matrix through column subsampling. Coefficient-based regularized regression can provide a simple paradigm for designing indefinite kernel methods. We show that a combination of these two schemes is not only computationally efficient but also statistically consistent with a mini-max optimal rates of convergence. We explicitly determine the lower bound of subsampling level as a function of the sample size such that the mini-max optimal convergence rates can be preserved. From our analysis, the subsampling level plays a role as a trade-off between computational and asymptotic behaviors of Nyström CRR, and hence is pivotal for algorithmic performances. In order to choose an appropriate subsampling level, we develop an incremental Nyström CRR for nested subsampling sets. The proposed algorithm can greatly reduce the cost of cross-validation, and even allows to compute the whole solution path through all possible subsampling levels. Based on our empirical studies, the incremental Nyström CRR can perform effective model selections and achieve the state-of-the-art results on both synthetic and real data sets.