PaperlayerView exact revision on arXiv

Source-linked AI summary

Practical Coreset Constructions for Machine Learning

Olivier Bachem, Mario Lucic, Andreas Krause

arXiv:1703.06476v2stat.ML

TL;DR

Large data sets make established machine-learning algorithms computationally infeasible, motivating small coresets whose size is sublinear in the data-set size. The paper surveys state-of-the-art coreset construction, presents a theoretically sound general framework illustrated with k-means, and summarizes constructions across machine-learning problems; such coresets can enable computationally intensive inference on small summaries.

  • Problem

    Large data sets make gathering, storing, and analyzing data expensive, while established algorithms can become computationally infeasible; the paper asks how to construct small coresets with size sublinear in n.

  • Method

    The paper surveys state-of-the-art coreset construction, develops a theoretically sound general framework illustrated with k-means clustering, and summarizes constructions for diverse machine-learning problems.

  • Results

    Coreset sizes are usually sublinear in, or independent of, the original number of data points, allowing computationally intensive inference algorithms to be applied to the original problem on a small coreset.

  • Takeaways & Limitations

    Coresets provide succinct summaries on which solutions can be sought while remaining provably competitive with solutions found on the full data set.

  • Takeaways & Limitations

    For a fixed query, unbiased uniform subsampling may converge slowly and require impractically large sample sizes.

Abstract

from arXiv · show

We investigate coresets - succinct, small summaries of large data sets - so that solutions found on the summary are provably competitive with solution found on the full data set. We provide an overview over the state-of-the-art in coreset construction for machine learning. In Section 2, we present both the intuition behind and a theoretically sound framework to construct coresets for general problems and apply it to $k$-means clustering. In Section 3 we summarize existing coreset construction algorithms for a variety of machine learning problems such as maximum likelihood estimation of mixture models, Bayesian non-parametric models, principal component analysis, regression and general empirical risk minimization.

Introduction

Massive data sets make storing and analyzing data increasingly expensive, motivating coresets: small summaries whose solutions remain provably competitive with full-data solutions. The paper surveys practical constructions, develops a general framework through k-means, and reviews applications across machine learning.

  • Massive data sets make established algorithms computationally infeasible and may require storage across machine clusters.
  • Coresets are succinct summaries designed so solutions found on them are provably competitive with solutions found on the full data set.
  • Sampling-based constructions identify point importance, form a weighted subsample, and solve the problem on the resulting coreset with theoretical guarantees.
  • Coreset sizes are usually sublinear in, or independent of, the original data-set size, enabling superlinear inference algorithms on the summary.
  • The paper presents a theoretically sound general framework illustrated with k-means and surveys constructions for mixture models, Bayesian non-parametric models, PCA, regression, and empirical risk minimization.

Sampling

The section formalizes coresets for optimization-based machine learning problems, emphasizing multiplicative cost approximation and the distinction between strong and weak guarantees. It also states why optimizing on a coreset can preserve full-data solution quality.

  • The framework targets optimization problems with weighted data and additively decomposable non-negative costs.
  • It illustrates the framework with support vector machines, logistic regression, linear regression, and k-means clustering.
  • A coreset provides a 1 ± ε multiplicative approximation to the original cost function for possible queries.
  • Strong coresets guarantee the approximation uniformly over all queries, whereas weak coresets guarantee it only for the optimal solution.
  • The optimal solution found on a coreset is provably competitive with the full-data optimum when evaluated on the full data set.

2.2 Naive approaches to constructing coresets

Uniform subsampling is unbiased for any fixed query but can require nearly linear sample sizes because a single point may dominate the cost. Thus, naive sampling is impractical for small coreset construction.

  • The central challenge is constructing coresets sublinear in n while remaining polynomial in dimension and desired error.
  • Uniform subsampling produces an unbiased cost estimator for any fixed query, but convergence can be slow.
  • For a single query, Chebyshev’s inequality yields an error probability bounded by n/(ε^2m).
  • At least m ≥ n/(ε^2δ) samples are required for probability at least δ, making uniform sampling no better than returning the full data set.
  • A data set with one cost-dominating point shows that uniform subsampling can fail even for a single query.

2.3. Importance sampling & sensitivity

