Generalization error for multi-class margin classification

Xiaotong Shen, Lifeng Wang

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


In this article, we study rates of convergence of the generalization error of multi-class margin classifiers. In particular, we develop an upper bound theory quantifying the generalization error of various large margin classifiers. The theory permits a treatment of general margin losses, convex or nonconvex, in presence or absence of a dominating class. Three main results are established. First, for any fixed margin loss, there may be a trade-off between the ideal and actual generalization performances with respect to the choice of the class of candidate decision functions, which is governed by the trade-off between the approximation and estimation errors. In fact, different margin losses lead to different ideal or actual performances in specific cases. Second, we demonstrate, in a problem of linear learning, that the convergence rate can be arbitrarily fast in the sample size n depending on the joint distribution of the input/output pair. This goes beyond the anticipated rate O(n−1). Third, we establish rates of convergence of several margin classifiers in feature selection with the number of candidate variables p allowed to greatly exceed the sample size n but no faster than exp(n).

Original languageEnglish (US)
Pages (from-to)307-330
Number of pages24
JournalElectronic Journal of Statistics
StatePublished - 2007


  • Convex and nonconvex losses
  • Import vector machines
  • Small n and large p
  • Sparse learning
  • Support vector machines
  • ψ-learning


Dive into the research topics of 'Generalization error for multi-class margin classification'. Together they form a unique fingerprint.

Cite this