Introduction
Suppose a learner receives samples from an unknown probability distribution p p p Q \mathcal{Q} Q p ^ \hat{p} p ^ p ^ \hat{p} p ^ p p p distribution learning or density estimation , and has seen significant study across a variety of adjacent research communities including computer science, statistics, and information theory (see, for example, [KMR+94, DL01, DDS12, Dia16, ABDH+20, LBD26]).
The problem of density estimation has also been studied extensively under the constraint of differential privacy (DP) [27 ] . Indeed, there is a rich body of literature on private learning of various classes of distributions. Some examples are private density estimation of structured univariate distributions [23 , 38 ] , high-dimensional Gaussians [32 , 17 , 15 , 2 , 7 KMV22, 34 , 6 , 29 ] , Gaussian Mixture Models [37 , 1 , 13 , 3 , 9 , 4 ] , and product distributions [32 , 17 , 45 ] .
One vibrant program within this area has focused on designing increasingly general and generic frameworks for learning distribution classes (see, for example, [17 , 7 , 29 , 12 , 3 , 4 ] ). At their core, many of these methods rely upon non-private learning algorithms as a black box, applying DP techniques on their outputs to design private algorithms. At a July 2022 workshop at the Fields Institute, Ashtiani conjectured that every learnable distribution class could be privately learned [Ash22].
Conjecture 1.1 (Ashtiani’s Conjecture). Every distribution class Q \mathcal{Q} Q that is learnable with respect to total variation distance is also learnable under the additional constraint of ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) differential privacy.
Our main result (Theorem 1.3 ) is a positive resolution to this conjecture: given a non-private algorithm for learning a distribution class up to arbitrarily small target error in total variation distance, we provide a private algorithm for learning the same distribution class.
A recent work by Bun, Kamath, Mouzakis, and Singhal [16 ] claimed to refute Ashtiani’s conjecture, which may seem to contradict our result. In fact, their work can be viewed as a weak refutation of Ashtiani’s conjecture. They constructed a distribution class which can be learned up to constant error in total variation distance, but cannot be learned privately to that same error. The distribution class in their counter-example, however, is not (non-privately) learnable to all values of error. In contrast, we use the traditional definition of learnability, wherein the distribution class must be learnable to arbitrarily small error [36 ] . Indeed, our private algorithm relies crucially upon non-private learning of the class to a higher accuracy than the target.
Our positive resolution of the conjecture may come as a surprise as private and non-private learnability are not necessarily equivalent for problems beyond density estimation. Indeed, in the standard binary classification setting, non-private learnability does not imply ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) [19 , 8 ] . It is also remarkable that for (non-private) density estimation, a nice characterization of learnability is not known (and in some sense impossible [39 , 40 ] ) while our private to non-private reduction works anyway.
Results
In what follows, let X \mathcal{X} X Δ ( X ) \Delta(\mathcal{X}) Δ ( X ) X \mathcal{X} X Q ⊆ Δ ( X ) \mathcal{Q} \subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) distribution class . Denote by T V \mathrm{TV} TV p , q ∈ Δ ( X ) p,q \in\Delta(\mathcal{X}) p , q ∈ Δ ( X ) T V ( p , q ) : = sup A ∈ B ∣ p ( A ) − q ( A ) ∣ \mathrm{TV}(p,q) := \sup_{A \in\mathcal{B}} \lvert p(A) - q(A) \rvert TV ( p , q ) := sup A ∈ B ∣ p ( A ) − q ( A )∣ B \mathcal{B} B X \mathcal{X} X
Definition 1.2 (Distribution learning). A distribution class Q ⊆ Δ ( X ) \mathcal{Q} \subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) is learnable if there exist a learner A : X ∗ → Δ ( X ) A : \mathcal{X}^{*} \to\Delta(\mathcal{X}) A : X ∗ → Δ ( X ) and a function m : ( 0 , 1 ) 2 → N m : (0,1)^{2} \to\mathbb{N} m : ( 0 , 1 ) 2 → N such that, for every α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 ) every n ≥ m ( α , β ) n \ge m(\alpha,\beta) n ≥ m ( α , β ) and every p ∈ Q p \in\mathcal{Q} p ∈ Q
Pr S ∼ p n [ T V ( A ( S ) , p ) ≥ α ] ≤ β . \Pr_{S \sim p^{n}}[\mathrm{TV}(A(S),p) \ge\alpha] \le\beta. S ∼ p n Pr [ TV ( A ( S ) , p ) ≥ α ] ≤ β . The sample complexity of learning Q \mathcal{Q} Q is the pointwise infimum of all functions m m m for which there exists a learner A A A satisfying the above guarantee.
Theorem 1.3 (Learnable classes are privately learnable; informal version of Theorem 6.1). Suppose Q ⊆ Δ ( X ) \mathcal{Q} \subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) is learnable with sample complexity m ( α , β ) m(\alpha,\beta) m ( α , β ) for α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 ) Then, for every ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) Q \mathcal{Q} Q is also learnable under ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) differential privacy, with sample complexity n ( α , β , ε , δ ) = n(\alpha,\beta,\varepsilon,\delta) = n ( α , β , ε , δ ) = O ( m ( 1 512 m ( α / 3 , 1 / 32 ) , 1 16 ) 1 ε log ( 4 δ ) log ( 4 β ) ) O\left(m\left(\frac{1}{512m(\alpha/3,1/32)},\frac{1}{16}\right)\frac{1}{\varepsilon}\log\left(\frac{4}{\delta}\right)\log\left(\frac{4}{\beta}\right)\right) O ( m ( 512 m ( α /3 , 1/32 ) 1 , 16 1 ) ε 1 log ( δ 4 ) log ( β 4 ) )
In particular, if a class Q \mathcal{Q} Q m ( α , β ) = poly ( 1 α , log 1 β ) m(\alpha,\beta) = \operatorname{poly}\left(\frac{1}{\alpha},\log\frac{1}{\beta}\right) m ( α , β ) = poly ( α 1 , log β 1 ) Q \mathcal{Q} Q ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) m ( α , β , ε , δ ) = poly ( 1 α , log 1 β , 1 ε , log 1 δ ) m(\alpha,\beta,\varepsilon,\delta) = \operatorname{poly}\left(\frac{1}{\alpha},\log\frac{1}{\beta},\frac{1}{\varepsilon},\log\frac{1}{\delta}\right) m ( α , β , ε , δ ) = poly ( α 1 , log β 1 , ε 1 , log δ 1 )
As part of our approach, we develop private samplers [44 , 21 ] for any learnable class, which can be of independent interest. These samplers receive private data points and output a synthetic data set, generated from a distribution that is close to the underlying (unknown) distribution.
Definition 1.4 (Approximate multi-sampler). Let Q ⊆ Δ ( X ) Q \subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) randomized algorithm M : X n → X ℓ M : \mathcal{X}^{n} \to\mathcal{X}^{\ell} M : X n → X ℓ ( ℓ , γ ) (\ell,\gamma) ( ℓ , γ ) sampler for Q Q Q n n n p ∈ Q p \in Q p ∈ Q
TV ( L ( Z ) , L ( Z ′ ) ) ≤ γ , \operatorname{TV}(\mathcal{L}(Z),\mathcal{L}(Z')) \leq\gamma, TV ( L ( Z ) , L ( Z ′ )) ≤ γ , where Z ∼ p ℓ Z \sim p^{\ell} Z ∼ p ℓ Z ′ = M ( S ) Z' = M(S) Z ′ = M ( S ) S ∼ p n S \sim p^{n} S ∼ p n L ( ⋅ ) \mathcal{L}(\cdot) L ( ⋅ )
Theorem 1.5 (Differentially private synthetic data for learnable classes; informal version of Theorem 4.3 ). Let Q ⊆ Δ ( X ) Q \subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) learnable with sample complexity m ( α , β ) m(\alpha,\beta) m ( α , β ) ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N γ , ε , δ ∈ ( 0 , 1 ) \gamma,\varepsilon,\delta\in(0,1) γ , ε , δ ∈ ( 0 , 1 ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ( ℓ , γ ) (\ell,\gamma) ( ℓ , γ ) Q Q Q
n = O ( m ( γ 64 ℓ , 1 16 ) log ( 1 γ δ ) 1 ε ) . n = O\left(m\left(\frac{\gamma}{64\ell},\frac{1}{16}\right)\log\left(\frac{1}{\gamma\delta}\right)\frac{1}{\varepsilon}\right). n = O ( m ( 64 ℓ γ , 16 1 ) log ( γ δ 1 ) ε 1 ) . For the problem of (non-private) density estimation, learnability in realizable setting is not equivalent to learnability in agnostic/robust setting [14 ] . Our next result is a private to non-private reduction for agnostic learning of distributions. The formal version and more discussions appear in Section C.
Theorem 1.6 (Agnostic learnability implies private agnostic learnability, Informal version of C.2). Suppose Q ⊆ Δ ( X ) Q \subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) m ( α , β ) m(\alpha,\beta) m ( α , β ) α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 ) Then, for every ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) Q Q Q ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
n ( α , β , ε , δ ) = O ( m ( Θ ( α ) , 1 16 ) m ( Θ ( α ) , β ) 1 ε log ( 1 α δ ) ) . n(\alpha,\beta,\varepsilon,\delta) = O\left(m\left(\Theta(\alpha),\frac{1}{16}\right)m\left(\Theta(\alpha),\beta\right)^{\frac{1}{\varepsilon}}\log\left(\frac{1}{\alpha\delta}\right)\right). n ( α , β , ε , δ ) = O ( m ( Θ ( α ) , 16 1 ) m ( Θ ( α ) , β ) ε 1 log ( α δ 1 ) ) . Techniques
At its core, our algorithm falls into the subsample-and-aggregate framework [43 ] . Suppose we have a non-private learning algorithm A A A Q Q Q
Partition the dataset into k = O ( log ( 1 / δ ) / ε ) k = O(\log(1/\delta)/\varepsilon) k = O ( log ( 1/ δ ) / ε )
Run the non-private learning algorithm A A A
Privately aggregate the outputs.
Let q i q_i q i i ∈ [ k ] i \in[k] i ∈ [ k ] i th i^{\text{th}} i th q i q_i q i globally stable [18 ] ), then they can be easily aggregated, for example, using DP stability-based mode [Vad17]. However, the non-private learner A A A q i q_i q i close to the ground truth p p p
Another idea for aggregating q i q_i q i q i q_i q i Z i ∼ q i ℓ Z_i \sim q_i^{\ell} Z i ∼ q i ℓ ℓ \ell ℓ q i q_i q i Z i Z_i Z i i i i p p p p p p q i q_i q i Z i Z_i Z i q i q_i q i Z i Z_i Z i Z i Z_i Z i i i i Z i Z_i Z i i i i
To make the idea concrete we turn to couplings . Couplings construct a joint distribution over a collection of random variables such that their marginal distributions are preserved. The key observation is that a suitable TV coupling can convert closeness in total variation distance into a high probability guarantee of exact equality between sampled outcomes. Specifically, after obtaining q 1 , … , q k q_1,\ldots,q_k q 1 , … , q k ( Z 1 , … , Z k ) (Z_1,\ldots,Z_k) ( Z 1 , … , Z k ) Definition 3.1 . The coupling is designed to satisfy two key desiderata: (1) each marginal has the correct law, so that Z i ∼ q i ℓ Z_i \sim q_i^\ell Z i ∼ q i ℓ i t h i^{\mathrm{th}} i th q i q_i q i Z i Z_i Z i exact same value with high probability. Thus, a TV coupling can convert total variation closeness of the q i q_i q i Z i Z_i Z i
Indeed, the use of correlated sampling to convert closeness in TV into agreement of sampled outcomes already appears in the user-level private learning algorithms of Ghazi, Kumar, and Manurangsi [28 ] . Kalavasis, Karbasi, Moran, and Velegkas [KKMV23] subsequently use a related coupling approach to reduce TV-indistinguishable PAC learning to approximate differentially private learning. A similar concept has been used in [CCWL+26] for private aggregation of teacher models. In our setting, we apply this principle to synthetic datasets.
Our constructions of a couplings are based on the Poisson coupling of Angel and Spinka [10 ] , which ensures that for all i , j ∈ [ k ] i,j \in[k] i , j ∈ [ k ] Pr [ Z i ≠ Z j ] ≤ 2 TV ( q i ℓ , q j ℓ ) \Pr[Z_i \ne Z_j] \le2\operatorname{TV}(q_i^\ell,q_j^\ell) Pr [ Z i = Z j ] ≤ 2 TV ( q i ℓ , q j ℓ ) σ \sigma σ [10 ] applies directly, as in [KKMV23]. This already covers many familiar distribution classes. For our main result, however, we must handle arbitrary learnable distribution classes, for which such a common dominating measure need not exist. For instance, P = { δ x : x ∈ R } \mathcal{P} = \{\delta_x : x \in\mathbb{R}\} P = { δ x : x ∈ R } σ \sigma σ
The coupling methods allow us to turn closeness of TV distances between q i q_i q i Z i Z_i Z i Z i Z_i Z i Theorem 1.5 . In order to have a private distribution learner, one can simply feed a privatized sample set to the non-private learner. However, this approach would result in a poor dependency on β \beta β
This results in the logarithmic dependence of sample complexity on 1 / β 1/\beta 1/ β Theorem 1.3 .
AI Disclosure
The initial resolution for Ashtiani’s conjecture in the case of countable domains was independently obtained by two authors prompting GPT-5.6 Sol. An internal Gemini model also produced a positive resolution of the conjecture by discovering a similar algorithm to the one presented. All authors digested the result and verified it to be correct.
Additional prompting, verification, and derivations from the authors resulted in the presented measure-theoretic arguments that constitute a full resolution to the conjecture for general domains. Care was taken to write the paper in a way that communicates the ideas most clearly to a human reader. The authors also conducted a literature search to attribute the main algorithmic ideas to [10 ] and [KKMV23]. All writing in this paper is done by the authors, who take full responsibility for the claims made herein.
Preliminaries
Let Y \mathcal{Y} Y B ( Y ) \mathcal{B}(\mathcal{Y}) B ( Y ) Δ ( Y ) \Delta(\mathcal{Y}) Δ ( Y ) Y \mathcal{Y} Y σ \sigma σ P ↦ P ( B ) P \mapsto P(B) P ↦ P ( B ) B ∈ B ( Y ) B \in\mathcal{B}(\mathcal{Y}) B ∈ B ( Y ) σ \sigma σ
For a random variable Z Z Z L ( Z ) \mathcal{L}(Z) L ( Z ) L ( Z ) ( B ) = Pr [ Z ∈ B ] \mathcal{L}(Z)(B) = \Pr[Z \in B] L ( Z ) ( B ) = Pr [ Z ∈ B ] B B B P , Q ∈ Δ ( Y ) P,Q \in\Delta(\mathcal{Y}) P , Q ∈ Δ ( Y ) TV ( P , Q ) : = sup B ∈ B ( Y ) ∣ P ( B ) − Q ( B ) ∣ \operatorname{TV}(P,Q) := \sup_{B \in\mathcal{B}(\mathcal{Y})} |P(B)-Q(B)| TV ( P , Q ) := sup B ∈ B ( Y ) ∣ P ( B ) − Q ( B ) ∣
Our coupling constructions use two standard measure-theoretic objects. First, we will use Markov kernels to formalize randomized mappings whose output distributions depend measurably on their inputs. In particular, they allow us to view our coupling procedures as randomized maps from tuples of distributions to joint synthetic datasets.
Definition 2.1 (Markov kernel). Let ( X , A ) (\mathcal{X},\mathcal{A}) ( X , A ) ( Y , B ) (\mathcal{Y},\mathcal{B}) ( Y , B ) K : X ⇝ Y K : \mathcal{X} \rightsquigarrow\mathcal{Y} K : X ⇝ Y x ∈ X x \in\mathcal{X} x ∈ X K ( x ; ⋅ ) K(x;\mathord\cdot) K ( x ; ⋅ ) Y \mathcal{Y} Y B ∈ B B \in\mathcal{B} B ∈ B x ↦ K ( x ; B ) x \mapsto K(x;B) x ↦ K ( x ; B ) A \mathcal{A} A
Second, our explicit coupling constructions are based on the Poisson coupling of Angel and Spinka [10 ] , which is built from Poisson point processes. We recall their basic definition below.
Informally, a Poisson point process with intensity measure μ \mu μ μ \mu μ B B B μ ( B ) \mu(B) μ ( B )
Definition 2.2 (Poisson point process). Let ( Y , B ) (\mathcal{Y},\mathcal{B}) ( Y , B ) μ \mu μ σ \sigma σ Y \mathcal{Y} Y A \mathcal{A} A Y \mathcal{Y} Y μ \mu μ
for every measurable B ⊆ Y B \subseteq\mathcal{Y} B ⊆ Y μ ( B ) < ∞ \mu(B) < \infty μ ( B ) < ∞ A ( B ) ∼ Poisson ( μ ( B ) ) \mathcal{A}(B) \sim\operatorname{Poisson}(\mu(B)) A ( B ) ∼ Poisson ( μ ( B ))
for every collection of pairwise disjoint measurable sets B 1 , … , B m B_1,\ldots,B_m B 1 , … , B m A ( B 1 ) , … , A ( B m ) \mathcal{A}(B_1),\ldots,\mathcal{A}(B_m) A ( B 1 ) , … , A ( B m )
We recall the celebrated definition of differential privacy, as well as its useful post-processing and parallel composition property.
Definition 2.3 (Differential privacy (DP) [27 , 25 ] ). Let ( X , A ) (\mathcal{X},\mathcal{A}) ( X , A ) ( Y , B ) (\mathcal{Y},\mathcal{B}) ( Y , B ) ϵ > 0 \epsilon> 0 ϵ > 0 δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) A : X ∗ → Y A : \mathcal{X}^{*} \to\mathcal{Y} A : X ∗ → Y ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) n ∈ N n \in\mathbb{N} n ∈ N S , S ′ ∈ X n S,S' \in\mathcal{X}^{n} S , S ′ ∈ X n B ⊆ Y B \subseteq\mathcal{Y} B ⊆ Y
Pr [ A ( S ) ∈ B ] ≤ e ϵ Pr [ A ( S ′ ) ∈ B ] + δ \Pr[A(S) \in B] \le e^{\epsilon}\Pr[A(S') \in B] + \delta Pr [ A ( S ) ∈ B ] ≤ e ϵ Pr [ A ( S ′ ) ∈ B ] + δ where the probabilities are over the internal randomness of A A A
Proposition 2.4 (Post-processing). Let ( X , A ) (\mathcal{X},\mathcal{A}) ( X , A ) ( Y , B ) (\mathcal{Y},\mathcal{B}) ( Y , B ) ( Z , C ) (\mathcal{Z},\mathcal{C}) ( Z , C ) A : X ∗ → Y A : \mathcal{X}^{*} \to\mathcal{Y} A : X ∗ → Y ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) K : Y ⇝ Z K : \mathcal{Y} \rightsquigarrow\mathcal{Z} K : Y ⇝ Z K ∘ A : S ↦ Z K \circ A : S \mapsto Z K ∘ A : S ↦ Z Z ∼ K ( A ( S ) ; ⋅ ) Z \sim K(A(S);\mathord\cdot) Z ∼ K ( A ( S ) ; ⋅ ) ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ )
Lemma 2.5 (Parallel composition [41 ] ). Let ϵ ≥ 0 \epsilon\ge0 ϵ ≥ 0 δ ∈ [ 0 , 1 ) \delta\in[0,1) δ ∈ [ 0 , 1 ) I 1 , … , I k I_1,\ldots,I_k I 1 , … , I k [ n ] [n] [ n ] i ∈ [ k ] i \in[k] i ∈ [ k ] A i : X ∗ → Y A_i : \mathcal{X}^{*} \to\mathcal{Y} A i : X ∗ → Y ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) S ∈ X n S \in\mathcal{X}^{n} S ∈ X n A ( S ) : = ( A 1 ( S I 1 ) , … , A k ( S I k ) ) A(S) := (A_1(S_{I_1}),\ldots,A_k(S_{I_k})) A ( S ) := ( A 1 ( S I 1 ) , … , A k ( S I k )) ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ )
Couplings
As discussed in § 1.2 , our private aggregation procedure requires a correlated sampling mechanism that converts TV closeness of the learner outputs into exact agreement of the sampled synthetic datasets. We now formalize the properties of the coupling needed for the subsequent privacy and utility analyses. In addition to having the correct marginals and a small pairwise disagreement probability discussed above, we further require the joint law of every finite collection of coupled samples to depend measurably on the input distributions. This ensures that the coupling can be applied to random data-dependent learner outputs and then supplied to subsequent randomized algorithms.1 Y \mathcal{Y} Y
Definition 3.1 (Grand coupling scheme). Let Y \mathcal{Y} Y P ⊆ Δ ( Y ) \mathcal{P} \subseteq\Delta(\mathcal{Y}) P ⊆ Δ ( Y ) P \mathcal{P} P ( Z P ) P ∈ P (Z_P)_{P\in\mathcal{P}} ( Z P ) P ∈ P Γ P \Gamma_{\mathcal{P}} Γ P
(G1) (Marginals.) Z P ∼ P Z_P \sim P Z P ∼ P P ∈ P P \in\mathcal{P} P ∈ P
(G2) (Agreement.) Pr [ Z P ≠ Z Q ] ≤ 2 TV ( P , Q ) \Pr[Z_P \ne Z_Q] \le2\operatorname{TV}(P,Q) Pr [ Z P = Z Q ] ≤ 2 TV ( P , Q ) P , Q ∈ P P,Q \in\mathcal{P} P , Q ∈ P
(G3) (Measurable marginal kernels.) For every k ≥ 1 k \ge1 k ≥ 1 P ↦ L ( Z P 1 , … , Z P k ) \mathbf{P} \mapsto\mathcal{L}(Z_{P_1},\ldots,Z_{P_k}) P ↦ L ( Z P 1 , … , Z P k ) Γ k : P k ⇝ Y k \Gamma_k:\mathcal{P}^k \rightsquigarrow\mathcal{Y}^k Γ k : P k ⇝ Y k P = ( P 1 , … , P k ) ∈ P k \mathbf{P}=(P_1,\ldots,P_k)\in\mathcal{P}^k P = ( P 1 , … , P k ) ∈ P k
Couple k ( P ) \operatorname{Couple}_k(\mathbf{P}) Couple k ( P ) Γ k ( P ; ⋅ ) \Gamma_k(\mathbf{P};\cdot) Γ k ( P ; ⋅ )
We present two constructions of this interface, based on the Poisson coupling of [10 ] . Full details and complete proofs for both constructions are deferred to Appendix § 7 . The first, presented in Appendix § 7 .§ 1 , is the original construction taken verbatim from [10 ] , which applies when the subset of relevant distributions P \mathcal{P} P σ \sigma σ ν \nu ν
We illustrate how Construction A.1 works with a simple example. Consider a set of distributions P \mathcal{P} P [ 0 , 1 ] [0,1] [ 0 , 1 ] P ∈ P P \in\mathcal{P} P ∈ P f P f_P f P M M M ( Y i , U i ) (Y_i,U_i) ( Y i , U i ) [ 0 , 1 ] × [ 0 , M ] [0,1] \times[0,M] [ 0 , 1 ] × [ 0 , M ] P ∈ P P \in\mathcal{P} P ∈ P P P P Y i Y_i Y i i i i U i ≤ f P ( Y i ) U_i \le f_P(Y_i) U i ≤ f P ( Y i ) P P P P P P Z P Z_P Z P P P P P , Q ∈ P P,Q \in\mathcal{P} P , Q ∈ P 1 − TV ( P , Q ) 1-\operatorname{TV}(P,Q) 1 − TV ( P , Q ) 1 + TV ( P , Q ) 1+\operatorname{TV}(P,Q) 1 + TV ( P , Q ) 1 − TV ( P , Q ) 1 + TV ( P , Q ) \frac{1-\operatorname{TV}(P,Q)}{1+\operatorname{TV}(P,Q)} 1 + TV ( P , Q ) 1 − TV ( P , Q ) Pr [ Z P ≠ Z Q ] ≤ 2 TV ( P , Q ) 1 + TV ( P , Q ) ≤ 2 TV ( P , Q ) \Pr[Z_P \ne Z_Q] \le\frac{2\operatorname{TV}(P,Q)}{1+\operatorname{TV}(P,Q)} \le2\operatorname{TV}(P,Q) Pr [ Z P = Z Q ] ≤ 1 + TV ( P , Q ) 2 TV ( P , Q ) ≤ 2 TV ( P , Q )
More precisely, Construction A.1 yields a grand coupling scheme on P \mathcal{P} P P ∈ P P \in\mathcal{P} P ∈ P P ∈ P P \in\mathcal{P} P ∈ P d P d ν \frac{\mathrm{d}P}{\mathrm{d}\nu} d ν d P Z P Z_P Z P y y y t t t
Proposition 3.2 (Informal version of Corollary A.3). Suppose Y \mathcal{Y} Y σ \sigma σ ν \nu ν P ≪ ν P \ll\nu P ≪ ν P ∈ P P \in\mathcal{P} P ∈ P ( Z P ) P ∈ P (Z_P)_{P\in\mathcal{P}} ( Z P ) P ∈ P Γ P \Gamma_{\mathcal{P}} Γ P P \mathcal{P} P
Construction A.1 already captures a wide range of distribution classes. For example, a family of distributions on R d \mathbb{R}^{d} R d σ \sigma σ P = { δ x : x ∈ R } \mathcal{P} = \{\delta_x : x \in\mathbb{R}\} P = { δ x : x ∈ R } σ \sigma σ
The key observation behind our second construction is that while a global measure ν \nu ν P = ( P 1 , … , P k ) ∈ Δ ( Y ) k \mathbf{P} = (P_1, \ldots, P_k) \in\Delta(\mathcal{Y})^k P = ( P 1 , … , P k ) ∈ Δ ( Y ) k ν P = ∑ i = 1 k P i \nu_{\mathbf{P}} = \sum_{i=1}^{k} P_i ν P = ∑ i = 1 k P i k k k P \mathbf{P} P Y i Y_i Y i P \mathbf{P} P ν P \nu_{\mathbf{P}} ν P Γ k ( P ; ⋅ ) ∈ Δ ( Y k ) \Gamma_k(\mathbf{P}; \cdot) \in\Delta(\mathcal{Y}^k) Γ k ( P ; ⋅ ) ∈ Δ ( Y k ) P 1 , … , P k P_1, \ldots, P_k P 1 , … , P k P \mathbf{P} P Γ k : Δ ( Y ) k ⇝ Y k \Gamma_k : \Delta(\mathcal{Y})^k \rightsquigarrow\mathcal{Y}^k Γ k : Δ ( Y ) k ⇝ Y k
The remaining issue is that, the reference measure ν P \nu_{\mathbf{P}} ν P P \mathbf{P} P k k k k k k k + 1 k+1 k + 1 ( P 1 , P 2 ) (P_1, P_2) ( P 1 , P 2 ) ( P 1 , P 2 , P 3 ) (P_1, P_2, P_3) ( P 1 , P 2 , P 3 ) 2
Finally, Kolmogorov’s Extension Theorem (Corollary A.6 ) then guarantees the existence of a single, universal joint measure Γ ∞ ∈ Δ ( Y Δ ( Y ) ) \Gamma_\infty\in\Delta(\mathcal{Y}^{\Delta(\mathcal{Y})}) Γ ∞ ∈ Δ ( Y Δ ( Y ) ) Γ ∞ \Gamma_\infty Γ ∞ Z P Z_{\mathbf{P}} Z P P ∈ Δ ( Y ) \mathbf{P} \in\Delta(\mathcal{Y}) P ∈ Δ ( Y ) Γ k \Gamma_k Γ k Z P ∼ P Z_{\mathbf{P}} \sim P Z P ∼ P P ∈ Δ ( Y ) \mathbf{P} \in\Delta(\mathcal{Y}) P ∈ Δ ( Y ) P ⊆ Δ ( Y ) \mathcal{P} \subseteq\Delta(\mathcal{Y}) P ⊆ Δ ( Y ) Γ P \Gamma_{\mathcal{P}} Γ P
Proposition 3.3 (Informal version of Corollary A.7 and A.6). Suppose Y \mathcal{Y} Y ( Z P ) P ∈ Δ ( Y ) ∼ Γ ∞ (Z_{\mathbf{P}})_{\mathbf{P}\in\Delta(\mathcal{Y})} \sim\Gamma_\infty ( Z P ) P ∈ Δ ( Y ) ∼ Γ ∞ Δ ( Y ) \Delta(\mathcal{Y}) Δ ( Y ) P ⊆ Δ ( Y ) \mathcal{P} \subseteq\Delta(\mathcal{Y}) P ⊆ Δ ( Y ) ( Z P ) P ∈ P (Z_{\mathbf{P}})_{\mathbf{P}\in\mathcal{P}} ( Z P ) P ∈ P Γ P \Gamma_{\mathcal{P}} Γ P P \mathcal{P} P
We emphasize that this grand coupling scheme serves purely as an analytical tool. Its purpose is to bring independent runs of the algorithms on two inputs into a shared probability space, for our privacy and utility analysis. By the nature of the coupling, the marginals exactly match the true target distributions (G1 in Definition 3.1 ). Consequently, all results derived within this joint probability space apply directly to the actual execution of the algorithms.
Private Synthetic Data Sampler
In this section, we apply the abstract grand coupling schemes developed in § 3 to construct a differentially private synthetic data sampler. Here, we set Y = X ℓ \mathcal{Y}=\mathcal{X}^{\ell} Y = X ℓ X \mathcal{X} X ℓ \ell ℓ F ⊆ Δ ( X ) \mathcal{F}\subseteq\Delta(\mathcal{X}) F ⊆ Δ ( X ) Q \mathcal{Q} Q P = { q ℓ : q ∈ F } \mathcal{P}=\{q^{\ell}:q\in\mathcal{F}\} P = { q ℓ : q ∈ F } Z ∈ X ℓ Z\in\mathcal{X}^{\ell} Z ∈ X ℓ ℓ \ell ℓ TV ( L ( Z ) , p ℓ ) ≤ β \operatorname{TV}(\mathcal{L}(Z),p^{\ell})\leq\beta TV ( L ( Z ) , p ℓ ) ≤ β S ∼ p n S\sim p^{n} S ∼ p n p ∈ Q p\in\mathcal{Q} p ∈ Q
Technical Intuition. At a high level, we partition the samples into disjoint blocks, run the non-private learner on each block, and use our grand coupling to generate correlated synthetic datasets from the resulting learner outputs.
For the utility analysis, we would like to show not only that the synthetic datasets Z 1 , … , Z k Z_1,\ldots,Z_k Z 1 , … , Z k p p p Z ∗ ∼ p ℓ Z^*\sim p^{\ell} Z ∗ ∼ p ℓ ( Z 1 , … , Z k , Z ∗ ) (Z_1,\ldots,Z_k,Z^*) ( Z 1 , … , Z k , Z ∗ ) Γ k + 1 ( ( q 1 ℓ , … , q k ℓ , p ℓ ) ; ⋅ ) \Gamma_{k+1}((q_1^{\ell},\ldots,q_k^{\ell},p^{\ell});\cdot) Γ k + 1 (( q 1 ℓ , … , q k ℓ , p ℓ ) ; ⋅ ) Γ P \Gamma_{\mathcal{P}} Γ P Proposition 3.3 . Note that the augmented vector is drawn from the same grand coupling, so adjoining this extra “ghost” coordinate does not change the joint law of the synthetic datasets produced by the algorithm, i.e., its marginal on the first k k k Γ k ( ( q 1 ℓ , … , q k ℓ ) ; ⋅ ) \Gamma_k((q_1^{\ell},\ldots,q_k^{\ell});\cdot) Γ k (( q 1 ℓ , … , q k ℓ ) ; ⋅ )
Moreover, by the disagreement bound, for every learn output q i q_i q i Pr [ Z i ≠ Z ∗ ] ≤ 2 TV ( q i ℓ , p ℓ ) ≤ 2 ℓ TV ( q i , p ) \Pr[Z_i\ne Z^*]\leq2\operatorname{TV}(q_i^{\ell},p^{\ell})\leq2\ell\operatorname{TV}(q_i,p) Pr [ Z i = Z ∗ ] ≤ 2 TV ( q i ℓ , p ℓ ) ≤ 2 ℓ TV ( q i , p ) Z ∗ Z^* Z ∗ Z ∗ Z^* Z ∗ Z ∗ Z^* Z ∗ Z ∗ Z^* Z ∗
For the privacy analysis, fix neighboring datasets S , S ′ S,S' S , S ′ q = ( q 1 , … , q k ) \mathbf{q}=(q_1,\ldots,q_k) q = ( q 1 , … , q k ) q ′ = ( q 1 ′ , … , q k ′ ) \mathbf{q}'=(q'_1,\ldots,q'_k) q ′ = ( q 1 ′ , … , q k ′ ) j j j ( Z P ) P ∈ P ∼ Γ P (Z_P)_{P\in\mathcal{P}}\sim\Gamma_{\mathcal{P}} ( Z P ) P ∈ P ∼ Γ P Z ~ i = Z q i ℓ \widetilde{Z}_i=Z_{q_i^{\ell}} Z i = Z q i ℓ Z ~ i ′ = Z ( q i ′ ) ℓ \widetilde{Z}'_i=Z_{(q'_i)^{\ell}} Z i ′ = Z ( q i ′ ) ℓ Couple k \operatorname{Couple}_k Couple k ( Z ~ 1 , … , Z ~ k ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k) ( Z 1 , … , Z k ) Γ k ( ( q 1 , … , q k ) ; ⋅ ) \Gamma_k((q_1,\ldots,q_k);\cdot) Γ k (( q 1 , … , q k ) ; ⋅ ) ( Z ~ 1 ′ , … , Z ~ k ′ ) (\widetilde{Z}'_1,\ldots,\widetilde{Z}'_k) ( Z 1 ′ , … , Z k ′ ) Γ k ( ( ( q 1 ′ ) ℓ , … , ( q k ′ ) ℓ ) ; ⋅ ) \Gamma_k(((q'_1)^{\ell},\ldots,(q'_k)^{\ell});\cdot) Γ k ((( q 1 ′ ) ℓ , … , ( q k ′ ) ℓ ) ; ⋅ ) i ≠ j i\ne j i = j q i = q i ′ q_i=q'_i q i = q i ′ Z ~ i = Z ~ i ′ \widetilde{Z}_i=\widetilde{Z}'_i Z i = Z i ′ 3
Thus, the two inputs to StabilityBasedMode are neighboring for every realization, so its privacy guarantee applies to each fixed coupling draw.
Road Map. We present the formal construction in two stages to isolate the coupling randomness from the statistical randomness of the dataset partition and base learners.
AGGREGATE (Algorithm 1): Operates on a fixed tuple q = ( q 1 , … , q k ) ∈ F k \mathbf{q}=(q_1,\ldots,q_k)\in\mathcal{F}^k q = ( q 1 , … , q k ) ∈ F k ( Z 1 , … , Z k ) (Z_1,\ldots,Z_k) ( Z 1 , … , Z k )
grand coupling, while its utility follows from the disagreement bound and the accuracy of the stability-based mode mechanism.
Sampler (Algorithm 2): Operates on raw datasets S ∈ X n S \in\mathcal{X}^n S ∈ X n S S S q \mathbf{q} q X n \mathcal{X}^n X n q \mathbf{q} q
We defer the detailed proofs and discussions in Appendix § 8 .
Tuple-Level Primitive: Aggregate
We first present Aggregate (Algorithm 1), a mechanism operating on a fixed tuple of candidate distributions q = ( q 1 , … , q k ) ∈ F k \mathbf{q}=(q_1,\ldots,q_k)\in\mathcal{F}^k q = ( q 1 , … , q k ) ∈ F k Z ∈ X ℓ Z\in\mathcal{X}^{\ell} Z ∈ X ℓ q , q ′ \mathbf{q},\mathbf{q}' q , q ′ q j q_j q j
Algorithm 1 Aggregate
Require: Distributions q 1 , … , q k ∈ F q_1,\ldots,q_k\in\mathcal{F} q 1 , … , q k ∈ F
Ensure: Synthetic dataset Z ∈ X ℓ Z\in\mathcal{X}^{\ell} Z ∈ X ℓ
Jointly sample ( Z 1 , … , Z k ) ← Couple k ( q 1 ℓ , … , q k ℓ ) (Z_1,\ldots,Z_k)\leftarrow\operatorname{Couple}_k(q_1^{\ell},\ldots,q_k^{\ell}) ( Z 1 , … , Z k ) ← Couple k ( q 1 ℓ , … , q k ℓ ) Couple k \operatorname{Couple}_k Couple k P = { q ℓ : q ∈ F } \mathcal{P}=\{q^{\ell}:q\in\mathcal{F}\} P = { q ℓ : q ∈ F }
Z = StabilityBasedMode ( Z 1 , … , Z k ) Z=\operatorname{StabilityBasedMode}(Z_1,\ldots,Z_k) Z = StabilityBasedMode ( Z 1 , … , Z k )
return Z Z Z
By instantiating Couple k \operatorname{Couple}_k Couple k Γ P \Gamma_{\mathcal{P}} Γ P 4 ( Z 1 , … , Z k ) (Z_1,\ldots,Z_k) ( Z 1 , … , Z k ) q \mathbf{q} q Z i ∼ q i ℓ Z_i\sim q_i^{\ell} Z i ∼ q i ℓ Pr [ Z i ≠ Z j ] ≤ 2 TV ( q i ℓ , q j ℓ ) \Pr[Z_i\ne Z_j]\le2\operatorname{TV}(q_i^{\ell},q_j^{\ell}) Pr [ Z i = Z j ] ≤ 2 TV ( q i ℓ , q j ℓ ) i ≠ j i\ne j i = j q i q_i q i p p p p ℓ p^{\ell} p ℓ
Theorem 4.1 (Informal version of Corollary B.4). For every ε > 0 \varepsilon>0 ε > 0 δ , β ∈ ( 0 , 1 ) \delta,\beta\in(0,1) δ , β ∈ ( 0 , 1 ) ℓ ∈ N + \ell\in\mathbb{N}^{+} ℓ ∈ N + k = Ω ( log ( 4 / β ) + log ( 1 / δ ) ε 2 ) k=\Omega\left(\frac{\log(4/\beta)+\log(1/\delta)}{\varepsilon^2}\right) k = Ω ( ε 2 l o g ( 4/ β ) + l o g ( 1/ δ ) ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) 5 p ∈ Q p\in\mathcal{Q} p ∈ Q q ∈ F k \mathbf{q}\in\mathcal{F}^k q ∈ F k 7 / 8 7/8 7/8 O ( β / ℓ ) O(\beta/\ell) O ( β / ℓ ) p p p β / 2 \beta/2 β /2 p ℓ p^{\ell} p ℓ
Proof Sketch. Privacy: Since the joint law of Couple k ( q ) \operatorname{Couple}_k(\mathbf{q}) Couple k ( q ) Γ P \Gamma_{\mathcal{P}} Γ P 6 q \mathbf{q} q q ′ \mathbf{q}' q ′ ( Z P ) P ∈ P ∼ Γ P (Z_P)_{P\in\mathcal{P}}\sim\Gamma_{\mathcal{P}} ( Z P ) P ∈ P ∼ Γ P Z ~ i = Z q i ℓ \widetilde{Z}_i=Z_{q_i^{\ell}} Z i = Z q i ℓ q \mathbf{q} q Z ~ i ′ = Z ( q i ′ ) ℓ \widetilde{Z}'_i=Z_{(q'_i)^{\ell}} Z i ′ = Z ( q i ′ ) ℓ q ′ \mathbf{q}' q ′ i ≠ j i\ne j i = j q i = q i ′ q_i = q_i' q i = q i ′ Z q i ℓ = Z ( q i ′ ) ℓ Z_{q_i}^{\ell} = Z_{(q_i')^{\ell}} Z q i ℓ = Z ( q i ′ ) ℓ ( Z ~ 1 , … , Z ~ k ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k) ( Z 1 , … , Z k ) ( Z ~ 1 ′ , … , Z ~ k ′ ) (\widetilde{Z}'_1,\ldots,\widetilde{Z}'_k) ( Z 1 ′ , … , Z k ′ ) j j j Γ P \Gamma_{\mathcal{P}} Γ P Γ P \Gamma_{\mathcal{P}} Γ P Γ P \Gamma_{\mathcal{P}} Γ P
Utility: As in the privacy analysis, the utility guarantee relies on constructing an analysis coupling from the grand coupling scheme Γ P \Gamma_{\mathcal{P}} Γ P q = ( q 1 , … , q k ) ∈ F k \mathbf{q}=(q_1,\ldots,q_k)\in\mathcal{F}^k q = ( q 1 , … , q k ) ∈ F k p ∈ F p\in\mathcal{F} p ∈ F ( Z P ) P ∈ P ∼ Γ P (Z_P)_{P\in\mathcal{P}}\sim\Gamma_{\mathcal{P}} ( Z P ) P ∈ P ∼ Γ P Z ~ i = Z q i ℓ \widetilde{Z}_i=Z_{q_i}^{\ell} Z i = Z q i ℓ i ∈ [ k ] i\in[k] i ∈ [ k ] Z ~ ∗ = Z p ℓ \widetilde{Z}_*=Z_{p^\ell} Z ∗ = Z p ℓ p ℓ ∈ P p^\ell\in\mathcal{P} p ℓ ∈ P L ( C o u p l e k ( q ) ) \mathcal{L}(\mathrm{Couple}_k(\mathbf{q})) L ( Couple k ( q )) L ( C o u p l e 1 ( p ) ) \mathcal{L}(\mathrm{Couple}_1(p)) L ( Couple 1 ( p )) Γ P \Gamma_{\mathcal{P}} Γ P Γ P \Gamma_{\mathcal{P}} Γ P ( Z ~ 1 , … , Z ~ k ) ∼ L ( C o u p l e k ( q ) ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k)\sim\mathcal{L}(\mathrm{Couple}_k(\mathbf{q})) ( Z 1 , … , Z k ) ∼ L ( Couple k ( q )) Z ~ ∗ ∼ L ( C o u p l e 1 ( p ) ) = p ℓ \widetilde{Z}_*\sim\mathcal{L}(\mathrm{Couple}_1(p))=p^\ell Z ∗ ∼ L ( Couple 1 ( p )) = p ℓ Definition 3.1 .
For every accurate input distribution where TV ( q i , p ) ≤ η \operatorname{TV}(q_i,p)\leq\eta TV ( q i , p ) ≤ η Pr [ Z ~ i ≠ Z ~ ∗ ] ≤ 2 TV ( q i ℓ , p ℓ ) ≤ 2 ℓ η \Pr[\widetilde{Z}_i\ne\widetilde{Z}_*]\leq2\operatorname{TV}(q_i^\ell,p^\ell)\leq2\ell\eta Pr [ Z i = Z ∗ ] ≤ 2 TV ( q i ℓ , p ℓ ) ≤ 2 ℓ η 7 / 8 7/8 7/8 q i q_i q i η \eta η p p p Z ~ i \widetilde{Z}_i Z i Z ~ ∗ ∼ p ℓ \widetilde{Z}_*\sim p^\ell Z ∗ ∼ p ℓ [46 Vad17] to output Z ~ ∗ \widetilde{Z}_* Z ∗ ≥ 1 − δ 0 \geq1-\delta_0 ≥ 1 − δ 0
We emphasize that neither Z ~ ∗ \widetilde{Z}_* Z ∗ Z ~ i ′ \widetilde{Z}'_i Z i ′ Proposition B.2 , Proposition B.1 , and Corollary B.4 .
Algorithm 2 Sampler
Require: Dataset S = ( X 1 , … , X n ) S=(X_1,\ldots,X_n) S = ( X 1 , … , X n ) n = b k n=bk n = bk k k k
Ensure: Synthetic samples Z ∈ X ℓ Z\in\mathcal{X}^{\ell} Z ∈ X ℓ
Let a random seed (a data-independent permutation) be Π ∼ U ( S n ) \Pi\sim U(S_n) Π ∼ U ( S n )
Partition S S S k k k S 1 , … , S k ∈ X b S_1,\ldots,S_k\in\mathcal{X}^b S 1 , … , S k ∈ X b S i ← ( X Π ( ( i − 1 ) b + 1 ) , … , X Π ( i b ) ) S_i\leftarrow(X_{\Pi((i-1)b+1)},\ldots,X_{\Pi(ib)}) S i ← ( X Π (( i − 1 ) b + 1 ) , … , X Π ( ib ) )
Let learners’ random seeds (data- and permutation-independent) be U 1 , … , U k ∼ i . i . d . U ( [ 0 , 1 ] ) U_1,\ldots,U_k \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} U([0,1]) U 1 , … , U k ∼ i.i.d. U ([ 0 , 1 ])
For each i ∈ [ k ] i\in[k] i ∈ [ k ] q i ← L ( S i ; U i ) q_i\leftarrow L(S_i;U_i) q i ← L ( S i ; U i )
Z ← Aggregate ( q 1 , … , q k ) Z\leftarrow\operatorname{Aggregate}(q_1,\ldots,q_k) Z ← Aggregate ( q 1 , … , q k )
return Z ∈ X ℓ Z\in\mathcal{X}^{\ell} Z ∈ X ℓ
End-to-End Private Correlated Sampler: Sampler
In the preceding subsection, we established the privacy and utility guarantees of Aggregate conditioned on a fixed tuple of candidate distributions q = ( q 1 , … , q k ) \mathbf{q}=(q_1,\ldots,q_k) q = ( q 1 , … , q k ) S = ( X 1 , … , X n ) ∈ X n S=(X_1,\ldots,X_n)\in\mathcal{X}^n S = ( X 1 , … , X n ) ∈ X n S S S q \mathbf{q} q S , S ′ ∈ X n S,S'\in\mathcal{X}^n S , S ′ ∈ X n
While much of the analysis relies on standard techniques, the primary technical step lies in explicitly controlling the sources of randomness to bridge Aggregate and Sampler, ensuring that the resulting random tuple satisfies the conditions required by Aggregate.
Theorem 4.3 (Informal version of Corollary B.7). Fix a base learner L L L Q Q Q ε , δ , β ∈ ( 0 , 1 ) \varepsilon,\delta,\beta\in(0,1) ε , δ , β ∈ ( 0 , 1 ) ℓ ∈ N + \ell\in\mathbb{N}^{+} ℓ ∈ N + b b b p ∈ Q p\in Q p ∈ Q L L L TV ( L ( S i ) , p ) ≤ O ( β / ℓ ) \operatorname{TV}(L(S_i),p)\le O(\beta/\ell) TV ( L ( S i ) , p ) ≤ O ( β / ℓ ) 15 / 16 15/16 15/16 S i ∼ p b S_i\sim p^b S i ∼ p b ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Moreover, for every p ∈ Q p\in Q p ∈ Q S ∼ p n S\sim p^n S ∼ p n n = Ω ( b log ( 4 / δ β ) ε ) n=\Omega\left(\frac{b\log(4/\delta\beta)}{\varepsilon}\right) n = Ω ( ε b l o g ( 4/ δ β ) ) Z ∈ X ℓ Z\in\mathcal{X}^{\ell} Z ∈ X ℓ TV ( L ( Z ) , p ℓ ) ≤ 3 β / 4 \operatorname{TV}(L(Z),p^{\ell})\le3\beta/4 TV ( L ( Z ) , p ℓ ) ≤ 3 β /4 ( ℓ , 3 β / 4 ) (\ell,3\beta/4) ( ℓ , 3 β /4 ) Q Q Q Definition 1.4 .
Proof Sketch. Privacy: Fix adjacent datasets S , S ′ ∈ X n S,S'\in\mathcal{X}^n S , S ′ ∈ X n j j j Π \Pi Π a a a S i S_i S i i ≠ a i\ne a i = a U 1 , … , U k U_1,\ldots,U_k U 1 , … , U k S S S q = L ( S ) \mathbf{q}=L(S) q = L ( S ) q ′ = L ( S ′ ) \mathbf{q}'=L(S') q ′ = L ( S ′ ) a a a Theorem 4.1 , directly lifts to dataset-level ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Utility: Define indicator variables I i = 1 { TV ( q i , p ) ≤ η } I_i=1\{\operatorname{TV}(q_i,p)\le\eta\} I i = 1 { TV ( q i , p ) ≤ η } η = O ( β / ℓ ) \eta=O(\beta/\ell) η = O ( β / ℓ ) S ∼ p n S\sim p^n S ∼ p n S i S_i S i p b p^b p b I 1 , … , I k I_1,\ldots,I_k I 1 , … , I k E [ I i ] ≥ 15 / 16 \mathbb{E}[I_i]\ge15/16 E [ I i ] ≥ 15/16 k = O ( log ( 1 / β ) ) k=O(\log(1/\beta)) k = O ( log ( 1/ β )) ∑ i = 1 k I i ≥ 7 8 k \sum_{i=1}^k I_i\ge\frac{7}{8}k ∑ i = 1 k I i ≥ 8 7 k 1 − β / 4 1-\beta/4 1 − β /4 = { ∣ { i : TV ( q i , p ) ≤ η } ∣ ≥ 7 8 k } =\{|\{i:\operatorname{TV}(q_i,p)\le\eta\}|\ge\frac{7}{8}k\} = { ∣ { i : TV ( q i , p ) ≤ η } ∣ ≥ 8 7 k } Theorem 4.1 guarantees that the output distribution L ( Z ∣ good event ) \mathcal{L}(Z\mid\text{good event}) L ( Z ∣ good event ) TV ( L ( Z ∣ good event ) , p ℓ ) ≤ β / 2 \operatorname{TV}(\mathcal{L}(Z\mid\text{good event}),p^{\ell})\le\beta/2 TV ( L ( Z ∣ good event ) , p ℓ ) ≤ β /2 TV ( L ( Z ) , p ℓ ) ≤ β / 2 + β / 4 = 3 4 β \operatorname{TV}(\mathcal{L}(Z),p^{\ell})\le\beta/2+\beta/4=\frac{3}{4}\beta TV ( L ( Z ) , p ℓ ) ≤ β /2 + β /4 = 4 3 β
Full technical details appear in Proposition B.5 and Proposition B.6 .
Remark 4.4. Since private and non-private PAC-learnability are known to not be equivalent [19 , 8 ] , it is instructive to understand where the present approach fails in supervised settings.
Algorithm 3 BlackBoxPrivateLearner
Require: Dataset S = ( X 1 , … , X n ) S=(X_1,\ldots,X_n) S = ( X 1 , … , X n ) Ensure: A distribution q ^ ∈ Δ ( X ) \hat{q}\in\Delta(\mathcal{X}) q ^ ∈ Δ ( X )
Z ← Sampler ( S ) Z\leftarrow\operatorname{Sampler}(S) Z ← Sampler ( S )
Pick a learner’s random seed (data-independent) V ∼ U ( [ 0 , 1 ] ) V\sim U([0,1]) V ∼ U ([ 0 , 1 ]) q ^ ← L ( Z ; V ) \hat{q}\leftarrow L(Z;V) q ^ ← L ( Z ; V )
return q ^ \hat{q} q ^
This becomes clear by looking at Algorithm 2. The algorithm crucially relies on the fact that a distribution learning algorithm outputs a density that is close to the ground truth in TV-distance. However, in supervised settings, the input consists of domain elements and their labels, while the learner outputs a function attempting to capture the rule that associates the former to the latter. This does not capture the distribution of the unlabeled examples, and therefore cannot be used as the basis for a sampler.
Main algorithm and reduction
We now present our main application, a black-box reduction that transforms any non-private base learner L L L m ( α , β ) m(\alpha,\beta) m ( α , β ) L L L α \alpha α 1 − β 1-\beta 1 − β
The algorithm is conceptually simple, where we first invoke Sampler to generate a private synthetic dataset Z ∈ X ℓ Z\in\mathcal{X}^{\ell} Z ∈ X ℓ L L L Z Z Z V V V
The complete procedure is described in Algorithm 3.
The results follows immediately from the guarantees of Sampler. Privacy follows by post-processing, and utility follows by coupling its output to an i.i.d. sample from p ℓ p^{\ell} p ℓ
Theorem 5.1 (Main Reduction). Let α , β , δ , ε ∈ ( 0 , 1 ) \alpha,\beta,\delta,\varepsilon\in(0,1) α , β , δ , ε ∈ ( 0 , 1 ) L L L Q \mathcal{Q} Q m ( α , β ) m(\alpha,\beta) m ( α , β ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
n = O ( m ( β 64 m ( α , β 4 ) , 1 16 ) 1 ε log ( 4 β δ ) ) n=O\left(m\left(\frac{\beta}{64m\left(\alpha,\frac{\beta}{4}\right)},\frac{1}{16}\right)\frac{1}{\varepsilon}\log\left(\frac{4}{\beta\delta}\right)\right) n = O m 64 m ( α , 4 β ) β , 16 1 ε 1 log ( β δ 4 ) such that, for every p ∈ Q p\in\mathcal{Q} p ∈ Q S ∼ p n S\sim p^n S ∼ p n q ^ \hat{q} q ^ TV ( q ^ , p ) < α \operatorname{TV}(\hat{q},p)<\alpha TV ( q ^ , p ) < α 1 − β 1-\beta 1 − β
Proof. Set ℓ = m ( α , β 4 ) \ell=m\left(\alpha,\frac{\beta}{4}\right) ℓ = m ( α , 4 β ) η = β 64 ℓ \eta=\frac{\beta}{64\ell} η = 64 ℓ β b = m ( η , 1 16 ) b=m\left(\eta,\frac{1}{16}\right) b = m ( η , 16 1 ) δ 0 = min { δ , β 4 } \delta_0=\min\left\{\delta,\frac{\beta}{4}\right\} δ 0 = min { δ , 4 β } Proposition B.5 , Sampler is ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) L L L Proposition 2.4 ). Since δ 0 ≤ δ \delta_0\le\delta δ 0 ≤ δ ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
For utility, take k = ⌈ max { 8 ε log ( 4 β δ ) , 128 log ( 4 β ) } ⌉ k=\left\lceil\max\left\{\frac{8}{\varepsilon}\log\left(\frac{4}{\beta\delta}\right),128\log\left(\frac{4}{\beta}\right)\right\}\right\rceil k = ⌈ max { ε 8 log ( β δ 4 ) , 128 log ( β 4 ) } ⌉ n = b k n=bk n = bk p ∈ Q p\in\mathcal{Q} p ∈ Q S ∼ p n S\sim p^n S ∼ p n Z Z Z TV ( L ( Z ) , p ℓ ) ≤ 3 β 4 \operatorname{TV}(L(Z),p^{\ell})\le\frac{3\beta}{4} TV ( L ( Z ) , p ℓ ) ≤ 4 3 β ℓ \ell ℓ α \alpha α p ℓ p^{\ell} p ℓ β 4 \frac{\beta}{4} 4 β Pr [ TV ( q ^ , p ) ≥ α ] ≤ β 4 + 3 β 4 = β \Pr[\operatorname{TV}(\hat{q},p)\ge\alpha]\le\frac{\beta}{4}+\frac{3\beta}{4}=\beta Pr [ TV ( q ^ , p ) ≥ α ] ≤ 4 β + 4 3 β = β
Finally, substituting the value of b b b k = O ( 1 ε log ( 4 β δ ) ) k = O\left(\frac{1}{\varepsilon}\log\left(\frac{4}{\beta\delta}\right)\right) k = O ( ε 1 log ( β δ 4 ) ) n = b k n = bk n = bk
A Boosted Private Learner
In the previous section, the PrivateLearner requires the block-level target TV error to satisfy η ≲ β / ℓ \eta\lesssim\beta/\ell η ≲ β / ℓ m ( α , β ) = poly ( 1 / α , log ( 1 / β ) ) m(\alpha,\beta) = \operatorname{poly}(1/\alpha,\log(1/\beta)) m ( α , β ) = poly ( 1/ α , log ( 1/ β )) η ∝ β \eta\propto\beta η ∝ β 1 / β Ω ( 1 ) 1/\beta^{\Omega(1)} 1/ β Ω ( 1 ) n n n O ( log ( 1 / β ) ) O(\log(1/\beta)) O ( log ( 1/ β ))
The core idea is confidence boosting: amplifying a learner’s constant success probability to 1 − β 1-\beta 1 − β T = O ( log ( 1 / β ) ) T = O(\log(1/\beta)) T = O ( log ( 1/ β )) S 1 , … , S T S_1,\ldots,S_T S 1 , … , S T 1 − β 0 1-\beta_0 1 − β 0 β 0 = 1 / 8 \beta_0 = 1/8 β 0 = 1/8 p ^ 1 , … , p ^ T \hat{p}_1,\ldots,\hat{p}_T p ^ 1 , … , p ^ T η ∼ 1 / ℓ \eta\sim1/\ell η ∼ 1/ ℓ β \beta β t ∈ [ T ] t \in[T] t ∈ [ T ] N t = ∣ { i ∈ [ T ] : TV ( p ^ i , p ^ t ) ≤ 2 α 0 } ∣ N_t = |\{i \in[T] : \operatorname{TV}(\hat{p}_i,\hat{p}_t) \le2\alpha_0\}| N t = ∣ { i ∈ [ T ] : TV ( p ^ i , p ^ t ) ≤ 2 α 0 } ∣ 2 α 0 2\alpha_0 2 α 0 p ^ t \hat{p}_t p ^ t α 0 = α / 3 \alpha_0 = \alpha/3 α 0 = α /3 j j j N j N_j N j p ^ j \hat{p}_j p ^ j
By doing so, if more than half of the estimates are α 0 \alpha_0 α 0 p p p 2 α 0 2\alpha_0 2 α 0 N t > T / 2 N_t > T/2 N t > T /2 N j > T / 2 N_j > T/2 N j > T /2 N j N_j N j α 0 \alpha_0 α 0 p p p TV ( p ^ j , p ) ≤ 2 α 0 + α 0 = α \operatorname{TV}(\hat{p}_j,p) \le2\alpha_0+\alpha_0 = \alpha TV ( p ^ j , p ) ≤ 2 α 0 + α 0 = α β 0 \beta_0 β 0 T T T
Theorem 6.1 (Boosted Private Learner). Let α , β , ε , δ ∈ ( 0 , 1 ) \alpha,\beta,\varepsilon,\delta\in(0,1) α , β , ε , δ ∈ ( 0 , 1 ) L L L Q \mathcal{Q} Q m ( α , β ) m(\alpha,\beta) m ( α , β ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
n = O ( m ( 1 512 m ( α / 3 , 1 / 32 ) , 1 16 ) 1 ε log ( 4 δ ) log ( 4 β ) ) n = O\left(m\left(\frac{1}{512m(\alpha/3,1/32)},\frac{1}{16}\right)\frac{1}{\varepsilon}\log\left(\frac{4}{\delta}\right)\log\left(\frac{4}{\beta}\right)\right) n = O ( m ( 512 m ( α /3 , 1/32 ) 1 , 16 1 ) ε 1 log ( δ 4 ) log ( β 4 ) ) such that, for every p ∈ Q p \in\mathcal{Q} p ∈ Q S ∼ p n S \sim p^n S ∼ p n q ^ \hat{q} q ^ TV ( q ^ , p ) < α \operatorname{TV}(\hat{q}, p) < \alpha TV ( q ^ , p ) < α 1 − β 1-\beta 1 − β m ( α , β ) = poly ( 1 α , log ( 1 β ) ) m(\alpha,\beta)=\operatorname{poly}\left(\frac{1}{\alpha},\log\left(\frac{1}{\beta}\right)\right) m ( α , β ) = poly ( α 1 , log ( β 1 ) ) n = poly ( 1 α , log ( 1 β ) , 1 ε , log ( 1 δ ) ) n=\operatorname{poly}\left(\frac{1}{\alpha},\log\left(\frac{1}{\beta}\right),\frac{1}{\varepsilon},\log\left(\frac{1}{\delta}\right)\right) n = poly ( α 1 , log ( β 1 ) , ε 1 , log ( δ 1 ) )
Note that the DP guarantee is non-trivial only when δ = o ( 1 / n ) \delta=o(1/n) δ = o ( 1/ n ) δ = Ω ( 1 / n ) \delta=\Omega(1/n) δ = Ω ( 1/ n ) [42 ] . Our sample complexity bound is meaningful in this regime because of its dependence on δ \delta δ log ( 1 / δ ) \log(1/\delta) log ( 1/ δ ) n ( δ ) = C log ( 4 / δ ) n(\delta)=C\log(4/\delta) n ( δ ) = C log ( 4/ δ ) C C C δ \delta δ δ ⋅ n ( δ ) = C δ log ( 4 / δ ) → 0 \delta\cdot n(\delta)=C\delta\log(4/\delta)\to0 δ ⋅ n ( δ ) = C δ log ( 4/ δ ) → 0 δ → 0 \delta\to0 δ → 0 δ = o ( 1 / n ) \delta=o(1/n) δ = o ( 1/ n ) n ( δ ) = C / δ n(\delta)=C/\delta n ( δ ) = C / δ δ ⋅ n ( δ ) = C \delta\cdot n(\delta)=C δ ⋅ n ( δ ) = C δ = Θ ( 1 / n ) \delta=\Theta(1/n) δ = Θ ( 1/ n )
Acknowledgements
We thank David Woodruff for discussions and assistance with the internal version of Gemini used. We also thank Matthew Joseph and Chris Liaw for their comments on a preliminary draft of this paper.
Poisson Coupling Details
We present two constructions of the grand coupling interface in Definition 3.1 , both based on the Poisson coupling of [10 ] . Subsection A.1 treats families P ⊆ Δ ( Y ) \mathcal{P} \subseteq\Delta(\mathcal{Y}) P ⊆ Δ ( Y ) σ \sigma σ Corollary A.3 establishes a grand coupling scheme on P \mathcal{P} P Y \mathcal{Y} Y Δ ( Y ) \Delta(\mathcal{Y}) Δ ( Y ) P ⊆ Δ ( Y ) \mathcal{P} \subseteq\Delta(\mathcal{Y}) P ⊆ Δ ( Y ) P \mathcal{P} P
A Globally Dominated Poisson Coupling
We first formalize the setting where all distributions in the family are dominated by a single reference measure. Let ( Y , B ) (\mathcal{Y},\mathcal{B}) ( Y , B ) P ⊆ Δ ( Y ) \mathcal{P} \subseteq\Delta(\mathcal{Y}) P ⊆ Δ ( Y ) [10 ] .
Construction A.1. Suppose there exists a σ \sigma σ ν \nu ν P ≪ ν P \ll\nu P ≪ ν P ∈ P P \in\mathcal{P} P ∈ P f P = d P d ν f_P = \frac{dP}{d\nu} f P = d ν d P P ∈ P P \in\mathcal{P} P ∈ P
Let A \mathcal{A} A Y × R + × R + \mathcal{Y} \times\mathbb{R}_{+} \times\mathbb{R}_{+} Y × R + × R + ν ( d y ) d s d t \nu(dy)dsdt ν ( d y ) d s d t Definition 2.2 ). For a realization a a a A \mathcal{A} A a P = { ( y , s , t ) ∈ a : s ≤ f P ( y ) } a_P = \{(y,s,t) \in a : s \le f_P(y)\} a P = {( y , s , t ) ∈ a : s ≤ f P ( y )} P ∈ P P \in\mathcal{P} P ∈ P Φ ( P , a ) \Phi(P,a) Φ ( P , a ) y y y a P a_P a P t t t ( y ∗ , s ∗ , t ∗ ) (y^*,s^*,t^*) ( y ∗ , s ∗ , t ∗ ) t ∗ = min { t : ( y , s , t ) ∈ a , s ≤ f P ( y ) } t^* = \min\{t : (y,s,t) \in a, s \le f_P(y)\} t ∗ = min { t : ( y , s , t ) ∈ a , s ≤ f P ( y )} Φ ( P , a ) = y ∗ \Phi(P,a) = y^* Φ ( P , a ) = y ∗ Φ ( P , a ) \Phi(P,a) Φ ( P , a ) 7
Using the same random process A \mathcal{A} A P ∈ P P \in\mathcal{P} P ∈ P Z P = Φ ( P , A ) Z_P = \Phi(P,\mathcal{A}) Z P = Φ ( P , A ) Γ = L ( ( Z P ) P ∈ P ) \Gamma= \mathcal{L}((Z_P)_{P \in\mathcal{P}}) Γ = L (( Z P ) P ∈ P )
Algorithm 5 Couple I from construction A.1
Input: Distributions q 1 , … , q k ∈ F q_1,\ldots,q_k \in\mathcal{F} q 1 , … , q k ∈ F σ \sigma σ ν \nu ν X ℓ \mathcal{X}^{\ell} X ℓ q ℓ ∈ { q ℓ : q ∈ F } q^{\ell} \in\{q^{\ell}:q \in\mathcal{F}\} q ℓ ∈ { q ℓ : q ∈ F }
Output: Synthetic samples ( Z 1 , … , Z k ) (Z_1,\ldots,Z_k) ( Z 1 , … , Z k ) Z i ∼ q i ℓ Z_i \sim q_i^{\ell} Z i ∼ q i ℓ Pr [ Z i ≠ Z j ] ≤ 2 TV ( q i ℓ , q j ℓ ) \Pr[Z_i \ne Z_j] \le2\operatorname{TV}(q_i^{\ell},q_j^{\ell}) Pr [ Z i = Z j ] ≤ 2 TV ( q i ℓ , q j ℓ ) i , j ∈ [ k ] i,j \in[k] i , j ∈ [ k ]
Let a random seed be A \mathcal{A} A ν ( d y ) d s d t \nu(dy)dsdt ν ( d y ) d s d t
Z i = Φ ( q i ℓ , A ) Z_i = \Phi(q_i^{\ell},\mathcal{A}) Z i = Φ ( q i ℓ , A ) i ∈ [ k ] i \in[k] i ∈ [ k ] ▹ \triangleright ▹ Conditional on a realization A = a \mathcal{A}=a A = a z i = Φ ( q i ℓ , a ) z_i=\Phi(q_i^{\ell},a) z i = Φ ( q i ℓ , a )
return ( Z 1 , … , Z k ) (Z_1,\ldots,Z_k) ( Z 1 , … , Z k ) ▹ \triangleright ▹ Equivalently, ( Z 1 , … , Z k ) (Z_1,\ldots,Z_k) ( Z 1 , … , Z k ) ( q 1 ℓ , … , q k ℓ ) (q_1^{\ell},\ldots,q_k^{\ell}) ( q 1 ℓ , … , q k ℓ ) Γ \Gamma Γ
Theorem A.2 (Proposition 5 and Theorem 2 in [10 ] ). Suppose Y \mathcal{Y} Y σ \sigma σ ν \nu ν P ≪ ν P \ll\nu P ≪ ν P ∈ P P \in\mathcal{P} P ∈ P Γ \Gamma Γ ( P ) P ∈ P (P)_{P \in\mathcal{P}} ( P ) P ∈ P Z P ∼ P Z_P \sim P Z P ∼ P P ∈ P P \in\mathcal{P} P ∈ P P , Q ∈ P P,Q \in\mathcal{P} P , Q ∈ P
Pr [ Z P ≠ Z Q ] ≤ 2 TV ( P , Q ) 1 + TV ( P , Q ) ≤ 2 TV ( P , Q ) \Pr[Z_P \ne Z_Q] \le\frac{2\operatorname{TV}(P,Q)}{1+\operatorname{TV}(P,Q)} \le2\operatorname{TV}(P,Q) Pr [ Z P = Z Q ] ≤ 1 + TV ( P , Q ) 2 TV ( P , Q ) ≤ 2 TV ( P , Q ) Theorem A.2 establishes the core marginal and agreement guarantees for the coupling construction. However, to formally show that it constitutes a grand coupling scheme on P \mathcal{P} P
Corollary A.3 (Grand coupling scheme Γ P \Gamma_{\mathcal{P}} Γ P Suppose Y \mathcal{Y} Y σ \sigma σ ν \nu ν P ≪ ν P \ll\nu P ≪ ν P ∈ P P \in\mathcal{P} P ∈ P ( Z P ) P ∈ P (Z_P)_{P \in\mathcal{P}} ( Z P ) P ∈ P Γ P \Gamma_{\mathcal{P}} Γ P P \mathcal{P} P
Proof. G1 and G2 follow immediately from Theorem A.2. It suffices to show G3 that the map P ↦ L ( Z P 1 , … , Z P k ) \mathbf{P} \mapsto\mathcal{L}(Z_{P_1},\ldots,Z_{P_k}) P ↦ L ( Z P 1 , … , Z P k ) P = ( P 1 , … , P k ) \mathbf{P}=(P_1,\ldots,P_k) P = ( P 1 , … , P k ) P i ∈ P P_i \in\mathcal{P} P i ∈ P
Since Y \mathcal{Y} Y P ≪ ν P \ll\nu P ≪ ν P ∈ P P \in\mathcal{P} P ∈ P ( P , y ) (P,y) ( P , y ) f ( P i , y ) = d P i d ν ( y ) f(P_i,y)=\frac{dP_i}{d\nu}(y) f ( P i , y ) = d ν d P i ( y ) A \mathcal{A} A Y × R + × R + \mathcal{Y} \times\mathbb{R}_{+} \times\mathbb{R}_{+} Y × R + × R + ν ( d y ) d s d t \nu(dy)dsdt ν ( d y ) d s d t i ∈ [ k ] i \in[k] i ∈ [ k ] A i = { ( y , s , t ) ∈ A : s ≤ f ( P i , y ) } \mathcal{A}_i=\{(y,s,t)\in\mathcal{A}:s\leq f(P_i,y)\} A i = {( y , s , t ) ∈ A : s ≤ f ( P i , y )} Z i Z_i Z i Z i = y Z_i=y Z i = y ( y , s , t ) (y,s,t) ( y , s , t ) A i \mathcal{A}_i A i t t t A i \mathcal{A}_i A i Z i = Φ ( P i , A ) Z_i=\Phi(P_i,\mathcal{A}) Z i = Φ ( P i , A ) Φ \Phi Φ
Now define Φ ( P , A ) = ( Φ ( P 1 , A ) , … , Φ ( P k , A ) ) \Phi(\mathbf{P},\mathcal{A})=(\Phi(P_1,\mathcal{A}),\ldots,\Phi(P_k,\mathcal{A})) Φ ( P , A ) = ( Φ ( P 1 , A ) , … , Φ ( P k , A )) B ⊆ Y k B\subseteq\mathcal{Y}^k B ⊆ Y k Γ k ( P ; B ) = Pr A [ Φ ( P , A ) ∈ B ] \Gamma_k(\mathbf{P};B)=\Pr_{\mathcal{A}}[\Phi(\mathbf{P},\mathcal{A})\in B] Γ k ( P ; B ) = Pr A [ Φ ( P , A ) ∈ B ] Γ k ( P ; ⋅ ) = L ( Φ ( P , A ) ) \Gamma_k(\mathbf{P};\cdot)=\mathcal{L}(\Phi(\mathbf{P},\mathcal{A})) Γ k ( P ; ⋅ ) = L ( Φ ( P , A )) f ( P i , y ) f(P_i,y) f ( P i , y ) 1 { s ≤ f ( P i , y ) } \mathbb{1}\{s\leq f(P_i,y)\} 1 { s ≤ f ( P i , y )} t t t ( P , a ) ↦ Φ ( P , a ) (\mathbf{P},a)\mapsto\Phi(\mathbf{P},a) ( P , a ) ↦ Φ ( P , a ) P ↦ Γ k ( P ; B ) \mathbf{P}\mapsto\Gamma_k(\mathbf{P};B) P ↦ Γ k ( P ; B ) B ⊆ Y k B\subseteq\mathcal{Y}^k B ⊆ Y k Γ k \Gamma_k Γ k
Thus, the joint law of ( Z P ) P ∈ P (Z_P)_{P\in\mathcal{P}} ( Z P ) P ∈ P Γ P \Gamma_{\mathcal{P}} Γ P Y \mathcal{Y} Y
Projectively Consistent Poisson Couplings on Standard Borel Spaces
The preceding construction requires a single σ \sigma σ σ \sigma σ P ⊆ Δ ( Y ) \mathcal{P}\subseteq\Delta(\mathcal{Y}) P ⊆ Δ ( Y ) σ \sigma σ P \mathcal{P} P P = ( P 1 , … , P k ) ∈ Δ ( Y ) k \mathbf{P}=(P_1,\ldots,P_k)\in\Delta(\mathcal{Y})^k P = ( P 1 , … , P k ) ∈ Δ ( Y ) k ν P = ∑ i P i \nu_{\mathbf{P}}=\sum_i P_i ν P = ∑ i P i ν P \nu_{\mathbf{P}} ν P
Construction A.4. Fix k ≥ 1 k\geq1 k ≥ 1 P = ( P 1 , … , P k ) ∈ Δ ( Y ) k \mathbf{P}=(P_1,\ldots,P_k)\in\Delta(\mathcal{Y})^k P = ( P 1 , … , P k ) ∈ Δ ( Y ) k P \mathbf{P} P ν P = ∑ i P i \nu_{\mathbf{P}}=\sum_i P_i ν P = ∑ i P i f i P = d P i d ν P f_i^{\mathbf{P}}=\frac{dP_i}{d\nu_{\mathbf{P}}} f i P = d ν P d P i A P \mathcal{A}_{\mathbf{P}} A P Y × R + × R + \mathcal{Y}\times\mathbb{R}_{+}\times\mathbb{R}_{+} Y × R + × R + ν P ( d y ) d s d t \nu_{\mathbf{P}}(dy)dsdt ν P ( d y ) d s d t Definition 2.2 ). Unlike Construction A.1, the law of A P \mathcal{A}_{\mathbf{P}} A P P \mathbf{P} P
*For a realization a P \mathbf{a}_{\mathbf{P}} a P A P \mathcal{A}_{\mathbf{P}} A P Φ i ( P , a P ) \Phi_i(\mathbf{P},\mathbf{a}_{\mathbf{P}}) Φ i ( P , a P ) y y y a P , i \mathbf{a}_{\mathbf{P},i} a P , i t t t a P , i = { ( y , s , t ) ∈ a P : s ≤ f i P ( y ) } \mathbf{a}_{\mathbf{P},i}=\{(y,s,t)\in\mathbf{a}_{\mathbf{P}}:s\leq f_i^{\mathbf{P}}(y)\} a P , i = {( y , s , t ) ∈ a P : s ≤ f i P ( y )} i ∈ [ k ] i\in[k] i ∈ [ k ] 8
*Using the same random process A P \mathcal{A}_{\mathbf{P}} A P i ∈ [ k ] i\in[k] i ∈ [ k ] 9 Z P , i = Φ i ( P , A P ) Z_{\mathbf{P},i}=\Phi_i(\mathbf{P},\mathcal{A}_{\mathbf{P}}) Z P , i = Φ i ( P , A P ) B ⊆ Y k B\subseteq\mathcal{Y}^k B ⊆ Y k Γ k ( P ; B ) = Pr [ ( Z P , 1 , … , Z P , k ) ∈ B ] \Gamma_k(\mathbf{P};B)=\Pr[(Z_{\mathbf{P},1},\ldots,Z_{\mathbf{P},k})\in B] Γ k ( P ; B ) = Pr [( Z P , 1 , … , Z P , k ) ∈ B ]
( Z P , 1 , … , Z P , k ) ∼ Γ k ( P ; ⋅ ) (Z_{\mathrm{P},1},\ldots,Z_{\mathrm{P},k}) \sim\Gamma_k(\mathbf{P};\cdot) ( Z P , 1 , … , Z P , k ) ∼ Γ k ( P ; ⋅ ) Γ k ( P ; ⋅ ) \Gamma_k(\mathbf{P};\cdot) Γ k ( P ; ⋅ ) P \mathbf{P} P
Algorithm 6 Couple II from construction A.4
Input: Distributions q 1 , … , q k ∈ F q_1,\ldots,q_k \in\mathcal{F} q 1 , … , q k ∈ F
Output: Synthetic samples ( Z 1 , … , Z k ) (Z_1,\ldots,Z_k) ( Z 1 , … , Z k ) Z i ∼ q i ℓ Z_i \sim q_i^\ell Z i ∼ q i ℓ Pr [ Z i ≠ Z j ] ≤ 2 TV ( q i ℓ , q j ℓ ) \Pr[Z_i \ne Z_j] \le2\operatorname{TV}(q_i^\ell,q_j^\ell) Pr [ Z i = Z j ] ≤ 2 TV ( q i ℓ , q j ℓ ) i , j ∈ [ k ] i,j \in[k] i , j ∈ [ k ]
Set P i = q i ℓ P_i=q_i^\ell P i = q i ℓ i ∈ [ k ] i\in[k] i ∈ [ k ] ν P = ∑ i P i \nu_{\mathbf{P}}=\sum_i P_i ν P = ∑ i P i f i ν P = d P i d ν P f_i^{\nu_{\mathbf{P}}}=\frac{\mathrm{d}P_i}{\mathrm{d}\nu_{\mathbf{P}}} f i ν P = d ν P d P i
Let a random seed be A P \mathcal{A}_{\mathbf{P}} A P ν P ( d y ) d s d t \nu_{\mathbf{P}}(\mathrm{d}y)\mathrm{d}s\mathrm{d}t ν P ( d y ) d s d t
Z i = Φ i ( P , A P ) Z_i=\Phi_i(\mathbf{P},\mathcal{A}_{\mathbf{P}}) Z i = Φ i ( P , A P ) i ∈ [ k ] i\in[k] i ∈ [ k ] ▹ \triangleright ▹ A P = a P \mathcal{A}_{\mathbf{P}}=a_{\mathbf{P}} A P = a P z i = Φ i ( P , a P ) z_i=\Phi_i(\mathbf{P},a_{\mathbf{P}}) z i = Φ i ( P , a P )
return ( Z 1 , … , Z k ) (Z_1,\ldots,Z_k) ( Z 1 , … , Z k ) ▹ \triangleright ▹ ( Z 1 , … , Z k ) ∼ Γ k ( P ; ⋅ ) (Z_1,\ldots,Z_k)\sim\Gamma_k(\mathbf{P};\cdot) ( Z 1 , … , Z k ) ∼ Γ k ( P ; ⋅ )
The key extra ingredients are to show that these tuple-specific couplings vary measurably with P \mathbf{P} P
For a measurable map T : S → T T:\mathcal{S}\to\mathcal{T} T : S → T μ \mu μ S \mathcal{S} S T # μ T_{\#}\mu T # μ μ \mu μ T T T ( T # μ ) ( B ) = μ ( T − 1 ( B ) ) (T_{\#}\mu)(B)=\mu(T^{-1}(B)) ( T # μ ) ( B ) = μ ( T − 1 ( B )) B ⊆ T B\subseteq\mathcal{T} B ⊆ T pr i ( y 1 , … , y k ) = y i \operatorname{pr}_i(y_1,\ldots,y_k)=y_i pr i ( y 1 , … , y k ) = y i i i i
Proposition A.5 (Projectively consistent Poisson coupling kernels). Let Y \mathcal{Y} Y k ≥ 1 k\ge1 k ≥ 1 Γ k : Δ ( Y ) k → Δ ( Y k ) \Gamma_k:\Delta(\mathcal{Y})^k\to\Delta(\mathcal{Y}^k) Γ k : Δ ( Y ) k → Δ ( Y k ) Γ k ( P ; ⋅ ) \Gamma_k(\mathbf{P};\cdot) Γ k ( P ; ⋅ ) Γ k ( P ) \Gamma_k(\mathbf{P}) Γ k ( P ) D i j = { ( y 1 , … , y k ) ∈ Y k : y i ≠ y j } D_{ij}=\{(y_1,\ldots,y_k)\in\mathcal{Y}^k:y_i\ne y_j\} D ij = {( y 1 , … , y k ) ∈ Y k : y i = y j }
(1) (Measurability.) For every measurable B ⊆ Y k B\subseteq\mathcal{Y}^k B ⊆ Y k P ↦ Γ k ( P ; B ) \mathbf{P}\mapsto\Gamma_k(\mathbf{P};B) P ↦ Γ k ( P ; B ) σ \sigma σ Δ ( Y ) k \Delta(\mathcal{Y})^k Δ ( Y ) k Γ k \Gamma_k Γ k Δ ( Y ) k \Delta(\mathcal{Y})^k Δ ( Y ) k Y k \mathcal{Y}^k Y k
(2) (Marginals.) For every P = ( P 1 , … , P k ) \mathbf{P}=(P_1,\ldots,P_k) P = ( P 1 , … , P k ) i ∈ [ k ] i\in[k] i ∈ [ k ] ( pr i ) # Γ k ( P ; ⋅ ) = P i (\operatorname{pr}_i)_{\#}\Gamma_k(\mathbf{P};\cdot)=P_i ( pr i ) # Γ k ( P ; ⋅ ) = P i
(3) (Disagreement bound.) For every P \mathbf{P} P i , j ∈ [ k ] i,j\in[k] i , j ∈ [ k ] Γ k ( P ; D i j ) ≤ 2 TV ( P i , P j ) 1 + TV ( P i , P j ) ≤ 2 TV ( P i , P j ) \Gamma_k(\mathbf{P};D_{ij})\le\frac{2\operatorname{TV}(P_i,P_j)}{1+\operatorname{TV}(P_i,P_j)}\le2\operatorname{TV}(P_i,P_j) Γ k ( P ; D ij ) ≤ 1 + TV ( P i , P j ) 2 TV ( P i , P j ) ≤ 2 TV ( P i , P j )
(4) (Projective consistency.) For every nonempty E = { i 1 , … , i k ′ } ⊆ [ k ] E=\{i_1,\ldots,i_{k'}\}\subseteq[k] E = { i 1 , … , i k ′ } ⊆ [ k ] i 1 < ⋯ < i k ′ i_1<\cdots<i_{k'} i 1 < ⋯ < i k ′ P ′ = ( P i ) i ∈ E \mathbf{P}'=(P_i)_{i\in E} P ′ = ( P i ) i ∈ E ( pr E ) # Γ k ( P ; ⋅ ) = Γ k ′ ( P ′ ; ⋅ ) (\operatorname{pr}_E)_{\#}\Gamma_k(\mathbf{P};\cdot)=\Gamma_{k'}(\mathbf{P}';\cdot) ( pr E ) # Γ k ( P ; ⋅ ) = Γ k ′ ( P ′ ; ⋅ ) pr E ( y 1 , … , y k ) = ( y i 1 , … , y i k ′ ) \operatorname{pr}_E(y_1,\ldots,y_k)=(y_{i_1},\ldots,y_{i_{k'}}) pr E ( y 1 , … , y k ) = ( y i 1 , … , y i k ′ )
(5) (Permutation equivariance.) For every permutation σ \sigma σ [ k ] [k] [ k ] ( Z 1 , … , Z k ) ∼ Γ k ( ( P 1 , … , P k ) ; ⋅ ) (Z_1,\ldots,Z_k)\sim\Gamma_k((P_1,\ldots,P_k);\cdot) ( Z 1 , … , Z k ) ∼ Γ k (( P 1 , … , P k ) ; ⋅ ) ( Z σ ( 1 ) , … , Z σ ( k ) ) ∼ Γ k ( ( P σ ( 1 ) , … , P σ ( k ) ) ; ⋅ ) (Z_{\sigma(1)},\ldots,Z_{\sigma(k)})\sim\Gamma_k((P_{\sigma(1)},\ldots,P_{\sigma(k)});\cdot) ( Z σ ( 1 ) , … , Z σ ( k ) ) ∼ Γ k (( P σ ( 1 ) , … , P σ ( k ) ) ; ⋅ )
Proof. Now, we prove these properties.
Measurability Fix k ≥ 1 k\ge1 k ≥ 1 P = ( P 1 , … , P k ) ∈ Δ ( Y ) k \mathbf{P}=(P_1,\ldots,P_k)\in\Delta(\mathcal{Y})^k P = ( P 1 , … , P k ) ∈ Δ ( Y ) k ν P = ∑ i P i \nu_{\mathbf{P}}=\sum_i P_i ν P = ∑ i P i P i ≪ ν P P_i\ll\nu_{\mathbf{P}} P i ≪ ν P i ∈ [ k ] i\in[k] i ∈ [ k ] Y \mathcal{Y} Y ( P , y ) (\mathbf{P},y) ( P , y ) f i ( P , y ) = d P i d ν P ( y ) f_i(\mathbf{P},y)=\frac{\mathrm{d}P_i}{\mathrm{d}\nu_{\mathbf{P}}}(y) f i ( P , y ) = d ν P d P i ( y ) P i ≪ ν P P_i\ll\nu_{\mathbf{P}} P i ≪ ν P 0 ≤ f i ( P , y ) ≤ 1 0\le f_i(\mathbf{P},y)\le1 0 ≤ f i ( P , y ) ≤ 1 ν P \nu_{\mathbf{P}} ν P
For each P \mathbf{P} P A P \mathcal{A}_{\mathbf{P}} A P Y × R + × R + \mathcal{Y}\times\mathbb{R}_+\times\mathbb{R}_+ Y × R + × R + ν P ( d y ) d s d t \nu_{\mathbf{P}}(\mathrm{d}y)\mathrm{d}s\mathrm{d}t ν P ( d y ) d s d t i ∈ [ k ] i\in[k] i ∈ [ k ] A P , i = { ( y , s , t ) ∈ A P : s ≤ f i ( P , y ) } \mathcal{A}_{\mathbf{P},i}=\{(y,s,t)\in\mathcal{A}_{\mathbf{P}}:s\le f_i(\mathbf{P},y)\} A P , i = {( y , s , t ) ∈ A P : s ≤ f i ( P , y )} Z i Z_i Z i Z i = y Z_i=y Z i = y ( y , s , t ) (y,s,t) ( y , s , t ) A P , i \mathcal{A}_{\mathbf{P},i} A P , i t t t A P , i \mathcal{A}_{\mathbf{P},i} A P , i Z i = Φ i ( P , A P ) Z_i=\Phi_i(\mathbf{P},\mathcal{A}_{\mathbf{P}}) Z i = Φ i ( P , A P ) Φ i \Phi_i Φ i Φ ( P , A P ) = ( Φ 1 ( P , A P ) , … , Φ k ( P , A P ) ) \Phi(\mathbf{P},\mathcal{A}_{\mathbf{P}})=(\Phi_1(\mathbf{P},\mathcal{A}_{\mathbf{P}}),\ldots,\Phi_k(\mathbf{P},\mathcal{A}_{\mathbf{P}})) Φ ( P , A P ) = ( Φ 1 ( P , A P ) , … , Φ k ( P , A P )) B ⊆ Y k B\subseteq\mathcal{Y}^k B ⊆ Y k Γ k ( P ; B ) = Pr A P [ Φ ( P , A P ) ∈ B ] \Gamma_k(\mathbf{P};B)=\Pr_{\mathcal{A}_{\mathbf{P}}}[\Phi(\mathbf{P},\mathcal{A}_{\mathbf{P}})\in B] Γ k ( P ; B ) = Pr A P [ Φ ( P , A P ) ∈ B ] Γ k ( P ; ⋅ ) = L ( Φ ( P , A P ) ) \Gamma_k(\mathbf{P};\cdot)=\mathcal{L}(\Phi(\mathbf{P},\mathcal{A}_{\mathbf{P}})) Γ k ( P ; ⋅ ) = L ( Φ ( P , A P )) Y \mathcal{Y} Y ν P ( d y ) d s d t \nu_{\mathbf{P}}(dy)dsdt ν P ( d y ) d s d t P \mathbf{P} P P \mathbf{P} P P \mathbf{P} P f i ( P , y ) f_i(\mathbf{P},y) f i ( P , y ) 1 { g ( P , y , s ) ≥ 0 } \mathbf{1}\{g(\mathbf{P},y,s)\geq0\} 1 { g ( P , y , s ) ≥ 0 } t t t ( P , a ) ↦ Φ ( P , a ) (\mathbf{P},a)\mapsto\Phi(\mathbf{P},a) ( P , a ) ↦ Φ ( P , a ) P ↦ Γ k ( P ; B ) \mathbf{P}\mapsto\Gamma_k(\mathbf{P};B) P ↦ Γ k ( P ; B ) B ⊆ Y k B\subseteq\mathcal{Y}^k B ⊆ Y k Γ k \Gamma_k Γ k
2. Marginal To see that Z i Z_i Z i A P , i \mathcal{A}_{\mathbf{P},i} A P , i f i ( P , y ) ν P ( d y ) d t = P i ( d y ) d t f_i(\mathbf{P},y)\nu_{\mathbf{P}}(dy)dt=P_i(dy)dt f i ( P , y ) ν P ( d y ) d t = P i ( d y ) d t y y y Φ i ( P , A P ) \Phi_i(\mathbf{P},\mathcal{A}_{\mathbf{P}}) Φ i ( P , A P ) P i P_i P i ( pr i ) # Γ k ( P ; ⋅ ) = P i (\operatorname{pr}_i)_{\#}\Gamma_k(\mathbf{P};\cdot)=P_i ( pr i ) # Γ k ( P ; ⋅ ) = P i
3. Disagreement bound Fix i , j ∈ [ k ] i,j\in[k] i , j ∈ [ k ] g = f i ( P , y ) g=f_i(\mathbf{P},y) g = f i ( P , y ) h = f j ( P , y ) h=f_j(\mathbf{P},y) h = f j ( P , y ) α = TV ( P i , P j ) \alpha=\operatorname{TV}(P_i,P_j) α = TV ( P i , P j ) ( y , s ) (y,s) ( y , s ) s ≤ g ( y ) ∨ h ( y ) s\leq g(y)\vee h(y) s ≤ g ( y ) ∨ h ( y ) s ≤ g ( y ) ∧ h ( y ) s\leq g(y)\wedge h(y) s ≤ g ( y ) ∧ h ( y ) Z i = Z j = y Z_i=Z_j=y Z i = Z j = y Z i Z_i Z i Z j Z_j Z j A A A ∫ A ( g ∧ h ) d ν P \int_A(g\wedge h)d\nu_{\mathbf{P}} ∫ A ( g ∧ h ) d ν P ∫ A ( g ∨ h ) d ν P \int_A(g\vee h)d\nu_{\mathbf{P}} ∫ A ( g ∨ h ) d ν P
Pr [ Z i = Z j ] ≥ Pr [ Z i = Z j ∈ A and the same point determines both Z i and Z j ] = ∫ A ( g ∧ h ) d ν P ∫ A ( g ∨ h ) d ν P . \Pr[Z_i=Z_j]\geq\Pr[Z_i=Z_j\in A\text{ and the same point determines both }Z_i\text{ and }Z_j]=\frac{\int_A(g\wedge h)d\nu_{\mathbf{P}}}{\int_A(g\vee h)d\nu_{\mathbf{P}}}. Pr [ Z i = Z j ] ≥ Pr [ Z i = Z j ∈ A and the same point determines both Z i and Z j ] = ∫ A ( g ∨ h ) d ν P ∫ A ( g ∧ h ) d ν P . Note that ∫ Y ( g ∨ h ) d ν P = 1 + α \int_{\mathcal{Y}}(g\vee h)d\nu_{\mathbf{P}}=1+\alpha ∫ Y ( g ∨ h ) d ν P = 1 + α ∫ Y ( g ∧ h ) d ν P = 1 − α \int_{\mathcal{Y}}(g\wedge h)d\nu_{\mathbf{P}}=1-\alpha ∫ Y ( g ∧ h ) d ν P = 1 − α Pr [ Z i = Z j ] ≥ 1 − α 1 + α \Pr[Z_i=Z_j]\geq\frac{1-\alpha}{1+\alpha} Pr [ Z i = Z j ] ≥ 1 + α 1 − α Pr [ Z i ≠ Z j ] ≤ 1 − 1 − α 1 + α ≤ 2 α \Pr[Z_i\neq Z_j]\leq1-\frac{1-\alpha}{1+\alpha}\leq2\alpha Pr [ Z i = Z j ] ≤ 1 − 1 + α 1 − α ≤ 2 α Γ k ( P ; D i j ) ≤ 2 TV ( P i , P j ) 1 + TV ( P i , P j ) ≤ 2 TV ( P i , P j ) \Gamma_k(\mathbf{P};D_{ij})\leq\frac{2\operatorname{TV}(P_i,P_j)}{1+\operatorname{TV}(P_i,P_j)}\leq2\operatorname{TV}(P_i,P_j) Γ k ( P ; D ij ) ≤ 1 + TV ( P i , P j ) 2 TV ( P i , P j ) ≤ 2 TV ( P i , P j ) D i j = { ( y 1 , … , y k ) ∈ Y k : y i ≠ y j } D_{ij}=\{(y_1,\ldots,y_k)\in\mathcal{Y}^k:y_i\neq y_j\} D ij = {( y 1 , … , y k ) ∈ Y k : y i = y j }
4. Projective consistency Let E ⊆ [ k ] E\subseteq[k] E ⊆ [ k ] P ′ = ( P i ) i ∈ E \mathbf{P}'=(P_i)_{i\in E} P ′ = ( P i ) i ∈ E ν P ′ = ∑ i ∈ E P i \nu_{\mathbf{P}'}=\sum_{i\in E}P_i ν P ′ = ∑ i ∈ E P i f i ( P ′ , y ) = d P i d ν P ′ ( y ) f_i(\mathbf{P}',y)=\frac{dP_i}{d\nu_{\mathbf{P}'}}(y) f i ( P ′ , y ) = d ν P ′ d P i ( y ) i ∈ E i\in E i ∈ E f i ( P , y ) = r ( y ) f i ( P ′ , y ) f_i(\mathbf{P},y)=r(y)f_i(\mathbf{P}',y) f i ( P , y ) = r ( y ) f i ( P ′ , y ) r ( y ) = d ν P ′ d ν P ( y ) r(y)=\frac{d\nu_{\mathbf{P}'}}{d\nu_{\mathbf{P}}}(y) r ( y ) = d ν P d ν P ′ ( y ) ν P \nu_{\mathbf{P}} ν P i ∈ E i\in E i ∈ E Y + = { y : r ( y ) > 0 } \mathcal{Y}_+=\{y:r(y)>0\} Y + = { y : r ( y ) > 0 } ν P ′ ( Y ∖ Y + ) = 0 \nu_{\mathbf{P}'}(\mathcal{Y}\setminus\mathcal{Y}_+)=0 ν P ′ ( Y ∖ Y + ) = 0 P i ≪ ν P ′ P_i\ll\nu_{\mathbf{P}'} P i ≪ ν P ′ i ∈ E i\in E i ∈ E P i ( Y ∖ Y + ) = 0 P_i(\mathcal{Y}\setminus\mathcal{Y}_+)=0 P i ( Y ∖ Y + ) = 0 i i i Y ∖ Y + \mathcal{Y}\setminus\mathcal{Y}_+ Y ∖ Y + r ( y ) = 0 r(y)=0 r ( y ) = 0 i ∈ E i\in E i ∈ E
Note that under the change of variable ( y , s , t ) ↦ ( y , s r ( y ) , t ) (y,s,t)\mapsto\left(y,\frac{s}{r(y)},t\right) ( y , s , t ) ↦ ( y , r ( y ) s , t ) A P \mathcal{A}_{\mathbf{P}} A P Y + × R + × R + \mathcal{Y}_+\times\mathbb{R}_+\times\mathbb{R}_+ Y + × R + × R + ν P ′ ( d y ) d u d t \nu_{\mathbf{P}'}(dy)dudt ν P ′ ( d y ) d u d t u = s / r ( y ) u=s/r(y) u = s / r ( y ) ν P ( d y ) d s d t = ν P ( d y ) r ( y ) d u d t = ν P ′ ( d y ) d u d t \nu_{\mathbf{P}}(dy)dsdt=\nu_{\mathbf{P}}(dy)r(y)dudt=\nu_{\mathbf{P}'}(dy)dudt ν P ( d y ) d s d t = ν P ( d y ) r ( y ) d u d t = ν P ′ ( d y ) d u d t i ∈ E i\in E i ∈ E s ≤ f i P ( y ) s\leq f_i^{\mathbf{P}}(y) s ≤ f i P ( y ) s r ( y ) ≤ f i ( P ′ , y ) ⟺ u ≤ f i ( P ′ , y ) \frac{s}{r(y)}\leq f_i(\mathbf{P}',y)\Longleftrightarrow u\leq f_i(\mathbf{P}',y) r ( y ) s ≤ f i ( P ′ , y ) ⟺ u ≤ f i ( P ′ , y ) s s s y y y t t t i ∈ E i\in E i ∈ E ( y , s , t ) (y,s,t) ( y , s , t ) i i i ( y , s / r ( y ) , t ) (y,s/r(y),t) ( y , s / r ( y ) , t ) y y y t t t E E E P ′ \mathbf{P}' P ′ ( pr E ) # Γ k ( P ; ⋅ ) = Γ k ′ ( P ′ ; ⋅ ) (\operatorname{pr}_E)_{\#}\Gamma_k(\mathbf{P};\cdot)=\Gamma_{k'}(\mathbf{P}';\cdot) ( pr E ) # Γ k ( P ; ⋅ ) = Γ k ′ ( P ′ ; ⋅ ) k ′ = ∣ E ∣ k'=|E| k ′ = ∣ E ∣
5. Permutation equivariance Let P = ( P 1 , … , P k ) \mathbf{P}=(P_1,\ldots,P_k) P = ( P 1 , … , P k ) P σ = ( P σ ( 1 ) , … , P σ ( k ) ) \mathbf{P}_{\sigma}=(P_{\sigma(1)},\ldots,P_{\sigma(k)}) P σ = ( P σ ( 1 ) , … , P σ ( k ) ) σ \sigma σ [ k ] [k] [ k ] ν P = ∑ i P i = ∑ i P σ ( i ) = ν P σ \nu_{\mathbf{P}}=\sum_iP_i=\sum_iP_{\sigma(i)}=\nu_{\mathbf{P}_{\sigma}} ν P = ∑ i P i = ∑ i P σ ( i ) = ν P σ i ∈ [ k ] i\in[k] i ∈ [ k ] f i ( P σ , y ) = d P σ ( i ) d ν P σ = d P σ ( i ) d ν P = f σ ( i ) ( P , ⋅ ) f_i(\mathbf{P}_{\sigma},y)=\frac{dP_{\sigma(i)}}{d\nu_{\mathbf{P}_{\sigma}}}=\frac{dP_{\sigma(i)}}{d\nu_{\mathbf{P}}}=f_{\sigma(i)}(\mathbf{P},\cdot) f i ( P σ , y ) = d ν P σ d P σ ( i ) = d ν P d P σ ( i ) = f σ ( i ) ( P , ⋅ ) ν P \nu_{\mathbf{P}} ν P A P \mathcal{A}_{\mathbf{P}} A P Y × R + × R + \mathcal{Y}\times\mathbb{R}_+\times\mathbb{R}_+ Y × R + × R + ν P ( d y ) d s d t \nu_{\mathbf{P}}(dy)dsdt ν P ( d y ) d s d t P σ \mathbf{P}_{\sigma} P σ ν P = ν P σ \nu_{\mathbf{P}}=\nu_{\mathbf{P}_{\sigma}} ν P = ν P σ A P σ , i = { ( y , s , t ) ∈ A P : s ≤ f i ( P σ , y ) } = { ( y , s , t ) ∈ A P : s ≤ f σ ( i ) ( P , y ) } = A P , σ ( i ) \mathcal{A}_{\mathbf{P}_{\sigma},i}=\{(y,s,t)\in\mathcal{A}_{\mathbf{P}}:s\leq f_i(\mathbf{P}_{\sigma},y)\}=\{(y,s,t)\in\mathcal{A}_{\mathbf{P}}:s\leq f_{\sigma(i)}(\mathbf{P},y)\}=\mathcal{A}_{\mathbf{P},\sigma(i)} A P σ , i = {( y , s , t ) ∈ A P : s ≤ f i ( P σ , y )} = {( y , s , t ) ∈ A P : s ≤ f σ ( i ) ( P , y )} = A P , σ ( i ) Z σ , i = Φ i ( P σ , A P ) Z_{\sigma,i}=\Phi_i(\mathbf{P}_{\sigma},\mathcal{A}_{\mathbf{P}}) Z σ , i = Φ i ( P σ , A P ) Z σ , i = Φ i ( P σ , A P ) = Φ σ ( i ) ( P , A P ) = Z σ ( i ) Z_{\sigma,i}=\Phi_i(\mathbf{P}_{\sigma},\mathcal{A}_{\mathbf{P}})=\Phi_{\sigma(i)}(\mathbf{P},\mathcal{A}_{\mathbf{P}})=Z_{\sigma(i)} Z σ , i = Φ i ( P σ , A P ) = Φ σ ( i ) ( P , A P ) = Z σ ( i ) Z i = Φ i ( P , A P ) Z_i=\Phi_i(\mathbf{P},\mathcal{A}_{\mathbf{P}}) Z i = Φ i ( P , A P ) ( Z σ , 1 , … , Z σ , k ) ∼ Γ k ( P σ ; ⋅ ) (Z_{\sigma,1},\ldots,Z_{\sigma,k})\sim\Gamma_k(\mathbf{P}_{\sigma};\cdot) ( Z σ , 1 , … , Z σ , k ) ∼ Γ k ( P σ ; ⋅ )
There are two aspects of A.5 worth remarking. First, the standard Borel machinery is not needed to construct the coupling for a fixed tuple P \mathbf{P} P P \mathbf{P} P P \mathbf{P} P ν P = ∑ i P i \nu_{\mathbf{P}} = \sum_i P_i ν P = ∑ i P i P \mathbf{P} P Γ k \Gamma_k Γ k Γ k ( P ; ⋅ ) \Gamma_k(\mathbf{P};\cdot) Γ k ( P ; ⋅ ) P \mathbf{P} P
Second, projective consistency allows couplings laws associated with different tuples to be realized as marginals of a single larger coupling. For example, given P = ( P 1 , … , P k ) \mathbf{P} = (P_1,\ldots,P_k) P = ( P 1 , … , P k ) Q = ( Q 1 , … , Q k ) \mathbf{Q} = (Q_1,\ldots,Q_k) Q = ( Q 1 , … , Q k ) Γ 2 k ( ( P 1 , … , P k , Q 1 , … , Q k ) ) ; ⋅ ) \Gamma_{2k}((P_1,\ldots,P_k,Q_1,\ldots,Q_k));\cdot) Γ 2 k (( P 1 , … , P k , Q 1 , … , Q k )) ; ⋅ ) k k k Γ k ( P ; ⋅ ) \Gamma_k(\mathbf{P};\cdot) Γ k ( P ; ⋅ ) k k k Γ k ( Q ; ⋅ ) \Gamma_k(\mathbf{Q};\cdot) Γ k ( Q ; ⋅ )
It is also worth noting the differences between the two constructions. Under a common σ \sigma σ ν \nu ν ( Z P ) P ∈ P (Z_P)_{P\in\mathcal{P}} ( Z P ) P ∈ P P ⊆ Δ ( Y ) \mathcal{P} \subseteq\Delta(\mathcal{Y}) P ⊆ Δ ( Y ) no global dominating measure , and for each finite tuple P \mathbf{P} P ν P \nu_{\mathbf{P}} ν P Q \mathbf{Q} Q ν Q \nu_{\mathbf{Q}} ν Q Q \mathbf{Q} Q Γ k ( Q ; ⋅ ) \Gamma_k(\mathbf{Q};\cdot) Γ k ( Q ; ⋅ ) Γ k ( P ; ⋅ ) \Gamma_k(\mathbf{P};\cdot) Γ k ( P ; ⋅ )
Despite this bottom-up approach, we can still establish a post-hoc universal coupling over all of Δ ( Y ) \Delta(\mathcal{Y}) Δ ( Y ) Proposition A.5 allows us to stitch the entire family of finite-dimensional couplings ( Γ k ) k ≥ 1 (\Gamma_k)_{k\geq1} ( Γ k ) k ≥ 1 Y Δ ( Y ) \mathcal{Y}^{\Delta(\mathcal{Y})} Y Δ ( Y ) Δ ( Y ) \Delta(\mathcal{Y}) Δ ( Y ) ( Z P ) P ∈ P (Z_P)_{P\in\mathcal{P}} ( Z P ) P ∈ P Γ \Gamma Γ ( Z P ) P ∈ Δ ( Y ) (Z_P)_{P\in\Delta(\mathcal{Y})} ( Z P ) P ∈ Δ ( Y ) Γ ∞ \Gamma_\infty Γ ∞ ( Z P ) P ∈ P (Z_P)_{P\in\mathcal{P}} ( Z P ) P ∈ P P \mathcal{P} P ν \nu ν P ≪ ν \mathcal{P}\ll\nu P ≪ ν P ∈ P P\in\mathcal{P} P ∈ P A \mathcal{A} A ν \nu ν P \mathbf{P} P ν P \nu_{\mathbf{P}} ν P A P \mathcal{A}_{\mathbf{P}} A P Γ k ( P ; ⋅ ) \Gamma_k(\mathbf{P};\cdot) Γ k ( P ; ⋅ ) P \mathbf{P} P ( Γ k ) k ≥ 1 (\Gamma_k)_{k\geq1} ( Γ k ) k ≥ 1 Γ ∞ \Gamma_\infty Γ ∞ Δ ( Y ) \Delta(\mathcal{Y}) Δ ( Y )
Corollary A.6. In the setup above, let ( Γ k ) k ≥ 1 (\Gamma_k)_{k\geq1} ( Γ k ) k ≥ 1 Proposition A.5 . Then there exists a probability measure Γ ∞ \Gamma_\infty Γ ∞ Y Δ ( Y ) \mathcal{Y}^{\Delta(\mathcal{Y})} Y Δ ( Y ) σ \sigma σ ( Z P ) P ∈ Δ ( Y ) ∼ Γ ∞ (Z_P)_{P\in\Delta(\mathcal{Y})}\sim\Gamma_\infty ( Z P ) P ∈ Δ ( Y ) ∼ Γ ∞ k ≥ 1 k\geq1 k ≥ 1 P = ( P 1 , … , P k ) \mathbf{P}=(P_1,\ldots,P_k) P = ( P 1 , … , P k ) ( Z P 1 , … , Z P k ) ∼ Γ k ( P ; ⋅ ) (Z_{P_1},\ldots,Z_{P_k})\sim\Gamma_k(\mathbf{P};\cdot) ( Z P 1 , … , Z P k ) ∼ Γ k ( P ; ⋅ ) P ∈ Δ ( Y ) P\in\Delta(\mathcal{Y}) P ∈ Δ ( Y ) Z P ∼ P Z_P\sim P Z P ∼ P P , Q ∈ Δ ( Y ) P,Q\in\Delta(\mathcal{Y}) P , Q ∈ Δ ( Y ) Pr [ Z P ≠ Z Q ] ≤ 2 TV ( P , Q ) \Pr[Z_P\ne Z_Q]\leq2\operatorname{TV}(P,Q) Pr [ Z P = Z Q ] ≤ 2 TV ( P , Q ) Γ ∞ \Gamma_\infty Γ ∞ Δ ( Y ) \Delta(\mathcal{Y}) Δ ( Y ) Γ ∞ \Gamma_\infty Γ ∞ ( Γ k ) k (\Gamma_k)_k ( Γ k ) k
Proof. Consider index set T = Δ ( Y ) T=\Delta(\mathcal{Y}) T = Δ ( Y ) S P = Y S_P=\mathcal{Y} S P = Y P ∈ T P\in T P ∈ T I = { P 1 , … , P k } ⊆ T I=\{P_1,\ldots,P_k\}\subseteq T I = { P 1 , … , P k } ⊆ T ( P 1 , … , P k ) (P_1,\ldots,P_k) ( P 1 , … , P k ) ( y P ) P ∈ I → ( y P i ) i ∈ [ k ] (y_P)_{P\in I}\to(y_{P_i})_{i\in[k]} ( y P ) P ∈ I → ( y P i ) i ∈ [ k ] μ I \mu_I μ I S I = ∏ P i ∈ I Y = S_I=\prod_{P_i\in I}\mathcal{Y}= S I = ∏ P i ∈ I Y = Y I \mathcal{Y}^{I} Y I Γ k ( ( P 1 , … , P k ) ; ⋅ ) \Gamma_k((P_1,\ldots,P_k);\cdot) Γ k (( P 1 , … , P k ) ; ⋅ ) ( P σ ( 1 ) , … , P σ ( k ) ) (P_{\sigma(1)},\ldots,P_{\sigma(k)}) ( P σ ( 1 ) , … , P σ ( k ) ) σ \sigma σ [ k ] [k] [ k ] Proposition A.5 shows that ( Z σ ( 1 ) , … , Z σ ( k ) ) ∼ Γ k ( ( P σ ( 1 ) , … , P σ ( k ) ) ; ⋅ ) (Z_{\sigma(1)},\ldots,Z_{\sigma(k)}) \sim\Gamma_k((P_{\sigma(1)},\ldots,P_{\sigma(k)});\cdot) ( Z σ ( 1 ) , … , Z σ ( k ) ) ∼ Γ k (( P σ ( 1 ) , … , P σ ( k ) ) ; ⋅ ) ( Z 1 , … , Z k ) ∼ Γ k ( ( P 1 , … , P k ) ; ⋅ ) (Z_1,\ldots,Z_k) \sim\Gamma_k((P_1,\ldots,P_k);\cdot) ( Z 1 , … , Z k ) ∼ Γ k (( P 1 , … , P k ) ; ⋅ ) Y I \mathcal{Y}^{I} Y I
Now let J ⊆ I J \subseteq I J ⊆ I Proposition A.5 implies ( pr J ) # μ I = μ J (\operatorname{pr}_J)_{\#}\mu_I=\mu_J ( pr J ) # μ I = μ J pr J : Y I ↦ Y J \operatorname{pr}_J:\mathcal{Y}^{I}\mapsto\mathcal{Y}^{J} pr J : Y I ↦ Y J ( μ I ) I (\mu_I)_I ( μ I ) I ( Z P ) P ∈ Δ ( Y ) (Z_P)_{P\in\Delta(\mathcal{Y})} ( Z P ) P ∈ Δ ( Y ) Z P ∈ Y Z_P\in\mathcal{Y} Z P ∈ Y I = { P 1 , … , P k } I=\{P_1,\ldots,P_k\} I = { P 1 , … , P k } ( Z P 1 , … , Z P k ) ∼ Γ k ( ( P 1 , … , P k ) ; ⋅ ) (Z_{P_1},\ldots,Z_{P_k})\sim\Gamma_k((P_1,\ldots,P_k);\cdot) ( Z P 1 , … , Z P k ) ∼ Γ k (( P 1 , … , P k ) ; ⋅ ) Γ ∞ = Law ( ( Z P ) P ∈ Δ ( Y ) ) \Gamma_\infty=\operatorname{Law}((Z_P)_{P\in\Delta(\mathcal{Y})}) Γ ∞ = Law (( Z P ) P ∈ Δ ( Y ) ) Y Δ ( Y ) \mathcal{Y}^{\Delta(\mathcal{Y})} Y Δ ( Y ) σ \sigma σ
It remains to remove the distinctness assumption. Fix an arbitrary tuple P = ( P 1 , … , P k ) ∈ T k \mathbf{P}=(P_1,\ldots,P_k)\in\mathcal{T}^k P = ( P 1 , … , P k ) ∈ T k Q 1 , … , Q n Q_1,\ldots,Q_n Q 1 , … , Q n P \mathbf{P} P P i = Q π ( i ) P_i=Q_{\pi(i)} P i = Q π ( i ) π : [ k ] ↦ [ n ] \pi:[k]\mapsto[n] π : [ k ] ↦ [ n ] T π : Y n ↦ Y k T_\pi:\mathcal{Y}^n\mapsto\mathcal{Y}^k T π : Y n ↦ Y k T π ( y 1 , … , y n ) = ( y π ( 1 ) , … , y π ( k ) ) T_\pi(y_1,\ldots,y_n)=(y_{\pi(1)},\ldots,y_{\pi(k)}) T π ( y 1 , … , y n ) = ( y π ( 1 ) , … , y π ( k ) ) Q Q Q ( Z Q 1 , … , Z Q n ) ∼ Γ n ( ( Q 1 , … , Q n ) ; ⋅ ) (Z_{Q_1},\ldots,Z_{Q_n})\sim\Gamma_n((Q_1,\ldots,Q_n);\cdot) ( Z Q 1 , … , Z Q n ) ∼ Γ n (( Q 1 , … , Q n ) ; ⋅ ) ( Z P ) P ∈ Δ ( Y ) ∼ Γ ∞ (Z_P)_{P\in\Delta(\mathcal{Y})}\sim\Gamma_\infty ( Z P ) P ∈ Δ ( Y ) ∼ Γ ∞ P i = Q π ( i ) P_i=Q_{\pi(i)} P i = Q π ( i ) Z P i = Z Q π ( i ) Z_{P_i}=Z_{Q_{\pi(i)}} Z P i = Z Q π ( i ) ( Z P 1 , … , Z P k ) = T π ( Z Q 1 , … , Z Q n ) (Z_{P_1},\ldots,Z_{P_k})=T_\pi(Z_{Q_1},\ldots,Z_{Q_n}) ( Z P 1 , … , Z P k ) = T π ( Z Q 1 , … , Z Q n ) Law Γ ∞ ( Z P 1 , … , Z P k ) = ( T π ) # Γ n ( ( Q 1 , … , Q n ) ; ⋅ ) \operatorname{Law}_{\Gamma_\infty}(Z_{P_1},\ldots,Z_{P_k})=(T_\pi)_{\#}\Gamma_n((Q_1,\ldots,Q_n);\cdot) Law Γ ∞ ( Z P 1 , … , Z P k ) = ( T π ) # Γ n (( Q 1 , … , Q n ) ; ⋅ )
Next, it suffices to show that ( T π ) # Γ n ( ( Q 1 , … , Q n ) ; ⋅ ) = Γ k ( P ; ⋅ ) (T_\pi)_{\#}\Gamma_n((Q_1,\ldots,Q_n);\cdot)=\Gamma_k(\mathbf{P};\cdot) ( T π ) # Γ n (( Q 1 , … , Q n ) ; ⋅ ) = Γ k ( P ; ⋅ ) E = { r 1 , … , r n } E=\{r_1,\ldots,r_n\} E = { r 1 , … , r n } r j = min { i ∈ [ k ] : P i = Q j } r_j=\min\{i\in[k]:P_i=Q_j\} r j = min { i ∈ [ k ] : P i = Q j } Q j Q_j Q j P \mathbf{P} P ( pr E ) # Γ k ( P ; ⋅ ) = Γ n ( ( Q 1 , … , Q n ) ; ⋅ ) (\operatorname{pr}_E)_{\#}\Gamma_k(\mathbf{P};\cdot)=\Gamma_n((Q_1,\ldots,Q_n);\cdot) ( pr E ) # Γ k ( P ; ⋅ ) = Γ n (( Q 1 , … , Q n ) ; ⋅ ) Q Q Q Γ k ( P ; D i j ) ≤ 2 TV ( P i , P j ) = 0 \Gamma_k(\mathbf{P};D_{ij})\leq2\operatorname{TV}(P_i,P_j)=0 Γ k ( P ; D ij ) ≤ 2 TV ( P i , P j ) = 0 P i = P j P_i=P_j P i = P j ( Y 1 , … , Y k ) ∼ Γ k ( P ; ⋅ ) (Y_1,\ldots,Y_k)\sim\Gamma_k(\mathbf{P};\cdot) ( Y 1 , … , Y k ) ∼ Γ k ( P ; ⋅ ) Y i = Y r π ( i ) Y_i=Y_{r_{\pi(i)}} Y i = Y r π ( i ) ( Y 1 , … , Y k ) = T π ( Y r 1 , … , Y r n ) (Y_1,\ldots,Y_k)=T_\pi(Y_{r_1},\ldots,Y_{r_n}) ( Y 1 , … , Y k ) = T π ( Y r 1 , … , Y r n ) Γ k ( P ; ⋅ ) = ( T π ) # Law ( Y r 1 , … , Y r n ) = ( T π ) # Γ n ( ( Q 1 , … , Q n ) ; ⋅ ) = Law Γ ∞ ( Z P 1 , … , Z P k ) \Gamma_k(\mathbf{P};\cdot)=(T_\pi)_{\#}\operatorname{Law}(Y_{r_1},\ldots,Y_{r_n})=(T_\pi)_{\#}\Gamma_n((Q_1,\ldots,Q_n);\cdot)=\operatorname{Law}_{\Gamma_\infty}(Z_{P_1},\ldots,Z_{P_k}) Γ k ( P ; ⋅ ) = ( T π ) # Law ( Y r 1 , … , Y r n ) = ( T π ) # Γ n (( Q 1 , … , Q n ) ; ⋅ ) = Law Γ ∞ ( Z P 1 , … , Z P k ) k ≥ 1 k\geq1 k ≥ 1 P ∈ Δ ( Y ) k \mathbf{P}\in\Delta(\mathcal{Y})^k P ∈ Δ ( Y ) k ( Z P 1 , … , Z P k ) ∼ Γ k ( P ; ⋅ ) (Z_{P_1},\ldots,Z_{P_k})\sim\Gamma_k(\mathbf{P};\cdot) ( Z P 1 , … , Z P k ) ∼ Γ k ( P ; ⋅ )
Finally, for all P ∈ Δ ( Y ) P\in\Delta(\mathcal{Y}) P ∈ Δ ( Y ) I = { P } I=\{P\} I = { P } Z P ∼ Γ 1 ( P ; ⋅ ) Z_P\sim\Gamma_1(P;\cdot) Z P ∼ Γ 1 ( P ; ⋅ ) Proposition A.5 , Γ 1 ( P ; ⋅ ) = P \Gamma_1(P;\cdot)=P Γ 1 ( P ; ⋅ ) = P Z P ∼ P Z_P\sim P Z P ∼ P P , Q ∈ Δ ( Y ) P,Q\in\Delta(\mathcal{Y}) P , Q ∈ Δ ( Y ) I = { P , Q } I=\{P,Q\} I = { P , Q } ( Z P , Z Q ) ∼ Γ 2 ( ( P , Q ) ; ⋅ ) (Z_P,Z_Q)\sim\Gamma_2((P,Q);\cdot) ( Z P , Z Q ) ∼ Γ 2 (( P , Q ) ; ⋅ ) Pr [ Z P ≠ Z Q ] = Γ 2 ( ( P , Q ) ; D 12 ) \Pr[Z_P\ne Z_Q]=\Gamma_2((P,Q);D_{12}) Pr [ Z P = Z Q ] = Γ 2 (( P , Q ) ; D 12 ) D 12 = { ( y 1 , y 2 ) ∈ Y 2 : y 1 ≠ y 2 } D_{12}=\{(y_1,y_2)\in\mathcal{Y}^2:y_1\ne y_2\} D 12 = {( y 1 , y 2 ) ∈ Y 2 : y 1 = y 2 } Proposition A.5 , it follows that Pr [ Z P ≠ Z Q ] = Γ 2 ( ( P , Q ) ; D 12 ) ≤ 2 TV ( P , Q ) \Pr[Z_P\ne Z_Q]=\Gamma_2((P,Q);D_{12})\leq2\operatorname{TV}(P,Q) Pr [ Z P = Z Q ] = Γ 2 (( P , Q ) ; D 12 ) ≤ 2 TV ( P , Q ) □ \square □
Having established the existence of the global measure Γ ∞ \Gamma_\infty Γ ∞ Δ ( Y ) \Delta(\mathcal{Y}) Δ ( Y ) P \mathcal{P} P
Corollary A.7 (Grand coupling scheme Γ P \Gamma_{\mathcal{P}} Γ P The family of random variables ( Z P ) P ∈ Δ ( Y ) ∼ Γ ∞ (Z_P)_{P\in\Delta(\mathcal{Y})}\sim\Gamma_\infty ( Z P ) P ∈ Δ ( Y ) ∼ Γ ∞ Corollary A.6 constitutes a universal grand coupling scheme on the entire space Δ ( Y ) \Delta(\mathcal{Y}) Δ ( Y ) ( Z P ) P ∈ P (Z_P)_{P\in\mathcal{P}} ( Z P ) P ∈ P Γ P \Gamma_{\mathcal{P}} Γ P P ⊆ Δ ( Y ) \mathcal{P}\subseteq\Delta(\mathcal{Y}) P ⊆ Δ ( Y )
Proof. G1 and G2 directly follows from Corollary A.6 , and G3 follows from Proposition A.5 . The restriction to any subset P \mathcal{P} P ( Z P ) P ∈ P (Z_P)_{P\in\mathcal{P}} ( Z P ) P ∈ P Γ P \Gamma_{\mathcal{P}} Γ P □ \square □
Private synthetic data sampler
In this section, we apply the grand coupling schemes developed in § 3 to construct a differentially private synthetic data sampler. In particular, we formally prove the privacy and utility guarantees of Aggregate (Algorithm 1) and Sampler (Algorithm 2), presented in § 4 .
Throughout, let Y = X ℓ \mathcal{Y}=\mathcal{X}^{\ell} Y = X ℓ X \mathcal{X} X ℓ \ell ℓ P = { q ℓ : q ∈ F } \mathcal{P}=\{q^{\ell}:q\in\mathcal{F}\} P = { q ℓ : q ∈ F } F \mathcal{F} F Q \mathcal{Q} Q
Aggregate: Tuple-Level Privacy and Utility
We establish the privacy and utility guarantees of Aggregate (Algorithm 1), instantiated with any grand coupling scheme on P \mathcal{P} P Definition 3.1 .
Tuple-Level Privacy. Recall that we use a change-by-one adjacency notion for neighboring tuples, i.e., q = ( q 1 , … , q k ) \mathbf{q}=(q_1,\ldots,q_k) q = ( q 1 , … , q k ) q ′ = ( q 1 ′ , … , q k ′ ) \mathbf{q}'=(q'_1,\ldots,q'_k) q ′ = ( q 1 ′ , … , q k ′ )
The privacy argument relies on using the grand coupling scheme Γ P \Gamma_{\mathcal{P}} Γ P q \mathbf{q} q q ′ \mathbf{q}' q ′ Couple k ( q ) \operatorname{Couple}_k(\mathbf{q}) Couple k ( q ) q ′ \mathbf{q}' q ′ Γ P 10 \Gamma_{\mathcal{P}}^{10} Γ P 10
Specifically, rather than drawing independent samples from L ( Couple k ( q ) ) \mathcal{L}(\operatorname{Couple}_k(\mathbf{q})) L ( Couple k ( q )) L ( Couple k ( q ′ ) ) \mathcal{L}(\operatorname{Couple}_k(\mathbf{q}')) L ( Couple k ( q ′ )) ( Z P ) P ∈ P ∼ Γ P (Z_P)_{P\in\mathcal{P}}\sim\Gamma_{\mathcal{P}} ( Z P ) P ∈ P ∼ Γ P Z ~ i = Z q i ℓ \widetilde{Z}_i=Z_{q_i}^{\ell} Z i = Z q i ℓ q \mathbf{q} q Z ~ i ′ = Z ( q i ′ ) ℓ \widetilde{Z}'_i=Z_{(q'_i)^{\ell}} Z i ′ = Z ( q i ′ ) ℓ q ′ \mathbf{q}' q ′ i ≠ j i\ne j i = j q i = q i ′ q_i=q'_i q i = q i ′ Z q i ℓ = Z ( q i ′ ) ℓ Z_{q_i}^{\ell}=Z_{(q'_i)^{\ell}} Z q i ℓ = Z ( q i ′ ) ℓ ( Z ~ 1 , … , Z ~ k ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k) ( Z 1 , … , Z k ) ( Z ~ 1 ′ , … , Z ~ k ′ ) (\widetilde{Z}'_1,\ldots,\widetilde{Z}'_k) ( Z 1 ′ , … , Z k ′ ) j j j Γ P \Gamma_{\mathcal{P}} Γ P Γ P \Gamma_{\mathcal{P}} Γ P ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Proposition B.1 (Privacy of Aggregate). If StabilityBasedMode is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) 10
Proof. Fix a pair of neighboring tuples q = ( q 1 , … , q k ) \mathbf{q}=(q_1,\ldots,q_k) q = ( q 1 , … , q k ) q ′ = ( q 1 ′ , … , q k ′ ) \mathbf{q}'=(q'_1,\ldots,q'_k) q ′ = ( q 1 ′ , … , q k ′ ) q i = q i ′ q_i=q'_i q i = q i ′ i ≠ j i\ne j i = j P i = q i ℓ P_i=q_i^{\ell} P i = q i ℓ P i ′ = ( q i ′ ) ℓ P'_i=(q'_i)^{\ell} P i ′ = ( q i ′ ) ℓ P i = P i ′ P_i=P'_i P i = P i ′ i ≠ j i\ne j i = j P = ( P 1 , … , P k ) \mathbf{P}=(P_1,\ldots,P_k) P = ( P 1 , … , P k ) P ′ = ( P 1 ′ , … , P k ′ ) \mathbf{P}'=(P'_1,\ldots,P'_k) P ′ = ( P 1 ′ , … , P k ′ )
By Definition 3.1 , let ( Z P ) P ∈ P (Z_P)_{P\in\mathcal{P}} ( Z P ) P ∈ P P \mathcal{P} P Couple k \operatorname{Couple}_k Couple k ( Z P ) P ∈ P (Z_P)_{P\in\mathcal{P}} ( Z P ) P ∈ P Z ~ = ( Z P 1 , … , Z P k ) \widetilde{\mathbf{Z}}=(Z_{P_1},\ldots,Z_{P_k}) Z = ( Z P 1 , … , Z P k ) Z ~ ′ = ( Z P 1 ′ , … , Z P k ′ ) \widetilde{\mathbf{Z}}'=(Z_{P'_1},\ldots,Z_{P'_k}) Z ′ = ( Z P 1 ′ , … , Z P k ′ ) Couple k ( q ) \operatorname{Couple}_k(\mathbf{q}) Couple k ( q ) L ( Z P 1 , … , Z P k ) \mathcal{L}(Z_{P_1},\ldots,Z_{P_k}) L ( Z P 1 , … , Z P k ) q ′ \mathbf{q}' q ′ Z ~ = d Couple k ( q ) \widetilde{\mathbf{Z}}\mathrel{\overset{\mathrm{d}}{=}}\operatorname{Couple}_k(\mathbf{q}) Z = d Couple k ( q ) Z ~ ′ = d Couple k ( q ′ ) \widetilde{\mathbf{Z}}'\mathrel{\overset{\mathrm{d}}{=}}\operatorname{Couple}_k(\mathbf{q}') Z ′ = d Couple k ( q ′ )
Furthermore, since P i = P i ′ P_i=P'_i P i = P i ′ i ≠ j i\ne j i = j Z ~ i = Z ~ i ′ \widetilde{Z}_i=\widetilde{Z}'_i Z i = Z i ′ i ≠ j i\ne j i = j ( Z ~ 1 , … , Z ~ k ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k) ( Z 1 , … , Z k ) ( Z ~ 1 ′ , … , Z ~ k ′ ) (\widetilde{Z}'_1,\ldots,\widetilde{Z}'_k) ( Z 1 ′ , … , Z k ′ ) M ( Z ; B ) M(\mathbf{Z};B) M ( Z ; B ) B B B Z \mathbf{Z} Z M M M ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) M ( ( Z ~ 1 , … , Z ~ k ) ; B ) ≤ e ε M ( ( Z ~ 1 ′ , … , Z ~ k ′ ) ; B ) + δ M((\widetilde{Z}_1,\ldots,\widetilde{Z}_k);B)\le e^{\varepsilon}M((\widetilde{Z}'_1,\ldots,\widetilde{Z}'_k);B)+\delta M (( Z 1 , … , Z k ) ; B ) ≤ e ε M (( Z 1 ′ , … , Z k ′ ) ; B ) + δ Γ \Gamma Γ
Pr [ Aggregate ( q ) ∈ B ] = E Γ [ M ( ( Z ~ 1 , … , Z ~ k ) ; B ) ] ≤ ε E Γ [ M ( ( Z ~ 1 ′ , … , Z ~ k ′ ) ; B ) ] + δ = ε ℓ Pr [ Aggregate ( q ′ ) ∈ B ] + δ . \Pr[\operatorname{Aggregate}(\mathbf{q}) \in B] = \mathbb{E}_{\Gamma}[M((\widetilde{Z}_1,\ldots,\widetilde{Z}_k);B)]
\leq\varepsilon\mathbb{E}_{\Gamma}[M((\widetilde{Z}'_1,\ldots,\widetilde{Z}'_k);B)] + \delta
= \varepsilon^{\ell}\Pr[\operatorname{Aggregate}(\mathbf{q}') \in B] + \delta. Pr [ Aggregate ( q ) ∈ B ] = E Γ [ M (( Z 1 , … , Z k ) ; B )] ≤ ε E Γ [ M (( Z 1 ′ , … , Z k ′ ) ; B )] + δ = ε ℓ Pr [ Aggregate ( q ′ ) ∈ B ] + δ . A symmetric argument holds for the reverse direction.
Tuple-Level Utility. We next show that if a large majority of the input distributions q i q_i q i p p p Aggregate \operatorname{Aggregate} Aggregate p ℓ ∼ p ℓ p^{\ell} \sim p^{\ell} p ℓ ∼ p ℓ p ℓ p^{\ell} p ℓ
As in the privacy analysis, the utility guarantee relies on constructing an analysis coupling from the grand coupling scheme Γ P \Gamma_{\mathcal{P}} Γ P q = ( q 1 , … , q k ) ∈ F k \mathbf{q}=(q_1,\ldots,q_k)\in\mathcal{F}^k q = ( q 1 , … , q k ) ∈ F k p ∈ F p\in\mathcal{F} p ∈ F ( Z P ) P ∈ P ∼ Γ P (Z_P)_{P\in\mathcal{P}}\sim\Gamma_{\mathcal{P}} ( Z P ) P ∈ P ∼ Γ P Z ~ i = Z q i ℓ \widetilde{Z}_i=Z_{q_i}^{\ell} Z i = Z q i ℓ i ∈ [ k ] i\in[k] i ∈ [ k ] Z ~ ∗ = Z p ℓ \widetilde{Z}_*=Z_{p^{\ell}} Z ∗ = Z p ℓ p ℓ ∈ P p^{\ell}\in\mathcal{P} p ℓ ∈ P L ( Couple k ( q ) ) \mathcal{L}(\operatorname{Couple}_k(\mathbf{q})) L ( Couple k ( q )) L ( Couple 1 ( p ) ) \mathcal{L}(\operatorname{Couple}_1(p)) L ( Couple 1 ( p )) Γ P \Gamma_{\mathcal{P}} Γ P Γ P \Gamma_{\mathcal{P}} Γ P ( Z ~ 1 , … , Z ~ k ) ∼ L ( Couple k ( q ) ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k)\sim\mathcal{L}(\operatorname{Couple}_k(\mathbf{q})) ( Z 1 , … , Z k ) ∼ L ( Couple k ( q )) Z ~ ∗ ∼ L ( Couple 1 ( p ) ) = p ℓ \widetilde{Z}_*\sim\mathcal{L}(\operatorname{Couple}_1(p))=p^{\ell} Z ∗ ∼ L ( Couple 1 ( p )) = p ℓ
We emphasize that Z ~ ∗ \widetilde{Z}_* Z ∗ q i q_i q i TV ( q i , p ) ≤ η \operatorname{TV}(q_i,p)\leq\eta TV ( q i , p ) ≤ η Z ~ i = Z ~ ∗ \widetilde{Z}_i=\widetilde{Z}_* Z i = Z ∗ 2 ℓ η 2\ell\eta 2 ℓ η 7 / 8 7/8 7/8 q i q_i q i η \eta η p p p Z ~ i \widetilde{Z}_i Z i Z ~ ∗ ∼ p ℓ \widetilde{Z}_*\sim p^{\ell} Z ∗ ∼ p ℓ StabilityBasedMode \operatorname{StabilityBasedMode} StabilityBasedMode
Proposition B.2 (Utility of Aggregate \operatorname{Aggregate} Aggregate p ∈ Q ⊆ F p\in\mathcal{Q}\subseteq\mathcal{F} p ∈ Q ⊆ F q = ( q 1 , … , q k ) ∈ F k \mathbf{q}=(q_1,\ldots,q_k)\in\mathcal{F}^k q = ( q 1 , … , q k ) ∈ F k J = { j ∈ [ k ] : TV ( q j , p ) ≤ η } J=\{j\in[k]:\operatorname{TV}(q_j,p)\leq\eta\} J = { j ∈ [ k ] : TV ( q j , p ) ≤ η } η \eta η StabilityBasedMode \operatorname{StabilityBasedMode} StabilityBasedMode 1 − β S B M 1-\beta_{\mathrm{SBM}} 1 − β SBM τ \tau τ c ∈ ( 0 , 1 ) c\in(0,1) c ∈ ( 0 , 1 ) 2 ( 1 − c ) ∣ J ∣ − k ≥ τ 2(1-c)|J|-k\geq\tau 2 ( 1 − c ) ∣ J ∣ − k ≥ τ
TV ( L ( Aggregate ( q ) ) , p ℓ ) ≤ 2 ℓ η c + β S B M \operatorname{TV}(\mathcal{L}(\operatorname{Aggregate}(\mathbf{q})),p^{\ell})\leq\frac{2\ell\eta}{c}+\beta_{\mathrm{SBM}} TV ( L ( Aggregate ( q )) , p ℓ ) ≤ c 2 ℓ η + β SBM Proof. Fix a tuple q = ( q 1 , … , q k ) ∈ F k \mathbf{q}=(q_1,\ldots,q_k)\in\mathcal{F}^k q = ( q 1 , … , q k ) ∈ F k p ∈ Q p\in\mathcal{Q} p ∈ Q P i = q i ℓ P_i=q_i^{\ell} P i = q i ℓ P ∗ = p ℓ P_*=p^{\ell} P ∗ = p ℓ ( Z P ) P ∈ P ∼ Γ P (Z_P)_{P\in\mathcal{P}}\sim\Gamma_{\mathcal{P}} ( Z P ) P ∈ P ∼ Γ P Z ~ i = Z P i \widetilde{Z}_i=Z_{P_i} Z i = Z P i i ∈ [ k ] i\in[k] i ∈ [ k ] Z ~ ∗ = Z P ∗ \widetilde{Z}_*=Z_{P_*} Z ∗ = Z P ∗ ( Z ~ 1 , … , Z ~ k ) ∼ L ( Couple k ( q ) ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k)\sim\mathcal{L}(\operatorname{Couple}_k(\mathbf{q})) ( Z 1 , … , Z k ) ∼ L ( Couple k ( q )) Z ~ ∗ ∼ p ℓ \widetilde{Z}_*\sim p^{\ell} Z ∗ ∼ p ℓ ( Z P ) P ∈ P ∼ Γ P (Z_P)_{P\in\mathcal{P}}\sim\Gamma_{\mathcal{P}} ( Z P ) P ∈ P ∼ Γ P Z ~ i = Z P i \widetilde{Z}_i=Z_{P_i} Z i = Z P i i ∈ [ k ] i\in[k] i ∈ [ k ] Z ~ ∗ = Z P ∗ \widetilde{Z}_*=Z_{P_*} Z ∗ = Z P ∗ ( Z ~ 1 , … , Z ~ k ) ∼ L ( Couple k ( q ) ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k)\sim\mathcal{L}(\operatorname{Couple}_k(\mathbf{q})) ( Z 1 , … , Z k ) ∼ L ( Couple k ( q )) Z ~ ∗ ∼ Couple 1 ( p ) = p ℓ \widetilde{Z}_*\sim\operatorname{Couple}_1(p)=p^{\ell} Z ∗ ∼ Couple 1 ( p ) = p ℓ
By the disagreement bound (G2), we have Pr [ Z ~ i ≠ Z ~ ∗ ] ≤ 2 TV ( P i , P ∗ ) = 2 TV ( q i ℓ , p ℓ ) \Pr[\widetilde{Z}_i\neq\widetilde{Z}_*]\leq2\operatorname{TV}(P_i,P_*)=2\operatorname{TV}(q_i^{\ell},p^{\ell}) Pr [ Z i = Z ∗ ] ≤ 2 TV ( P i , P ∗ ) = 2 TV ( q i ℓ , p ℓ ) i ∈ [ k ] i\in[k] i ∈ [ k ] J = { j ∈ [ k ] : TV ( q j , p ) ≤ η } J=\{j\in[k]:\operatorname{TV}(q_j,p)\leq\eta\} J = { j ∈ [ k ] : TV ( q j , p ) ≤ η } Pr [ Z ~ j ≠ Z ~ ∗ ] ≤ 2 ℓ η \Pr[\widetilde{Z}_j\neq\widetilde{Z}_*]\leq2\ell\eta Pr [ Z j = Z ∗ ] ≤ 2 ℓ η
Consider the indicator I j = 1 { Z ~ j ≠ Z ~ ∗ } I_j=1\{\widetilde{Z}_j\neq\widetilde{Z}_*\} I j = 1 { Z j = Z ∗ } j ∈ J j\in J j ∈ J E [ ∑ j ∈ J I j ] ≤ 2 ℓ η ∣ J ∣ \mathbb{E}[\sum_{j\in J}I_j]\leq2\ell\eta|J| E [ ∑ j ∈ J I j ] ≤ 2 ℓ η ∣ J ∣ Pr [ ∑ j ∈ J I j > c ∣ J ∣ ] ≤ 2 ℓ η c \Pr[\sum_{j\in J}I_j>c|J|]\leq\frac{2\ell\eta}{c} Pr [ ∑ j ∈ J I j > c ∣ J ∣ ] ≤ c 2 ℓ η ∑ j ∈ J I j ≤ c ∣ J ∣ \sum_{j\in J}I_j\leq c|J| ∑ j ∈ J I j ≤ c ∣ J ∣ ∣ J ∣ − ∑ j ∈ J I j ≥ ( 1 − c ) ∣ J ∣ |J|-\sum_{j\in J}I_j\geq(1-c)|J| ∣ J ∣ − ∑ j ∈ J I j ≥ ( 1 − c ) ∣ J ∣ ( Z ~ 1 , … , Z ~ k ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k) ( Z 1 , … , Z k ) Z ~ ∗ \widetilde{Z}_* Z ∗ 2 ( 1 − c ) ∣ J ∣ − k ≥ τ > 0 2(1-c)|J|-k\geq\tau>0 2 ( 1 − c ) ∣ J ∣ − k ≥ τ > 0 c c c ( 1 − c ) ∣ J ∣ > k / 2 (1-c)|J|>k/2 ( 1 − c ) ∣ J ∣ > k /2 Z ~ ∗ \widetilde{Z}_* Z ∗ k k k Z ~ ∗ \widetilde{Z}_* Z ∗ k − ( 1 − c ) ∣ J ∣ k-(1-c)|J| k − ( 1 − c ) ∣ J ∣ 2 ( 1 − c ) ∣ J ∣ − k ≥ τ 2(1-c)|J|-k\geq\tau 2 ( 1 − c ) ∣ J ∣ − k ≥ τ Z ~ \widetilde{Z} Z ( Z ~ 1 , … , Z ~ k ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k) ( Z 1 , … , Z k ) ( Z ~ 1 , … , Z ~ k ) = d Couple k ( q ) (\widetilde{Z}_1,\ldots,\widetilde{Z}_k) \overset{\mathrm{d}}{=} \operatorname{Couple}_k(q) ( Z 1 , … , Z k ) = d Couple k ( q ) Z ~ = d Aggregate ( q ) \widetilde{Z} \overset{\mathrm{d}}{=} \operatorname{Aggregate}(q) Z = d Aggregate ( q ) ( Z ~ , Z ~ ∗ ) (\widetilde{Z},\widetilde{Z}_*) ( Z , Z ∗ ) L ( Aggregate ( q ) ) \mathcal{L}(\operatorname{Aggregate}(q)) L ( Aggregate ( q )) p ℓ p^\ell p ℓ
By the accuracy guarantee of StabilityBasedMode, we have Pr [ Z ~ ≠ Z ~ ∗ ∣ ∑ j ∈ J I j ≤ c ∣ J ∣ ] ≤ β S B M \Pr[\widetilde{Z} \ne\widetilde{Z}_* \mid\sum_{j \in J} I_j \le c|J|] \le\beta_{\mathrm{SBM}} Pr [ Z = Z ∗ ∣ ∑ j ∈ J I j ≤ c ∣ J ∣ ] ≤ β SBM Pr [ Z ~ ≠ Z ~ ∗ ] ≤ β S B M + 2 ℓ η c \Pr[\widetilde{Z} \ne\widetilde{Z}_*] \le\beta_{\mathrm{SBM}} + \frac{2\ell\eta}{c} Pr [ Z = Z ∗ ] ≤ β SBM + c 2 ℓ η TV ( L ( Aggregate ( q ) ) , p ℓ ) = TV ( L ( Z ~ ) , L ( Z ~ ∗ ) ) ≤ Pr [ Z ~ ≠ Z ~ ∗ ] ≤ β S B M + 2 ℓ η c \operatorname{TV}(\mathcal{L}(\operatorname{Aggregate}(q)),p^\ell) = \operatorname{TV}(\mathcal{L}(\widetilde{Z}),\mathcal{L}(\widetilde{Z}_*)) \le\Pr[\widetilde{Z} \ne\widetilde{Z}_*] \le\beta_{\mathrm{SBM}} + \frac{2\ell\eta}{c} TV ( L ( Aggregate ( q )) , p ℓ ) = TV ( L ( Z ) , L ( Z ∗ )) ≤ Pr [ Z = Z ∗ ] ≤ β SBM + c 2 ℓ η
To complete the utility guarantee, we instantiate the mode mechanism step with the stability-based mode mechanism [46 Vad17] , whose privacy and accuracy properties are recalled below.
Fact B.3 (Stability-based mode, Proposition 3.4 from [Vad17]; [46 ] ). For every ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) m ∈ N m \in\mathbb{N} m ∈ N ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) M : X m → X M:\mathcal{X}^m \to\mathcal{X} M : X m → X x m x^m x m 4 log ( 1 / δ ) / ε 4\log(1/\delta)/\varepsilon 4 log ( 1/ δ ) / ε M ( x ) M(x) M ( x ) 1 − δ 1-\delta 1 − δ
We can now synthesize these components. By combining our tuple-level privacy guarantee (in Proposition B.1 ), the utility bound of our analysis coupling (Proposition B.2 ), and the accuracy of the mode mechanism (Fact B.3 ), we obtain the final privacy and utility guarantee for the Aggregate subroutine, stated below.
Corollary B.4. Let β , ε , δ ∈ ( 0 , 1 ) \beta,\varepsilon,\delta\in(0,1) β , ε , δ ∈ ( 0 , 1 ) ℓ ∈ N + \ell\in\mathbb{N}^{+} ℓ ∈ N + η = β 64 ℓ \eta= \frac{\beta}{64\ell} η = 64 ℓ β δ 0 = min { δ , β / 4 } \delta_0 = \min\{\delta,\beta/4\} δ 0 = min { δ , β /4 } k k k k ≥ 8 log ( 4 / β ) + log ( 1 / δ ) ε k \ge8\frac{\log(4/\beta)+\log(1/\delta)}{\varepsilon} k ≥ 8 ε l o g ( 4/ β ) + l o g ( 1/ δ ) ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) Fact B.3 , is ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) p ∈ Q p \in\mathcal{Q} p ∈ Q q ∈ F k q \in\mathcal{F}^k q ∈ F k ∣ { j ∈ [ k ] : TV ( q j , p ) ≤ η } ∣ ≥ 7 k / 8 |\{j \in[k] : \operatorname{TV}(q_j,p) \le\eta\}| \ge7k/8 ∣ { j ∈ [ k ] : TV ( q j , p ) ≤ η } ∣ ≥ 7 k /8 TV ( L ( Aggregate ( q ) ) , p ℓ ) ≤ β / 2 \operatorname{TV}(\mathcal{L}(\operatorname{Aggregate}(q)),p^\ell) \le\beta/2 TV ( L ( Aggregate ( q )) , p ℓ ) ≤ β /2
Proof. By Proposition B.1 , Aggregate is ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) τ = 4 log ( 1 / δ 0 ) / ε \tau= 4\log(1/\delta_0)/\varepsilon τ = 4 log ( 1/ δ 0 ) / ε β S B M = δ 0 \beta_{\mathrm{SBM}} = \delta_0 β SBM = δ 0 Fact B.3 , and choose c = 1 / 8 c = 1/8 c = 1/8 2 ( 1 − c ) ∣ J ∣ − k ≥ k / 2 ≥ τ 2(1-c)|J|-k \ge k/2 \ge\tau 2 ( 1 − c ) ∣ J ∣ − k ≥ k /2 ≥ τ Proposition B.2 therefore gives a coupling ( Z ~ , Z ~ ∗ ) (\widetilde{Z},\widetilde{Z}_*) ( Z , Z ∗ ) Z ~ = d Aggregate ( q ) \widetilde{Z} \overset{\mathrm{d}}{=} \operatorname{Aggregate}(q) Z = d Aggregate ( q ) Z ~ ∗ = d p ℓ \widetilde{Z}_* \overset{\mathrm{d}}{=} p^\ell Z ∗ = d p ℓ Pr [ Z ~ ≠ Z ~ ∗ ] ≤ β S B M + 2 ℓ η c = δ 0 + β / 4 ≤ β / 2 \Pr[\widetilde{Z} \ne\widetilde{Z}_*] \le\beta_{\mathrm{SBM}} + \frac{2\ell\eta}{c} = \delta_0 + \beta/4 \le\beta/2 Pr [ Z = Z ∗ ] ≤ β SBM + c 2 ℓ η = δ 0 + β /4 ≤ β /2 TV ( L ( Aggregate ( q ) ) , p ℓ ) ≤ β / 2 \operatorname{TV}(\mathcal{L}(\operatorname{Aggregate}(q)),p^\ell) \le\beta/2 TV ( L ( Aggregate ( q )) , p ℓ ) ≤ β /2
We establish the privacy and utility guarantees of Sampler (Algorithm 2), which takes a dataset S ∈ X n S \in\mathcal{X}^n S ∈ X n S , S ′ ∈ X n S,S' \in\mathcal{X}^n S , S ′ ∈ X n
Proposition B.5 (Privacy of Sampler). If StabilityBasedMode in Aggregate is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) 12
Proof. Fix neighboring datasets S = ( X 1 , … , X n ) S=(X_1,\ldots,X_n) S = ( X 1 , … , X n ) S ′ = ( X 1 ′ , … , X n ′ ) S'=(X'_1,\ldots,X'_n) S ′ = ( X 1 ′ , … , X n ′ ) X i = X i ′ X_i=X'_i X i = X i ′ i ≠ j i\ne j i = j
We first couple the data-independent randomness used in the two executions on S S S S ′ S' S ′ Π ∼ U ( S n ) \Pi\sim\mathcal{U}(S_n) Π ∼ U ( S n ) U 1 , … , U k ∼ i . i . d . U ( [ 0 , 1 ] ) U_1,\ldots,U_k \overset{\mathrm{i.i.d.}}{\sim} \mathcal{U}([0,1]) U 1 , … , U k ∼ i.i.d. U ([ 0 , 1 ])
Now fix a realization ( π , u 1 , … , u k ) (\pi,u_1,\ldots,u_k) ( π , u 1 , … , u k ) ( s i ) i (s_i)_i ( s i ) i ( s i ′ ) i (s'_i)_i ( s i ′ ) i a a a π − 1 ( j ) \pi^{-1}(j) π − 1 ( j ) X i = X i ′ X_i = X_i' X i = X i ′ i ≠ j i \ne j i = j s i = s i ′ s_i = s_i' s i = s i ′ i ≠ a i \ne a i = a u i u_i u i s i s_i s i s i ′ s_i' s i ′ q i = L ( s i ; u i ) = L ( s i ′ ; u i ) = q i ′ q_i = L(s_i;u_i) = L(s_i';u_i) = q_i' q i = L ( s i ; u i ) = L ( s i ′ ; u i ) = q i ′ i ≠ a i \ne a i = a q = ( q 1 , … , q k ) \mathbf{q} = (q_1,\ldots,q_k) q = ( q 1 , … , q k ) q ′ = ( q 1 ′ , … , q k ′ ) \mathbf{q}' = (q_1',\ldots,q_k') q ′ = ( q 1 ′ , … , q k ′ )
Let M ( q ; B ) M(\mathbf{q};B) M ( q ; B ) Aggregate ( q ) \operatorname{Aggregate}(\mathbf{q}) Aggregate ( q ) B ⊆ X ℓ B \subseteq\mathcal{X}^{\ell} B ⊆ X ℓ ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) Proposition B.1 , Aggregate is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ( π , u 1 , … , u k ) (\pi,u_1,\ldots,u_k) ( π , u 1 , … , u k ) M ( q ; B ) ≤ e ε M ( q ′ ; B ) + δ M(\mathbf{q};B) \le e^{\varepsilon}M(\mathbf{q}';B) + \delta M ( q ; B ) ≤ e ε M ( q ′ ; B ) + δ
Pr [ Sampler ( S ) ∈ B ] = E Π , ( U i ) i ∈ [ k ] [ M ( q ; B ) ] ≤ e ε E Π , ( U i ) i ∈ [ k ] [ M ( q ′ ; B ) ] + δ = e ε Pr [ Sampler ( S ′ ) ∈ B ] + δ . \Pr[\operatorname{Sampler}(S) \in B] = \mathbb{E}_{\Pi,(U_i)_{i\in[k]}}[M(\mathbf{q};B)]
\le e^{\varepsilon}\mathbb{E}_{\Pi,(U_i)_{i\in[k]}}[M(\mathbf{q}';B)] + \delta
= e^{\varepsilon}\Pr[\operatorname{Sampler}(S') \in B] + \delta. Pr [ Sampler ( S ) ∈ B ] = E Π , ( U i ) i ∈ [ k ] [ M ( q ; B )] ≤ e ε E Π , ( U i ) i ∈ [ k ] [ M ( q ′ ; B )] + δ = e ε Pr [ Sampler ( S ′ ) ∈ B ] + δ . and similarly for the reverse direction. Therefore, Sampler is ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
Proposition B.6 (Utility of Sampler). Fix a base learner L L L Q Q Q ε > 0 \varepsilon> 0 ε > 0 β , δ ∈ ( 0 , 1 ) \beta,\delta\in(0,1) β , δ ∈ ( 0 , 1 ) ℓ ∈ N + \ell\in\mathbb{N}^{+} ℓ ∈ N + η = β 64 ℓ \eta= \frac{\beta}{64\ell} η = 64 ℓ β δ 0 = min { δ , β / 4 } \delta_0 = \min\{\delta,\beta/4\} δ 0 = min { δ , β /4 } k k k k ≥ max { 8 β log ( 4 β δ ) , 128 log ( 4 β ) } k \ge\max\left\{\frac{8}{\beta}\log\left(\frac{4}{\beta\delta}\right),128\log\left(\frac{4}{\beta}\right)\right\} k ≥ max { β 8 log ( β δ 4 ) , 128 log ( β 4 ) } b ∈ N + b \in\mathbb{N}^{+} b ∈ N + p ∈ Q p \in Q p ∈ Q S i ∼ p b S_i \sim p^b S i ∼ p b U i ∼ U ( [ 0 , 1 ] ) U_i \sim\mathrm{U}([0,1]) U i ∼ U ([ 0 , 1 ]) Pr [ TV ( L ( S i ; U i ) , p ) ≥ η ] ≤ 1 / 16 \Pr[\operatorname{TV}(L(S_i;U_i),p) \ge\eta] \le1/16 Pr [ TV ( L ( S i ; U i ) , p ) ≥ η ] ≤ 1/16 n = k b n = kb n = k b p ∈ Q ⊆ F p \in Q \subseteq\mathcal{F} p ∈ Q ⊆ F S ∼ p n S \sim p^n S ∼ p n TV ( L ( Sampler ( S ) ) , p ℓ ) ≤ 3 β / 4 \operatorname{TV}(\mathcal{L}(\operatorname{Sampler}(S)),p^\ell) \le3\beta/4 TV ( L ( Sampler ( S )) , p ℓ ) ≤ 3 β /4 ( ℓ , 3 β / 4 ) (\ell,3\beta/4) ( ℓ , 3 β /4 ) Q Q Q Definition 1.4 .
Proof. Fix p ∈ Q p \in Q p ∈ Q 7 k / 8 7k/8 7 k /8 η \eta η p p p ( X π ( 1 ) , … , X π ( n ) ) ∼ p n (X_{\pi(1)},\ldots,X_{\pi(n)}) \sim p^n ( X π ( 1 ) , … , X π ( n ) ) ∼ p n π \pi π S ∼ p n S \sim p^n S ∼ p n Π = π \Pi= \pi Π = π S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k S i = ( X π ( ( i − 1 ) b + 1 ) , … , X π ( i b ) ) S_i = (X_{\pi((i-1)b+1)},\ldots,X_{\pi(ib)}) S i = ( X π (( i − 1 ) b + 1 ) , … , X π ( ib ) ) S i ∼ p b S_i \sim p^b S i ∼ p b i i i U 1 , … , U k U_1,\ldots,U_k U 1 , … , U k Π = π \Pi= \pi Π = π S S S Π = π \Pi= \pi Π = π ( S i , U i ) , … , ( S k , U k ) (S_i,U_i),\ldots,(S_k,U_k) ( S i , U i ) , … , ( S k , U k ) q i = L ( S i ; U i ) q_i = L(S_i;U_i) q i = L ( S i ; U i )
Now define indicators I i = 1 { TV ( q i , p ) > η } I_i = 1\{\operatorname{TV}(q_i,p) > \eta\} I i = 1 { TV ( q i , p ) > η } i ∈ [ k ] i \in[k] i ∈ [ k ] Pr [ I i = 1 ∣ Π = π ] ≤ 1 / 16 \Pr[I_i = 1 \mid\Pi= \pi] \le1/16 Pr [ I i = 1 ∣ Π = π ] ≤ 1/16 i i i I 1 , … , I k I_1,\ldots,I_k I 1 , … , I k 1 / 16 1/16 1/16 Π = π \Pi= \pi Π = π Pr [ ∑ i = 1 k I i ≥ k / 8 ∣ Π = π ] ≤ exp ( − 2 k ( 1 / 8 − 1 / 16 ) 2 ) = e − k / 128 ≤ β / 4 \Pr[\sum_{i=1}^{k} I_i \ge k/8 \mid\Pi= \pi] \le\exp(-2k(1/8-1/16)^2) = e^{-k/128} \le\beta/4 Pr [ ∑ i = 1 k I i ≥ k /8 ∣ Π = π ] ≤ exp ( − 2 k ( 1/8 − 1/16 ) 2 ) = e − k /128 ≤ β /4 π \pi π Π \Pi Π Pr [ ∑ i = 1 k I i ≥ k / 8 ] ≤ β / 4 \Pr[\sum_{i=1}^{k} I_i \ge k/8] \le\beta/4 Pr [ ∑ i = 1 k I i ≥ k /8 ] ≤ β /4 Pr [ E c ] ≤ β / 4 \Pr[E^c] \le\beta/4 Pr [ E c ] ≤ β /4 E = { ∣ { i ∈ [ k ] : TV ( q i , p ) ≤ η } ∣ ≥ 7 k / 8 } E = \{|\{i \in[k] : \operatorname{TV}(q_i,p) \le\eta\}| \ge7k/8\} E = { ∣ { i ∈ [ k ] : TV ( q i , p ) ≤ η } ∣ ≥ 7 k /8 }
By Corollary B.4 , every realized q \mathbf{q} q E E E TV ( L ( Aggregate ( q ) ) , p ℓ ) ≤ β / 2 \operatorname{TV}(\mathcal{L}(\operatorname{Aggregate}(\mathbf{q})),p^\ell) \le\beta/2 TV ( L ( Aggregate ( q )) , p ℓ ) ≤ β /2 L ( Sampler ( S ) ∣ E ) = E [ L ( Aggregate ( q ) ) ∣ E ] \mathcal{L}(\operatorname{Sampler}(S)\mid E) = \mathbb{E}[\mathcal{L}(\operatorname{Aggregate}(\mathbf{q}))\mid E] L ( Sampler ( S ) ∣ E ) = E [ L ( Aggregate ( q )) ∣ E ] TV ( L ( Sampler ( S ) ∣ E ) , p ℓ ) ≤ β / 2 \operatorname{TV}(\mathcal{L}(\operatorname{Sampler}(S)\mid E),p^\ell) \le\beta/2 TV ( L ( Sampler ( S ) ∣ E ) , p ℓ ) ≤ β /2
TV ( L ( Sampler ( S ) ) , p ℓ ) ≤ Pr [ E ] TV ( L ( Sampler ( S ) ∣ E ) , p ℓ ) + Pr [ E c ] TV ( L ( Sampler ( S ) ∣ E c ) , p ℓ ) ≤ β / 2 + Pr [ E c ] ≤ β / 2 + β / 4 = 3 β / 4. \operatorname{TV}(\mathcal{L}(\operatorname{Sampler}(S)),p^\ell)
\le\Pr[E]\operatorname{TV}(\mathcal{L}(\operatorname{Sampler}(S)\mid E),p^\ell)
+ \Pr[E^c]\operatorname{TV}(\mathcal{L}(\operatorname{Sampler}(S)\mid E^c),p^\ell)
\le\beta/2 + \Pr[E^c] \le\beta/2 + \beta/4 = 3\beta/4. TV ( L ( Sampler ( S )) , p ℓ ) ≤ Pr [ E ] TV ( L ( Sampler ( S ) ∣ E ) , p ℓ ) + Pr [ E c ] TV ( L ( Sampler ( S ) ∣ E c ) , p ℓ ) ≤ β /2 + Pr [ E c ] ≤ β /2 + β /4 = 3 β /4. Finally, by the coupling characterization of total variation distance, there exists a coupling ( Z ~ , Z ~ ∗ ) (\widetilde{Z},\widetilde{Z}_*) ( Z , Z ∗ ) Z ~ = d Sampler ( S ′ ) \widetilde{Z} \overset{\mathrm{d}}{=} \operatorname{Sampler}(S') Z = d Sampler ( S ′ ) Z ~ ∗ = d p ℓ \widetilde{Z}_* \overset{\mathrm{d}}{=} p^\ell Z ∗ = d p ℓ Pr [ Z ~ ≠ Z ~ ∗ ] ≤ 3 β / 4 \Pr[\widetilde{Z} \ne\widetilde{Z}_*] \le3\beta/4 Pr [ Z = Z ∗ ] ≤ 3 β /4 ( ℓ , 3 β / 4 ) (\ell,3\beta/4) ( ℓ , 3 β /4 ) Q Q Q
Combining the dataset-level privacy guarantee of Proposition B.5 with the utility guarantee of Proposition B.6 yields the formal guarantee for the end-to-end pipeline Sampler.
Corollary B.7. Under the same setting as B.6, Sampler is ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) ( ℓ , 3 β / 4 ) (\ell,3\beta/4) ( ℓ , 3 β /4 ) Q Q Q Definition 1.4 .
Agnostic private distribution learning
In this section, we extend our main result beyond the realizable setting. We show that if a class of distributions is agnostic learnable, then it is also agnostic private learnable. The following is the definition of agnostic learnability.
Definition C.1 (C C C C ≥ 1 C \ge1 C ≥ 1 Q ⊆ Δ ( X ) Q \subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) Q Q Q C C C m : ( 0 , 1 ) 2 → N ≥ 1 m:(0,1)^2 \to\mathbb{N}_{\ge1} m : ( 0 , 1 ) 2 → N ≥ 1 L : X ∗ → Δ ( X ) L:\mathcal{X}^{*} \to\Delta(\mathcal{X}) L : X ∗ → Δ ( X ) α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 ) p ∈ Δ ( X ) p \in\Delta(\mathcal{X}) p ∈ Δ ( X ) S ∼ p m ( α , β ) S \sim p^{m(\alpha,\beta)} S ∼ p m ( α , β ) p ^ = L ( S ) \hat{p}=L(S) p ^ = L ( S ) TV ( p , p ^ ) ≤ C OPT ( p ) + α \operatorname{TV}(p,\hat{p}) \le C\operatorname{OPT}(p)+\alpha TV ( p , p ^ ) ≤ C OPT ( p ) + α ≥ 1 − β \ge1-\beta ≥ 1 − β OPT ( p ) : = inf q ∈ Q TV ( p , q ) \operatorname{OPT}(p):=\inf_{q\in Q}\operatorname{TV}(p,q) OPT ( p ) := inf q ∈ Q TV ( p , q )
Theorem C.2 (General agnostic private reduction). Let X \mathcal{X} X C ≥ 1 C \ge1 C ≥ 1 Q ⊆ Δ ( X ) Q \subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) C C C m ( α , β ) m(\alpha,\beta) m ( α , β ) ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) ( 8 C 2 + 9 C ) (8C^2+9C) ( 8 C 2 + 9 C ) ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
n 0 ( α , β , ε , δ ) = O ( m ( α 16 ( C + 3 ) , 1 16 ) m ( 2 α C + 3 , β ) 1 ℓ log ( 4 ( C + 3 ) α δ ) ) n_0(\alpha,\beta,\varepsilon,\delta)=O\left(m\left(\frac{\alpha}{16(C+3)},\frac{1}{16}\right)m\left(\frac{2\alpha}{C+3},\beta\right)^{\frac{1}{\ell}}\log\left(\frac{4(C+3)}{\alpha\delta}\right)\right) n 0 ( α , β , ε , δ ) = O ( m ( 16 ( C + 3 ) α , 16 1 ) m ( C + 3 2 α , β ) ℓ 1 log ( α δ 4 ( C + 3 ) ) ) for every α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 )
Proof. Let L L L C C C Definition C.1 with sample complexity m m m
a = α C + 3 , b = m ( a 16 , 1 16 ) , T = m ( 2 a , β ) , δ 0 = min { δ , a 4 } , and k = ⌈ max { 16 ε log ( 1 δ 0 ) , 128 log ( 4 a ) } ⌉ . a=\frac{\alpha}{C+3},\quad b=m\left(\frac{a}{16},\frac{1}{16}\right),\quad T=m(2a,\beta),\quad\delta_0=\min\left\{\delta,\frac{a}{4}\right\},\quad\text{and}\quad k=\left\lceil\max\left\{\frac{16}{\varepsilon}\log\left(\frac{1}{\delta_0}\right),128\log\left(\frac{4}{a}\right)\right\}\right\rceil. a = C + 3 α , b = m ( 16 a , 16 1 ) , T = m ( 2 a , β ) , δ 0 = min { δ , 4 a } , and k = ⌈ max { ε 16 log ( δ 0 1 ) , 128 log ( a 4 ) } ⌉ . Let n 0 = T k b n_0=Tkb n 0 = T k b
We use Algorithm 7 with the parameters chosen above. Each call to Sampler invokes Algorithm 2 on a batch S j ∈ X k b S_j \in\mathcal{X}^{kb} S j ∈ X k b k k k b b b L b a s e L_{\mathrm{base}} L base Z j ∈ X Z_j \in\mathcal{X} Z j ∈ X F = Δ ( X ) \mathcal{F}=\Delta(\mathcal{X}) F = Δ ( X ) ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) L L L ( Z 1 , … , Z T ) (Z_1,\ldots,Z_T) ( Z 1 , … , Z T ) q ^ \hat{q} q ^
For inputs larger than n 0 n_0 n 0 n 0 n_0 n 0 n 0 n_0 n 0 Q Q Q
Privacy. By Proposition B.5 , each invocation of Sampler is ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) Lemma 2.5 ) therefore implies that ( Z 1 , … , Z T ) (Z_1,\ldots,Z_T) ( Z 1 , … , Z T ) ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) Proposition 2.4 the learner is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) δ 0 ≤ δ \delta_0 \le\delta δ 0 ≤ δ L L L Q Q Q
Utility. Fix p ∈ Δ ( X ) p \in\Delta(\mathcal{X}) p ∈ Δ ( X ) OPT : = inf q ∈ Q TV ( p , q ) \operatorname{OPT}:=\inf_{q\in Q}\operatorname{TV}(p,q) OPT := inf q ∈ Q TV ( p , q ) S 0 ∼ p k b S_0 \sim p^{kb} S 0 ∼ p k b q 1 , … , q k q_1,\ldots,q_k q 1 , … , q k η = C OPT + a 16 \eta=C\operatorname{OPT}+\frac{a}{16} η = C OPT + 16 a L L L b b b Pr [ TV ( q i , p ) ≤ η ] ≥ 15 16 \Pr[\operatorname{TV}(q_i,p)\le\eta]\ge\frac{15}{16} Pr [ TV ( q i , p ) ≤ η ] ≥ 16 15 i ∈ [ k ] i\in[k] i ∈ [ k ]
Let J = { i ∈ [ k ] : TV ( q i , p ) ≤ η } J=\{i\in[k]:\operatorname{TV}(q_i,p)\le\eta\} J = { i ∈ [ k ] : TV ( q i , p ) ≤ η } E = { ∣ J ∣ ≥ 7 k 8 } E=\{|J|\ge\frac{7k}{8}\} E = { ∣ J ∣ ≥ 8 7 k } { TV ( q i , p ) > η } \{\operatorname{TV}(q_i,p)>\eta\} { TV ( q i , p ) > η } 1 16 \frac{1}{16} 16 1 Pr [ E c ] ≤ exp ( − 2 k ( 1 8 − 1 16 ) 2 ) = e − k / 128 ≤ a 4 \Pr[E^c]\le\exp\left(-2k\left(\frac{1}{8}-\frac{1}{16}\right)^2\right)=e^{-k/128}\le\frac{a}{4} Pr [ E c ] ≤ exp ( − 2 k ( 8 1 − 16 1 ) 2 ) = e − k /128 ≤ 4 a
By Fact B.3 , the mode mechanism instantiated with ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) τ = 4 ε log ( 1 δ 0 ) \tau=\frac{4}{\varepsilon}\log\left(\frac{1}{\delta_0}\right) τ = ε 4 log ( δ 0 1 ) β S B M = δ 0 \beta_{\mathrm{SBM}}=\delta_0 β SBM = δ 0
On E E E c = 1 4 c=\frac{1}{4} c = 4 1 k k k 2 ( 1 − c ) ∣ J ∣ − k ≥ 5 k 16 ≥ k 4 ≥ τ 2(1-c)|J|-k\ge\frac{5k}{16}\ge\frac{k}{4}\ge\tau 2 ( 1 − c ) ∣ J ∣ − k ≥ 16 5 k ≥ 4 k ≥ τ
For each tuple q \mathbf{q} q μ q : = L ( Aggregate ( q ) ) \mu_{\mathbf{q}}:=\mathcal{L}(\operatorname{Aggregate}(\mathbf{q})) μ q := L ( Aggregate ( q )) Proposition B.2 with ℓ = 1 \ell=1 ℓ = 1 E E E TV ( μ q , p ) ≤ 8 η + δ 0 \operatorname{TV}(\mu_{\mathbf{q}},p)\le8\eta+\delta_0 TV ( μ q , p ) ≤ 8 η + δ 0 1 − e − k / 128 ≥ 1 − a 4 1-e^{-k/128}\ge1-\frac{a}{4} 1 − e − k /128 ≥ 1 − 4 a
Let R p : = L ( Sampler ( S 0 ) ) R_p:=\mathcal{L}(\operatorname{Sampler}(S_0)) R p := L ( Sampler ( S 0 )) S 0 ∼ p k b S_0\sim p^{kb} S 0 ∼ p k b B ⊆ X B\subseteq\mathcal{X} B ⊆ X R p ( B ) = E q [ μ q ( B ) ] R_p(B)=\mathbb{E}_{\mathbf{q}}[\mu_{\mathbf{q}}(B)] R p ( B ) = E q [ μ q ( B )]
TV ( R p , p ) = sup B ∣ E q [ μ q ( B ) − p ( B ) ] ∣ ≤ E q [ sup B ∣ μ q ( B ) − p ( B ) ∣ ] = E q [ TV ( μ q , p ) ] ≤ ( 8 η + δ 0 ) Pr [ E ] + Pr [ E c ] ≤ 8 η + δ 0 + e − k / 128 ≤ 8 C OPT + a 2 + a 4 + a 4 = 8 C OPT + a . \begin{aligned}
\operatorname{TV}(R_p,p)&=\sup_B\left|\mathbb{E}_{\mathbf{q}}[\mu_{\mathbf{q}}(B)-p(B)]\right|\\
&\le\mathbb{E}_{\mathbf{q}}\left[\sup_B|\mu_{\mathbf{q}}(B)-p(B)|\right]\\
&=\mathbb{E}_{\mathbf{q}}[\operatorname{TV}(\mu_{\mathbf{q}},p)]\\
&\le(8\eta+\delta_0)\Pr[E]+\Pr[E^c]\\
&\le8\eta+\delta_0+e^{-k/128}\\
&\le8C\operatorname{OPT}+\frac{a}{2}+\frac{a}{4}+\frac{a}{4}\\
&=8C\operatorname{OPT}+a.
\end{aligned} TV ( R p , p ) = B sup ∣ E q [ μ q ( B ) − p ( B )] ∣ ≤ E q [ B sup ∣ μ q ( B ) − p ( B ) ∣ ] = E q [ TV ( μ q , p )] ≤ ( 8 η + δ 0 ) Pr [ E ] + Pr [ E c ] ≤ 8 η + δ 0 + e − k /128 ≤ 8 C OPT + 2 a + 4 a + 4 a = 8 C OPT + a . The data-independent permutation preserves the joint distribution p T k b p^{Tkb} p T k b S 1 , … , S T S_1,\ldots,S_T S 1 , … , S T p k b p^{kb} p k b j ∈ [ T ] j\in[T] j ∈ [ T ] L ( Z j ) = R p \mathcal{L}(Z_j)=R_p L ( Z j ) = R p Z j Z_j Z j S j S_j S j ( Z 1 , … , Z T ) ∼ R p T (Z_1,\ldots,Z_T)\sim R_p^T ( Z 1 , … , Z T ) ∼ R p T
Applying the C C C L L L T = m ( 2 a , β ) T=m(2a,\beta) T = m ( 2 a , β ) R p R_p R p
TV ( q ^ , R p ) ≤ C inf q ∈ Q TV ( q , R p ) + 2 a \operatorname{TV}(\widehat{q},R_p)\le C\inf_{q\in\mathcal{Q}}\operatorname{TV}(q,R_p)+2a TV ( q , R p ) ≤ C q ∈ Q inf TV ( q , R p ) + 2 a with probability at least 1 − β 1-\beta 1 − β inf q ∈ Q TV ( q , R p ) ≤ OPT + TV ( p , R p ) \inf_{q\in\mathcal{Q}}\operatorname{TV}(q,R_p)\le\operatorname{OPT}+\operatorname{TV}(p,R_p) inf q ∈ Q TV ( q , R p ) ≤ OPT + TV ( p , R p )
TV ( q ^ , p ) ≤ TV ( q ^ , R p ) + TV ( R p , p ) ≤ C OPT + ( C + 1 ) TV ( R p , p ) + 2 a ≤ C OPT + ( C + 1 ) ( 8 C OPT + a ) + 2 a = ( 8 C 2 + 9 C ) OPT + ( C + 3 ) a = ( 8 C 2 + 9 C ) OPT + α . \begin{aligned}
\operatorname{TV}(\widehat{q},p)&\le\operatorname{TV}(\widehat{q},R_p)+\operatorname{TV}(R_p,p)\\
&\le C\operatorname{OPT}+(C+1)\operatorname{TV}(R_p,p)+2a\\
&\le C\operatorname{OPT}+(C+1)(8C\operatorname{OPT}+a)+2a\\
&=(8C^2+9C)\operatorname{OPT}+(C+3)a\\
&=(8C^2+9C)\operatorname{OPT}+\alpha.
\end{aligned} TV ( q , p ) ≤ TV ( q , R p ) + TV ( R p , p ) ≤ C OPT + ( C + 1 ) TV ( R p , p ) + 2 a ≤ C OPT + ( C + 1 ) ( 8 C OPT + a ) + 2 a = ( 8 C 2 + 9 C ) OPT + ( C + 3 ) a = ( 8 C 2 + 9 C ) OPT + α . Finally, log ( 1 δ 0 ) = max { log ( 1 δ ) , log ( 4 a ) } ≤ log ( 4 a δ ) \log\left(\frac{1}{\delta_0}\right)=\max\left\{\log\left(\frac{1}{\delta}\right),\log\left(\frac{4}{a}\right)\right\}\le\log\left(\frac{4}{a\delta}\right) log ( δ 0 1 ) = max { log ( δ 1 ) , log ( a 4 ) } ≤ log ( a δ 4 ) ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) k = O ( 1 ε log ( 4 a δ ) ) k=O\left(\frac{1}{\varepsilon}\log\left(\frac{4}{a\delta}\right)\right) k = O ( ε 1 log ( a δ 4 ) )
n 0 = T k b = O ( m ( a 16 , 1 16 ) m ( 2 a , β ) 1 ε log ( 4 a δ ) ) = O ( m ( α 16 ( C + 3 ) , 1 16 ) m ( 2 α C + 3 , β ) 1 ε log ( 4 ( C + 3 ) α δ ) ) , \begin{aligned}
n_0=Tkb=O\left(m\left(\frac{a}{16},\frac{1}{16}\right)m(2a,\beta)\frac{1}{\varepsilon}\log\left(\frac{4}{a\delta}\right)\right) \\
&=O\left(m\left(\frac{\alpha}{16(C+3)},\frac{1}{16}\right)m\left(\frac{2\alpha}{C+3},\beta\right)\frac{1}{\varepsilon}\log\left(\frac{4(C+3)}{\alpha\delta}\right)\right),
\end{aligned} n 0 = T k b = O ( m ( 16 a , 16 1 ) m ( 2 a , β ) ε 1 log ( a δ 4 ) ) = O ( m ( 16 ( C + 3 ) α , 16 1 ) m ( C + 3 2 α , β ) ε 1 log ( α δ 4 ( C + 3 ) ) ) , which proves the stated sample bound.
Algorithm 7 AgnosticPrivateLearner
Input: Dataset $S=(X_1,\ldots,X_n)$ with $n=Tkb$, a non-private $C$-agnostic learner $L$, and parameters $a,b,k,T,\beta,\varepsilon,\delta_0$.
Output: An estimate $\widehat{q}\in\Delta(\mathcal{X})$.
1: Define $L_{\mathrm{base}}(D):=L\left(D;\frac{a}{16},\frac{1}{16}\right)$.
2: Draw a data-independent permutation $\Pi\sim\mathop{\mathrm{U}}(S_n)$.
3: for each $j\in[T]$ do
4: $S_j\leftarrow(X_{\Pi((j-1)kb+1)},\ldots,X_{\Pi(jkb)})$.
5: $Z_j\leftarrow\operatorname{Sampler}(S_j;\ell=1,k,b,L_{\mathrm{base}},\varepsilon,\delta_0)$.
6: end for
7: $\widehat{q}\leftarrow L((Z_1,\ldots,Z_T);2a,\beta)$.
8: return $\widehat{q}$.Next, we present a generic agnostic private learner based on the non-private Minimum distance estimator of [26 ] . This automatically gives an agnostic private learner for every countable class whose Yatracos class has finite VC dimension.
Definition C.3 (Yatracos class). Let Q ⊆ Δ ( X ) \mathcal{Q}\subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) ( q , q ′ ) ∈ Q (q,q')\in\mathcal{Q} ( q , q ′ ) ∈ Q A q , q ′ ⊆ X A_{q,q'}\subseteq\mathcal{X} A q , q ′ ⊆ X q ( A q , q ′ ) − q ′ ( A q , q ′ ) = TV ( q , q ′ ) q(A_{q,q'})-q'(A_{q,q'})=\operatorname{TV}(q,q') q ( A q , q ′ ) − q ′ ( A q , q ′ ) = TV ( q , q ′ ) 13
Yat ( Q ) : = { A q , q ′ : q , q ′ ∈ Q } . \operatorname{Yat}(\mathcal{Q}):=\{A_{q,q'}:q,q'\in\mathcal{Q}\}. Yat ( Q ) := { A q , q ′ : q , q ′ ∈ Q } . Theorem C.4 (Minimum-distance estimator, [26 ] ). Let C > 0 C>0 C > 0 α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 ) Q ⊆ Δ ( X ) \mathcal{Q}\subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) 14 d = VC ( Yat ( Q ) ) < ∞ d=\operatorname{VC}(\operatorname{Yat}(\mathcal{Q}))<\infty d = VC ( Yat ( Q )) < ∞ p ∈ Δ ( X ) p\in\Delta(\mathcal{X}) p ∈ Δ ( X ) S ∼ p n S\sim p^n S ∼ p n n ≥ C ( d + log ( 2 / β ) ) / α 2 n\ge C(d+\log(2/\beta))/\alpha^2 n ≥ C ( d + log ( 2/ β )) / α 2 q ^ ∈ Q \widehat{q}\in\mathcal{Q} q ∈ Q
Pr [ TV ( q ^ , p ) ≤ 3 OPT + α ] ≥ 1 − β , \Pr[\operatorname{TV}(\widehat{q},p)\le3\operatorname{OPT}+\alpha]\ge1-\beta, Pr [ TV ( q , p ) ≤ 3 OPT + α ] ≥ 1 − β , where OPT : = inf q ∈ Q TV ( p , q ) \operatorname{OPT}:=\inf_{q\in\mathcal{Q}}\operatorname{TV}(p,q) OPT := inf q ∈ Q TV ( p , q )
The following corollary gives a generic agnostic private learner for any countable class with finite VC ( Yat ( Q ) ) \operatorname{VC}(\operatorname{Yat}(\mathcal{Q})) VC ( Yat ( Q ))
Corollary C.5 (Agnostic private learning Yatracos classes). Let C > 0 C>0 C > 0 α , β , ε , δ ∈ ( 0 , 1 ) \alpha,\beta,\varepsilon,\delta\in(0,1) α , β , ε , δ ∈ ( 0 , 1 ) Q ⊆ Δ ( X ) \mathcal{Q}\subseteq\Delta(\mathcal{X}) Q ⊆ Δ ( X ) d = VC ( Yat ( Q ) ) < ∞ d=\operatorname{VC}(\operatorname{Yat}(\mathcal{Q}))<\infty d = VC ( Yat ( Q )) < ∞ ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) p ∈ Δ ( X ) p\in\Delta(\mathcal{X}) p ∈ Δ ( X ) S ∼ p n S\sim p^n S ∼ p n n ≥ C ( d + 1 ) ( d + log ( 2 / β ) ) ε α 4 log ( 2 α δ ) n\ge C\frac{(d+1)(d+\log(2/\beta))}{\varepsilon\alpha^4}\log\left(\frac{2}{\alpha\delta}\right) n ≥ C ε α 4 ( d + 1 ) ( d + l o g ( 2/ β )) log ( α δ 2 ) q ^ ∈ Q \widehat{q}\in\mathcal{Q} q ∈ Q
Pr [ TV ( q ^ , p ) ≤ 99 OPT + α ] ≥ 1 − β , \Pr[\operatorname{TV}(\widehat{q},p)\le99\operatorname{OPT}+\alpha]\ge1-\beta, Pr [ TV ( q , p ) ≤ 99 OPT + α ] ≥ 1 − β , where OPT : = inf q ∈ Q TV ( p , q ) \operatorname{OPT}:=\inf_{q\in\mathcal{Q}}\operatorname{TV}(p,q) OPT := inf q ∈ Q TV ( p , q )
:::
Proof. In Algorithm 7, take L ( D ; t , ρ ) : = MDE ( D ; t , ρ ) L(D;t,\rho) := \operatorname{MDE}(D;t,\rho) L ( D ; t , ρ ) := MDE ( D ; t , ρ ) Theorem C.4 , this is a proper 3-agnostic learner for Q \mathcal{Q} Q m ( t , ρ ) = ⌈ C 0 d + log ( 2 / ρ ) t 2 ⌉ m(t,\rho) = \left\lceil C_0\frac{d+\log(2/\rho)}{t^2}\right\rceil m ( t , ρ ) = ⌈ C 0 t 2 d + l o g ( 2/ ρ ) ⌉ C 0 C_0 C 0 Theorem C.2 therefore makes Algorithm 7 ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) q ^ ∈ Q \widehat{q} \in\mathcal{Q} q ∈ Q TV ( q ^ , p ) ≤ 99 OPT + α \operatorname{TV}(\widehat{q},p) \le99\operatorname{OPT}+\alpha TV ( q , p ) ≤ 99 OPT + α 1 − β 1-\beta 1 − β
Its sample bound is n 0 = O ( m ( α 96 , 1 16 ) m ( α 3 , β ) 1 ε log ( 24 α δ ) ) n_0 = O\left(m\left(\frac{\alpha}{96},\frac{1}{16}\right)m\left(\frac{\alpha}{3},\beta\right)\frac{1}{\varepsilon}\log\left(\frac{24}{\alpha\delta}\right)\right) n 0 = O ( m ( 96 α , 16 1 ) m ( 3 α , β ) ε 1 log ( α δ 24 ) ) m ( α 96 , 1 16 ) = O ( d + 1 α 2 ) m\left(\frac{\alpha}{96},\frac{1}{16}\right) = O\left(\frac{d+1}{\alpha^2}\right) m ( 96 α , 16 1 ) = O ( α 2 d + 1 ) m ( α 3 , β ) = O ( d + log ( 2 / β ) α 2 ) m\left(\frac{\alpha}{3},\beta\right) = O\left(\frac{d+\log(2/\beta)}{\alpha^2}\right) m ( 3 α , β ) = O ( α 2 d + l o g ( 2/ β ) ) n 0 = O ( ( d + 1 ) ( d + log ( 2 / β ) ) ε α 4 log ( 2 α δ ) ) n_0 = O\left(\frac{(d+1)(d+\log(2/\beta))}{\varepsilon\alpha^4}\log\left(\frac{2}{\alpha\delta}\right)\right) n 0 = O ( ε α 4 ( d + 1 ) ( d + l o g ( 2/ β )) log ( α δ 2 ) ) □ \square □
For potentially infinite classes, Bun et al. [17 Theorem 4] give a private hypothesis selection guarantee depending on d = VC ( Yat ( Q ) ) d = \operatorname{VC}(\operatorname{Yat}(\mathcal{Q})) d = VC ( Yat ( Q )) α \alpha α H ⊆ Q \mathcal{H} \subseteq\mathcal{Q} H ⊆ Q TV \operatorname{TV} TV α \alpha α q ∈ Q q \in\mathcal{Q} q ∈ Q ( k , r ) (k,r) ( k , r ) sup h ∈ H ∣ { h ′ ∈ H : TV ( h , h ′ ) ≤ r } ∣ ≤ k \sup_{h\in\mathcal{H}}|\{h' \in\mathcal{H} : \operatorname{TV}(h,h') \le r\}| \le k sup h ∈ H ∣ { h ′ ∈ H : TV ( h , h ′ ) ≤ r } ∣ ≤ k ( k , 8 α ) (k,8\alpha) ( k , 8 α ) α \alpha α ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) O ( d + log ( 1 / β ) α 2 + log ( k / β ) + log ( 1 / δ ) ε ) O\left(\frac{d+\log(1/\beta)}{\alpha^2}+\frac{\log(k/\beta)+\log(1/\delta)}{\varepsilon}\right) O ( α 2 d + l o g ( 1/ β ) + ε l o g ( k / β ) + l o g ( 1/ δ ) ) TV ( q ^ , p ) ≤ 7 α \operatorname{TV}(\widehat{q},p) \le7\alpha TV ( q , p ) ≤ 7 α 1 − β 1-\beta 1 − β TV ( p , h ) ≤ α \operatorname{TV}(p,h) \le\alpha TV ( p , h ) ≤ α h ∈ H h \in\mathcal{H} h ∈ H Corollary C.5 removes both this requirement and the locally small cover assumption: finite d d d TV ( q ^ , p ) ≤ 99 OPT + α \operatorname{TV}(\widehat{q},p) \le99\operatorname{OPT}+\alpha TV ( q , p ) ≤ 99 OPT + α 1 − β 1-\beta 1 − β p p p
Omitted proof from Section 6
Here, we formally prove the guarantee for the boosted learner introduced in § 5.1 . Its core idea is confidence boosting: amplifying a learner’s constant success probability to 1 − β 1-\beta 1 − β
Proof of Theorem 6.1. Set α 0 = α 3 \alpha_0 = \frac{\alpha}{3} α 0 = 3 α β 0 = 1 8 \beta_0 = \frac{1}{8} β 0 = 8 1 δ 0 = min { δ , β 0 / 4 } \delta_0 = \min\{\delta,\beta_0/4\} δ 0 = min { δ , β 0 /4 } T = ⌈ 128 ln ( 1 / β ) ⌉ T = \lceil128\ln(1/\beta)\rceil T = ⌈ 128 ln ( 1/ β )⌉ β 0 \beta_0 β 0 c c c β \beta β T T T Theorem 5.1 , each private learner is ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) Lemma 2.5 ) gives the same privacy guarantee for the vector of estimates. Selecting p ^ j \widehat{p}_j p j Proposition 2.4 ). Since δ 0 ≤ δ \delta_0 \le\delta δ 0 ≤ δ ( ε , δ ) (\varepsilon,\delta) ( ε , δ )
For utility, Theorem 5.1 provides a block size c = O ( m ( β 0 64 m ( α 0 , β 0 / 4 ) , 1 16 ) 1 ε log ( 4 β 0 δ 0 ) ) c = O\left(m\left(\frac{\beta_0}{64m(\alpha_0,\beta_0/4)},\frac{1}{16}\right)\frac{1}{\varepsilon}\log\left(\frac{4}{\beta_0\delta_0}\right)\right) c = O ( m ( 64 m ( α 0 , β 0 /4 ) β 0 , 16 1 ) ε 1 log ( β 0 δ 0 4 ) ) TV ( p ^ t , p ) < α 0 \operatorname{TV}(\widehat{p}_t,p) < \alpha_0 TV ( p t , p ) < α 0 1 − β 0 1-\beta_0 1 − β 0 p ∈ Q p \in\mathcal{Q} p ∈ Q T = { t ∈ [ T ] : TV ( p ^ t , p ) < α 0 } \mathcal{T} = \{t \in[T] : \operatorname{TV}(\widehat{p}_t,p) < \alpha_0\} T = { t ∈ [ T ] : TV ( p t , p ) < α 0 } Pr [ ∣ T ∣ ≤ T 2 ] ≤ exp ( − 2 T ( 1 2 − β 0 ) 2 ) ≤ β \Pr\left[|\mathcal{T}| \le\frac{T}{2}\right] \le\exp\left(-2T\left(\frac{1}{2}-\beta_0\right)^2\right) \le\beta Pr [ ∣ T ∣ ≤ 2 T ] ≤ exp ( − 2 T ( 2 1 − β 0 ) 2 ) ≤ β ∣ T ∣ > T / 2 |\mathcal{T}| > T/2 ∣ T ∣ > T /2 T \mathcal{T} T 2 α 0 2\alpha_0 2 α 0 N t ≥ ∣ T ∣ N_t \ge|\mathcal{T}| N t ≥ ∣ T ∣ t ∈ T t \in\mathcal{T} t ∈ T j j j N j ≥ ∣ T ∣ > T / 2 N_j \ge|\mathcal{T}| > T/2 N j ≥ ∣ T ∣ > T /2 N j N_j N j i ∈ T i \in\mathcal{T} i ∈ T TV ( p ^ j , p ) ≤ TV ( p ^ j , p ^ i ) + TV ( p ^ i , p ) < 3 α 0 = α \operatorname{TV}(\widehat{p}_j,p) \le\operatorname{TV}(\widehat{p}_j,\widehat{p}_i)+\operatorname{TV}(\widehat{p}_i,p) < 3\alpha_0 = \alpha TV ( p j , p ) ≤ TV ( p j , p i ) + TV ( p i , p ) < 3 α 0 = α n = T c n = Tc n = T c β 0 = 1 / 8 \beta_0 = 1/8 β 0 = 1/8 δ 0 = min { δ , 1 32 } \delta_0 = \min\{\delta,\frac{1}{32}\} δ 0 = min { δ , 32 1 } log ( 4 β 0 δ 0 ) = O ( log ( 4 δ ) ) \log\left(\frac{4}{\beta_0\delta_0}\right) = O\left(\log\left(\frac{4}{\delta}\right)\right) log ( β 0 δ 0 4 ) = O ( log ( δ 4 ) ) T = O ( log ( 4 β ) ) T = O\left(\log\left(\frac{4}{\beta}\right)\right) T = O ( log ( β 4 ) )
Finally, if m ( α , β ) = poly ( 1 α , log ( 1 β ) ) m(\alpha,\beta) = \operatorname{poly}\left(\frac{1}{\alpha},\log\left(\frac{1}{\beta}\right)\right) m ( α , β ) = poly ( α 1 , log ( β 1 ) ) poly ( 1 α , log ( 1 β ) , 1 ε , log ( 1 δ ) ) \operatorname{poly}\left(\frac{1}{\alpha},\log\left(\frac{1}{\beta}\right),\frac{1}{\varepsilon},\log\left(\frac{1}{\delta}\right)\right) poly ( α 1 , log ( β 1 ) , ε 1 , log ( δ 1 ) ) □ \square □
