Private coresets

By Dan Feldman, Amos Fiat, Haim Kaplan, Kobbi Nissim. 2009

129 citations recorded by the source corpus.

A coreset of a point set P is a small weighted set of points that captures some geometric properties of $P$. Coresets have found use in a vast host of geometric settings. We forge a link between coresets, and differentially private sanitizations that can answer any number of queries without compromising privacy. We define the notion of private coresets, which are simultaneously both coresets and differentially private, and show how they may be constructed. We first show that the existence of a small coreset with low generalized sensitivity (i.e., replacing a single point in the original point set slightly affects the quality of the coreset) implies (in an inefficient manner) the existence of a private coreset for the same queries. This greatly extends the works of Blum, Ligett, and Roth [STOC 2008] and McSherry and Talwar [FOCS 2007]. We also give an efficient algorithm to compute private coresets for k-median and k-mean queries in Red, immediately implying efficient differentially private sanitizations for such queries. Following McSherry and Talwar, this construction also gives efficient coalition proof (approximately dominant strategy) mechanisms for location problems. Unlike coresets which only have a multiplicative approximation factor, we prove that private coresets must have an additive error. We present a new technique for showing lower bounds on this error.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Tight Lower Bounds for Differentially Private Selection (2017, methodology): “(ε, δ)differential privacy with δ = 0) lower bounds can be proved using the “packing” technique [38], [39], [40].”
Functional Mechanism: Regression Analysis under Differential Privacy (2012, methodology): “For instance, the exponential mechanism has been applied for the publication of audition results [21], coresets [10], frequent patterns [3], decision trees [11], support vector machines [25], and synthetic datasets [7,16].”
Distributed Private Data Analysis: On Simultaneously Solving How and What (2008, background): “It has been demonstrated that differentially private analyses exist for a variety of tasks including the approximation of numerical functions (by adding carefully chosen random noise that conceals any single individual’s contribution) [11, 2, 22, 17], non-numerical analyses [20], datamining [2, 22],”
On the geometry of differential privacy (2009, background): “[13] construct private core sets for the k-median problem, enabling approximate computation of the k-median cost of any set of k facilities in R.”
Differentially private combinatorial optimization (2009, background): “[15] also consider the problem of privately approximating k-medians for points in <.”
Simultaneous Private Learning of Multiple Concepts (2015, background): “In the case of pure differential privacy, a packing argument [17, 21, 3] shows that any non-trivial concept class requires sample complexity Ω(k) to privately k-learn (Theorem 5.”
Pan-Private Streaming Algorithms (2010, background): “As noted in [10], coreset constructions frequently imply streaming algorithms, and indeed this fact, combined with results of Feldman et al.”
Data mining with differential privacy (2010, result): “This approach was studied in several works [2, 11, 10].”
Differentially Private Clustering in High-Dimensional Euclidean Spaces (2017, methodology): “, 2016), or √ d × OPT + poly(d, k, log n) when d is a small constant (Feldman et al., 2009) (See Table 1), the problem is left unresolved in the big-data (large n), high-dimensional (d = Ω(polylogn)) scenarios if we require both α and β to be as small as polylog(n).”
Computational Differential Privacy (2009, background): “, [5,6,7,8]), in this paper we suggest that such information-theoretic privacy may sometimes have a significant price (in utility or complexity).”
Core‐sets: An updated survey (2019, background): “A more humble but important result is to suggest private coresets for specific problems, based on their corresponding nonprivate versions as in Feldman et al. (2009) and Feldman, Xiang, et al. (2017).”
Impossibility of Differentially Private Universally Optimal Mechanisms (2010, unknown): “Contents”
A unified framework for approximating and clustering data (2011, unknown): “For example, in [28, 10, 21, 23, 19, 24, 31] the starting point for the efﬁcient construction of small ε -coresets for k -median is an efﬁcient bicriteria algorithm for k - median.”
Locally Private k-Means in One Round (2021, background): “There is a growing literature on this topic (Blum et al., 2005; Nissim et al., 2007; Feldman et al., 2009; Gupta et al., 2010; Mohan et al., 2012; Wang et al., 2015; Nissim et al., 2016; Nock et al., 2016; Su et al., 2016; Feldman et al., 2017; Balcan et al., 2017; Nissim and Stemmer, 2018; Huang…”
PrivBayes: private data release via bayesian networks (2014, background): “Even if the data is skewed in the domain space, i.e., there are some entries x[i] with high counts, such peaks are infrequent and so the vast majority of published values x∗[i] are useless.”
Differentially private data cubes: optimizing noise sources and consistency (2011, methodology): “For example, the notion of DP has been applied to releasing query and click histograms from search logs [18, 22], recommender systems [29], publishing commuting patterns [27], publishing results of machine learning [6, 8, 20], clustering [13, 30], decision tree [14], mining frequent patterns [5], an”
Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, background): “For non-convex problem under differential privacy, [15][10][13] studied private SVD. [14] investigated k-median clustering.”