An error bound for L1-norm support vector machine coefficients in ultra-high dimension

Bo Peng, Lan Wang, Yichao Wu

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1-26
Number of pages26
JournalJournal of Machine Learning Research
Volume17
StatePublished - Dec 1 2016

Fingerprint

L1-norm
Error Bounds
Higher Dimensions
Support vector machines
Support Vector Machine
Coefficient
Preforming
Oracle Property
Generalization Error
Zero
Feature Selection
Error Rate
Feature extraction
Sample Size
Classifiers
Asymptotic Behavior
Classifier
Simulation Study
Estimator
Norm

Keywords

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

Cite this

An error bound for L1-norm support vector machine coefficients in ultra-high dimension. / Peng, Bo; Wang, Lan; Wu, Yichao.

In: Journal of Machine Learning Research, Vol. 17, 01.12.2016, p. 1-26.

Research output: Contribution to journalArticle

@article{ae50349156824725a4aadfbe9669a60f,
title = "An error bound for L1-norm support vector machine coefficients in ultra-high dimension",
abstract = "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.",
keywords = "Error bound, Feature selection, L-norm SVM, Non-convex penalty, Oracle property, Support vector machine, Ulta-high dimension",
author = "Bo Peng and Lan Wang and Yichao Wu",
year = "2016",
month = "12",
day = "1",
language = "English (US)",
volume = "17",
pages = "1--26",
journal = "Journal of Machine Learning Research",
issn = "1532-4435",
publisher = "Microtome Publishing",

}

TY - JOUR

T1 - An error bound for L1-norm support vector machine coefficients in ultra-high dimension

AU - Peng, Bo

AU - Wang, Lan

AU - Wu, Yichao

PY - 2016/12/1

Y1 - 2016/12/1

N2 - 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.

AB - 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.

KW - Error bound

KW - Feature selection

KW - L-norm SVM

KW - Non-convex penalty

KW - Oracle property

KW - Support vector machine

KW - Ulta-high dimension

UR - http://www.scopus.com/inward/record.url?scp=85011665519&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85011665519&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85011665519

VL - 17

SP - 1

EP - 26

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

SN - 1532-4435

ER -