Constraint classification: A new approach to multiclass classification

Sariel Har-Peled, Dan Roth, Dav Zimak

Research output: Contribution to journalArticlepeer-review


In this paper, we present a newviewof multiclass classification and introduce the constraint classification problem, a generalization that captures many flavors of multiclass classification. We provide the first optimal, distribution independent bounds for many multiclass learning algorithms, including winner-take-all (WTA). Based on our view, we present a learning algorithm that learns via a single linear classifier in high dimension. In addition to the distribution independent bounds, we provide a simple margin-based analysis improving generalization bounds for linear multiclass support vector machines.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Constraint classification: A new approach to multiclass classification'. Together they form a unique fingerprint.

Cite this