Differentially private combinatorial optimization

By Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar. 2009

253 citations recorded by the source corpus.

Consider the following problem: given a metric space, some of whose points are "clients," select a set of at most k facility locations to minimize the average distance from the clients to their nearest facility. This is just the well-studied k-median problem, for which many approximation algorithms and hardness results are known. Note that the objective function encourages opening facilities in areas where there are many clients, and given a solution, it is often possible to get a good idea of where the clients are located. This raises the following quandary: what if the locations of the clients are sensitive information that we would like to keep private? Is it even possible to design good algorithms for this problem that preserve the privacy of the clients? In this paper, we initiate a systematic study of algorithms for discrete optimization problems in the framework of differential privacy (which formalizes the idea of protecting the privacy of individual input elements). We show that many such problems indeed have good approximation algorithms that preserve differential privacy; this is even in cases where it is impossible to preserve cryptographic definitions of privacy while computing any non-trivial approximation to even the value of an optimal solution, let alone the entire solution. Apart from the k-median problem, we consider the problems of vertex and set cover, min-cut, k-median, facility location, and Steiner tree, and give approximation algorithms and lower bounds for these problems. We also consider the recently introduced sub-modular maximization problem, "Combinatorial Public Projects" (CPP), shown by Papadimitriou et al. [28] to be inapproximable to subpolynomial multiplicative factors by any efficient and truthful algorithm. We give a differentially private (and hence approximately truthful) algorithm that achieves a logarithmic additive approximation.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Privacy & Security

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

In Privacy & Security

Citations in the corpus

Differentially Private Learning with Adaptive Clipping (2019, neutral): “An approach based on target accuracy was provided in (Gupta et al., 2010), which was further improved in terms of privacy cost and computational efﬁciency in (Liu and Talwar, 2018).”
Tight Lower Bounds for Differentially Private Selection (2017, background): “Selection problems appear in many natural statistical problems, including private multiple hypothesis testing [1], sparse linear regression [2], [3], finding frequent itemsets [4], and as subroutines in algorithms for answering exponentially many statistical queries [5], [6], [7], [8], [9], approxim”
Proving Differential Privacy via Probabilistic Couplings (2016, neutral): “(2013) prove differential privacy of the vertex cover algorithm (Gupta et al. 2010).”
Differentially Private Empirical Risk Minimization (2009, neutral): “Some follow-up work on differential privacy includes work on differentially-private combinatorial optimization, due to Gupta et al. (2010), and differentially-private contingency tables, due to Barak et al. (2007) and Kasivishwanathan et al. (2010).”
Private selection from private candidates (2018, background): “[17] studied a closely related question that implies a quadratic-time algorithm for the known threshold version of the private candidate selection problem.”
Beating randomized response on incoherent matrices (2011, background): “[20, 11, 12]), and that it corresponds to “full user level privacy” in any setting in which an individual’s private data naturally corresponds to a pair of vertices in a graph (e.”
Differentially Private Clustering in High-Dimensional Euclidean Spaces (2017, methodology): “The analysis of clustering loss of Algorithm 3 is based on a lower bound on the total gains of k swap pairs (Gupta et al., 2010).”
Deep Learning with Gaussian Differential Privacy (2019, unknown): “Therefore, from a practical standpoint, it would be of great importance to incorporate hyperparameter tuning into the f -DP framework [26].”
Large-Scale Differentially Private BERT (2021, methodology): “Theorem 1 (Theorem 10.2 of Gupta et al. (2010)) .”
Characterizing Private Clipped Gradient Descent on Convex Generalized Linear Problems (2020, unknown): “There has been both theoretical [18, 7, 26, 41, 4] and empirical research [40, 33] providing algorithms which can be used for choosing a “near-optimal” value of the clipping norm.”
Differentially Private Learning with Adaptive Clipping (2019, methodology): “An approach based on target accuracy was provided in [11], which was further improved in terms of privacy cost and computational efficiency in [16].”
Deep Learning with Differential Privacy (2016, background): “[29] (see the full version of the paper for”