Coresets for Classification - Simplified and Strengthened

Tung Mai, Anup B. Rao, Cameron Musco

Abstract

We give relative error coresets for training linear classifiers with a broad class of loss functions, including the logistic loss and hinge loss. Our construction achieves $(1\pm \epsilon)$ relative error with $\tilde O(d \cdot \mu_y(X)^2/\epsilon^2)$ points, where $\mu_y(X)$ is a natural complexity measure of the data matrix $X \in \mathbb{R}^{n \times d}$ and label vector $y \in \{-1,1\}^n$, introduced by Munteanu et al.

  1. Our result is based on subsampling data points with probabilities proportional to their $\ell_1$ Lewis weights. It significantly improves on existing theoretical bounds and performs well in practice, outperforming uniform subsampling along with other importance sampling methods. Our sampling distribution does not depend on the labels, so can be used for active learning. It also does not depend on the specific loss function, so a single coreset can be used in multiple training scenarios.

Introduction

In the era of "Big Data," training machine learning models on millions or billions of points is computationally grueling. Coresets offer a solution: they are tiny, weighted subsets of the original data that act as a proxy. If you find the best model for the coreset, it should be nearly as good as the model trained on the full dataset.

However, for classification tasks (using loss functions like logistic or hinge loss), creating small coresets with "relative error" guarantees is hard. Standard techniques often fail because these loss functions can be very small for many points, making it difficult to approximate the total loss without taking a huge number of samples. Previous research introduced a complexity measure, $\mu_y(X)$, to handle this, but the resulting coreset sizes had high polynomial dependencies on the dimension and error margins, making them less practical.

Methodology

The authors depart from the traditional "sensitivity framework" used in most coreset research. Instead, they utilize:

  • $\ell_1$ Lewis Weights: This is the paper's "secret sauce." Lewis weights are a measure of a row's importance in a matrix. While leverage scores (related to $\ell_2$) are common in linear regression, $\ell_1$ Lewis weights are better suited for "hinge-like" losses (logistic, hinge, ReLU) because these losses grow linearly, similar to the $\ell_1$ norm.
  • Rademacher Complexity & Contraction: To prove their method works, they use the Ledoux-Talagrand contraction principle. This allows them to show that if their sampling preserves the $\ell_1$ norm of the data, it will also preserve the classification loss.
  • Label-Independent Sampling: Crucially, their sampling distribution depends only on the feature matrix $X$, not the labels $y$. This means a single coreset can be used for multiple training scenarios or even active learning where labels are initially unknown.

Key Results and Empirical Evaluation

The paper provides a significant theoretical leap, reducing the required coreset size from $\tilde{O}(d^3 \mu^3 / \epsilon^4)$ in previous work to just $\tilde{O}(d \mu^2 / \epsilon^2)$. This is a massive improvement in how the coreset scales with dimension ($d$) and desired accuracy ($\epsilon$).

Comparison of coreset sizes and theoretical guarantees for linear classification.

Empirical Dominance

The authors evaluated their method against three standard large-scale benchmarks: Webb Spam (350,000 instances), Covertype (581,012 instances), and KDD Cup ’99 (494,021 instances). In experiments, the Lewis weight method (lewis) consistently outperformed uniform sampling. On the KDD Cup '99 dataset—which has high complexity—it significantly outperformed the previous state-of-the-art importance sampling method (l2s).

Lower Bounds

The authors also proved a new lower bound for regularized classification, showing that when you add a regularization term, uniform sampling is actually quite hard to beat, essentially reaching the theoretical limit.

Discussion and Future Work

While the bounds are much better, they still depend on the complexity measure $\mu_y(X)$. If a dataset is perfectly separable, $\mu$ can become very large, which would theoretically require a larger coreset. Additionally, computing Lewis weights is more expensive than uniform sampling or basic leverage scores (requiring about 5x more time than the previous best method). However, for very large datasets, the time saved during the training phase (on a much smaller coreset) far outweighs this initial setup cost.

Since the sampling is label-independent, a promising future direction is applying this specifically to active learning pipelines to reduce labeling costs.

Summary updated

Abstract

We give relative error coresets for training linear classifiers with a broad class of loss functions, including the logistic loss and hinge loss. Our construction achieves $(1\pm \epsilon)$ relative error with $\tilde O(d \cdot \mu_y(X)^2/\epsilon^2)$ points, where $\mu_y(X)$ is a natural complexity measure of the data matrix $X \in \mathbb{R}^{n \times d}$ and label vector $y \in \{-1,1\}^n$, introduced in by Munteanu et al. 2018. Our result is based on subsampling data points with probabilities proportional to their $\ell_1$ $Lewis$ $weights$. It significantly improves on existing theoretical bounds and performs well in practice, outperforming uniform subsampling along with other importance sampling methods. Our sampling distribution does not depend on the labels, so can be used for active learning. It also does not depend on the specific loss function, so a single coreset can be used in multiple training scenarios.
BibTeX
@inproceedings{mai2021coresets,
  author = {Tung Mai and Anup B. Rao and Cameron Musco},
  title = {{Coresets for Classification - Simplified and Strengthened}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=qz0MLeaTP1C},
}

Loading related content...

Figure