Differentially Private Release and Learning of Threshold Functions

By Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan. 2015

221 citations recorded by the source corpus.

We prove new upper and lower bounds on the sample complexity of (ε, δ) differentially private algorithms for releasing approximate answers to threshold functions. A threshold function c over a totally ordered domain X evaluates to cz(y) = 1 if y ≤ x, and evaluates to 0 otherwise. We give the first nontrivial lower bound for releasing thresholds with (ε, δ) differential privacy, showing that the task is impossible over an infinite domain X, and moreover requires sample complexity n ≥ Ω(log* |X|), which grows with the size of the domain. Inspired by the techniques used to prove this lower bound, we give an algorithm for releasing thresholds with n ≤ 2(1+ο(1)) log* |X| samples. This improves the previous best upper bound of 8(1+ο(1)) log* |X| (Beimel et al., RANDOM '13). Our sample complexity upper and lower bounds also apply to the tasks of learning distributions with respect to Kolmogorov distance and of properly PAC learning thresholds with differential privacy. The lower bound gives the first separation between the sample complexity of properly learning a concept class with (ε, δ) differential privacy and learning without privacy. For properly learning thresholds in ℓ dimensions, this lower bound extends to n ≥ Ω(ℓ · log* |X|). To obtain our results, we give reductions in both directions from releasing and properly learning thresholds and the simpler interior point problem. Given a database D of elements from X, the interior point problem asks for an element between the smallest and largest elements in D. We introduce new recursive constructions for bounding the sample complexity of the interior point problem, as well as further reductions and techniques for proving impossibility results for other basic problems in differential privacy.

Subfields: Artificial Intelligence

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

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “Speciﬁcally, we use lower bounds for ε -di ﬀ erential private learning of the threshold functions in the cura-tor model [11, 30]; these lower bounds do not hold for ( ε,δ )-di ﬀ erential private learning of the threshold functions [12, 17].”
Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, background): “A side note is that privacy ampliﬁcation is also the key underlying technical tool for characterizing the learnability in statistical learning (Wang et al., 2016) and achieving tight sample complexity bounds for simple function classes (Beimel et al., 2013; Bun et al., 2015).”
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences (2018, background): “Our bound matches the asymptotics of [Bun et al., 2015] while providing optimal constants and allowing for white-box group privacy bounds.”
Make Up Your Mind: The Price of Online Queries in Differential Privacy (2016, methodology): “Our algorithm makes crucial use of a stability argument similar to the propose-test-release techniques of Dwork and Lei [2009]. To our knowledge, this is the first use of a stabiltiy argument for any online or adaptive problem in differential privacy and may be of independent interest.”
Simultaneous Private Learning of Multiple Concepts (2015, background): “Generalizing a result of [10], the next theorem shows that the converse is true as well: a differentially private (agnostic) PAC k-learner yields a private empirical k-learner with only a constant factor increase in the sample complexity.”
Private selection from private candidates (2018, background): “The problem of private median finding, and more generally private percentile estimation has been studied in several works [5, 10, 30, 33].”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, background): “2), which improves over a previously published result that requires O(n−1−α) for any α > 0 in Bun et al. (2015). The consequence is that the general learning setting is hard for ( , δ)-DP too unless δ becomes meaninglessly large for privacy purposes.”
Private Query Release Assisted by Public Data (2020, background): “Moreover, subsequent results by (Bun et al., 2015; Alon et al., 2019b) implied that this impossibility is true even for a simple class such as onedimensional thresholds over R.”
Adaptive Learning with Robust Generalization Guarantees (2016, background): “In particular, based on the result of Bun et al. (2015), we can show that there is no proper threshold learner that satisfies perfect generalization when the domain size is infinite.”
Clustering Algorithms for the Centralized and Local Models (2017, unknown): “An example is the Interior Point problem [6] where the task is, given n points in the unit interval x1, x2, .”
The Complexity of Differential Privacy (2017, background): “In the case of proper learning, there are concept classes known where the sample complexity is at least Ω(log∗ d ·VC(C) · log(1/δ)), such as threshold functions [22], but this does not rule out an upper bound of n = O(VC(C) · polylog(1/δ)) when δ is negligible in n and d.”
Renyi Differential Privacy Mechanisms for Posterior Sampling (2017, background): “The most popular relaxation is approximate DP [6], and a number of uniquely approximate DP mechanisms have been designed by [7, 16, 3, 1] among others.”
Generalization for Adaptively-chosen Estimators via Stable Median (2017, methodology): “The algorithm in (Bun et al., 2015) is relatively complex and, therefore, here we will use a simple and efficient algorithm that is based on the exponential mechanism (McSherry and Talwar, 2007), and is similar to an algorithm by Smith (2011) to estimate quantiles of a distribution.”
Differentially private model selection with penalized and constrained likelihood (2016, background): “, 2013); there is also a large literature on private probably approximately correct learning, which echoes the concerns of statistical estimation in the context of classification (Kasiviswanathan et al., 2011; Beimel et al., 2010, 2014, 2015; Bun et al., 2015; Karwa et al., 2015).”
Composable and versatile privacy via truncated CDP (2018, background): “( ε , δ ) -DP, the sample complexity’s dependence on the number of thresholds k is much more intriguing. log ∗ k and 2 log ∗ k [3, 5], the true dependence on k remains an open problem x ∈ [ k ] n , a solution to the interior point problem is a number j”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, methodology): “There are also algorithms for learning structured univariate distributions in TV-distance [25], and learning arbitrary univariate distributions in Kolomogorov distance [13].”
Differentially Private Assouad, Fano, and Le Cam (2020, methodology): “Bun et al. (2019) proves an upper bound of O ( kd log ( kd α )( 1 α2 + 1 αε )) .”