In the era of massive datasets, training models on every single data point is often computationally prohibitive. Coresets—small, representative, weighted subsets of the original data—offer a compelling solution. Training a model on a well-constructed coreset yields parameters nearly as good as those trained on the full dataset. This paper introduces a simplified and significantly more efficient method to create coresets for training linear classifiers, such as Logistic Regression and Support Vector Machines (SVMs). By sampling data points based on their $\ell_1$ Lewis weights, the authors achieve a near-optimal theoretical bound that scales linearly with the feature dimension ($d$), drastically improving upon previous methods.
The Challenge of Classification Coresets
Creating coresets for classification tasks using logistic or hinge loss is notoriously difficult. Unlike linear regression, these loss functions do not naturally allow for small "relative error" coresets unless one accounts for the "complexity" of the data—specifically, how separable or imbalanced the classification might be.
Previous state-of-the-art methods relied on the "sensitivity framework," which often hit a bottleneck. These methods required coreset sizes that grew with the cube of the number of features ($d^3$). This poor scaling made them less practical for high-dimensional data.
Methodology: $\ell_1$ Lewis Weights
The authors propose a novel sampling strategy based on $\ell_1$ Lewis weights. These weights measure the "importance" or "influence" of each row in a data matrix, serving as a generalization of leverage scores (used in $\ell_2$ regression) to the $\ell_1$ norm.
The core insight is that "hinge-like" losses (Logistic, Hinge, ReLU) behave similarly to the $\ell_1$ norm: they grow linearly for "important" (misclassified or near-boundary) points and flatten out for others. Therefore, tools designed for $\ell_1$ regression are surprisingly effective here. The algorithm proceeds as follows:
- Calculate or approximate the $\ell_1$ Lewis weights for the data matrix $X$.
- Subsample $m$ points with probabilities proportional to these weights.
- Assign each sampled point a weight $w_i$ to compensate for its sampling probability.
Crucially, this sampling distribution depends only on the feature matrix $X$, not the labels $y$. This label independence means a single coreset can be used for multiple training scenarios or even active learning, where labels are initially unknown.
Theoretical and Empirical Results
By utilizing Rademacher averages and contraction bounds instead of the traditional sensitivity framework, the authors prove that their coreset approximates the total loss with significantly fewer points. They introduce the concept of "Nice Hinge Functions," a broad class of loss functions that allows them to prove guarantees for Logistic Regression, SVMs, and ReLU regression simultaneously.
As shown in the comparison above, they reduced the required coreset size from $\tilde{O}(d^3 \mu^3 / \epsilon^4)$ to $\tilde{O}(d \mu^2 / \epsilon^2)$, where $\mu$ represents the data complexity measure. This is a massive improvement in how the coreset size scales with the number of features.
Empirically, the authors evaluated their method on three standard large-scale benchmarks: WEBB SPAM (350k points), COVERTYPE (581k points), and KDD CUP ’99 (494k points). In head-to-head tests, Lewis weight sampling consistently outperformed uniform sampling and previous importance sampling methods (like square-root leverage scores). It proved particularly robust on the KDD CUP '99 dataset, which has a high complexity measure ($\mu \approx 35$) where other sampling methods struggled.
Limitations and Future Directions
While a significant leap forward, the method has a few limitations:
- Separability Sensitivity: The coreset size still depends on the complexity measure $\mu_y(X)$. If the data is perfectly separable, $\mu$ can be very large, leading to larger coresets. Finding ways to mitigate this dependence remains an open challenge.
- Regularization: The method works well with regularization in practice, but the current theoretical bounds do not improve when regularization is added, unlike some other specialized coreset techniques.
- Linear Models Only: This work focuses strictly on linear classifiers. Extending these bounds to non-linear models or deep neural networks is a significant next step for the field.
Summary updated