Importance sampling addresses uniform sampling’s high variance by sampling influential points more often, using sensitivity to design a distribution that supports coreset guarantees. Tighter sensitivity bounds reduce the required sample size.

  • Importance sampling skews selection toward important points while retaining an unbiased cost estimate.
  • The ideal distribution for one query samples points according to their influence, minimizing estimator variance.
  • A single distribution must work uniformly across all queries, motivating sensitivity as each point’s worst-case impact on the objective.
  • Sensitivity-based sampling provides valid ε-coresets when the sample size is sufficiently large, with the full proof deferred to the uniform-guarantee framework.
  • The sample requirement depends quadratically on total sensitivity, so tighter sensitivity bounds reduce sampling needs; trivial bounds recover impractical uniform sampling.

2.4 Bounding the sensitivity

The sensitivity-bounding framework first obtains an efficient rough solution, then uses it to bound each point’s worst-case impact; k-means illustrates this process through bicriteria approximations and D2-sampling.

  • Bounding the sensitivity: Sensitivity bounds begin with a rough approximation of the optimal solution and use it to bound every point’s worst-case impact.The framework is illustrated for k-means clustering.
  • Bounding the sensitivity: A bicriteria approximation is a set of βk centers whose cost is compared with the optimal k-center solution.Here, OPT denotes the optimal solution with k centers.
  • Bounding the sensitivity: D2-sampling selects an initial center uniformly, then samples subsequent centers with probability proportional to squared distance from existing centers.The procedure runs for k − 1 subsequent iterations.
  • Bounding the sensitivity: O(log k) expected competitiveness follows for the k sampled centers under D2-sampling.The bound is E[cost(X, B)] ≤ 8(log2 k + 2) cost(X, OPT).
  • Bounding the sensitivity: 16(log2 k + 2) cost(X, OPT) bounds the selected solution’s cost with probability at least 1 − δ.Thus, the solution is an (α, β)-bicriteria approximation with α = 16(log2 k + 2) and β = 1.

2.4. Bounding the sensitivity

The resulting bicriteria solution bounds point sensitivities, enabling importance sampling whose total sensitivity is linear in k and independent of the data-set size.

  • Bounding the sensitivity: The toy example visualizes bicriteria centers and sensitivity-based probabilities, with smaller clusters receiving greater sampling emphasis.Blue indicates low probability and red high probability.
  • Bounding the sensitivity: Any (α, β)-bicriteria approximation can be used to bound the sensitivity function.The approximation supplies the reference solution for measuring each point’s worst-case impact.
  • Bounding the sensitivity: Lemma 2.2 assigns each point to its closest bicriteria center and uses the resulting cluster partition to derive its sensitivity bound.The construction is for squared Euclidean k-clustering.
  • Bounding the sensitivity: O(k) is the total sensitivity bound obtained after a constant number of Algorithm 1 runs, independent of the number of data points n.The result is tight because some data sets have total sensitivity in Ω(k).
  • Bounding the sensitivity: The proof bounds the squared distance from a point to any query using the double triangle inequality through its assigned bicriteria center.The key inequality is d(x,Q)^2 ≤ 2d(x,b_x)^2 + 2d(b_x,Q)^2.

2.5. Uniform guarantee for all queries

Sensitivity yields a coreset guarantee for one query, while a bounded pseudo-dimension and a finite query cover extend the guarantee uniformly to every query.

  • Uniform guarantee for all queries: The framework extends a single-query coreset guarantee to an ε-coreset that satisfies the property for every query Q ∈ Q.This is the central transition of the section.
  • Uniform guarantee for all queries: A small query subset Q* enables a union bound: satisfying the guarantee on Q* with ε/2 implies it for all Q with ε.This avoids bounding infinitely many query-specific bad events directly.
  • Uniform guarantee for all queries: Pseudo-dimension generalizes VC dimension to non-binary cost functions mapping to non-negative reals.It measures threshold-based patterns realizable by the function family.
  • Uniform guarantee for all queries: The relevant function family is F = {g_Q(·) | Q ∈ Q}, whose pseudo-dimension controls the uniform coreset analysis.The functions g_Q are bounded in [0,1].
  • Uniform guarantee for all queries: Theorem 2.3 samples points with probabilities proportional to µ_X(x)s(x), assigning sampled points corresponding weights to obtain an ε-coreset with probability at least 1 − δ.The sample-size guarantee depends on the sensitivity sum and the pseudo-dimension.

