When dealing with massive datasets, training complex machine learning models or running optimization algorithms becomes computationally prohibitive. A natural response is to downsample the data. However, standard uniform random sampling suffers from a fundamental flaw: it treats all data points equally, completely ignoring their structural importance.
If a dataset contains a massive, dense cluster of redundant points alongside a few isolated outliers, uniform sampling will overwhelmingly select from the dense cluster and miss the outliers entirely. In many foundational problems—such as clustering, robust regression, and subspace approximation—missing these rare but highly influential points completely distorts the final model.
To solve this, researchers developed the framework of coresets: small, weighted subsets of the original data that mathematically guarantee that the loss function evaluated on the subset closely approximates the loss function evaluated on the full dataset for any potential model parameters. The engine behind constructing these coresets is sensitivity-based importance sampling.
The Core Intuition: What is Sensitivity?
The sensitivity of a data point measures its maximum possible importance to the global objective function. Mathematically, the sensitivity $s(x)$ of a point $x$ is defined as the maximum fraction of the total cost that this single point can incur, taken over all possible parameter configurations $\theta$:
$$s(x) = \max_{\theta} \frac{\text{cost}(x, \theta)}{\sum_{x' \in D} \text{cost}(x', \theta)}$$
Consider a $k$-means clustering problem. If a point lies in a highly dense region surrounded by millions of other points, its individual leverage over the cluster center is tiny; if we move the center slightly, the other millions of points still dominate the cost. Thus, its sensitivity is low. Conversely, if a point is an isolated outlier far from the rest of the data, a candidate cluster center placed far away will incur a massive cost from this single point relative to the rest of the dataset. Its sensitivity is high.
As noted in Coresets for Nonparametric Estimation - the Case of DP-Means by Bachem et al., sampling points proportional to these sensitivities drastically reduces error variance compared to uniform subsampling, specifically because it prevents the omission of low-density but highly significant data regions.
The Mechanics of Inverse-Probability Weighting
Once sensitivities are computed, we sample data points with a probability $p_x$ proportional to their sensitivity $s(x)$. To ensure our compressed summary remains an unbiased estimator of the full dataset, we must reweight each selected point by the inverse of its sampling probability:
$$w_x = \frac{1}{n \cdot p_x}$$
This reweighting creates a beautiful balancing act:
- High-sensitivity points (outliers, unique geometric features) have a high probability of being selected. Because they are almost always included, they receive a low weight (close to 1), ensuring they do not artificially overpower the model.
- Low-sensitivity points (redundant points in dense regions) have a low probability of being selected. On the rare occasions they are picked, they receive a very high weight. This allows a single sampled point to act as a "proxy" or stand-in for the thousands of redundant points it represents.
This mechanism explains why the coreset acts as a high-fidelity proxy for the entire distribution. As demonstrated by Lucic in Strong Coresets for Hard and Soft Bregman Clustering with Applications to Exponential Family Mixtures, this targeted preservation allows practitioners to achieve massive computational speedups (often exceeding 80x) while maintaining strict accuracy bounds.
Resolving the Chicken-and-Egg Paradox
There is an immediate algorithmic hurdle to this strategy: to compute the exact sensitivity of a point, the definition requires us to know the total cost over all possible parameter configurations $\theta$. This creates a classic chicken-and-egg paradox. We want to build a coreset to find the optimal parameters efficiently, but we apparently need to know the behavior of all parameters to build the coreset.
To bypass this loop, algorithms compute upper bounds on sensitivity rather than the exact values. If we can find a cheaply computable function $\alpha(x) \ge s(x)$ such that the sum of all bounds $\sum \alpha(x)$ remains small, we can safely sample proportional to $\alpha(x)$ instead.
The standard recipe for bounding sensitivity involves computing a coarse, cheap approximation of the final solution first—often called a bicriteria approximation or a rough initial clustering. In One-shot Coresets: The Case of k-Clustering, Bachem et al. show that a lightweight, initial clustering pass provides a reference framework. The sensitivity of any point can then be bounded by its distance to its nearest rough cluster center plus the average distance of the cluster. This rough pass provides enough geometric structure to safely estimate each point's potential influence without solving the full optimization problem upfront.
Similarly, in the context of Bayesian inference, Huggins et al. in Coresets for Scalable Bayesian Logistic Regression utilize rough $k$-clustering to establish efficient upper bounds on log-likelihood sensitivities, avoiding the exhaustive computational overhead of exact influence calculations.
What Determines the Size of a Coreset?
The ultimate goal of a coreset is compression: we want the size of the subset to be as small as possible, ideally independent of the original dataset size $n$. The required size of a coreset is governed by two main factors: the complexity of the model's query space (often bounded by its VC-dimension or shattering dimension) and the total sensitivity ($t = \sum s(x)$) of the dataset.
In a major theoretical refinement, Feldman proved in Efficient Coreset Constructions via Sensitivity Sampling that the number of points required to form a valid coreset scales near-linearly with the total sensitivity ($O(t \log t)$), breaking a long-standing quadratic barrier.
Because coreset size depends so heavily on total sensitivity, any mechanism that reduces individual point influence directly yields smaller data summaries. This reveals a deep, elegant connection between data compression and regularization. As analyzed by Chhaya et al. in On Coresets for Regularized Regression, adding regularization penalties (like Ridge or Lasso) mathematically functions as a denominator penalty that caps the maximum influence any single outlier can exert. By shrinking individual sensitivities, regularization directly enables the construction of significantly smaller, more efficient coresets.
A Versatile Paradigm Across Domains
While the intuition originates in geometric clustering, sensitivity-based importance sampling generalizes across a vast array of mathematical problems:
- Robust Regression: In streaming environments where data arrives continuously, Mahabadi et al. in Adaptive Sketches for Robust Regression with Importance Sampling combine sensitivity sampling with sketching. Their approach isolates high-sensitivity "heavy rows" to protect the model from outliers while compressing the remaining "light rows."
- Generalized Linear Models: For count data, Lie and Munteanu in Data subsampling for Poisson regression with pth-root-link developed the first rigorous sensitivity bounds for Poisson regression, proving that massive count datasets can be compressed polylogarithmically.
- Alternative Influence Frameworks: The core philosophy of weighting by model impact extends beyond explicit sensitivity bounds. For instance, Ting in Optimal Subsampling with Influence Functions leverages statistical influence functions to balance input feature distributions with model errors, optimizing data reduction for generalized linear and quantile regressions.
Ultimately, sensitivity-based sampling works because it shifts the data-reduction paradigm from random selection to informational value. By identifying which points hold the veto power over an objective function and scaling the rest, it allows massive, unmanageable datasets to be condensed into lean, mathematically rigorous summaries.
Key Foundational Work
Strong Coresets for Hard and Soft Bregman Clustering with Applications to Exponential Family Mixtures (2015) — contributed 2 concept elements to this direction.
Coresets for Nonparametric Estimation - the Case of DP-Means (2015) — contributed 2 concept elements to this direction.