Maximum margin coresets for active and noise tolerant learning

Sariel Har-Peled, Dan Roth, Dav Zimak

Research output: Contribution to journalConference articlepeer-review


We study the problem of learning largemargin half-spaces in various settings using coresets and show that coresets are a widely applicable tool for large margin learning. A large margin coreset is a subset of the input data sufficient for approximating the true maximum margin solution. In this work, we provide a direct algorithm and analysis for constructing large margin coresets1. We show various applications including a novel coreset based analysis of large margin active learning and a polynomial time (in the number of input data and the amount of noise) algorithm for agnostic learning in the presence of outlier noise. We also highlight a simple extension to multi-class classification problems and structured output learning.

Original languageEnglish (US)
Pages (from-to)836-841
Number of pages6
JournalIJCAI International Joint Conference on Artificial Intelligence
StatePublished - 2007
Event20th International Joint Conference on Artificial Intelligence, IJCAI 2007 - Hyderabad, India
Duration: Jan 6 2007Jan 12 2007

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Maximum margin coresets for active and noise tolerant learning'. Together they form a unique fingerprint.

Cite this