Generalization error for multi-class margin classification

Xiaotong Shen, Lifeng Wang

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

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
Volume1
DOIs
StatePublished - Jan 1 2007

Keywords

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

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

  • Cite this