It has been shown that diferential privacy bounds improve when subsampling within a randomized mechanism. Episodic training, utilized in many standard machine learning techniques, uses a multistage subsampling procedure which has not been previously analyzed for privacy bound amplification. In this paper, we focus on improving the calculation of privacy bounds in episodic training by thoroughly analyzing privacy amplification due to subsampling with a multi-stage subsampling procedure. The newly developed bound can be incorporated into existing privacy accounting methods.
the privacy amplification due to subsampling as well as a
complete analysis for Poisson and simple random
subsamAs more data is being utilized by algorithms and machine pling both with and without replacement subsampling
learning techniques, rigorously maintaining the privacy methods.
of this data has become important. Cyber security, health, The subsampling methods analyzed previously include
and census data collection are all examples of fields that many of the subsampling methods utilized by machine
are seeing increased scrutiny for ensuring the privacy learning; however, the methods does not capture batches
of data, and it is well known that just anonymizing the formed by algorithms that use episodic training. Episodic
data by removing features such as name is not suficient training methods are utilized by a variety of machine
to guarantee privacy due to vulnerabilities such as re- learning algorithms, such as meta learning (e.g., [
Diferential privacy, first introduced by Dwork, is one In this paper, we analyze the privacy amplification
technical definition of privacy that has been studied due to the subsampling method utilized in an episodic
widely in the literature [
Machine learning practitioners initially integrated dif- sulting theorem can be easily applied to episodic training
ferential privacy by naively applying these composition methods and integrated with privacy accounting
meththeorems algorithm by assuming that the algorithm ac- ods such as the moment’s accountant [
In a multistage sampling procedure, the universe from which samples are drawn is partitioned. These partitions may contain the examples we are ultimately interested in sampling or may contain one or several levels of partitions. The subsampling procedure is to sample partitions at each level until examples are sampled. For example, if we are interested in the demographics of students at a school, we could partition students by teacher, sample some number of teachers and then sample students from each sampled teacher.
To see that episodic training is a multistage
subsampling procedure, consider how training batches are formed Given > 0, let ′ = (1+ ( − 1)) and = /′ ,
in Algorithm 2 of [
Given a randomized algorithm or mechanism ℳ : → P(), where P() is the set of probability mea- 3. OUR APPROACH: Privacy sures on the output space , ℳ is (, )-diferentially Bounds for Multistage private w.r.t ≃ if for every pair ≃ ′ and every measurable subset ⊆ , Sampling Analysis We will begin the analysis with an example. Through this example, we will introduce the notation necessary for the general analysis.
Example 3.1. Let be a universe of 18 examples from which the database or training data is drawn from. Suppose we can categorize the data from the universe at 3 diferent levels, so we will perform a 3-stage sampling.
Let = 1 ∪ 2 = (11 ∪ 12 ∪ 13) ∪ (21 ∪ 22) = (︀ {111, 112, 113, 114} ∪ {121, 122} ∪ {131, 132, 133}︀) ∪ ︀( {211, 212, 213, 214} ∪ {221, 222, 223, 224, 225}︀)
Pr[ℳ( ) ∈ ] ≤ Pr[ℳ( ′) ∈ ] + .
Utilizing the tools from [
()) of two probability measures , ′ ∈ P(), where ranges over all measurable subsets of . Diefrential privacy can then be stated in terms of -divergence; specifically, a mechanism ℳ is (, )-diferentially private if and only if (ℳ( )||ℳ( ′)) ≤ for every adjacent datasets ≃ ′.
We can now define the privacy profile of a mechanism ℳ as ℳ = sup ≃ ′ (ℳ( )||ℳ( ′)), which associates each privacy parameter = with a bound on the -divergence between the results of the mechanism on two adjacent datasets.
Two theorems from [
The first is Advanced Joint Convexity, which we restate in terms of = since we are interested in applying this theorem to improve the privacy bounds due to multistage subsampling.
In this example, 1 for ∈ {1, 2} are the primary sampling units, the 12 are the ultimate sampling units and the 123 are the examples that would be provided to a training algorithm.
In general, let be a universe from which the training
data is drawn and suppose a finite number of levels, ,
partition this universe. Define be the primary
samTheorem 1. ([
Set := ⋃︀ Set := ∅ Given : the number of units to be sampled at each level (1 ≤ ≤ ) for ∈ {1, ...., } do for ∈ PrevLevel do sample without replacement elements from add sampled elements to end end = := ∅
Now, let ⊂ be the training data or database we are analyzing. We will require that the training data has at least one element from each sampling unit described above. Thus we only allow the ultimate sampling units of the training data 12· − 1 ⊂ 12· − 1 , to be a non-empty finite subset of the ultimate sampling units with at least elements (i.e. at least the number of units that will be sampled from the ultimate sampling units). All other sampling units defined for the universe will remain the same for the training set.
We want to analyze the privacy bound on algorithms
that use a multistage subsampling procedure on . To do
this, we will apply the theorems from [
(, ′) = 1 − ∑︁ min ( (), ′()) ∈ Note we can easily extend our probability measures , ′ to the entire universe by setting the inclusion probability to 0 for any element not in or ′. For all elements ∈ ′ ∖ 12· − 1 , we have min( (), ′()) = () = ′(). Since 12· − 1 1 ̸∈ ′, we also have min( (12· − 1 1), ′(12· − 1 1)) = 0 . So we just need to consider the elements of the ultimate unit from which we removed an element. Since, we removed an element from this unit, the probability ′() > () since ′12· − 1 (the ultimate unit missing an element in ′) has fewer elements than 12· − 1 , therefore for all 12· − 1 ∈ ′12· − 1 and ̸= 1, we have (12· − 1 ) < ′(′12· − 1 ) where (12· − 1 ) = ′(′12· − 1 ) = ∏︀=1 ∏︀=1 |1 ||12 | · · · | 12· − 1 | |1 ||12 | · · · | ′12· − 1 | .
∈ ∑︁ min ( (), ′()) = ∑︁ () = 1− (12· − 1 1).
∈ ′ Hence the total variational distance is just the inclusion probability of the element we removed. Determining the total variational distance when adding an element from to is similar to the above argument.
We can now provide an amplified privacy bound for multistage subsampling.
Theorem 3. Let ℳ′ be a subsampled mechanism on described by Algorithm 1 and let 12 . . . − 1 be the index of the penultimate sampling unit that satisfies
min 1,2,...,− 1
(|1 ||12 | · · · | 12· − 1 |). ∏︀=1
Then, for any ≥ 0, we have that ℳ′ ( ′) ≤ ℳ′ ( ) (12· ) = |1 ||12 | · · · | 12· − 1 | for and = |1 ||12∏|︀·|=112· − 1 | and ′ = where 12· is in the ultimate unit 12· − 1 . (1 + ( − 1)) under the add-one/remove-one rela
Now consider ′ created by removing one element tion. from , say without loss of generality, 12· − 1 1 for some 1, 2, ..., − 1 . The probability measure ′ for sampling from ′ can be defined similar to above. We wish to compute the total variational distance between these two measure so that we can apply the Advanced
To fully complete the proof, let , ′ be training sets drawn from with ≃ ′ under the add-one/removeone relation ≃ and let ( ) denote the subsampling mechanism described by Algorithm 1 for = (, ′).
Let 0 = ∩ ′, then by definition of ≃, 0 = or
0 = ′. Let 0 = (0), = ( ) and ′ =
( ′). Then the decompositions of and ′ induced
by their maximal coupling have that 1 = 0 when
0 = or ′1 = 0 when 0 = ′. We only need to
consider 0 = ′ since this is when the maximum is
obtained in applying advanced joint convexity. Finally,
we note that one can easily create a ≃ -compatible pair
according to the definition provided in [
We briefly mention how one might incorporate this
new bound into a privacy accounting method. Many
accounting methods, like the moments accountant [
This paper completely analyzes the privacy amplification due to multistage subsampling. This provides the correct privacy bounds for any algorithm that utilizes multistage subsampling, such as machine learning algorithms that use episodic training. Our future goal is to perform experiments to better understand privacy in machine learning algorithms that use episodic training like meta-learning algorithms. We hope our presented approach and discussion will prove useful to other researchers wanting to apply privacy bounds on multistage sampling in other studies and applications. [13] C.-E. Särndal, B. Swensson, J. Wretman, Model Assisted Survey Sampling, Springer-Verlag, 2003, p. 124–162. [14] I. Mironov, K. Talwar, L. Zhang, R\’enyi diferential privacy of the sampled gaussian mechanism (????). URL: http://arxiv.org/abs/1908.10530. arXiv:1908.10530.