2.5. Uniform guarantee for all queries

The proof applies concentration to normalized cost functions over the sensitivity-weighted sample, then transfers the resulting uniform bound from the function family back to all queries.

  • Uniform guarantee for all queries: The analysis defines a bad event as the existence of a query whose coreset and full-data costs differ by more than ε times the full-data cost.The target guarantee is uniform over Q.
  • Uniform guarantee for all queries: A finite query cover reduces the uniform analysis to finitely many events, allowing the union bound to control failure probability.The cover uses an ε/2 approximation to obtain an ε guarantee.
  • Uniform guarantee for all queries: The formal proof uses Li et al.’s chaining result for bounded functions with pseudo-dimension d′.The theorem applies to independently sampled points from an arbitrary distribution q.
  • Uniform guarantee for all queries: Choosing ν = 1/2 and α = ε/(3S) applies the chaining theorem to F = {g_Q(·) | Q ∈ Q}.This parameter choice connects the abstract concentration result to the sensitivity-based coreset construction.
  • Uniform guarantee for all queries: The normalized functions g_Q relate coreset cost to full-data cost through g_Q(x) = cost(C,Q) / (S cost(X,Q)).This normalization enables the function-family analysis.

2.6 Exemplary coreset construction for k-means

The k-means construction applies the general coreset framework by bounding the pseudo-dimension of its function family. This yields a bound of O(dk log k).

  • The k-means construction applies the general coreset framework to the function family F = {gQ(·) | Q ∈ Q}.
  • The pseudo-dimension of the k-means function family is bounded by O(dk log k).The bound follows by relating the pseudo-dimension to the VC dimension of k-fold intersections of halfspaces.
  • The extra log k factor is obtained using an argument based on Sauer’s Lemma.

2.6. Exemplary coreset construction for k-means

The construction combines a stronger pseudo-dimension bound with sensitivity-based importance sampling to produce a probabilistically guaranteed k-means coreset. The resulting procedure first obtains a rough solution and then samples weighted points according to sensitivity-derived probabilities.

  • A primal shattering dimension bound of O(dk) implies only a pseudo-dimension bound of O(dk log dk).This discrepancy can lead to larger coreset sizes when the general theorem is applied.
  • The construction instead uses the stronger pseudo-dimension bound O(dk log k).
  • The procedure first computes a rough approximation using k-means++ seeding, then subsamples points by importance sampling based on sensitivity.
  • The algorithm samples weighted points from X according to probabilities p(x), assigning each sampled point weight 1/(m·p(x)).
  • With probability at least 1 − δ, the resulting set C is a (k, ε)-coreset for k-means.
  • The proof follows from Theorem 2.3, Lemma 2.2, and the bound Pdim(F) ∈ O(dk log k).

Coresets for Machine Learning

The paper surveys practical coreset constructions across machine learning, emphasizing sampling-based methods, theoretical guarantees, and applications from clustering to regression and SVMs.

  • General framework: Coreset construction combines an approximation, sensitivity bounds, and weighted importance sampling to summarize data while preserving solution quality.The framework then applies existing machine-learning algorithms to the weighted coreset.
  • Additional settings: Coresets also support PCA, kernel methods, SVMs, communication-efficient ERM, and streaming or parallel computation through merge-and-compress trees.For SVMs, the Core Vector Machine has linear time in n, space independent of n, and a (1 + ε)^2 approximation to the objective.
  • Mixture models: For mixture-model likelihood estimation, fitting a weighted model on a much smaller coreset can make EM orders of magnitude faster while approximating the full-data likelihood.The surveyed results also state uniform approximation of likelihoods as ε approaches zero.
  • Nonparametric mixture models: Sublinear coresets are reported for DP-Means when the optimal center count is sublinear, using D2-sampling to infer a bicriteria center count.The resulting bicriteria approximation is O(log^2 k′)-competitive.
  • Regression: Regression coresets can be deterministic and polynomial-time, with size O(k/ε^2) where k is the data matrix rank.The results extend to multiple-response regression and include nearly matching lower bounds.
Loading 1703.06476v2…