When training models on billions of rows, the computational bottleneck is often the sheer volume of data. Coresets offer a solution: they are tiny, weighted subsets of the original data that act as a mathematical proxy. If you train a model on a well-constructed coreset, the resulting parameters should be nearly identical to those obtained from the full dataset.
While coresets are well-understood for simple problems like $k$-means clustering, they become significantly harder to construct for the complex loss functions used in modern machine learning, such as logistic regression or F1-score optimization.
The Sensitivity Problem
The fundamental challenge in coreset construction is sensitivity—the measure of how much a single data point can influence the total loss. For a coreset to be small and accurate, we must be able to bound this influence.
In simple linear regression with squared loss, Steve Hanneke and colleagues note that every data point exerts a global influence on the optimal parameters. However, the problem becomes even more acute with monotonic loss functions, such as the sigmoid or logistic loss. As Elad Tolochinsky explains, these functions do not naturally bound the influence of individual observations. If a data point is an outlier and the model is currently far from fitting it, that single point can exert an unbounded pull on the gradient.
This leads to a "hard limit" for data reduction. Alexander Munteanu and David P. Woodruff proved that for logistic regression, universal sublinear compression is theoretically impossible in the worst case. Some datasets are simply "uncompressible" because every point is critical to defining the decision boundary.
Bridging the Gap with Regularization
If universal compression is impossible, how do we proceed? The research suggests two primary paths: adding structural constraints or relaxing the approximation requirements.
Elad Tolochinsky and Dan Feldman demonstrated that regularization is the "missing link." By adding a standard penalty term (like $\ell_2$ regularization), the influence of any single point is mathematically capped. This allows for the creation of coresets that are less than 1% of the original data size while maintaining rigorous theoretical guarantees on accuracy. This framework is generic enough to apply to logistic regression, sigmoid-based networks, and other monotonic kernels.
Strong vs. Weak Coresets
Another major hurdle appears when we move from simple additive losses to non-decomposable metrics like the F1-score or the Matthews Correlation Coefficient (MCC). These metrics are non-linear combinations of true/false positives and negatives, meaning you cannot calculate the total score by simply summing up the scores of individual points.
Anirban Dasgupta and Rachit Chhaya identify a distinction between two types of coresets:
- Strong Coresets: Must approximate the loss for every possible model.
- Weak Coresets: Only need to approximate the loss for a subset of "good" or relevant models.
For F1-scores, a strong coreset must be nearly the size of the original dataset—rendering it useless for compression. However, by aiming for a weak coreset, researchers found that simple stratified uniform sampling becomes surprisingly powerful. This approach provides strong guarantees for the models that actually matter (the high-performing ones) while ignoring the models that fit the data poorly anyway.
Expanding the Reach of Coresets
This logic of sensitivity and approximation has been extended to various specialized architectures:
- Decision Trees: Ibrahim Jubran and Dan Feldman bridged computational geometry and ML to create coresets for decision trees, enabling faster hyperparameter tuning.
- Dependency Networks: Alejandro Molina and Kristian Kersting showed that while count-based models (like Poisson) have theoretical compression limits due to outlier sensitivity, Gaussian models admit coresets whose size is entirely independent of the original dataset size.
Ultimately, the field is converging on the realization that while "perfect" compression is often impossible, "useful" compression is highly achievable. By understanding the complexity of the dataset—a measure Gregory Dexter and Petros Drineas recently showed can be calculated via linear programming—we can determine exactly how much a dataset can be distilled without losing its essence.