An Error Bound for L1-norm Support Vector Machine Coefficients in Ultra-high Dimension
An Error Bound for L1-norm Support Vector Machine Coefficients in Ultra-high Dimension
复制标题
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Bo Peng;Lan Wang;Yichao Wu
中科院分区：
文献类型：
--
作者：
Bo Peng;Lan Wang;Yichao Wu
与标准的L2-范数支持向量机相比，L1-范数支持向量机具有同时进行分类和特征选择的优点。在本文中，我们研究了L1范数支持向量机的统计性能在超高维，其中的特征数量p的样本大小n的指数增长率。与现有的支持向量机理论主要关注泛化错误率和经验风险不同，本文研究了L1范数支持向量机系数的渐近行为。我们的分析表明，估计的L1-范数SVM系数达到接近预言率，即，在很大的概率下，估计的L1-范数SVM系数的L2误差界是Op（q log p/n）的顺序，其中q是具有非零系数的特征的数量。此外，我们表明，如果使用L1范数SVM作为最近提出的用于求解非凸惩罚SVM的算法的初始值（Zhang等人，2016 b），则在两个迭代步骤中，保证产生在超高维度中具有预言性质的估计器，这特别意味着在概率接近1的情况下，零系数被精确地估计为零。仿真结果表明，L1范数支持向量机作为稀疏分类器具有良好的性能，可以有效地解决高维非凸惩罚支持向量机问题。
Comparing with the standard L2-norm support vector machine (SVM), the L1-norm SVM enjoys the nice property of simultaneously preforming classification and feature selection. In this paper, we investigate the statistical performance of L1-norm SVM in ultra-high dimension, where the number of features p grows at an exponential rate of the sample size n. Different from existing theory for SVM which has been mainly focused on the generalization error rates and empirical risk, we study the asymptotic behavior of the coefficients of L1- norm SVM. Our analysis reveals that the estimated L1-norm SVM coefficients achieve near oracle rate, that is, with high probability, the L2 error bound of the estimated L1- norm SVM coefficients is of order Op(√q log p/n), where q is the number of features with nonzero coefficients. Furthermore, we show that if the L1-norm SVM is used as an initial value for a recently proposed algorithm for solving non-convex penalized SVM (Zhang et al., 2016b), then in two iterative steps it is guaranteed to produce an estimator that possesses the oracle property in ultra-high dimension, which in particular implies that with probability approaching one the zero coefficients are estimated as exactly zero. Simulation studies demonstrate the fine performance of L1-norm SVM as a sparse classifier and its effectiveness to be utilized to solve non-convex penalized SVM problems in high dimension.