Source-linked AI summary
New Frameworks for Offline and Streaming Coreset Constructions
Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, Samson Zhou
TL;DR
The paper addresses whether sensitivity-based coreset sizes must depend quadratically on total sensitivity. It connects sensitivity sampling to VC-dimension learning bounds and shows that O(t log t) samples suffice, with applications to several clustering and subspace problems.
Problem
Many coreset constructions require sample sizes quadratic in total sensitivity t, although smaller dependence would make downstream processing more efficient.
Method
The paper reduces sensitivity sampling to obtaining an (ν, α)-sample for a bounded-VC-dimension function class, using sensitivity-weighted sampling and inverse-probability reweighting.
Results
O(t log t) samples suffice instead of O(t^2), and this dependence is necessary in some cases by coupon-collector arguments.
Takeaways & Limitations
The framework applies to k-median/k-means, k-line clustering, j-subspace approximation, and integer (j,k)-projective clustering.
Takeaways & Limitations
The paper's primary contribution is theoretical, and its framework includes settings where the loss function may return negative values.
Abstract
from arXiv · showhide
A coreset for a set of points is a small subset of weighted points that approximately preserves important properties of the original set. Specifically, if $P$ is a set of points, $Q$ is a set of queries, and $f:P\times Q\to\mathbb{R}$ is a cost function, then a set $S\subseteq P$ with weights $w:P\to[0,\infty)$ is an $ε$-coreset for some parameter $ε>0$ if $\sum_{s\in S}w(s)f(s,q)$ is a $(1+ε)$ multiplicative approximation to $\sum_{p\in P}f(p,q)$ for all $q\in Q$. Coresets are used to solve fundamental problems in machine learning under various big data models of computation. Many of the suggested coresets in the recent decade used, or could have used a general framework for constructing coresets whose size depends quadratically on what is known as total sensitivity $t$. In this paper we improve this bound from $O(t^2)$ to $O(t\log t)$. Thus our results imply more space efficient solutions to a number of problems, including projective clustering, $k$-line clustering, and subspace approximation. Moreover, we generalize the notion of sensitivity sampling for sup-sampling that supports non-multiplicative approximations, negative cost functions and more. The main technical result is a generic reduction to the sample complexity of learning a class of functions with bounded VC dimension. We show that obtaining an $(ν,α)$-sample for this class of functions with appropriate parameters $ν$ and $α$ suffices to achieve space efficient $ε$-coresets. Our result implies more efficient coreset constructions for a number of interesting problems in machine learning; we show applications to $k$-median/$k$-means, $k$-line clustering, $j$-subspace approximation, and the integer $(j,k)$-projective clustering problem.
1 Introduction
Coresets compress large datasets into weighted representatives that preserve query costs, enabling more efficient downstream optimization. The paper reduces the sensitivity-sampling size dependence from O(t^2) to O(t log t) and applies the framework across several learning problems.
- Motivation: Coresets represent large datasets with fewer weighted points while approximately preserving query costs.For k-means, optimizing on the smaller coreset can replace optimization on the full dataset.
- Sensitivity Sampling: Sensitivity sampling estimates point sensitivities, then samples points with probability proportional to those sensitivities.The total sensitivity is the sum of point sensitivities and controls the number of sampled points.
- Main Improvement: O(t log t) samples suffice for the common sensitivity-sampling framework, improving on the previous O(t^2) dependence.The paper states that Ω(t log t) samples are necessary in some cases, establishing optimal dependence on t.
- Technical Approach: The analysis reduces coreset construction to learning a function class with bounded VC dimension and obtaining an (ν, α)-sample.This guarantee yields multiplicative accuracy for sufficiently large functions and additive accuracy when functions are too small.
- Applications: Applications include k-median/k-means, k-line clustering, j-subspace approximation, and integer (j,k)-projective clustering.These problems are represented through unions of affine j-subspaces and related distance objectives.
2 Sensitivity Sampling
The paper proves that sensitivity sampling can achieve constant-factor coreset guarantees with O(t log t) samples. Its proof connects VC-dimension sampling bounds to sensitivity-weighted sampling and then to ε-coresets.
- Sensitivity Sampling: O(t log t) samples suffice for constant-factor coreset guarantees, replacing the previous O(t^2) sample bound.The result is theoretical and improves existing algorithms by changing their sampling parameters without requiring novel implementations.
- Sensitivity Sampling: Sensitivity upper bounds determine sampling probabilities, while inverse-probability reweighting preserves an unbiased estimate of the objective.The total upper sensitivity t is the sum of the pointwise bounds m(p).
- Theorem: The sampling theorem uses O(t log t) points, with dependence also governed by query-space VC dimension, approximation, and failure parameters.The supplied theorem statement specifies sampling probabilities based on m(p)/t and success probability at least 1−δ.
- Learning Reduction: VC-dimension sampling results provide simultaneous (ν, α)-approximations for every function in a class with probability at least 1−δ.The paper obtains this result by replacing a pseudo-dimension packing argument with an analogous VC-dimension bound.
- Reduction to ε-Coresets: Partitioning points by their contribution lets an (ν, α)-sample control both large-contribution groups and the aggregate error of small-contribution groups.This reduction establishes that the resulting sample is an ε-coreset.
3 Applications
The paper applies its improved sensitivity-sampling guarantee to projective clustering and related problems, yielding more efficient coreset constructions from known total-sensitivity bounds. These applications include k-line center, integer (j,k)-projective clustering, k-median/k-means, and j-subspace fitting.
- Applications: Theorem 1.1 improves the sample-size dependency on total sensitivity from O(t^2) to O(t log t), enabling more efficient coreset constructions across projective-clustering applications.The improvement applies whenever the problem's total sensitivity is known.
- Applications: The (j,k)-projective clustering framework includes k-median, k-means, and k-line clustering as special cases under suitable choices of j and distance function.When j = 0, Euclidean distance gives k-median and squared Euclidean distance gives k-means; when j = 1, the objective becomes k-line clustering.
- Applications: For k-line center and integer (j,k)-projective clustering, known total-sensitivity bounds combine with Theorem 1.1 to yield efficient coresets.The cited bounds depend on problem parameters and, in these results, may include logarithmic dependence on n.
- Applications: For k-line center, the paper combines total-sensitivity bounds with its sampling theorem to state coreset-output algorithms with probability guarantees.The relevant theorems provide separate results before and after tightening the total-sensitivity bound.
- Applications: For k-median and k-means, the paper states that the total-sensitivity bound yields algorithms outputting weighted ε-coresets with probability at least the theorem’s stated guarantee.These problems correspond to the j = 0 projective-clustering case.
- Applications: For j-subspace fitting, the paper uses sensitivity bounds depending on s = min(j,d) and the distance exponent z to derive weighted ε-coresets.The stated sensitivity regimes distinguish 1 ≤ z < 2, z = 2, and z > 2.
4 Coreset for k-clustering
This section develops sensitivity-style coreset constructions for k-clustering, using bicriteria assignments and generalized distance functions to obtain sharper bounds. The resulting algorithms sample weighted points and provide probabilistic ε-coreset guarantees, including smaller constructions for generalized pseudo distances.
- General framework: Importance generalizes sensitivity for k-clustering under ρ-pseudo distances.The framework uses importance to derive sharper coreset bounds than the general sensitivity formulation.
- General framework: An (α, β)-assignment is a bicriteria clustering with approximation factor α and up to β times as many centers.For k-means, an α-approximation selecting βk centers supplies such an assignment.
- Sampling construction: The Coreset algorithm samples points according to assignment-based probabilities combining cluster loss and cluster mass.It draws s samples independently and forms a weighted set from the sampled points.
- Sampling construction: With probability at least 1 −δ, the sampled set is an ε-coreset of size s for the k-clustering query space.The guarantee applies under the stated VC-dimension and parameter assumptions.
- Smaller coreset: The paper extends pseudo distances to (ρ, ψ, φ)-pseudo distance functions and introduces Smaller-Coreset constructions for them.The conditional normalized distance requires ψ < ε/(4ρ(α + 1)) and supports a construction that augments sampled points with assignment centers.
- Smaller coreset: For the generalized setting, the resulting coreset also has an ε-guarantee with probability at least 1 −δ.A related construction outputs a weighted subset of size s, while the smaller construction includes the centers B.
5 Empirical Evaluations
The empirical evaluations compare the paper’s coreset algorithms with uniform sampling on offline sensor datasets and a streaming Wikipedia document-term matrix. The algorithms improve over uniform sampling, with the conditional normalized approach outperforming general sensitivity sampling in the streaming experiment.
- Experimental setup: The experiments evaluate coreset constructions against uniform sampling on gyroscope and accelerometer datasets, plus a Wikipedia document-term matrix stream.The offline evaluations use sensor data, while the streaming evaluation uses k-means with k = 100 and k = 200.
- 5.1 Evaluations on Offline Data: The offline evaluations use sample or coreset sizes from 1000 to 7000 and evaluate k = 100 and k = 200.Empirical multiplicative error is computed from the costs of clustering the full data and the coreset.
- 5.1 Evaluations on Offline Data: The paper reports a significant improvement of its algorithms over uniform sampling on the gyroscope and accelerometer evaluations.The gyroscope results are shown in Figure 2 and the accelerometer results in Figure 3.
- 5.2 Evaluations on Streaming Data: The conditional normalized algorithm performs much better than the general sensitivity sampling algorithm in the streaming evaluation.The figure caption identifies these as Algorithms 2 and 1, respectively.