## Abstract

Comparing with the standard L_{2}-norm support vector machine (SVM), the L_{1}-norm SVM enjoys the nice property of simultaneously preforming classification and feature selection. In this paper, we investigate the statistical performance of L_{1}-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 L_{1}-norm SVM. Our analysis reveals that the estimated L_{1}-norm SVM coefficients achieve near oracle rate, that is, with high probability, the L_{2} error bound of the estimated L_{1}-norm SVM coefficients is of order O_{p}(√q log p/n), where q is the number of features with nonzero coefficients. Furthermore, we show that if the L_{1}-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 L_{1}-norm SVM as a sparse classifier and its effectiveness to be utilized to solve non-convex penalized SVM problems in high dimension.

Original language | English (US) |
---|---|

Pages (from-to) | 1-26 |

Number of pages | 26 |

Journal | Journal of Machine Learning Research |

Volume | 17 |

State | Published - Dec 1 2016 |

### Bibliographical note

Funding Information:We would like to acknowledge support for this project from the National Science Foundation (NSF grant DMS-1308960) for Peng and Wang's research and the National Science Foundation (NSF grant DMS-1055210) and National Institutes of Health (NIH grants R01 CA149569 and P01 CA142538) for Wu's research respectively.

Publisher Copyright:

© 2016 Bo Peng, Lan Wang and Yichao Wu.

## Keywords

- Error bound
- Feature selection
- L-norm SVM
- Non-convex penalty
- Oracle property
- Support vector machine
- Ulta-high dimension

## Fingerprint

Dive into the research topics of 'An error bound for L_{1}-norm support vector machine coefficients in ultra-high dimension'. Together they form a unique fingerprint.