Prateeti Mukherjee \Email[email protected]
\addrMicrosoft Research
and \NameSatya Lokam \Email[email protected]
\addrMicrosoft Research
On the Query Complexity of Training Data Reconstruction in Private Learning
Abstract
We analyze the number of queries that a whitebox adversary needs to make to a private learner in order to reconstruct its training data. For DP learners with training data drawn from any arbitrary compact metric space, we provide the first known lower bounds on the adversary’s query complexity as a function of the learner’s privacy parameters. Our results are minimax optimal for every , covering both -DP and DP as corollaries. Beyond this, we obtain query complexity lower bounds for Rényi DP learners that are valid for any . Finally, we analyze data reconstruction attacks on locally compact metric spaces via the framework of Metric DP, a generalization of DP that accounts for the underlying metric structure of the data. In this setting, we provide the first known analysis of data reconstruction in unbounded, high dimensional spaces and obtain query complexity lower bounds that are nearly tight modulo logarithmic factors.
1 Introduction
Machine Learning has become increasingly pervasive, finding applications in multiple real world, risk-sensitive workflows. The fascinating potential of machine learning is perhaps most apparent in recent times, with the development of large-scale deep learning algorithms such as Large Language Models ([Brown et al. (2020)]) and Diffusion Models ([Ramesh et al. (2021)]). These powerful algorithms consume enormous amounts of data to derive meaningful patterns for improved empirical performance. Theoretical analyses (Bresler and Nagaraj, 2020; Bubeck et al., 2020; Vardi et al., 2021), however, reveal that Neural Networks are capable of memorizing the underlying training data, rendering them vulnerable to information leakage and adversarial attacks that can infer sensitive attributes of the training set, or worse, reconstruct one or more training samples entirely. Differential privacy was introduced in an attempt to formalize the notion of privacy protection while deriving meaningful conclusions from statistical information, and has since evolved into the de-facto notion of privacy in machine learning. This has inspired a plethora of research in the development of private counterparts to popular machine learning (Chaudhuri and Monteleoni, 2008; Jain et al., 2011; Chaudhuri et al., 2009; Alabi et al., 2020) and deep learning (Abadi et al., 2016; Fu et al., 2022; Song et al., 2013) algorithms. However, the promise of differential privacy is often difficult to interpret, and a rigorous quantification of “how much data privacy does an -DP guarantee actually confer?” is important to develop sufficiently private algorithms.
Analysis in this setting involves measuring the level of protection conferred by private learners against information leakage, a quantity that is largely specified by an adversary’s success rate in performing a particular class of attacks. For instance, Yeom et al. (2018) demonstrate that, for the class of Membership Inference Adversaries (MIAs), where the objective is to infer the membership status of a target individual in the training set of a private learner, an adversary cannot perform much better than random guessing if the learner is -DP with . On the flip side, a more recent work of Humphries et al. (2020) suggests that, under minimal modeling assumptions, if , one can design adversaries that can correctly predict the membership status of a target individual through the output of the -DP learner with probability . This is concerning, since, most practical deployments of -DP algorithms consider to be sufficiently private (Allen et al. ; Apple ). From the perspective of an individual supplying their sensitive information to a learning algorithm, under the impression that their participation is kept secret, such large lower bounds on the success probability of an attack implies little privacy protection. Therefore, for effective mitigation of privacy risks in this context, must be sufficiently small. However, prior work of Tramèr and Boneh (2021) has already established that private learning in the small regime yields models that perform significantly worse than their non-private counterparts, and find limited applicability in real-world deployments.
Membership status, however, may not be the security concern of interest in every scenario. For instance, an individual’s online presence in a social network platform is generally public, and therefore may not qualify as sensitive information. However, if an adversary is able to reconstruct private message transcripts or the individual’s personal details, their privacy is at risk. In machine learning tasks, this would be an instance of a Training Data Reconstruction Attack (DRA), wherein, the adversary attempts to reconstruct a target sample of the training dataset through the output of a learner. Carlini et al. (2021) have demonstrated that state of the art language models are susceptible to simple reconstruction adversaries that can perfectly reconstruct personally identifiable information and 128-bit UUIDs through repeated queries to the model, even when the sequences appear just once in the training set. This is particularly concerning in recent times, as we witness widespread adoption of powerful algorithms that necessitate the use of large scale, diverse training sets, procured from various sources. The results of Balle et al. (2022); Carlini et al. (2021); Zhu et al. (2019) indicate that unauthorized recovery, and subsequent misuse, of an individual’s sensitive information is a very tangible threat. Therefore, it is imperative that learning algorithms be scrutinized for their resilience to training data reconstruction attacks.
Privacy analysis in this setting has some nice properties. Intuitively, reconstruction must be harder than membership inference, since the latter involves recovering a single binary random variable, while the former may require reconstructing samples that are supported on some arbitrary domain beyond . This leads us to the question ‘can DP imply meaningful protection against DRAs for a larger range of , even when membership is compromised?’. Empirically, prior work of Balle et al. (2022) has established that this hypothesis is indeed true. In this work, we answer this question by studying the theoretical underpinnings of a private algorithm’s resilience to such reconstruction adversaries.
To facilitate a formal analysis, we must first identify the parameters that characterize protection offered by a private learner. For -DP learners, that there must be a dependence on the privacy parameters () is obvious. Furthermore, the empirical success of the reconstruction adversaries in Carlini et al. (2021) indicate that the number of interactions between the adversary and the learner, which we call the adversary’s query complexity , is crucial to the success of the attack. Finally, we note that privacy violations are largely context-dependent. For instance, it is public information that Bill Gates is a billionaire; if an adversary is able to recover a rough approximation of his net worth with error of the order of , it is very unlikely to be a violation of his privacy. However, if the adversary’s reconstruction has an error of the order , this level of precision suggests a very detailed and potentially invasive investigation into his financial affairs, thereby raising privacy concerns. Therefore, the level of protection offered by a private learner against reconstruction adversaries is also parameterized by the reconstruction error tolerance , i.e., the precision to which a worst-case adversary is able to reconstruct a training sample, through the output of the private learner. From the learner’s point of view, is the threshold of non-privacy – if an adversary is able to reconstruct any training sample with error , it counts as a privacy violation with respect to DRAs. Intuitively, this can be thought of as a smoothed version of the notion of blatant non-privacy proposed in the seminal work of Dinur and Nissim (2003). To this end, we seek answers to the following question: “What is the maximum number of queries that a private learner can safely answer, while avoiding highly accurate reconstruction of training samples by any adversary?”
1.1 Contributions
Our work aims to present a comprehensive analysis of the effectiveness of training data reconstruction attacks against private learners. To this end, we establish tight non-asymptotic bounds on the query complexity of any informed reconstruction adversary, as a function of the privacy parameters of the learner and the system’s purported tolerance to reconstruction attacks. Our contributions are summarized as follows:
Reconstruction Attacks on Differentially Private Learners
Our first result analyzes data reconstruction attacks on -DP learners whose training dataset is supported on some arbitrary compact metric space. In particular, we operate under a similar threat model to that of Balle et al. (2022); Guo et al. (2022) (see Section 3 for a detailed overview) and tightly characterize the query complexity, i.e. the number of queries that the attacker needs to make, as a function of and the non-privacy threshold . The result is informally stated below:
Theorem 1.1 (DRAs on DP Learners (Informal)).
Let be an -DP learning algorithm whose training data is supported on a compact metric space . Then, any data reconstruction adversary needs to make at least queries to in order to ensure a squared reconstruction error of at most . Furthermore, the obtained query complexity is minimax optimal upto constant factors.
To the best of our knowledge, Theorem 1.1 is the first known analysis of DRAs that holds for arbitrary compact metric spaces, and is minimax optimal for all regimes. In particular, it gives minimax optimal query complexities of for -DP and for -DP learners.
Reconstruction Attacks on -Rényi DP Learners
Within the framework of Theorem 1.1, we analyze DRAs on -Rényi DP learners and obtain a query complexity lower bound of where . To the best of our knowledge, this is the first non-asymptotic analysis of data reconstruction on Rényi DP learners which holds for any and . This result also recovers the minimax optimal -DP bound of Theorem 1.1 as . A key component of our proof is a novel total variation bound on the output distributions of Rényi DP learners, which could be of independent interest.
Metric Differential Privacy and Reconstruction Attacks on Locally Compact Spaces
We now extend our analysis beyond standard differential privacy by considering the notion of Metric Differential Privacy or Lipschitz Privacy (Chatzikokolakis et al., 2013; Fernandes et al., 2021; Koufogiannis et al., 2017; Imola et al., 2022; Boedihardjo et al., 2022), a privacy formalism that generalizes differential privacy by accounting for the underlying metric structure of the data (beyond the Hamming metric). Operating under this broader notion of privacy, we analyze DRAs on -metric DP learners, whose training data is supported on arbitrary locally compact metric spaces (which may be unbounded) and obtain tight query complexity bounds. Our result is informally stated as follows:
Theorem 1.2 (DRAs on Metric DP Learners (Informal)).
Let be an -metric DP learning algorithm whose training data is sampled from a locally compact metric space . Let be the metric entropy of the unit ball in . Then, any data reconstruction adversary needs to make at least queries to in order to ensure a squared reconstruction error of at most . The obtained query complexity is minimax optimal upto logarithmic factors.
To the best of our knowledge, Theorem 1.2 is the first known analysis of data reconstruction attacks that directly applies to unbounded metric spaces (such as all of ), as well as the first result that aims to quantify the semantics of Metric Differential Privacy. To complement these results, we also demonstrate in Appendix D that commonly used privacy-inducing mechanisms and learning algorithms such as the Gaussian Mechanism, Stochastic Gradient Descent, and Projected Noisy Stochastic Gradient Descent, naturally satisfy metric differential privacy with little to no algorithmic modifications.
Our work analyzes data reconstruction attacks almost entirely from first principles, relying only on the basic definitions of differential privacy (and its variants), classical privacy-inducing mechanisms (Warner, 1965; McSherry and Talwar, 2007) and well-established connections between information divergences and hypothesis testing (Tsybakov, 2004).
2 Notation and Preliminaries
Let be an arbitrary collection of secrets, with samples drawn from the metric space . We assume is locally compact unless stated otherwise. Note that this property is satisfied by almost every possible data domain, including finite dimensional normed spaces, such as . We denote the Hamming metric as . In practical applications, is modelled as an aggregation of samples and the measure of dissimilarity for any two such collections is given by , where is the set of all permutations of . Two datasets are neighboring if they differ in a single element, i.e., . We use the and notation to characterize the dependence of our rates on the privacy parameters of the algorithms and the system’s threshold of non-privacy, suppressing numerical constants. We use and to denote and respectively, modulo numerical constants. Beyond this, we also make use of the packing number of compact spaces (or compact subsets)
Definition 2.1 (Packing Number (Wainwright (2019))).
An -packing of the set with respect to the metric is a set such that for all distinct , we have . The -packing number
2.1 Differential Privacy
Definition 2.2 (Pure Differential Privacy (Dwork and Roth (2014))).
For any , a randomized learner is -differentially private(DP) if, for every pair of neighboring datasets , the output probability distributions satisfy:
| (1) |
Or, equivalently, the max divergence of the output distributions satisfies:
| (2) |
where denote the output distributions , respectively.
Informally, DP bounds the change in the output distribution induced by a randomized algorithm when one of the input samples is replaced or removed. The constraint ensures that the output distributions are sufficiently statistically indistinguishable, often characterized by a constant contraction in the output space in terms of some statistical divergence. When defined in terms of the Rényi Divergence, we obtain the following popular relaxation of differential privacy:
Definition 2.3 (Rényi Differential Privacy (Mironov (2017))).
For any , a randomized learner is -Rényi differentially private(RDP) if, for every pair of neighboring datasets , the Rényi Divergence is bounded as follows:
| (3) |
where and denote the output distributions and , respectively.
For , Rényi DP recovers the definition of -DP (Mironov (2017)). Another popular relaxation of differential privacy, termed approximate differential privacy, measures this change in terms of -indistinguishability.
Definition 2.4 (Approximate Differential Privacy(Dwork et al. (2006))).
For any , a randomized learner is differentially private if for every pair of neighboring datasets , the output probability distributions and are indistinguishable, i.e.,
| (4) |
2.2 Metric Differential Privacy
While there exist several variants and relaxations of DP, the traditional notion is fundamentally restricted to the discrete setting. Specifically, the definition requires that the private inputs to the randomized mechanism must belong to a product space, where collections can break down into natural single elements to allow for neighboring datasets to exist. We argue that this requirement is too stringent, particularly in situations where the sensitive information does not belong to a database at all, but is some arbitrary collection of secrets. In unstructured data domains, such as text, it is challenging to establish a natural definition of neighbors, but there does exist a notion of distinguishability of representations. For instance, consider a topic classification problem where the author’s identity is to be protected. In this case, two representations that are ”similar in topic” must remain so in the output of a private mechanism, irrespective of the author. This notion of distance is not natural to the Hamming metric, and requires more sophisticated metric (e.g. Earth Mover’s distance (Fernandes et al. (2019))). In fact, general measures also do not break down into natural single elements, as is required by DP (Boedihardjo et al. (2022)). To facilitate privacy protection in such settings, we would need to incorporate the underlying metric structure of the input space of the private algorithm in the parameter that bounds the shift in the output probability distributions, when altering a single input. The following notion incorporates this desiderata, and extends the classical concept of DP to general metric spaces.
Definition 2.5 (Metric Differential Privacy (Chatzikokolakis et al. (2013))).
Let be a locally compact metric space and be measurable. For any , a randomized learner is -metric differentially private (mDP) if for every pair of inputs and any measurable subset ,
| (5) |
We observe that metric differential privacy (often appearing under the pseudonym of Metric Privacy (Boedihardjo et al., 2022) and Lipschitz Privacy (Koufogiannis et al., 2017)) is a strict generalization of differential privacy. In fact, as we shall show in Appendix D, the two definitions are equivalent when the inputs belong to a product space equipped with the Hamming metric. Beyond this, we also discuss in Appendix D how popular privacy preserving mechanisms in the DP literature, such as the Gaussian mechanism, and learning algorithms, such as Projected Noisy SGD (Feldman et al. (2018)) satisfy metric DP with little to no modifications.
3 Formalizing Data Reconstruction Attacks as a Privacy Game
Our analysis begins by formalizing data reconstruction attacks as a privacy game between the learner and the reconstruction adversary , which proceeds as follows:
Let be a fixed dataset, comprising of training samples, that is known to both the learner and the adversary.
Learner chooses an arbitrary target sample , appends it to the training dataset , and outputs a sample drawn from its output distribution 111By definition of differential privacy, must be a randomized algorithm, see Vadhan (2017) .
Adversary makes queries to the model, i.e., she draws samples from the learner’s output distribution, and generates a reconstruction of the target sample . Since adversaries are generally resource bounded in almost all practical settings, we assume that the query complexity of , i.e., the number of times that can query is finite.
A prototypical example of would be a logistic regression classifier trained with DP-SGD (with representing the regressor/model weights). Examples of include the GLM attack of Balle et al. (2022).
We note that such a privacy game formulation of reconstruction attacks is also the cornerstone of prior works such as Balle et al. (2022) and Guo et al. (2022) (when restricted to the case of ). In fact, analogous privacy game formulations for MIAs are highly predominant in a wide range of applications including (but not limited to):interpretations of the semantics of DP guarantees (Mahloujifar et al., 2022; Humphries et al., 2020; Yeom et al., 2018) and devising auditing strategies for practical deployments of private learning algorithms (Salem et al., 2023; Shokri, 2022)
Equipped with the above formulation, it is natural to quantitatively analyze data reconstruction attacks via the machinery of two-player zero-sum games (Von Neumann and Morgenstern, 1947). To this end, an intuitive choice of the utility/payoff function of the learner is given by 222More generally, one can set for some non-negative increasing differentiable function . We choose for clarity but our proof techniques extend to arbitrary and the corresponding value function of the game is given by
| (6) |
where the infimum is taken over all reconstruction adversaries. Note that, given any error tolerance parameter , ensures that no data reconstruction adversary that is allowed to make at most queries to can uniformly obtain an expected squared reconstruction error less than on every target point . To this end, we say that an adversary has attained the threshold of non-privacy , if for any possible choice of the target point , they are able to reconstruct upto an expected squared error of at most . The remainder of our work aims to derive tight lower bounds for as a function of and the privacy parameters of the learner . This in turn can be used to derive tight query-complexity lower bounds for informed adversaries, i.e., quantify the number of times an adversary needs to query the model in order to reach a given threshold of non-privacy.
Remark 3.1.
This instantiation of a powerful white-box reconstruction adversary is borrowed from prior work of Balle et al. (2022). Although the modeling may seem very stylized, investigating provable mitigations conferred by -DP learners against such worst-case adversaries is a useful exercise – theoretical lower bounds on the adversary’s error suggest that such algorithms implicitly protect against reconstruction of training samples by less powerful, more realistic adversaries.
4 Data Reconstruction Attacks against Differentially Private Learners
Our first result is a query complexity lower bound for data reconstruction attacks on DP learners whose training dataset is supported on a compact metric space . The proof of this result is presented in Appendix B.2.
Theorem 4.1 (Query Complexity Lower Bounds for -DP Learners).
Let be any compact metric space. Consider any arbitrary and . Then, for any target sample in the training dataset of an differentially private learner , and any data reconstruction adversary that queries the learner times, the following holds:
where .
Consequently, for any fixed non-privacy threshold , the number of times that needs to query in order to always ensure an expected squared reconstruction error of at most , is lower bounded as
We now demonstrate the minimax optimality of the above lower bound by deriving a matching upper bound for the two point metric space . The proof of this result is presented in Appendix B.5.
Theorem 4.2 (Upper Bound for -DP Learners).
Let be a two-point metric space, i.e., . Furthermore, let and be arbitrary. Then, there exists an differentially private learner whose training dataset contains , and a reconstruction adversary which makes queries to and achieves an expected squared error of .
Our upper bound construction is an DP variant of the seminal randomized response algorithm (Warner, 1965). This choice is motivated by the fact that the randomized mechanism used in our proof is known to be complete among the class of DP algorithms, i.e., any DP algorithm can be represented as a composition of with some (possibly) randomized algorithm (see Kairouz et al. (2015), Murtagh and Vadhan (2015) Lemma 3.2 and Bun and Steinke (2016) ) We also highlight that our upper bound construction is general enough to be directly extendable to -point metric spaces and can potentially be extended to arbitrary compact metric spaces via covering arguments.
Applicability and Minimax Optimality
We note that the lower bound of Theorem 4.1 holds for any compact metric space . Furthermore, Theorem 4.1 and Theorem 4.2 are applicable for every . Thus, our obtained query complexity guarantee is minimax optimal in all regimes, which, to the best of our knowledge, is the first such result of its kind. To this end, our results cover both pure DP (or -DP) and DP. In particular, Theorem 4.1 implies a query complexity lower bound of for -DP and for DP. Both these guarantees are minimax optimal as per Theorem 4.2.
Bounded Domain Assumption
Although the bound in Theorem 4.1 is minimax optimal, and to the best of our knowledge, the most general such result of its kind, we note that it requires . We emphasize that this assumption is not specific to our analysis, and is in agreement with several prior works that investigate the protection offered by traditional DP (including variants and relaxations) algorithms (Yeom et al., 2018; Tramèr and Boneh, 2020; Guo et al., 2022; Balle et al., 2022). We conjecture that this assumption cannot be avoided in the analysis of traditional DP algorithms without making stringent modelling assumptions on the either the private learner, the data distribution, or the adversary’s reconstruction algorithm. This is due to the fact that the standard notion of differential privacy (as defined in Definitions 2.2 and 2.4) is oblivious to the underlying metric structure of the input space, thereby yielding worst-case behavior. In Section 5, we remove this boundedness assumption and extend the analysis to arbitrary metric spaces, presenting the first query complexity bounds for data reconstruction attacks against metric DP learners.
4.1 Comparison to Prior Work
To the best of our knowledge, the result closest to Theorem 4.1 in prior works is Theorem 1 of Guo et al. (2022), which considers data reconstruction attacks under the same threat model as ours (see Section 3), but is restricted to -Rényi DP and . Furthermore, it requires the data domain to be a compact subset of . For the sake of completeness, we restate their result as follows:
Theorem 4.3 (Theorem 1 Guo et al. (2022)).
For a target sample in the training set of a -Rényi DP learner, the MSE of a reconstruction attack that outputs an unbiased estimate of upon observing follows . The i-th coordinate-wise diameter is given by .
Invalid Lower Bound
As we shall prove in Appendix B.6, the lower bound implied by Theorem 1 of Guo et al. (2022) is invalid for any , i.e., it violates trivial upper bounds implicit in the notion of the squared distance in bounded domains (this can also be intuitively seen by observing that the RHS diverges to infinity exponentially fast as ). To this end, the above lower bound result is vacuous for a surprisingly large range of , particularly in high dimensional settings. Even for elementary use-cases like the MNIST dataset (Lecun et al., 1998), where , the lower bound of Guo et al. (2022) is vacuous for any . We recall that practical deployments of DP algorithms typically use (Apple, ). On the contrary, our results in Theorem 4.1 and 4.2 are minimax optimal in all regimes . Beyond this, we also establish a query complexity lower bound for Rényi DP in Corollary 4.4, which holds for any (as opposed to the specific case of , as in Theorem 1 of Guo et al. (2022))
Restriction to compact subsets of
We highlight that Theorem 1 of Guo et al. (2022) is restricted only to compact subsets of whereas our lower bound applies to any compact metric space. In fact, the validity of Guo et al. (2022) Theorem 1 is dependent on the coordinate wise diameter being well defined. We note that there exist several applications where this condition may not be satisfied. For instance, let be a collection of strings of varying lengths (where the maximum length is finite), equipped with the edit distance metric. The coordinate-wise edit distance is the maximum difference between corresponding characters of any two strings of the same length, which is not well-defined when is composed of variable-length strings. Thus, their lower bound does not apply to this setting. On the contrary, our result in Theorem 4.1 is still valid, since is well-defined and represents the maximum dissimilarity between any two strings in .
4.2 Data Reconstruction Attacks on Rényi DP Learners
We now consider reconstruction attacks on Rényi DP learners (for ). To this end, we derive the following query complexity lower bound by extending the proof technique of Theorem 4.2 to the notion of Rényi DP. A key step in the proof involves deriving a novel Total Variation bound between the output distributions of Rényi DP Learners (Lemma 6.2 in Section 6), which could be of independent interest.
Corollary 4.4 (Query Complexity Lower Bounds for -Rényi DP).
Let be any compact metric space. Consider any arbitrary and . Then, for any target sample in the training dataset of an -Rényi DP learner , and any data reconstruction adversary that queries the learner times, the following holds:
where and .
Consequently, for any fixed non-privacy threshold , the number of times that needs to query in order to always ensure an expected squared reconstruction error of at most , is lower bounded as follows:
5 Data Reconstruction Attacks on Metric DP Learners
We now present our results for data reconstruction attacks on locally compact linear spaces by considering metric DP learners. In this setting, we obtain the following lower bound, which we prove in Appendix C.1
Theorem 5.1 (Lower Bounds for Metric DP Learners).
Let be any locally compact metric space and let , where is the unit ball in . For any target sample in the training dataset of an metric differentially private learner , and any data reconstruction adversary that queries the learner times, . Consequently, for any fixed non-privacy threshold , needs to query at least times in order to always ensure an expected squared reconstruction error of at most .
We note that for , (or more generally, any finite dimensional normed space), and thus, the query complexity lower bound becomes . We complement this with an upper bound that is tight modulo logarithmic factors. The proof is presented in Appendix C.2
Theorem 5.2 (Upper Bound for Metric DP Learners).
Let be an metric differentially private learner whose training datapoints are elements of the normed space . Let be any arbitrary sample in the training dataset of and let be arbitrary. Then, there exists a reconstruction adversary which makes queries to in order to achieve an expected squared error of at most .
Unlike prior works on data reconstruction that require some boundedness assumption on the data domain, (Yeom et al., 2018; Tramèr and Boneh, 2020; Guo et al., 2022; Stock et al., 2022), Theorem 5.1 and Theorem 5.2, are, to the best of our knowledge, the first near-optimal analysis of training data reconstruction for unbounded metric spaces
Dimension dependence
The nearly-matching upper and lower bounds of Theorem 5.1 and Theorem 5.2 captures the inherent hardness of the data reconstruction problem in high dimensions, and thus provides solid theoretical grounding to the observations of Balle et al. (2022) which shows that the performance of data reconstruction adversaries scales inversely with dimension. The intuition may be formalized as follows: let be a finite dimensional vector space. Any target sample has -degrees of freedom. From the lens of an adversary, the complexity of reconstructing the target sample must grow with . Therefore, the number of queries the adversary needs to make to the learner to achieve good quality reconstruction must scale proportional to , which is accurately captured in Theorem 5.1.
6 Proof Sketch
Our analysis hinges on the following insight: Suppose the target sample is chosen from some finite set which is apriori known to the adversary. The task of the adversary then reduces to inferring (or testing) which one of is actually the target sample , by using samples from . Intuitively, this task of testing from samples cannot be harder than the original data reconstruction problem (wherein can be arbitrary). Such testing reductions have a rich history in theoretical CS (Goldreich et al., 1998), learning theory (Kearns and Vazirani, 1994) and statistics (Tsybakov, 2004). We complement this insight with the statistical indistinguishability interpretation of differential privacy and its relaxations, i.e., for any private learner , the output distributions and must be sufficiently close, which in turn imposes fundamental limits (quantified via information divergences) on the accuracy of the adversary’s testing problem described above.
6.1 Proof of the Reconstruction Lower Bounds
We sketch the proof of Theorem 4.1 and Corollary 4.4. For any , let denote the output distribution of and let to be the associated product distribution. Recall that . Moreover, let and let be the two farthest points in , i.e., . In accordance with the above discussion, we reduce the general reconstruction problem to the case when by replacing the supremum in the definition of with an average over and applying Markov’s inequality to obtain:
Since , an application of triangle inequality shows that holds whenever . Similarly, holds whenever . It follows that,
By the definition of , one can see that for any adversary , the sum of the two probabilities on the RHS can be uniformly lower bounded by . Subsequently, using the tensorization properties of and recalling the definition of , we obtain the following lower bound
| (7) |
The proof of both Theorem 4.1 and Corollary 4.4 are now concluded by bounding the Total Variation between the two output distributions of the private learner . To this end, we first consider Theorem 4.1 and derive the following upper bound for the output distributions of DP learners in Appendix B.1.
Lemma 6.1 (TV Bounds for DP Learners).
Let be any arbitrary DP learner and let be any two arbitrary neighbouring datasets (i.e. datasets that differ in only one record). Then, the following holds:
For Corollary 4.4, we derive the following novel bound between the output distributions of Renyi DP Learners, which may be of independent interest. We prove this in Appendix B.3
Lemma 6.2 (TV Bounds for Renyi DP Learners).
Let be any arbitrary Renyi DP learner and let be any two arbitrary neighbouring datasets (i.e. datasets that differ in only one record). Then, the following holds:
The proof of Theorem 4.1 and Corollary 4.4 are now completed by respectively applying Lemma 6.1 and Lemma 6.2 to equation (7). We also highlight that the proof of Theorem 5.1 proceeds along very similar lines, except that it involves a more delicate choice of the testing set using the fact that the definition of Metric DP is sensitive to the metric structure of the input.
6.2 Upper Bound for DP : Proof Sketch of Theorem 4.2
Since , . Without loss of generality, let , i.e., . As stated earlier, our construction of is a variant of the randomized response mechanism defined as follows:
-
1.
Flip a coin . If , then
-
2.
Otherwise, if , then is defined as follows:
As we shall show in Appendix B.5, is differentially private. We now consider a reconstruction adversary which draws as follows: If for some , . Else, define as follows:
where denotes bitwise OR. Conditioned on the event , where . Note that iff . Since this event occurs with probability , it follows that
To set the RHS to be equal to , it suffices to set
We note that this adversary uses a randomized decision rule, which is consistent with our modeling assumptions in Section 3 and of prior work (Guo et al. (2022); Balle et al. (2022)). In Appendix B, we construct a deterministic majority-based adversary and demonstrate that the lower bound is still tight .
6.3 Upper Bound for Metric DP: Proof Sketch of Theorem 5.2
Our upper bound construction for metric DP is based upon the exponential mechanism in . In particular, for , let be a probability measure on whose density with respect to the Lebesgue measure is given by,
For any , we set the output distribution of to be . We verify in Appendix C.2 that is metric DP w.r.t since for any , due to the triangle inequality. We consider a reconstruction adversary which draws and computes . It is easy to see that where . Thus, bounding the reconstruction error reduces to sharply bounding . To this end, we use classical results in probability theory on the isoperimetric properties of the exponential distribution (Bobkov and Ledoux, 1997; Bobkov, 2003) in as well the connections between moment control and isoperimetry (Aida and Stroock, 1994; Huang and Tropp, 2021; Garg et al., 2020) to sharply bound as . It follows that,
To make the RHS at most , it suffices to set
References
- Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, page 308–318, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341394. 10.1145/2976749.2978318. URL https://doi.org/10.1145/2976749.2978318.
- Aida and Stroock (1994) Shigeki Aida and Daniel Stroock. Moment estimates derived from poincaré and logarithmic sobolev inequalities. Mathematical Research Letters, 1(1):75–86, 1994.
- Alabi et al. (2020) Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan. Differentially private simple linear regression, 2020. URL https://arxiv.org/abs/2007.05157.
-
(4)
Joshua Allen, Janardhan Kulkarni, Abhradeep Thakurta, and Sergey Yekhanin.
Tracking dp budget while handling basic sql queries.
URL https://github.com/opendp/smartnoise-sdk/blob/main/
sql/docs/papers/DP_SQL_budget.pdf. - (5) Differential Privacy Team Apple. Learning with privacy at scale. URL https://machinelearning.apple.com/research/learning-with-privacy-at-scale.
- (6) Wiki Article. Binomial Distribution. URL https://en.wikipedia.org/wiki/Binomial_distribution#Tail_bounds.
- Balle et al. (2022) Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries, 2022. URL https://arxiv.org/abs/2201.04845.
- Bobkov and Ledoux (1997) Sergey Bobkov and Michel Ledoux. Poincaré’s inequalities and talagrand’s concentration phenomenon for the exponential distribution. Probability Theory and Related Fields, 107:383–400, 1997.
- Bobkov (2003) Sergey G Bobkov. Spectral gap and concentration for some spherically symmetric probability measures. In Geometric Aspects of Functional Analysis: Israel Seminar 2001-2002, pages 37–43. Springer, 2003.
- Boedihardjo et al. (2022) March Boedihardjo, Thomas Strohmer, and Roman Vershynin. Private measures, random walks, and synthetic data, 2022.
- Bresler and Nagaraj (2020) Guy Bresler and Dheeraj Nagaraj. A corrective view of neural networks: Representation, memorization and learning, 2020. URL https://arxiv.org/abs/2002.00274.
- Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020. URL https://arxiv.org/abs/2005.14165.
- Bubeck et al. (2020) Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and size of the weights in memorization with two-layers neural networks. Advances in Neural Information Processing Systems, 33:4977–4986, 2020.
- Bun and Steinke (2016) Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635–658. Springer, 2016.
- Cam (1986) Lucien Le Cam. Asymptotic methods in statistical decision theory. 1986. URL https://api.semanticscholar.org/CorpusID:118432452.
- Carlini et al. (2021) Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models, 2021.
- Chatzikokolakis et al. (2013) Kostas Chatzikokolakis, Miguel Andrés, Nicolás Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metrics. 07 2013. ISBN 978-3-642-39076-0. 10.1007/978-3-642-39077-7_5.
- Chaudhuri and Monteleoni (2008) Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008. URL https://proceedings.neurips.cc/paper/2008/file/8065d07da4a77621450aa84fee5656d9-Paper.pdf.
- Chaudhuri et al. (2009) Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization, 2009. URL https://arxiv.org/abs/0912.0071.
- Dinur and Nissim (2003) Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’03, page 202–210, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581136706. 10.1145/773153.773173. URL https://doi.org/10.1145/773153.773173.
- Dwork (2011) Cynthia Dwork. Differential Privacy, pages 338–340. Springer US, Boston, MA, 2011. ISBN 978-1-4419-5906-5. 10.1007/978-1-4419-5906-5_752. URL https://doi.org/10.1007/978-1-4419-5906-5_752.
- Dwork and Roth (2014) Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3–4):211–407, aug 2014. ISSN 1551-305X. 10.1561/0400000042. URL https://doi.org/10.1561/0400000042.
- Dwork and Rothblum (2016) Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy, 2016.
- Dwork et al. (2006) Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology (EUROCRYPT 2006), volume 4004 of Lecture Notes in Computer Science, pages 486–503. Springer Verlag, May 2006. URL https://www.microsoft.com/en-us/research/publication/our-data-ourselves-privacy-via-distributed-noise-generation/.
- Feldman et al. (2018) Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. pages 521–532, 10 2018. 10.1109/FOCS.2018.00056.
- Fernandes et al. (2019) Natasha Fernandes, Mark Dras, and Annabelle McIver. Generalised differential privacy for text document processing. In Flemming Nielson and David Sands, editors, Principles of Security and Trust, pages 123–148, Cham, 2019. Springer International Publishing. ISBN 978-3-030-17138-4.
- Fernandes et al. (2021) Natasha Fernandes, Annabelle McIver, and Carroll Morgan. The laplace mechanism has optimal utility for differential privacy over continuous queries, 2021. URL https://arxiv.org/abs/2105.07176.
- Fu et al. (2022) Jie Fu, Zhili Chen, and XinPeng Ling. Sa-dpsgd: Differentially private stochastic gradient descent based on simulated annealing, 2022. URL https://arxiv.org/abs/2211.07218.
- Garg et al. (2020) Ankit Garg, Tarun Kathuria, and Nikhil Srivastava. Scalar poincaré implies matrix poincaré, 2020.
- Goldreich et al. (1998) Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653–750, 1998.
- Guo et al. (2022) Chuan Guo, Brian Karrer, Kamalika Chaudhuri, and Laurens van der Maaten. Bounding training data reconstruction in private (deep) learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 8056–8071. PMLR, 17–23 Jul 2022. URL https://proceedings.mlr.press/v162/guo22c.html.
- Huang and Tropp (2021) De Huang and Joel A Tropp. From poincaré inequalities to nonlinear matrix concentration. 2021.
- Humphries et al. (2020) Thomas Humphries, Matthew Rafuse, Lindsey Tulloch, Simon Oya, Ian Goldberg, and Florian Kerschbaum. Differentially private learning does not bound membership inference. ArXiv, abs/2010.12112, 2020.
-
Imola et al. (2022)
Jacob Imola, Shiva Kasiviswanathan, Stephen White, Abhinav Aggarwal, and Nathanael Teissier.
Balancing utility and scalability in metric differential privacy.
In UAI 2022, 2022.
URL https://www.amazon.science/publications/balancing-utility-and-
scalability-in-metric-differential-
privacy. - Jain et al. (2011) Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning, 2011. URL https://arxiv.org/abs/1109.0105.
- Kairouz et al. (2015) Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376–1385. PMLR, 2015.
- Kearns and Vazirani (1994) Michael J Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994.
- Koufogiannis et al. (2017) Fragkiskos Koufogiannis, Shuo Han, and George J. Pappas. Gradual release of sensitive data under differential privacy. Journal of Privacy and Confidentiality, 7(2), Jan. 2017. 10.29012/jpc.v7i2.649. URL https://journalprivacyconfidentiality.org/index.php/jpc/article/view/649.
- Lecun et al. (1998) Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. 10.1109/5.726791.
- Levin and Peres (2017) David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
- Mahloujifar et al. (2022) Saeed Mahloujifar, Alexandre Sablayrolles, Graham Cormode, and Somesh Jha. Optimal membership inference bounds for adaptive composition of sampled gaussian mechanisms, 2022.
- McSherry and Talwar (2007) Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103. IEEE, 2007.
- Mironov (2017) Ilya Mironov. Rényi differential privacy. pages 263–275, 08 2017. 10.1109/CSF.2017.11.
- Murtagh and Vadhan (2015) Jack Murtagh and Salil Vadhan. The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference, pages 157–175. Springer, 2015.
- Ramesh et al. (2021) Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pages 8821–8831. PMLR, 2021.
- Rudin (1976) Walter Rudin. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1976.
- Salem et al. (2023) Ahmed Salem, Giovanni Cherubin, David Evans, Boris Köpf, Andrew Paverd, Anshuman Suri, Shruti Tople, and Santiago Zanella-Béguelin. Sok: Let the privacy games begin! a unified treatment of data inference privacy in machine learning, 2023.
- Shokri (2022) Reza Shokri. Auditing data privacy for machine learning. Santa Clara, CA, February 2022. USENIX Association.
- Song et al. (2013) Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages 245–248, 2013. 10.1109/GlobalSIP.2013.6736861.
- Stock et al. (2022) Pierre Stock, Igor Shilov, Ilya Mironov, and Alexandre Sablayrolles. Defending against reconstruction attacks with rényi differential privacy, 2022.
- Tramèr and Boneh (2020) Florian Tramèr and Dan Boneh. Differentially private learning needs better features (or much more data), 2020. URL https://arxiv.org/abs/2011.11660.
- Tramèr and Boneh (2021) Florian Tramèr and Dan Boneh. Differentially private learning needs better features (or much more data), 2021.
- Tsybakov (2004) Alexandre B Tsybakov. Introduction to nonparametric estimation, 2009. URL https://doi. org/10.1007/b13794. Revised and extended from the, 9(10), 2004.
- Vadhan (2017) Salil Vadhan. The Complexity of Differential Privacy, pages 347–450. Springer, Yehuda Lindell, ed., 2017. URL https://link.springer.com/chapter/10.1007/978-3-319-57048-8_7.
- Vardi et al. (2021) Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of relu neural networks. arXiv preprint arXiv:2110.03187, 2021.
- Von Neumann and Morgenstern (1947) John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior, 2nd rev. 1947.
- Wainwright (2019) Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. 10.1017/9781108627771.
- Warner (1965) Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63–69, 1965. ISSN 01621459. URL http://www.jstor.org/stable/2283137.
- Yeom et al. (2018) Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. pages 268–282, 07 2018. 10.1109/CSF.2018.00027.
- Zhu et al. (2019) Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients, 2019.
Appendix A Additional Notation and Technical Lemmas
Definition A.1 (Total Variation Distance).
Let and be two probability measures on a measurable space . The Total Variation distance between is given by:
| (8) |
Lemma A.2 (Tensorization of Total Variation Affinity).
Let and be two probability measures supported on a set . For any , let and denote the respective product measures of and , supported on the set . Then, the following holds:
Proof A.3.
Let denote the set of all couplings of and . We make use of the fact that (Levin and Peres, 2017). To this end, let denote the -optimal coupling of and , i.e., such that . We now construct a coupling of and as follows. Let and be two random variables on such that . It is easy to see that is a coupling of and . It follows that:
where the third step uses the co-ordinatewise i.i.d. structure of and the last step uses the fact that are sampled from the -optimal coupling of and . Hence, .
Definition A.4 (Binary Hypotheses Testing).
Let and be two probability measures and be an observation drawn from either or . If the objective is to determine which distribution generated the observation , it corresponds to the following statistical hypothesis testing problem:
| (9) | |||||
A test indicates which hypothesis is true.
In a binary hypothesis test, the test can make two kinds of errors: A type I error(false alarm) corresponds to the case when the null hypothesis is true but rejected, i.e., . A type II error(missed detection) is when the null hypothesis is false but retained, i.e., .
Lemma A.5 (Variational Representation of Total Variation(Cam (1986))).
For any distributions and on a measurable space , we have:
| (10) |
where the is over all tests .
Definition A.6 (M-ary Hypothesis Test (Wainwright (2019))).
Let be probability distributions such that and be an observation drawn from any one of . If the objective is to determine which distribution generated the observation , it corresponds to an -ary hypothesis testing problem, i.e., it is a generalization of Definition A.4 to multiple hypotheses.
Lemma A.7 (Fano’s Inequality for M-ary Hypotheses (Wainwright (2019))).
Let be probability distributions such that and be an observation drawn from any one of . Let be a test that indicates which distribution was drawn from, i.e., which of the hypotheses is true. Then, we have
| (11) |
where the is over all tests with values in
Lemma A.8 (Proposition 10 of Mironov (2017)).
Let be an Renyi DP learner and let and be neighboring datasets (i.e. datasets differing in only one entry). Then, for any , the following holds
Lemma A.9 (KL Upper Bounds for Metric DP Learners).
Let be an metric differentially private learner. Then, for any two datasets , the KL divergence between the output distributions and is upper bounded as follows:
Proof A.10.
This follows from Lemma 3.8 of Dwork and Rothblum (2016) by replacing with .
Appendix B Analysis of Data Reconstruction for DP
B.1 Proof of Lemma 6.1
Proof B.1.
Consider any arbitrary . By definition of total variation, the following holds
| (12) |
Note that since is an DP mechanism and are neighboring datasets, the following constraints must be satisfied:
| (13) |
From (12) and (B.1), it is easy to see that can be upper bounded by the solution to the following linear program:
| subject to | ||||
| (14) |
We now check that and y = lies in the constraint set of the linear program (B.1). Clearly, since and , and are trivially satisfied. We then note that,
i.e. the third constraint in (B.1) is satisfied as an equality. Finally,
where the last inequality follows from the fact that and . Thus, the fourth constraint in the linear program (B.1) is also satisfied. From (12), (B.1) an (B.1), we conclude that,
B.2 Lower Bound for DP : Proof of Theorem 4.1
Proof B.2.
Let be the two farthest points in , i.e. . Note that by compactness of , and are guaranteed to exist, and since is not a singleton, . Let be any arbitrary reconstruction adversary and let . For any , let denote the output distribution of and let be its associated product measure (i.e. ) Note that this means is equivalent to where we use as a shorthand for .
By Markov’s Inequality, the following holds for any
Taking the supremum over on both sides,
| (15) |
Suppose the event were true. Then, the following would hold by an application of the triangle inequality :
Thus, we note that hence . By parallel reasoning, . Substituting into (B.2), we obtain
where the fifth inequality applies Lemma A.2 and the last inequality applies Lemma 6.1 using the fact that and are datasets differing only in one point. Now, taking an infimum over all adversaries in the LHS, we obtain
By definition of it is easy to see that if an adversary attains an expected squared reconstruction error of at most for every possible target point , must be at least , i.e., the following must hold
Rearranging appropriately, we obtain the required query complexity lower bound.
B.3 Proof of Lemma 6.2
Proof B.3.
The proof of this lemma is similar to that of Lemma 6.1. To this end, we consider any arbitrary . By definition of total variation, the following holds
Note that since is an Renyi DP mechanism and are neighboring datasets, the following constraints must be satisfied as per Lemma A.8:
where . Note that since . Subsequently, it is easy to see that can be upper bounded by the solution to the following optimization problem:
| subject to | ||||
| (16) |
We now show that and lie in the constraint set of the above problem. We first note that since and , and . Hence, the first two constraints are satisfied. Furthermore, , i.e., the third constraint is satisfied with equality. The final constraint can be verified by observing that:
where we use the fact that as . Rearranging terms, it follows that:
Hence, the final constraint is satisfied. Thus, the solution to the optimization problem B.3 is bounded by and hence,
B.4 Renyi DP : Proof of Corollary 4.4
As suggested by the proof sketch in Section 6.1, we follow the exact same steps as the proof of Theorem 4.1 in Section B.2 and obtain the following:
Substituting the TV upper bound obtained in Lemma 6.2, we obtain the following:
where . Following the same arguments as Theorem 4.1, the sample complexity is obtained by upper bounding with and rearranging the expression to get a lower bound on .
B.5 Reconstruction Upper Bound : Proof of Theorem 4.2
Since , . Let be the true sample, i.e., . Our construction of is a variant of the randomized response mechanism, defined as follows:
-
1.
Flip a coin . If , then
-
2.
Otherwise, if , then is defined as follows:
Claim : is DP
Consider any . Let and . Let refer to the coin flip in step 1 of and denote the same for . Now, denote the events and . Note that, . Furthermore, when conditioned on , is the randomized response mechanism and the same holds for conditioned on . In particular, the following holds true for any :
| (17) |
Using the fact that for any two events , , we conclude the following
Repeating the same argument with , we infer that . Hence, is differentially private.
Reconstruction Adversary
Given i.i.d samples , the reconstruction adversary is defined as follows. Firstly, if there exists any such that , . Under this event, our construction of ensures that the adversary does not incur any reconstruction error, i.e. . On the contrary, if , the adversary uses the following randomized strategy: It first constructs random bits defined as:
It then uses the random bits to output a reconstruction as follows:
where denotes the binary OR operator. In summary, conditioned on the event , the adversary returns the true data point if there exists any such that , and returns otherwise. On the contrary, when conditioned on the event , the adversary outputs the true data point almost surely (by construction of )
Note that, when conditioned on , where . Furthermore, by definition of , . Now, define the event as . Clearly, . It follows that
| (18) |
where the second equality uses the fact that , the fourth equality uses the fact that and the fifth equality uses the fact that .
To make the RHS of Equation (B.5) equal to , it suffices to set .
Validity of the Adversary
We note that is a valid adversary in the set of all data reconstruction adversaries. In particular, it satisfies the desiderata put forward in Section 3, and its construction is consistent with the statement of Theorem 4.2, i.e., for every and there exists a private learner and adversary that needs queries to for achieving a reconstruction error of . In particular, takes i.i.d samples and outputs a reconstruction as per a randomized decision rule, which is completely in agreement with our modelling assumptions in Section 3 (note that our threat model is not restricted to deterministic adversaries) and of prior work (Guo et al. (2022); Balle et al. (2022)). Finally, the fact that has prior knowledge of the values of the privacy parameters also does not lead to any inconsistency since the learner’s privacy parameters are almost always publicly released (see Definition 1 of Dwork (2011)).
Next, we construct a deterministic majority-based adversary and establish tightness of the same.
Tightness of Majority Adversary
Operating under the same assumptions and parameter settings as above, let denote the two-point metric space, i.e., let , and let , be arbitrary. Moreover, let be as defined in the proof of Theorem 4.2 and let .
We construct the majority adversary defined as follows:
The following result establishes the optimality of this adversary for .
Theorem (Analysis of Majority Adversary)
Let denote the two-point metric space, i.e., let , and let , be arbitrary. Moreover, let be as defined in the proof of Theorem 4.2 and be as defined above. Then, for any and , achieves an expected squared reconstruction error of at most by making queries to .
Proof B.4.
Let . Let denote the event . By definition of , and . It follows that:
Note that, conditioned on , where . Define . Clearly, conditioned on , . Since , we control via a Chernoff Bound (Article, ) to obtain:
where . It follows that,
Thus, we conclude
To set the RHS of the above inequality equal to , it suffices to set .
Now, consider defined as . Note that . Furthermore, . Thus, . Rearranging, we conclude that .
Hence, for any , and for any , and thus . It follows that for any and ,
Moreover, since , we conclude the following
Thus, for any and , it suffices to set in order to obtain a squared reconstruction error of at most ,
B.6 Comparison with Guo et al. (2022)
For convenience, we restate the main result of Guo et al. (2022)
Theorem B.5 (Theorem 1 of Guo et al. (2022)).
Let be the input metric space, with , of a -Rényi DP learner . Let be a reconstruction attack that outputs upon observing one sample from the learner’s output distribution , i.e., . Then, if is unbiased,
| (19) |
where denotes the i-th coordinate-wise diameter defined as , and is a universal constant.
We shall now show that the above result is invalid for a large range of . In particular, Theorem 1 of Guo et al. (2022) yields invalid lower bounds for any
Consider a canonical instance of the data reconstruction problem where the data domain is the unit ball in . Then, whereas . Let be arbitrary. As per our problem setup in Section 3, denotes the output distribution induced by the randomized learner, when the target sample is . By definition of the diameter, any data reconstruction attack satisfies the trivial upper bound
| (20) |
However, the lower bound in Theorem 1 of Guo et al. (2022) states that, for any data reconstruction attack on a Renyi Differentially Private learner, the reconstruction MSE is lower bounded as
The RHS in the above bound is strictly greater than for any , thereby contradicting the trivial upper bound established above.
Appendix C Analysis of Data Reconstruction for Metric DP
C.1 Reconstruction Lower Bound : Proof of Theorem 5.1
We borrow the notation of and from the proof of Theorem 4.1 in Appendix B.2. Let be a finite subset of (to be specified later) with . Following the same steps as the proof of Theorem 1.1 by applying Markov’s inequality, we obtain:
| (21) |
where the last inequality follows from the fact that . For a tight lower bound, we must carefully construct the set . We recall from Section 6 that the adversary’s task of reconstructing a training sample is at least as hard deciding which among the was included in the training set, i.e., reconstruction is at least as hard as an -ary hypothesis testing problem. To reduce from reconstruction to testing, we construct a sample space such that the elements are uniformly distinguishable i.e., , i.e., is a packing in the metric. For ease of exposition, we assume is a homogeneous metric.
Given this construction, we again follow the same steps as the proof of Theorem 4.1. In particular, suppose there exists such that were true, then by an application of triangle inequality, one would have:
Thus, . Defining the minimum distance test as , we conclude that
It follows that
| (22) |
where the second inequality applies Lemma A.7 and the last inequality uses the tensorization of KL divergence for product measures.
Now, let be maximal -packing of the unit ball . Note that due to the local compactness of (Rudin, 1976). Since is a linear homogeneous metric space, we can scale by a factor of (assuming without loss of generality) to obtain a maximal packing of . Let this scaling of be the set . Note that and by maximality of the packing , is also a covering of . Thus, and thus, by Lemma A.9, the following holds:
Optimizing over and taking an infimum over all adversaries gives us where . As before, the required query complexity is obtained by upper bounding with and rearranging the inequality to obtain a lower bound on .
C.2 Reconstruction Upper Bound : Proof of Theorem 5.2
Our upper bound construction is based upon the exponential mechanism in . In particular, for , let be a probability measure on whose density with respect to the Lebesgue measure is given by,
For any , we set the output distribution of to be . Note that for any , their ratio of densities is bounded as follows due to the triangle inequality
Note that the same upper bound holds for It follows that for any Borel set ,
Consequently, is Lipchitz DP w.r.t .
We consider a reconstruction adversary which draws and computes . It is easy to see that where .
To sharply bound , we first note that by Theorem 1 of Bobkov (2003) shows that for any , the Poincare constant (or the inverse spectral gap) of is . We now bound using the fact that for any distribution, an inverse spectral gap of implies subexponential concentration with parameter (Bobkov and Ledoux, 1997; Aida and Stroock, 1994). In particular, Theorem 2.7 of Huang and Tropp (2021) ensures that . It follows that,
To make the RHS at most , it suffices to set
Appendix D Metric Differential Privacy in Practice
We first note that mDP is a strict generalization of DP.
Lemma D.1 (Metric DP is a generalization of DP).
Let be an arbitrary collection of secrets. A randomized learner is -differentially private if and only if is -metric differentially private with respect to the Hamming metric on .
Proof D.2.
See Lemma 2.3 of Boedihardjo et al. (2022)
Next, we establish the requisite framework for analyzing mDP in practice and present an extension of the Gaussian Noise Mechanism to metric privacy. We emphasize that, since mDP is a generalization of DP, practical applications would require a relaxation similar to 2.3 in order to establish privacy guarantees. To this end, we consider the following relaxed version of metric differential privacy.
Definition D.3 (Rényi mDP).
Given a metric space , for any , a randomized learner is Rényi mDP if for every pair of input datasets the Rényi Divergence is bounded as follows
| (23) |
where and denote the output distributions and , respectively.
It is easy to see that Definition D.3 recovers Rényi DP when restricted to the Hamming metric, in a manner similar to how mDP generalizes pure DP. Before proceeding further, we recall standard notions of sensitivity and noise mechanisms for classical differential privacy.
A common paradigm in releasing statistical information with differential privacy is to generate a noisy estimate of the true statistic. Namely, if is a real-valued function333The restriction to real-valued functions is not essential., is differentially private for an appropriate noise level . The magnitude of perturbation is generally calibrated according to the sensitivity of the function , defined as follows:
Definition D.4 (Sensitivity).
Given any function ,
| (24) |
The Gaussian mechanism, for instance, requires that be perturbed with noise drawn from the Gaussian distribution, as follows:
Definition D.5 (Gaussian Mechanism).
Given any function , the Gaussian mechanism is defined by
| (25) |
For and , the Gaussian mechanism with parameter satisfies -DP (Dwork and Roth, 2014).
The sensitivity constraint described in Definition D.4 is over all neighboring datasets , in order to accommodate for classical differential privacy. For metric differential privacy, we define a relaxed requirement which we call input lipschitzness.
Definition D.6 (Input Lipschitzness).
A function is input lipschitz if the following holds
| (26) |
Equipped with this notion, we extend the Gaussian mechanism for DP (D.5) to mDP, as follows:
Proposition D.7 (Gaussian Mechanism for mDP).
Consider any two datasets , at a distance and an input lipschitz function . For any and , the Gaussian Mechanism with parameter is mDP, where is the input Lipchitz constant of .
Proof D.8.
From the definition of input Lipschitzness and sensitivity, it follows that
| (27) |
Setting , we are required to bound the following quantity for applied on datasets :
| (28) |
where the numerator is the probability of observing a specific output and the denominator is the probability of observing the same output when the input dataset is replaced by . The proof of our claim then follows trivially from the proof of Gaussian Mechanism for differential privacy (Dwork and Roth, 2014).
We are now ready to develop mDP accountants for privacy-preserving algorithms. A popular approach to differentially private deep learning involves an extension of Stochastic Gradient Descent (SGD)(Abadi et al., 2016) to incorporate gradient clipping and noisy gradient updates. The resulting algorithm is called Differentially Private SGD (DP-SGD), wherein, differential privacy is guaranteed via an application of the Gaussian mechanism at each iteration. Since mDP is a generalization of traditional DP, we expect that iterative DP algorithms that rely on additive noise at each intermediate solution step are often inherently mDP, owing to the application of composition theorems that admit natural extensions to arbitrary metric spaces.
D.1 Metric DP Accounting for DP-SGD
In the analysis of DP-SGD (Abadi et al., 2016), privacy is attained via the addition of Gaussian distributed noise. Standard arguments on the composition of privacy mechanisms renders the differentially private variant of SGD differentially private at each step, where is the lot size. We note that, by replacing the global sensitivity assumption with input Lipschitzness, the Gaussian mechanism ensures -mDP for appropriately scaled noise, as in Proposition D.7. Thus, DP-SGD inherently incorporates metric differential privacy, with privacy accounting based on standard composition theorems.
D.2 Privacy Analysis for Metric DP in PN-SGD
When analysing the privacy of learning algorithms that require iterative updates on an intermediate solution, it is common practice to ensure privacy at each iteration and argue about the cumulative loss of privacy via composition theorems. Another popular direction is the theoretical analysis of Noisy Stochastic Gradient Descent to formalize privacy amplifications under certain assumptions and obtain bounds on the degradation of privacy across iterations. We extend the analysis of one such algorithm, the Projected Noisy Stochastic Gradient Descent (PNSGD) (Feldman et al., 2018), restated in Algorithm 1, and establish that the algorithm satisfies -Rényi mDP with a lower noise magnitude than that required for -Rényi DP.
Proposition
Let be a convex set and let be a family of convex, Lipschitz, -smooth functions over , where the gradients are -input Lipschitz. Furthermore, assume is a bounded set. Then, for any and , initializing and dataset , PNSGD run with satisfies -Rényi mDP.
Proof D.9.
The proof of this theorem is an extension of Theorem 23 of Feldman et al. (2018) to Renyi mDP. Let and be two arbitrary datasets that differ in index . Since , the projected SGD updates are contractive noisy iterations as per Definition 19 of Feldman et al. (2018).
We define the projected SGD operators for the dataset as . The projected SGD operators for the dataset are defined in a similar fashion. Since the datsets differ only in the index, we note that and,
Now, applying Theorem 22 of Feldman et al. (2018) with , , and , we conclude,
From the above inequality, we conclude that setting suffices to ensure .
Appendix E Related Literature
Theoretical investigation of reconstruction adversaries in the framework of differential private machine learning was initially studied in the recent works of Balle et al. (2022) and Guo et al. (2022), in the bayesian and frequentist settings respectively. Their analyses, however, only considers a single round of communication between the adversary and the learner, thereby limiting the expressibility of the attack. Balle et al. (2022) introduced the notion of reconstruction robustness to bound the success probability of an attack against DP learners, and, under certain modeling assumptions on the adversary’s prior belief, derived upper bounds as a function of . This metric is somewhat restrictive, since it is only equivalent to DP when considering perfect reconstruction, and requires a very specific class of priors, concentrated on pairs of data points(see Theorem 5 in Balle et al. (2022)). Instead, we focus on the minimax rate of reconstruction error of an adversary, described in detail in Section 3. This is more general than reconstruction robustness, and captures a privacy game between the learner and the adversary. Informally, the learner chooses a target sample that is the hardest to reconstruct, while the adversary picks the optimal attack that minimizes the error of reconstruction.
Guo et al. (2022) operate in the frequentist setting, and obtain lower bounds on the Euclidean MSE of reconstruction through the output of Rényi DP learners. A key limitation of their work is that their lower bound result is invalid for a broad range of , as we formally state in Section 4, with corresponding proof in Appendix B.6. Furthermore, prior work requires the input metric space to be compact and relies on the existence of coordinate-wise diameters. Such stringent assumptions hinder the generalizability of their results beyond , particularly in unstructured domains such as text, where the notion of coordinate-wise diameters may not be well-defined or relevant.
Stock et al. (2022) obtain lower bounds on the leakage of secrets in language tasks in Rényi differentially private learners. However, they are restricted to a structured and simplistic notion of secret bits, which does not capture the complexity of privacy protection in unstructured textual data. On the contrary, our lower bound results are more general and hold for arbitrary metric spaces.