Maximum Margin Coresets for Active and Noise Tolerant Learning

Sariel Har-Peled, Dan Roth, Dav ZimakIJCAI 2007 · OpenReview

Abstract

We study the problem of learning large-margin 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 coresets. 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.

Introduction

Training Support Vector Machines (SVMs) to find the maximum margin hyperplane—the widest possible gap between two classes—is a cornerstone of machine learning. However, standard optimization algorithms often scale poorly with dataset size $m$, typically requiring $O(m^3)$ time and $O(m^2)$ space. While the final decision boundary is defined by a small number of "support vectors," these are usually only identified after training on the full dataset. This paper demonstrates that a $(1-\epsilon)$-approximation of the maximum margin can be found using only a tiny, mathematically guaranteed subset of the data, known as a "coreset."

The Coreset SVM Framework

The primary contribution is an iterative algorithm for constructing large-margin coresets. Instead of processing the entire dataset, the algorithm starts with a single point and iteratively adds the most significant "violator"—the point that most aggressively breaches the current margin.

Geometric intuition of large-margin coresets in 2D and 3D spaces.

This geometric approach ensures that the coreset size depends only on the problem's geometry (the ratio of data spread $R$ to the margin $\rho^*$) and the desired accuracy $\epsilon$, remaining independent of the total number of points $M$. This decoupling allows for significantly faster training times, $O(nd|C| + |C|T(|C|))$, where $T(|C|)$ is the cost of solving the SVM on the small coreset $C$.

Extensions: Active Learning and Noise Tolerance

The coreset framework naturally extends to more complex learning scenarios where data labels are scarce or noisy.

Active Learning

In active learning, the model identifies points near the decision boundary to query an "oracle" (e.g., a human labeler). The authors provide a coreset-based justification for this process, moving away from the "version space halving" heuristic. They prove that active learning is essentially a targeted search for the few points that constitute the coreset, ensuring high confidence ($1-\delta$) with a limited number of queries.

Learning with Outliers

Agnostic learning, where data contains noise or outliers, is traditionally computationally hard. The authors frame this as finding a "clean" coreset hidden among $k$ outliers. They propose the SIMPLE OUTLIER SVM algorithm, which uses intelligent subsampling to find a near-optimal boundary in polynomial time relative to the number of points and noise level.

The SIMPLE OUTLIER SVM algorithm for finding maximum margin hyperplanes in the presence of outliers.

Key Results and Discussion

The research yields several significant advancements:

  • Improved Bounds: The coreset size bound is improved by a factor of $1/\epsilon$ to $O((R/\rho^*)^2/\epsilon)$.
  • Algorithmic Efficiency: The proposed methods offer substantial speedups over full-dataset SVM training by focusing on the coreset size rather than the total dataset size.
  • Theoretical Robustness: The work provides the first polynomial-time algorithm for maximum margin classification with a fixed number of outliers.

While the outlier-tolerant algorithm is polynomial, its complexity still depends on the coreset size, which may be high for very complex boundaries. Future work aims to apply coreset principles to broader tasks like clustering and regression in high-noise environments, suggesting that coresets are a widely applicable tool for efficient and robust machine learning.

Summary updated

Abstract

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 coresets. 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.
BibTeX
@inproceedings{harpeled2007maximum,
  author = {Sariel Har-Peled and Dan Roth and Dav Zimak},
  title = {{Maximum Margin Coresets for Active and Noise Tolerant Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=HkbC7QzO-H},
}
Figure