A unified framework for approximating and clustering data

By Dan Feldman, Michael Langberg. 2011

505 citations recorded by the source corpus.

Given a set F of n positive functions over a ground set X, we consider the problem of computing x* that minimizes the expression ∑f ∈ Ff(x), over x ∈ X. A typical application is shape fitting, where we wish to approximate a set P of n elements (say, points) by a shape x from a (possibly infinite) family X of shapes. Here, each point p ∈ P corresponds to a function f such that f(x) is the distance from p to x, and we seek a shape x that minimizes the sum of distances from each point in P. In the k-clustering variant, each x\in X is a tuple of k shapes, and f(x) is the distance from p to its closest shape in x. Our main result is a unified framework for constructing coresets and approximate clustering for such general sets of functions. To achieve our results, we forge a link between the classic and well defined notion of ε-approximations from the theory of PAC Learning and VC dimension, to the relatively new (and not so consistent) paradigm of coresets, which are some kind of "compressed representation" of the input set F. Using traditional techniques, a coreset usually implies an LTAS (linear time approximation scheme) for the corresponding optimization problem, which can be computed in parallel, via one pass over the data, and using only polylogarithmic space (i.e, in the streaming model). For several function families F for which coresets are known not to exist, or the corresponding (approximate) optimization problems are hard, our framework yields bicriteria approximations, or coresets that are large, but contained in a low-dimensional space. We demonstrate our unified framework by applying it on projective clustering problems. We obtain new coreset constructions and significantly smaller coresets, over the ones that appeared in the literature during the past years, for problems such as: k-Median [Har-Peled and Mazumdar,STOC'04], [Chen, SODA'06], [Langberg and Schulman, SODA'10]; k-Line median [Feldman, Fiat and Sharir, FOCS'06], [Deshpande and Varadarajan, STOC'07]; Projective clustering [Deshpande et al., SODA'06] [Deshpande and Varadarajan, STOC'07]; Linear lp regression [Clarkson, Woodruff, STOC'09 ]; Low-rank approximation [Sarlos, FOCS'06]; Subspace approximation [Shyamalkumar and Varadarajan, SODA'07], [Feldman, Monemizadeh, Sohler and Woodruff, SODA'10], [Deshpande, Tulsiani, and Vishnoi, SODA'11]. The running times of the corresponding optimization problems are also significantly improved. We show how to generalize the results of our framework for squared distances (as in k-mean), distances to the qth power, and deterministic constructions.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

Coresets via Bilevel Optimization for Continual Learning and Streaming (2020, methodology): “A popular approach is to require uniform approximation guarantees on the loss function, e.g., coresets for k -means [18], Gaussian mixture model [41] and logistic regression [28].”
Geometric median in nearly linear time (2016, neutral): “…(1 + (cid:15) ) -approximate solution, i.e. x ∈ R d with f ( x ) ≤ (1 + (cid:15) ) f ( x ∗ ) , the previous fastest running times were either O ( d · n 4 / 3 (cid:15) − 8 / 3 ) by [7], ˜ O ( d exp − 4 log − ) by [1], ˜ O ( nd + poly ( d, − 1 )) by [10], or O (( nd ) O (1) log 1 ) time by [24, 31].”
Automated Scalable Bayesian Inference via Hilbert Coresets (2017, methodology): “This is indeed the case; Braverman et al. (2016); Feldman and Langberg (2011) showed that with high probability, the coreset likelihood L ( W, θ ) satisﬁes Eq.”
Provable Filter Pruning for Efficient Neural Networks (2019, background): “…in Big Data settings, ranging from sparsifying matrices (Baykal et al., 2019a; Achlioptas et al., 2013; Drineas & Zouzias, 2011; Kundu & Drineas, 2014; Tropp et al., 2015) to constructing coresets for machine learning problems (Braverman et al., 2016; Feldman & Langberg, 2011; Bachem et al., 2017).”
Training Gaussian Mixture Models at Scale via Coresets (2017, methodology): “Feldman and Langberg (2011) successfully used the same idea to construct coresets for geometric clustering problems.”
Practical Coreset Constructions for Machine Learning (2017, methodology): “Feldman et al. [2006] provided strong coresets with size exponential in d, j, and logarithmic in n with O(n) construction time. The results were later improved to linear dependence on d, at the cost of O(njd) construction time [Feldman et al., 2010]. Feldman et al. [2013] proved that the sum of Eucl”
Coresets for Nonparametric Estimation - the Case of DP-Means (2015, methodology): “…authors’ knowledge, all previous work on coresets was focused exclusively on parametric models such as K-Means (Har-Peled & Mazumdar, 2004; Har-Peled & Kushal, 2005; Feldman et al., 2007; Chen, 2009; Langberg & Schulman, 2010; Feldman & Langberg, 2011) and Gaussian mixtures (Feldman et al., 2011).”
Training Mixture Models at Scale via Coresets (2017, methodology): “For example, Feldman and Langberg (2011) apply Algorithm 3 which, with probability at least 1 − δ, provides a constant-factor approximation of size O(dk log 1/δ log n).”
Data-Independent Structured Pruning of Neural Networks via Coresets (2020, methodology): “Definition 4 (VC-Dimension [13]): Let (P, w, X, f ) be a query space.”
Improved Distributed Principal Component Analysis (2014, background): “A beautiful property of the coresets developed in [9] is that for approximate PCA their size also only depends linearly on the dimension d, whereas previous coresets depended quadratically on d [8].”
Handbook of Big Data (2016, methodology): “The software will be available as an R-package, but the instructions below do not reﬂect this and get the reader going by sourcing the software from the ﬁrst author’s site.”
Core‐sets: An updated survey (2019, methodology): “P The size of the sample depends polynomially on max p 2 P , x 2X j f p , x ð Þ j , the sum of weights p 2 P w ( p ), 1/ ε , log(1/ δ ), and a measure of complexity for a query space that is related to generalized VC-dimension (Braverman et al., 2016; Feldman & Langberg, 2011).”
Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering (2013, unknown): “Our main result is a dimensionality reduction algorithm for n points in high d-dimensional space to n points in O(j/ε2) dimensional space, such that the sum of squared distances to every object that is contained in a j-dimensional subspace is approximated up to a (1 + ε)factor.”
k-Means for Streaming and Distributed Big Sparse Data (2015, methodology): “This problem is solved in theory using rough approximation algorithms or bi-criteria approximations [22, 10] that replaces the optimal solution, or using the merge-and-reduce tree that apply the coreset constuction only on small sets.”
Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds (2018, methodology): “Coresets have been used successfully to accelerate various machine learning algorithms such as k-means clustering [20, 9], graphical model training [38], and logistic regression [23] (see the surveys of [6] and [39] for a complete list).”
Low rank approximation with entrywise l1-norm error (2017, methodology): “A sequence of work [25, 33, 40, 41, 82] shows how to obtain an O (1)-approximation to this problem in nnz(A) + (n + d ) poly(k ) + exp(k ) time, and using that ‖C ‖1,2 ≤ ‖C ‖1 ≤ √ d ‖C‖1,2 results in an O ( √ d )-approximation.”