Optimized Tradeoffs for Private Prediction with Majority Ensembling
Authors: Shuli Jiang
Qiuyi Zhang
Gauri Joshi
Venue: Accepted by TMLR ()

Abstract: We study a classical problem in private prediction, the problem of computing an $(m\epsilon, \delta)$-differentially private majority of $K$ $(\epsilon, \Delta)$-differentially private algorithms for $1 \leq m \leq K$ and $1 > \delta \geq \Delta \geq 0$. Standard methods such as subsampling or randomized response are widely used, but do they provide optimal privacy-utility tradeoffs? To answer this, we introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm. It is parameterized by a data-dependent noise function $\gamma$, and enables efficient utility optimization over the class of all private algorithms, encompassing those standard methods. Surprisingly, we show that an $(m\epsilon, \delta)$-private majority algorithm with maximal utility can be computed tractably for any $m \leq K$ by a novel structural result that reduces the infinitely many privacy constraints into a polynomial set. In some settings, we show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility. Lastly, we demonstrate the strong empirical effectiveness of our first-of-its-kind privacy-constrained utility optimization for ensembling labels for private prediction from private teachers in image classification. Notably, our DaRRM framework with an optimized $\gamma$ exhibits substantial utility gains when compared against several baselines.

Published in Transactions on Machine Learning Research (November/2005
Optimized Tradeoffs for Private Prediction with Majority Ensembling
Shuli Jiang
shulij@ondrew.com cww. edu
Robotics Instibute, Carnegie Mellon University
Qiuyi (Richard) Zhang
qiuyiz@yoogle.c com
Google Dind
Gauri Joshi
geurijShandrew. cmau. edu
Electrical and Computer Engineering, Carnegie Mellon University
Reviewed on OpenReview: https: opwreevee.....e...e net/ htt/formm? id- duJluAokMS
Abstract
We study a classical problem in private prediction, the problem of computing an (me, 6)- differentially private majority of K (e, diffeerreett private algorithms for 1 S m S K and 8 2 A 2 0. Standard methods such as subsampling or randomized response are widely used, but do they provide optimal privacy-utility tradcoffs? To answer this, introduce the Dala-dependent Randomized Response Majority (DaRRM) algorithm. It is parameterized by data-dependens noise function 7, and enables efficient utility optimization over the class of all private algorithms, encompassing those standard methods. We show that maximizing the utility of an (me, 6)-private majority algorithm can be computed tractably through an optimization problem for any m S K by a novel structural result that reduces the infinitely many privacy constraints into a polynomial set. In some settings, we show that DaRRM provably enjoys privacy gain of factor of over common baselines, with fixed utility. Lastly; we demonstrate the strong empirical effectiveness of our first-ffiis-kind constrccd utility optimization for ensembling labels for private prediction from private teachers in image classification. Notably, our DaRRM framework with an optimized y exhibits substantial utility gains when compared against several baselines.
1 Introduction
Differential privacy (DP) is a widely applied framework for formally reasoning about privacy leakage when releasing statistics on a sensitive database Erlingsson et al. (2014); Cormode et al. (2018). Differential privacy protects data privacy by obfuscating algorithmic output, ensuring that query responses look similar on adjacent datasets while preserving utility as much as possible Dwork et al. (2006).
Privacy in practice often requires aggregating or composing multiple private procedures that are distributed for data training efficiency. For example, it is common to aggregate multiple private algorithmic or model outputs in methods such as boosting or calibration (Sagi & Rokach 2018). In federated learning, model training is distributed across multiple edge devices. Those devices need to send local information, such as labels or gradients Konečný el al. (2016), to an aggregating server, which often honest but curious about the local training data. Hence, the output from each model at an edge device needs to be privatized locally before being sent the server. When translating from a local privacy guarantee a centralized one, one needs to reason about the composition of the local privacy leakage Naseri et al. 2020) Therefore, we formally ask the following:
Problem 1.1 (Private Majority Ensombling (Ilustraated Figure 1). Consider K 2 (c, diffffrrrnnti private mechanisms Mj.... Mg for K odd. Given a dataset D, each mechanism outputs a binary answer that is, M, D (0,1), Vi E [K]. Given privacy allowance 1 s < K, m R and a failure probability

---

Published in Transactions on Machine Learning Research (November/2004
2 A 0, 8, (0,1), how can one mazimize the utility of an difffeerretllll private mechanism A to compute the majorily function S2.... ,K), where S; ~ M,(D)?
Sensitive Dataset
(c, DP Mechanism M,
(e,A)-DP
(e, A)PP Mechanism Mx
Mechanism M₁
Sample
S1 ~ (D)
S₂ M2(D)
Sx (MxM)
Output
g gS, Sk.,
g: majority/mode function
m S K,m E I::
privacy allowance 2 8, E [0, 1):
Goal
Algorithm A computes g and A is (me, 8)DDP
fallure probability
Figure 1: An illustration of the problem setting. The inputs are the dataset. D and K (e, Addifferrrenl private mechanisms M,,...,MM One draws samples S, ~ MD) and computes an aggregated output g( Sk) based on all observed samples. Our goal is to design a randomized algorithm A that approximately computes g and is (me, -i-ifferrny private for 1 S m < K and 8 z A 2 0. We focus on g being the majority function..
The majority function g is often used in private prediction, where one studies the privacy cost of releasing one prodiction Dwork Feldman (2018) and exploits the fact that relcasing only the aggregated output on sharded models significantly more private than releasing each prediction. For example, this occurs in semi-supervised knowledge transfer with private aggregated teacher ensembles (PATE) Papernot et al. 22017 2018), in ensemble learning algorithms Jia & Qiu (2020); Xiang et al. (2018). machine unlearning Bourtoule ct al. 20021) private distributed learning algorithms such as Stochastic Sign-SGD Xiang & Su (2023), and in ensemble feature selection Liu et al. (0118). Private prediction is also shown to be a competitive Lechnique in data-adaptive settings, where the underlying dataset is changing slowly over time, to quickly adjust to online dataset updates Zhu et al.] (2023). Furthermore, to address the large privacy loss of private prediction under the many-query regime, there has been recent works in everlasting private prediction that extends privacy guarantees with repeated, possibly infinite, queries without suffering linear increase in privacy loss Naor
ct al.
2023 Stemmer 2024)..
These works, however, rely often on the standard sensitivity analysis of g to provide a private output and thus generally provide limited utility guarantees. This is because the maximum sensitivity of g can be too pessimistic in practice, as observed in the problem of private hyperparameter optimization (Liu & Talwar 2019). On the other hand, for private model ensembling, a naive way to bound privacy loss without restrictive assumptions to apply simple composition (Theorem [.2) or general composition (Theorem 2.3 a tighter version compared to advanced composition) to reason about the final privacy loss after aggregation. A black-box application of the simple composition theorem to compute g would incur a Ke privacy cost in the pure differential privacy setting, that is, 8 = 0, or if one is willing to tolerate some failure probability 6, general composition would yield a O(VKe) privacy cost Kairouz et al. 2015).. Thus, a natural baseline algorithm A private applies privacy amplification by subsampling and randomly chooses m
that is (me, of the K mechanisms aggregate and returns the majority of the subsampled mechanisms. This technique is reminiscent of the subsampling procedure used for the maximization function g (Liu & Talwar 2019) or some general techniques for privacy amplification in the federated setting via shuflling (Erlingsson al. 2019
However, standard composition analysis and privacy amplication techniques can be suboptimal for computing private majority, in terms of both utility and privacy. Obscrve that if there is a clear majority among one can add less noise. This is because each mechanism M, is (e, A)- differentially private already, and hence, is less likely to change its output on a neighboring dataset by definition. This implies the majority outcome is unlikely to change based on single isolated changes D. Furthermore, composition theorems make two pessimistic assumptions: 1) the worst-case function g and the dataset D are considered, and 2) all intermediate mechanism outputs (D). ..., Mx (D) are released,
the outputs of (P),.....
2

---

Published in Transactions on Machine Learning Research (November/2005
rather than just the final aggregate. Based on these observations, is it possible then to improve the utility of computing private majority, under a fixed privacy loss?
1.1 Our Contributions
We give a (perhaps surprising) affirmative answer to the above question by using our novel dala-dependent randomized response framework (DaRRM), which captures all private majority algorithms, we introduce tractable noise optimization procedure that maximizes the privacy-utility tradeoffs. Furthermore, we provably achieve a constant factor improvement in utility over simple subsampling by applying data-dependent noise injection when Mj's s are i.i.d. and 8 = O. To our knowledge, this is the first of its work of its kind that gives a tractable utility optimization over the possibly infinite set of privacy constraints.
Data-dependent Randomized Response Majority (DaRRM). We generalize the classical Randomized Response (RR) mechanism and the commonly used subsampling baseline for solving Problem 1.1 and propose general randomized response framework DaRRM (sce Algorithm D which comes with customizable noisc function 7. We show that DaRRM act ually captures all algorithms computing the majority whose outputs are at least as good as a random guess (see Lemma 3.3) by choosing different 7y functions.
Designing Y with Provable Privacy Amplification. The choice of the y function in DaRRM allows us to explicitly optimize noise while trading off privacy and utility. Using structural observations, we show privacy amplification by a factor of 2 under mild conditions over applying simple composition in the pure differential privacy sctting when the mechanisms M, 's are i.i.d. (sce Theorem 4.1
Finding the Best through Dimension-Reducedd Optimization. We further exploit the generality of DaRRM by applying a novel optimization-baseeee approach that applies constrained optimization to find a data-dependent that maximizes some measure of utility. One challenge is that there are infinitely many privacy constraints, which are necessary for DaRRM with the optimized y to satisfy the given privacy loss. We show that we can reformulate the privacy constraints, which are infinite dimensional, to a finite polynomial-sized constraint set, allowing us to efficiently constrain the optimization problem to find the best 7, even for approximate differential privacy (see Lemma 5.1). Empirically, we show that with small and e, the optimized y (see Topt in Figure 2) achieves the best utility among all y functions, even compared to the subsampling and the data-independent bascline. To our knowledge, this is the first utility maximization algorithm that optimizes over all private algorithms by constrained optimization ion with dimension reduction.
Experiments. In downstream tasks, such as semi-supervised knowledge transfer for private image classi- fication, we compare our DaRRM with an optimizod y to compute the private label majority from private teachers against PATE Papernot al. (2018), which compules the private label majority from non-private teachers. We fix the privacy loss of the output of both algorithms to be the same and find that when the number of teachers K is small, DaRRM indeed has higher utility than PATE, achieving 10%-159% and 30% higher accuracy on datasets MNIST and Fashion -MMISS, respectively.
2 Background
2.1
Related Work
Private Composition. Blackbox privacy composition analysis often leads to pessimistic utility guarantees. In the blackbox composition setting, one can do no better than the O(Kc) privacy analysis for pure differential privacy Dwork et al. (2014). For approximate differential privacy, previous work has found optimal constants for advanced composition by reducing the binary case of hypothesis testing with randomized response; and optimal tradeoffs between c, 5 for black box composition are given in Kairouz et al. (2015), where there could be a modest improvement 20%.
Thus, for specific applications, previous work has turned to white-box composition analysis for improved utility. This includes, for example, moment accountant for private SGD Abadi al. (2016) and the application of contractive maps in stochastic convex optimization Feldman et al. (2018). For the specific case of model ensembles, Papernot et al. (2018) shows data-dependent privacy bound that vanishes as the probability of
3

---

Published in Transactions on Machine Learning Research (rrember/202//
disagreement goes to O. Their method provides no utility analysis but they empirically observed less privacy loss when there is greater ensemble agreement.
When g is the maximization function, some previous work shows that an approximately maximum value can be outputted with high probability while incurring O(e) privacy loss, independently of K. Liu & Talwar (2019) proposed random stopping mechanism for m = 1 that draws samples uniformly at random from (D) at each iteration. In any given iteration, the sampling halts with probability y and the final output is computed based on the samples collected until that time. This leads to final privacy cost of only 3e for the maximization function 9, which can be improved to 2E (Papernot & Steinke 2022). In addition to the aforementioned works, composing top-k and exponential mechanisms also enjoy slightly improved composition analysis via a bounded-range analysis Durfee & Rogers (201 Dong et al. (2020).
Bypassing the Global Sensitivity. To ensure differential privacy, it is usually assumed the query function g has bounded global scnsitivity that is, the output of g does not change much on any adjacent input datasets differing in one entry. The noise added to the output then proportional to the global sensitivity of 9. If the sensitivity is large, the output utility will thus be terrible due to a large amount of noises added. However, the worst case global sensitivity can be rare in practice, and this observation has inspired line of works on designing private algorithms with data-dependent sensitivity bound to reduce the amount of noises added.
Instead of using the maximum global sensitivity of g on any dataset, the classical Propose-Teste Resteee framework of Dwork Dwork & Lei (2009) uses a local sensitivity value for robust queries that is tested privately and if the sensitivity value is too large, the mechanism is halted before the query release. The halting mochanism incurs some failure probability but deals with the worst-case scnsitivity situations, while allowing for lower noise injection in most average-case cases.
One popular way to estimate average-case case sensitivity is to use the introducing the notion of perturbation stability, also known as local sensitivity of a function g on a datasct D Thakurta & Smith (2013); Dwork et al. (2014), which represents the minimum number of entries in D needs to be changed to change (D). One related concept is smooth sensitivity, a measure of variability of g in the neighborhood of cach dataset instance. To apply the framework under smooth sensitivity, one needs to privately estimate function's 's local sensitivity Lg and adapt noise injection to be order of Oz2)), where I., can often be as small as O(e="), where n = |2], the total dataset size Nissim et al. (2007). Generally, the private computation of the smooth sensitivity of a blackbox function is nontrivial but is aided by the Subsample and Aggregate approach for certain functions.
aaataplleaan-Aggggggatt framework by
These techniques hinge on the observation that a function with higher stability on requires less noise to ensure worst case privacy. Such techniques are also applied to answer multiple online functions/ functions/queries in model-agnostic learning Bassily et al.) 2018)) However, we highlight two key differences in our setting with weaker stability assumption. First, in order to estimate the perturbation stability of g on D, one needs to downsample or split 'D into multiple blocks Thakurta & Smith (2013); Dwork et al. (0014); Bassily et al. (2018), D,,..., DB , and estimate the perturbation slability based on the mode of g (D)), (.).,...,,(()))) (Dp)). This essentially reduces the amount of change in the output of g due to a single entry in D, with high probability and replaces the hard-to-estimate perturbation stability of g with an masy-to-comput perturbation stability of the mode. Such a notion of stability has also been successfully applied, along with the sparse vector technique, for model-agnostic private learning to handle exponentially number of queries to model [asssly al. (2018). Note that in these cases, since private stochastic test is applied, one cannot achieve pure differential privacy Dwork et al. (2014). In practice, c.g. federated lcarning, however, one does not have direct access to D, and thus it is impractical to draw samples from or to split D. Second, to ensure good utility, one relies on key assumption, i.e. the subsampling stability of g, which requires gDD) = g(D) with high probability over the draw of subsamples D.
Although our intuition in designing DaRRM also relies on the stability of the mode function g, previous usage of stability to improve privacy-utility tradcoffs, e-g., propose-test-releass Vadhan (2017); Dwork et al. (201)). requires the testing of such stability, based on which one adds larger (constant) noise 7. This can still lead to adding redundant noise in our case.
4

---

Published in Transactions on Machine Learning Research (November/2005
Optimal Randomized Response. Holohan et al. (2017) and Kairouz al. (2015) show that the classical Randomized Response (RR) mechanism with constant probability of faithfully revealing the true answer is optimal in certain private estimation problems. Our proposed DaRRM framework and our problem setting is a generalized version of the ones considered in both Holohan et al. (2017) and Kairouz et al. (2015), which not only subsumes RR but also enables a data-dependent probability, or noise addition.
While RR with constant probability can be shown optimal in problems such as private count queries or private estimation of trait possession in population, it is not optimal in other problems, such private majority ensembling, since unlike the former problems, changing one response of the underlying mechanisms does not necessarily change the output of the majority. To explicitly compute the minimum amout of noise required, one needs the output distributions of the underlying mechanisms but this is unknown. To resolve this, our proposed DaRRM framework adds the amount of noise dependent on the set of observed outcomes from the underlying private mechanisms, S, which is a random variable of the dataset and hence a proxy. This enables DaRRM calibrate the amount of noise basod on whether the majority output is likely change. The amount of noise is aulomatically reduced when the majority output is not likely to change.
Second, Holoban et al. 2017) and Kairouz et al. 2015 both consider special case in our setting where all K private mechanisms are ii.d., while our approach focuses on the more general setting where each private mechanism can have a different output distribution.
Learning Good Noise Distribution. There have been limited works that attempt to derive or learn a good noise distribution that improves the utility. For deep neural networks inference, Mireshghalaah et al. (2020) attempts learn the best noise distribution to maximizing utility subject to entropy Lagrangian, but formal privacy guarantees were derived. For queries with bounded scnsitivity, Geng & Viswanath (2015) demonstrate that the optimal noise distribution is in fact a staircase distribution that approaches the Laplacian distribution as e - 0.
Private Prediction. Instead of relcasing a privately trained model as in private learning, private prediction hides the models and only releases privale outputs. Private prediction has been shown as a practical alternative compared to private learning, as performing private prediction is much easier compared
private learning
wide range of tasks Dwork & Feldman (2018); Naor et al. (2023) van der Maaten & Hannun (2020) Although privately trained model can make infinitely many predictions at the inference time without incurring additional privacy loss, since different ial privacy is closed under post-processing, it has been shown recently that it is indeed possible to make infinitely many private predictions Naor et al. (2023) with a finite privacy loss for specific problems.
2.2 Preliminaries
We first introduce the definition of differential privacy, simple composition and general composition as follows. The general composition Kairouz et al. (2015) gives a near optimal and closed-form bound on privacy loss under adaptive composition, which improves upon advanced composition Dwork et al. (0144).
Definition 2.1 (Differential Privacy (DP) Dwork et al. (2014)) ). A randomized mechanism M: D - R with
a domain D and range satisfies (e, diffferrrll privacy for e, ö 2 0 if for any two adjacent datasets D. D' and for any subset of outputs S R it holds that Pr(M(D) E $] S e Pr[M(D') E S] + 8.
is
often called pure differential privacy; while > 0 is often called approzimate differential privacy-
Theorem 2.2 (Simple Composition Dwork et al. (2014)). For any e >> O and ó E [0, 1], the class of differential privacy under k-foldd adoptive composition.
(c, differffrrentilllyy private mechanisms satisfy (ke, kō)
Theorem 2.3 (General Composition (Theorem 3.4 of Kairouz et al. (015))) )). For any e 0, [0, 1] and 8' 10, the class of (c, 8) diffferrrntll private mechanisms satisfies (c', (1 5) 8')) -iffeeeffrettaal privacy under k-fold adoptive composition for
(e-- 18-11p 1)ck
Vke² 8' ) (e - 11ek
é' é' min ke,
+ +eV 2 log(e +
+ e 2k log(1188)
e +
e +1
We then formalize the error and utility metric in our problem as follows:
5

---

Published in Transactions on Machine Learning Research (November/2005
Definition 2.4 (Error Metric and Utility Metric). For the problem setting in Definition 1.1 let the observed (rundom) outcomes set be S = (S Sx),, where S; MD) For a fixed DD we define the error of on algorithm A, i.e., E(A), in computing the majority function as the Total Variation (TV) distance between ((S) and A(D). Specifically,
= = DDv(((S) A(D) = (P((A(D) = 1] Pr(g(() = =1]
and the ulilily is defined 1 - E(A).
Notation. Throughout the paper, we use the same notations defined in Problem 1.1 and Definition 2.4 Furthermore, let D and D' to denote a pair of adjacent datasets with one entry being different. Also, let P: (D) = 1] and pf (r'M,(D')
1], Vi E [K]. We omit the subscript i when all p.'s or p/'s are equal. I(.} denotes the indicator function and [K] = (1,2,.... K}. For the purpose of analysis, let. ((D) Σ (D) E {0, I,..,, K}, i.e. the (random) sum of all observed outcomes on dataset D. D is omitted when the context is clear. Unless specified, we use the noise function y {0, 1,..,,,, K} [0. 1] input to algorithms to calibrate the probabilistic noise injection. Unless specified, the privacy allowance R.
3 Private Majority Algorithms
since the output The very first approach to consider when solving private majority ensembling (Problem 1.1 is binary, is the classical Randomized Response (RR) mechanism Dwork et al. (2014), where one flips a biased coin with a constant probability Pconst E [o, 1]. If the coin lands on head with probability Peonst, output the true majority basc on K samples; if not, then simply output noisy random answer. However, to make the output (me, d)diffeernt private, the success probability Pronst can be at most 0 ((m) (or 0 m when = (or 6 > 0) (see Appendix
A.I which is too small for any reasonable utility.
The key observation for improved utility is that the probability success should not be a constant, but should depend on the umpublished set of observed outcomes from the mechanisms S. Tf we see many I's or 0's in S, then there should be clear majority even on adjacent datasets. On the other hand, if we see about half I's and half O's, this means the majority highly volatile to data changes, which implies we need more noise to ensure privacy. In summary, if we calibrate the success probability based on S to smoothly increase when there is a clear majority, we can improve the utility without affecting privacy.
Subsampling. One natural baseline is outputting the majorily of m out of K randomly subsampled mechanisms (without replacement), given a privacy allowance m E [K]. Suppose 2 mA, the privacy loss of the aggregated output can be reasoned through simple composition or general composition. Interestingly, we show out outputing the majority of m out of K subsampled mechanisms corresponds to RR with non-consland probability Py = 7' (DD)), which is set by a polynomial function Ysub : {0..... K) - [0, 1] based the sum of observed outcomes L(D) in Lemma 3.1 (see full proof in Appendix A.2p. Intuitively, subsampling may be seen implicitly adding noise by only outputting based on a randomly chosen subset of the mechanisms; therefore this implicit. noise is inherently data-dependent on L(D).
Lemma 3.1. Consider Problem 1.1 with the privacy allowance m E [K]. Consider the dala-dependent algorithm that computes L(D) and then applies RR with probability p-y pf = (T), where E {0, 1, .., K} is the value of L(D), i.e., the (random) sum of observed outcomes on dataset D, and Ysub 10,1,..., K} [0, 1] is
1 - 2-
if m is odd
(l = 7/8wb -1)
(
2- -
if m even
then the majority of m out of K subsampled mechanisms without replacement and the output of our data- dependent RR algorithm have the same distribution.
One thing special about subsampling is that when m 1, it indeed results in the optimal error, which we show in Lemma 3.2 as follows. See a full proof in Appendix A.3 Note that when 1, subsampling outputs

---

Published in Transactions on Machine Learning Research (November/2005
majority of 1 with probability exactly k Ex= Pr- This lower bound only applies to the case when 1, since when m > 1, the probability of subsampling outputting a majority of 1 is not necessary 1 K E Ps.
Lemma 3.2 (Lower Bound on Error when m 1). Let A be an (e, -ifffefrerntl private algorithm, [0, 2), that computes the majority of K ddff-eeifrrn private mechanisms MI...., Mk, where M, : D {0, 1} on dataset 'D and (D) = 1] = Pt, Vi E [K]. Then, the error
where e E (0. 2) and
((A) 2 Pr(g(S) = + 2i Pil, where g(S) is the probability of the true majority oulput being 1 as
K
defined in Definition 1.1
Algorithm (aRRM()): Data-dependent Randomized Response Majority
1: Input: K (e, A)-DP mechanisms {M noise function y : {0, 1] + [0, 1] (in our specific setting
y: -0,,,..... K} + [0, 1l), dataset D, privacy allowance 1 1 m S K, failure probability 8 2 2 0 Output: (me, o)-DP majority vote of (M)
S = [k)),, where S M(())
C C-
Set probability py (S) (in our setting P., + (())
Flip the py- biased coin
7: if Head (with probability Py) then
8: Output 2 }
9: else
10: Output 0/1 with equal probability
11: end if
Data-dependent Randomized Response (DaRRM). Does subsampling give optimal utility when m > 1? Inspired by the connection between RR and subsampling, we propose Data-dependent Randomized Response Majority (DaRRM) in Algorithm [ to study optimizing privacy-utility tradeoffs in private majority ensembling. In particular, DaRRM has non-constand success probability py that is set by parameterized noise function 7, which in turn depends on the set of observed outcomes S = (S,...., S,., J. In fact, we can show that DaRRM is general: any reasonable algorithm A, name one whose output is least as good a random guess, can be captured by the DaRRM framework in Lemma. 3.3 (see full proof in Appendix A.4. We denote DaRRM instantiated with a specific noise function by DaRRM,
Lemma 3.3 (Generality of DaRRM). Let A be any randomized algorithm to compute the majority function on S such that for all S, Pr(A(S) = g{) 2 1/2 (i.e. A is at least as good as random guess). Then, there evists a a general function 7 {0, 1 1] 1 + [0, 1] such that if one sels p4 by 7SS) in DaRRM, the oulpul distribution of DaRRM, the same as the output distribution of A.
Designing the Y Function. With the DaRRM framework, we ask: how to design a good y function that maximizes the utility? First, we introduce two characteristics of y that do not affect the utility, while simplifying the analysis and the empirical optimization:
(a) A function of the sum of observed samples: Since the observed samples set is a permutation- invariant set, sufficient statistic that captures the full state of S is L = Σx St. the sum of observed outcomes. This allows us to reduce (S))= = xC)). Hence, in the rest of the poper, we focus on Y {0, 1,....Ky K) - [0, 1].
(b) Symmetric around K, If y is asymmetric, we can symmetrize by reflecting one region about K and achiove better or equal expected utility, where the utility is summed over symmetric distributions of Pc-
Note that 7su6 satisfies both characteristics. Now, recall L(D) and L(D') are the sum of observed outcomes on adjacent datasets D and D'. Also, recall p; = Pr[M = 1] and pf = (D') = 1] are the output probabilities of the mechanism M, on D,D'. To design good noise function & in DaRRM, we start by deriving conditions for y function such that DaRRM,, is (me, d)dfifferentially private in Lemma 3.4 (sce a full proof in Appendix A.5
7

---

Published in Transactions on Machine Learning Research (November/2005
Lemma 3.4 (r privacy condition). Consider using DaRRM (Algorithm 1 to solve Problem 1.1 let ay Pr(C(D) =1 and 0f (D' = =], where 'D and DD' are adjacent dalasels and I {O...., K}. For noise function y : {0, ,,...,K,, K} - [0, 1] such that 7(1) = 7 - 1l, DaRRM, is (me, o) -idifffernttialyy private if and only if for all 0q, of, the following holds,
7)) S e -1 + 20
(1)
where f is colled the privacy cost objective and
K
PK P...........k...)) Pki7)= =
(em 77() +
(a-- - e c²" 7())
4 Provable Privacy Amplification
We thcorctically demonstrate that privacy provably amplified under improved design of y in our DaRRM framework. Specifically, we show when the mechanisms are i.idd and ō = O, we gain privacy amplification by factor of 2 compared to the naive subsampling baseline by carefully designing 7,
Theorem 4.1 (Provable Privacy Amplification by 2). Consider using DaRRM (Algorithm 7 to solue
Problem 1.1 with i. mechanisms {M:) i.c., Pj = P, pl, p', Vi E [K], the privacy allowance m [K]
and d A = 0. Let the noise function y 1. K} - [0. 1] be thal:
if m > K+1
2 (1) = 1 and if m < K-1
1- 1- 2h(1) 2h(11) -1 A K+1
4 < K-1
(()
(-L)) where h(1) Σ 2m-1 () i= >mmm
then DaRRM, is mc-differentially private.
&
corresponds to outputting the majority based on subsampling 2m 1 outcomes, from Lemma 3.1 However, the subsampling baseline, whose privacy loss is reasoned through simple composition, would have indicated that one can only output the majority based on m outcomes, therefore implying a 2x privacy gain. When 2 K+1 the above theorem 2
Interpretation. First, when m < K-1 is small, the 7() in Theorem 4.1
indicates that we can a constant 7 1, which implies we are optimally outputting the true majority with noise while still surprisingly ensuring privacy.
Intuition. This 2x privacy gain is intuitively possible because the majority is only dependent on half of the mechanisms" outputs, therefore the privacy leakage is also halved. To see this, we start by analyzing the privacy cost objective in Eq. 31 where with a careful analysis of its gradicnt, we show that the maximum indoed occurs (p*,
p'*) "p",p"" (0, 0) when y satisfies certain conditions. Now, when (p", ) + O, note that the probability ratio of outputting with 2m outcomes is approximately e""c, where dependence on m follows because the probability of outputting 1 is dominated by the probability that exactly m mechanisms output 1. To rigorize this, we derive sufficient conditions for y functions that satisfy max(g,r) f p': f00, 0; S e indicated by Lemma 3.4 to ensure DaRRM to be me-differentially private and a more detailed overview and the full proof can be found in Appendix B
5 Optimizing the Noise Function Y in DaRRM
Theoretically designing and extending privacy amplification results to the 8 > 0 case is difficult and it is likely that our crafted y is far from imll On the other hand, one can optimize for such > that maximizes the utility but this involves solving a 'Semii-iniiite Programming" problem, due to the infinitely many privacy constraints, which are the constraints in the optimization problem necessary to ensure DaRRM with the optimized & satisfy given privacy loss. Solving a "Semi-infinite Programming" problem in general is non-tractable, but we show that in our specific setting this is in fact tractable, proposing novel learning
8

---

Published in Transactions on Machine Learning Research (irember/202//
approach based on DaRRM that optimize the noise function to maximize the utility. To the best of our knowledge, such optimization, presented as follows, is the first of its kind:
min EpI.P.....PK- (1tP=..px>/(((DRMMM.)
(e(DaRRM
(2)
vE(0.1]
s.t.
max f(p...... PID.....PP.PP........... S c - -1+ +8
(3)
((P.P.)AAA)
71) = 7 1), E ,0, K}
where f is the privacy cost objective as defined in Lemmaa 3.4 F; is the feasible region where (pi, (p).p() lies due to each mechanism M, being e-differentially private. Observe that since 7 is symmetric around & need to optimize K+1 variables instcad of K +1 variables. T is the distribution from which .......PK. are drawn. We want to stress that no prior knowledge about the dataset or the amount of consensus among the private mechanisms is required to use our optimization framework. When there no prior knowledge about PI.....PKK. T is set to be the uniform distribution for maximizing the expected utility. Note the above optimization problem also enables the flexibility of incorporating prior knowledge about the mechanisms by choosing prior distribution T to further improve the utility.
7: we only
Optimizing Over All Algorithms. We want to stress that by solving the above optimization problem, we are indeed optimizing over all algorithms for maximal utility, since we show in Lemma 3.3 DaRRM that captures all reasonable algorithms computing a private majority.
Linear Optimization Objective. Perhaps surprisingly, it turns out that optimizing for y" is a Linear Programming (LP) problem! Indeed, after expanding the optimization objective in Eq. 2 by the utility definition (see Definition 2.4 optimizing the above objective is essentially same as optimizing:
min xE
Σ
E Pp..Pa....Pp ((o (xk-:)]-71
2
where og Pr([(D) = 11, 47 E 1....... K} and observe L(D) ~ Poisson PPk). .Pk). The above objective is linear in 7. See a full derivation in Appendix
Although taking the expectation over PK involves integrating over K variables and this can be computationally expensive, we discuss how to formulate a computationally efficient approximation of the objective in Appendix C.2] which we later use in the experiments. Note that the objective only for maximizing the utility and hence approximating the objective does not affect the privacy guarantee.
Reducing Infinitely Many Constraints to A Polynomial Set. The constraints in the optimization problem (Eq. 3) is what makes sure the output of DaRRM,, is me-differentially private. We thus call them the privacy constraints. Note that the privacy constraints are linear in 7-
Though it appears we need to solve for infinitely many such privacy constraints since pú's and pf are continuous, we show that through a structural understanding of DaRRM, we can reduce the number of privacy constraints from infinitely many to exponentially many, and further to a polynomial set. First, we observe the privacy cost objective f is lincar in each independent pair of (p..p)) fixing all (pj, p/), Vj + i, and hence finding the worst case probabilities in (p;,P)) p!) given any 7, (pi (p(,2(") = arg (ax.)r f'p PK. P/. (/.....'''') is a linear programming (LP) problem. Furthermore, since p: and p are the probability of outputting 1 from the i-th (). -differentially private mechanism M, on adjacent datasets, by definition, they are close and lie in feasible region Fe, which (pt,p,") only happens at one of the corners of F,, and hence the number of constraints reduces to K (and K if 5 0). Second, observe that on and of in the privacy cost objective f are the pmf of two Poisson Binomial distributions at E fO....,KK, Notice that the Poisson Binomial is invariant under the permutation of its parameters, i.c. Poisson Binomialin ... ..... .Pk) has the same distribution as PoissonBinomiaa under some permutation æ. Basod on this observation, we show the number of constraints can be further reduced to O(KT) if 8 > 0 (and O(K3) if 8 = 0). We formalize the two-step reduction of the number of privacy constraints in Lemma 5.1 follows. See full proof in Appendix C.3
show has 8 corners if 8 > 0 (and only 4 corners if 5 = 0). This implies
(P1,.... .Pk.....)))))..
Practical Limitation. Although the number of constraints polynomial in K and optimizing y in DaRRM I.P. OKK)) can still make the number of constraints intractably large when K large. In practice, we observe with the Gurobi
9

---

Published in Transactions on Machine Learning Research (November/2004
to solue Problem 1.1 and let be the privacy cost objective defined in Lemma 3.4 Given an arbilrary noise function let the worst case protobilities be PR.Pi PT pk) = arg max ((PL f(p,...., PK P1, Pki7))
Lemma 5.1. Consider using DaRRM (Algorithm
(pi.... Pk .r......PPP...
= arg max f(pi.... PK. P............ Pkin)) HPEEP)1
Then, each pair (p. )) ) Vi E [K]
satisfies
(p) E {(0,0), (1, (0, (A,0) (1, A,
(1,1- e
+
1
1-A
1-A +
6+
es +1
E++1 e+11
Furthermore, when 8 > 0, there crists finite vector P of size O(K") such that if max ((r.)))) f'pi,....PPKK (.....-PPii))) then ........ Pkk ...... P can be reduced to O(K*).
..... .kk77) B. When ô = 0, the size of
6 Experiments
We empirically solve the above optimization problem (Eq. 2 using the Gurobi solver and first present the shape of the optimized 7 function, which we call Yopt: and its utility in Section 6.1 Then, we demonstrate the compelling effectiveness of DaRRM with an optimized y function, i.e., DaRRM Towet in ensembling labels for private prediction from private teachers through the application semi-supervised knowledge transfer for
private image classification in Section 6.2
6.1
Optimized y in Simulations
Shape of functions
8DaRRM,)
m
m
m
0.2
0.1
0.5
0.1
values
0.0
0.0
m
5
0.10
0.05
0.5
0.05
0.00
0.00
5.5
11
0
5.5
11
Support E (0, .,
functions
You (Ours)
Yau (Baseline)
Vusua (Baseline)
Figure Plots of the shape and (DaRRMM,) of different y functions: the optimized Topt and the baselines YSub (corresponding subsampling) and Toostt (corresponding RR). Here, A 10-5 and 6 A)m mA.
K 11, m E (,7,, E =
We compare the shape and the subsampling 7su as in Lemma 3.1 We also compare against Poont in the classical baseline RR (see
E(DaRRM,) of different y functions: optimized Nopt and the
optimizer,
optimize for K < 41 laptop if à But if 0, since the number of privacy constraints is O(K3), can uptimize for K over 100.
2All code for the experiments be found https: htwp://wwws.ooo.....cooooooeeeee htt.s/awww...aa...aaaaaaaaaaaaar
hattps::/wwx. www.ggurobicoom
Note the subsampling mechanism from Section which enjoys privacy amplification by factor only applies pure
differential privacy settings (f.e., when = However, we focus the more general approximate differential privacy
10

---

Published in Transactions on Machine Learning Research (irember/202//
Section A.1 and E(RR). Here, Peonst can be viewed a constant noise function Tcooss (1) Poonst AZ E 1.. K) and E(RR) is the same as {DaRRMM (comas).
We present the results with K = 11, 0.1, = 10-5 and m E 3,73, We assume there is no prior knowledge about the mechanisms {M, and set the prior distribution from which p,'s 's are drawn, T, to be the uniform distribution, the optimization objective (Eq. D searching for Yopt. To ensure a fair comparison against the subsampling baseline, we set å to be the one by m-fold general composition (see Theorem 2.3 which in this case, is 6 = 1 (1 -1-11 A)T mA. We plot each y functions over the support {0, (0.1..... K} and the corresponding error of each algorithm in Figure 2
Discussion. In summary, at m = 1, the optimized noise function Topt overlaps with Toub which corresponds to the subsampling baseline. This agrees with our lower bound on the error in Lemma 3.2 which implies that at m = 1, subsampling indeed gives the optimal error. When m > 1, the optimized noise function Yopt has the highest probability of outputting the true majority over the support than the y functions corresponding to the baselines. This implies DaRRM Yopt has the lowest error (and hence, highest utility), which is verified on the bottom set of plots. More results on comparing the DaR optimized under the uniform T against
the baselines by general composition (Theorem 2.3 and in pure differential privacy settings (i.e., A = d = 0)
for large K and m can be found in Appendix D.1.1 and D.1.2 Furthermore, we include results optimizing y
using& a non-uniform T prior in Appendix D.1.3
6.2 Private Supervupe Knowledge Transfer
Dataset
MNIST
Dataset
Fashi on-MNIST
GNMax
DaRRMasw
DaRRM
GNMax
DaRRM 72
DaRRM
# Queries
(Baseline)
(Baseline)
(Ours)
# Queries
(Baseline)
(Baseline)
(Ours)
Q 20
0.63 (0.09)
0.76 (0.09)
0.79 (0.09)
20
0.65 (0.11)
0.90 (0.07)
0.96 (0.03)
Q 50
0.66 (0.06)
0.75 (0.06)
0.79 (0.05)
Q = 50
0.59 (0.06)
0.94 (0.03)
0.96 (0.02)
Q 100
0.64 (0.04)
0.76 (0.04)
0.80 (0.04)
Q = 100
0.64 (0.04)
0.93 (0.02)
0.96 (0.02)
Table 1: Accuracy of the predicted labels of Q query samples on datasets MNIST (on the left) and Fashion-MIIST (on the right). We report the mean and one std. in parentheses over 10 random draws of the query samples from the test dataset. Note cach prediction -diferentially private. With the same per query privacy loss (and hence the same total privacy loss over Q samples), DaRRM achieves the highest accuracy compared to the other two baselines.
the query sample is (Equergs Squery)
We apply our DaRRM framework in the application of semi- supervised knowledge transfer for private image classification. We follow a similar setup as in PATE Papernot) let al. (2017 2018), where one trains K teachers, each on a subset of a sensitive dataset, and at the inference time, queries the teachers for the majority of their votes, i.e., the predicted labels, of test sample. Each time the teachers are queried, there is privacy loss, and we focus on this private prediction subroutine in this scetion. To limit the total privacy loss over all queries, the student model is also trained on public dalaset without labels. The sludent model queries the labels of a small portion of the samples in this dalaset from the teachers and is then trained using supervipe learning algorithms on both the labeled and unlabelod samples from the public datasct.
Semi-supervised Knowledge Transfer.
Baselines. We want the privacy loss per query of a Lest sample to the teachers to be (Equery: Squery). )- This can be achieved via two ways: 1) Train K non-private teachers, add Gaussian noise to the number of predicted labels from the teachers in each output class, and output the majority of the noisy votes. This is exactly the GNMax algorithm from PATE Papernot et al. (2018). 2) Train K (c, A) diiffeeernt private teachers and output the majority of the teachers' votes by adding smaller amount of noise. This can be computed using DaRRM with an appropriate noise function 7. We compare the performance of GNMax and DaRRM with two Yopt (i.e., the optimized 7), and 78ws (i.e., the subsampling baseline). The overall privacy loss over Q queries to the teachers can be computed by general composition (Theorem 2.3
functions:
settings (with A > in the experiments, and hence, the subsampling bascline we consider throughout this section is the basic version without privacy amplification. To see how the subsampling mechanism from Section with privacy amplification compares against the other algorithms, please refer to Appendix 1.1.2 D.1.2
11

---

Published in Transactions on Machine Learning Research (November/2000
Experiment Setup. We use samples from two randomly chosen classes - class 5 and 8 - from the MNIST and Fashion-MNIST datasets to form our training and testing datasets. Our MNIST has a total of 11272 training samples and 1866 testing samples; our Fashion-MVIST has 10000 training samples and 2000 testing samples. We train K = teachers on equally divided subsets of the training datascts. Each teacher is a CNN model. The non-private and private teachers are trained using SGD and DP-SGD Abadi et al. (2016), respectively, for 5 epochs. DaRRM Sctup: The Gaussian noise in DP-SGD has zero mcan and std. adpsgd = 12; the gradient norm clipping threshold is C 1. This results in each private teacher, trained on MNIST and Mashion-MMIST, being (e, (0.0892, 10 10-4) and (0.0852, 10 --iffferrnnt private, respectively, after 5 epochs. We set the privacy allowance m = 7 and the privacy loss per query is then computed using general composition under m-fold, which give the same privacy loss in the high privacy regime, resulting in (Equery, )qurry = (0.2676, 0.0003) on MNIST and (0.2556, 0.0003) on Fashion-MNIST. GNMax Setup: We now compute the std. a of the Gaussian noise used by GNMax to achieve a per-query privacy loss of (me, ma), as in the DaRRM sctup. We optimize a according to the Renyi differential privacy loss bound of Gaussian noisc. Although Papernot et al.] (2018) gives a potentially tighter data-dependent privacy loss bound for majority ensembling non-privce pripprivate teachers, we found when K and the number of output classes small as in our case, even if all teachers agree Hence, we only use the privacy loss bound of Gaussian noise here to set o in GNMax. See Appendix D.2.1 for more details, including the a values and other parameters. Finally, the per sample privacy loss and the total privacy loss over Q queries, which is computed by advanced composition, are reported in Table g
single output class, the condition of the data-dependent bound is not satisfied.
The testing dataset is treated as the public dataset on which one trains a student model. Papernot et al. (2018) empirically shows querying Q 1%N samples from public dataset of size N suffices to train student model with a good performance. Therefore, we pick Q (20, 50, 100). We repeat the sclection of Q samples 10 times and report the mean test accuracy with one std. in parentheses in Table [ The Q queries serve as the labeled samples in training the student model. The higher the accuracy of the labels from the queries, the better the final performance of the student model. We skip the actual training of the student. model using semi-supervised learning algorithms here.
Privacy loss per query (Equery: Squery)
Total privacy loss over Q queries
Dataset
# Queries
(Etotal Scotat) (5.352, 0.006)
Q = 20
MNIST
Q = 50
(0.2676, 0.0003)
(9.901, 0.015)
Q = 100
(15.044, 0.030)
Q = 20
(5.112, 0.006)
Fashion MNIST
Q 50
(0.2556, 0.0003)
(9.382, 0.015)
Q 100
(14.219, 0.030)
The privacy loss per query to the teachers and the total privacy loss over Q queries. Note the total privacy loss is computed by general composition (sce Theorem 2.3 where set 8' = 0.0001.
Table 2:
Discussion. Table I shows DaRRM s.pt achieves the highest accuracy (i.e., utility) compared to the two baselines on both datasets. First, comparing to DaRRM we verify that subsampling does not achieve a tight privacy-utility tradeoff, and we can optimize the noise function y in DaRRM to maximize the utility given a target privacy loss. Second, comparing to GNMax, the result shows there are regimes where ensembling private teachers gives a higher utility than directly ensembling non-private teachers, assuming the outputs in both settings have the same privacy loss. Intuitively, this is because ensembling private teachers adds fine fine-grained noise during both training the teachers and aggregation of teachers" votes, while ensembling non-private teachers adds a coarser amount of noise only to the teachers' outputs. This further motivates
Heeee we present results with privacy allowance = 3 because think this is more interesting case. m 1 is less interesting, since cannot get improvement compared to the subsampling baseline. close to a K 2 5 is also less interesting, too easy for proposed method (the optimized function is very close which a case when improvement is possible, and also potentially
as this case needs to be addod in this casc). Hence, we pick challenging for our optimization framework. This is also realistic as most applications would only want tolerate constant. privacy overhead. See more results with different privacy allowance 's this setting in Appendix D.2.
meaning very little noise
12

---

Published in Transactions on Machine Learning Research (November/2005
private prediction from private teachers and the practical usage of DaRRM, in addition to the need of aggregating private teachers in federated learning settings with an honest-but-curious server.
7 Conclusion
In computing private majority from K private mechanisms, propose the DaRRM framework, which is provably general, with customizable function. We show a privacy amplification by factor of 2 in the i.i.d. mechanisms and a pure differential privacy setting. For the general setting, we propose an tractable optimization algorithm that maximizes utility while ensuring privacy guarantees. Furthermore, we demonstrate the empirical effectiveness of DaRRM with an optimized y. We hope that this work inspires more research on the intersection of privacy frameworks and optimization.
13

---

SIAM, Published in Transactions on Machine Learning Research (November/2005
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Tlya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Racf Bassily, Om Thakkar, and Abhradocp Thakurta. Model-agnostic private learning via stability. arXiv preprinl Xiv: 05101, 2018.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159 IEFE, 2021.
Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang. Privacy at scale: Local differential privacy in practice. In Proceedings of the 2018 International Conference on Management of Data, pp. 1655-1658, 2018.
Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal differential privacy composition for exponential mechanisms.. In International Conference on Machine Learning, pp. 2597 2606. PMLR, 2020.
David Durfee and Ryan M Rogers. Practical differentially private top-k selection with pay-what-you-gee composition. Advances in Neural Information Processing Systems, 32, 2019.
Cynthia Dwork and Vitaly Feldman. Privacy-presorving prediction. In Conference On Learning Theory, pp- 1693 1702. PMLR, 2018.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-forst annual ACM symposium on Theory of computing, pp. 371-380, 2009.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryplogrophy conference, pp. 265 284. Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-407 2014.
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS '1,, pp. 1054 1067, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450329576. doi: 0..1145/2660251 26663448. URL https::/doi. ottp:///6oo...o///...111///68/// 02616664677266638888
Ülfar Erlingsson, Vitaly Feldman, Nya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtitth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2019.
Vitaly Feldman, Nya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pp. 521-521---6 532. IEEE, 2018.
Quan Geng and Pramod Viswanath. The optimal noiso-adding mechanism in differential privacy. IEEE Transactions Information Theory, 62(2))925 951, 2015.
Naoise Holohan, Douglas J. Leith, and Oliver Mason. Optimal differentially private mechanisms for randomised response. IEEE Transactions Information Forensics and Security, 12(11):2726 2735, November 2017. ISSN 1556-6021.
doi:
URL httt:://dxx...///// doi. 1wwp///...10/TIFSS... 2017 201.7.288877
Junjie Jia and Wanyong Qiu. Research on an eusemble classification algorithm based on differential privacy. IEEE Access, 8:93499-9355 2020. doi:
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pp. 1376-1385. PMTR, 2015.
14

---

Published in Transactions on Machine Learning Research (November/2005
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. Xiv preprint orviv 1r1:i:1610.0000 (610.05492 2016.
Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 298 309 New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367059. doi: 10.1145/3813276.331128
URL https://dol: http:///oo.or//////// 1111111113326666 331133777733333777 3316377
Zhongfeng Liu, Yun Li, and Wei Ji. Differential private ensemble feature selection. In 2018 International Joint Conference on Newral Networks (IJCNN), pp. 1 6, 2018. doi: /ttp///1NN..2.......
Fatemehsadat Mireshghallah, Mohammadkazem Taram, Prakash Ramrakhyani, Ali Jalali, Dean Tullsen, and Hadi Esmaeilzadeh. Shredder: Learning noise distributions to protect inference privacy. In Proceedings of the Swinty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 3 18, 2020.
Moni Naor, Kobbi Nissim, Uri Stemmer, and Chao Yan. Private everlasting prediction. arv preprint orXiv:2305.09599, 2023.
Mohammad Naseri, Jamie Hayes, and Emiliano De Cristofaro. Local and central differential privacy for robustness and privacy in federated learning. arXiv preprint arXiv:2009.0856: 2020.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 75-84, 2007.
Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. In International Conference on Learning Representations, 2022. URL htttps://openrevvie http://www..e.oooo////////0////0
Nicolas Papernot, Martin Abadi, Ulfar Erlingsson, lan Goodfellow, and Kunal Talwar. Semi-supervised knowledge transfer for deep learning from private training data. In Proceedings of the International Conference on Learning Representations, 2017. URL httpss://axiv.. org/ /a//ab//////6 05755
Nicolas Papernot, Shuang Song, Πya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with pate. arXiv preprint 1Xx::1802.0890 2018.
Omer Sagi and Lior Rokach. Ensemble learning: A survey. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 8(4):e1249 2018
Uri Stemmer. Private truly-everlasting robust-prediction. arXiv preprint arXiv:2401.04311 2024.
Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory, pp. 819-850. PMLR, 2013.
Salil Vadhan. The Complerity of Differential Privacy, 347 450. Springer International Publishing, Cham, 2017. doi:
URL https: http::://.....ogg11100//////////
Laurens van der Maaten and Awni Hannun. The trade-offs of private prediction, 2020.
Ming Xiang and Lili Su. battsstttocc sign SGD: A byzantine resilient and differennially private gradient compressor for federated learning, 2023. URL
Tao Xiang, Yang Li, Xiaoguo Li, Shigang Zhong, and Shui Yu. Collaborative ensemble learning under differential privacy. Web Intellggnce, 16:73 87, 03 2018. doi: 10.3233/ (0.3233/WEBB111 -
Ving-Ying Zhang, Teng-Zhoog Rong, and Man-Man Li. Expectation identity for the binomial distribution and its application in the calculations of high-order binomial moments. Communications in Statistics
Theory and Methods, 48622) 2019. doi:
URL https
7/doi http://orrr11.110000111111001110 2018..00111111 1435818
Yuqing Zhu, Xuandong Zhao, Chuan Guo, and Yu-Xiang Wang. pprvaaee prediction strikes back!"private kernelized nearest. neighbors with individual renyi filter. arXiv preprint 2xXim:336607388) 2023.
15

---

Published in Transactions on Machine Learning Research (November/2004 22024)
A Details of Section 3
A.1 Randomized Response with Constant Probability Poonst
A Algorithm Randomized Response Majority (RR)
Imput: K (c, A)-DP mechanisms {M, f== noise function 7 (O...., K} [0. 1]. dataset D, privacy
allowance Σ m < K, failure probability 8 2 A 2 0
2: Output: (me, 0)-DP majority vote of {M;
3: Compute a consland probability Poonst E [0,
4: Flip the Peonst" biased coin
Head (with probability Peonst) then
S (S,, Sk),, where S, M,(D)
7: C S
Output If 2
else
10: Output 0/1 with equal probability
11:
end if
We show the magnitude of Pomst in RR (Algorithm 2 to solve Problem 1.1 such that the output is (me, 6D-DP, in Lemma A.1
Lemma A.1. Consider using RR (Algorithm g to solve Problem
1. Let the majority of K A)
differentially private mechanisms be (Tc, X)-differentially private, where
1. K] and E [0, 1) are computed
by simple composilion (Theorem 2.2 or general composilion (Theurem
2.3 If
mE 1 1 28
Poonst S
(4)
2(ete e (1+em))A) + m
e
then RR is (me, -idffeferntt private.
Proof of Lemma A.1 Let {0,1) denote the output of RR. Let q. Pr(C(D) and d' = Pr[C(D)) = x),
where C(D) = E MD) C(D') = Ex M((')) and D, D' are adjacent datasets. Recall each mechanism .rifffrriirr private. When A 0, using simple composition, r K and A O. When A 0, using general composition 7 = VK
Mj is (c, A Adifferrenntl private, and the majority of the outputs of [M
and À KA. By definition of differential privacy (Definition 2.1 all of the following four constraints
gz d' apply:
4e S e de and 1- de S 51 (u)
d/ s Tx qu X, and 1 qu S c0 (1- %%)) +
To ensure RR is (me, 8) differeeentl private, Pconst needs be such that for all possible qus da [0. 1].
Pr(RR(D) = =x] me Pr(RRR(D)= = 6
(5)
1
Peonst Or 2(1 Pconst) S me (Peonst L/
2/(
Peonstt ))
(6)
1 ) Peonst
1
(qx me 9' + 2
m
< m
+
(7)
2
2
2
Let h(ges (/6) == Or em + -eme The above inequality of Poonst (Eq. needs to hold for worst case output probabilities oh df that cause the maximum privacy loss. That is, Poonst needs satisfy
1
Peonst maagg.a higg (m) < ze"
me
+
(8)
2
16

---

Published in Transactions on Machine Learning Research (November/2005
To find the worst case output probabilities, solve the following Linear Programming (LP) problem:
M(qas Voo = 40 e. - + = = 1
Objective:
max 8r
(9)
2
2
Subject to:
0 1s S 1,0 - 1/2 $
(10)
9x S Th dz + X, 1 1/2 S ( - 4z) +
(11)
g e" 9z + X, 1 4r S cTt(1 (1) +
(12)
LP Problem Illustration
(1,1)
-11--=00--00 -1))-
(1,1-1)
=1 -)
optimum objective
qx
1-1
e +1 e
+1
0.2
(0.2)
Maximization Direction
0.0
(0,0)
0.0
02,0)
0.4
0.5
0.8
1.0
qx
Figure 3: A visualization of the above LP problem.
The optimum of any LP problem is the corners of the feasible region, which is bounded by the optimization constraints. We plot the feasible region F and the objective of the above LP prob- lem in Figure
Here, (t) = arg g. h(gz: d')) E {(0,0), (1, 1), (0, A), (1, X, 1),
1-1 )= The optimum of the LP problem that is, the worse case probabili- A), 1-1 (2-A e1 +1:
+*
ties Lo lx is.
Th +X
C
de
(13)
eTe
+
te +
By Eq.
Te + X
mr 1 X
1
1
Peonst
eeme
te
(14)
TH +1
@T +1
2
TE me
(1 + me )
1
Pconst
+
(e
1))
$
me
1) +
(15)
ecc +1
2
2
me 111 26
Poonst
S
2(e +(1+e
(16)
+ m
e11
For small m, K, using the approximation e N 1 y and that 7E < 2,
me + 25
me 28
(17)
Poonst me+ (2+me]
mE TC + (2 + mc)A
rE+2
In the pure differential privacy setting,
=0, 0, = K, and so Peonst Ro R; and in the approximate
differential privacy setting, À ~ 0.8 0, VK, and Peonst VK
E
17

---

Published in Transactions on Machine Learning Research (November/2005
Algorithm Subsampling Majority (SubMaj)
Imput: K (c, A)- mechanisms {M, 1= noise function 7 (O...., K} [0, 1], dataset D, privacy
allowance S m & K, failure probability 8 82 A A20 0
2: Output: (me,0) 03-DP majority vote of {M.
3: (S,, where S M,())
Im + m indices chosen uniformly at random from [K] without replacement
5: C Ejes Sj
6: Output 1 1
A.2 Proof of Lemma 3.1
Lemma A.2 (Restatement of Lemmaa 3.1 Consider Problem 1.1 with the privocy allowance m [K] Consider the dela-deerndenl algorithm that compules L(D) and then applies RR with probobilily py- If
Py (Sub (I), where I E {0, ....,,KK KK is the value of L(D), i.e., the (random) sum of observed outcomes dataset D, and Ysub {0, (....... ..k...KK
K} - [0, 1] is
(lb (1) 7/Sub (K -1) 1)
Σド= m+1 ((()))
===
(m))
if m is odd (4)(
Σ 7
if is even
then the majority of m out of K subsampled mechanisms without replacement and the output of our data- dependent RR algorithm have the same distribution.
Proof of Lemma 3.1 Let L == == S, be the sum of observed outcomes from K mechanisms. Following Al Algorithm 3. Jn denotes the m indices chosen uniformly at random from [K] without replacement. Conditioned on C, notice the output of SubMaj follows a hypergeometric distribution. The output probability of SubMaj is
Pr(SubMaj(D) = 11
Σ
Pr P Pr|C []
(18)
1=0
Pr
832
c c= 1] Pr[C I]
(19)
2
1=0
JEJm
()
Σ 1E:
Pr(C =
if m is odd
(20)
()
if is Pr[c
Consider an arbitrary noise function Ysub 10.1...., K} + 10. Let RR-d(D) denote the output of the data-dopendent RR-d on dataset D, where RR-d has the non non-constant probability set by Ysub- The output probability of RR is,
K Σ (r(RR-d(D) = 1| C= I| Pr[C = 1]
Pr(RR-d(D) =] =
(21)
1=0
K +1
(rsws (1) -112
2 + 2 (1 (()) Pr(c
(22)
1=0
We want Pr(RR-d(D) =1] -1]= Pr((ubbaj((D) 1).
18

---

Published in Transactions on Machine Learning Research (November/2004
If m is odd, for any 1 K-1 this is
K-!
1
[1 7Su (1) =
2
j
m
1m-
K
+ (1 = -2
(23)
j= m
and for any 12
K+1 this is 2
K
1 1
+ Ysub(!)
Σ
m
2 2
j m+1
7 (sub(1)
=
>
(24)
m
Similarly, if m is even, for any 1 K-1 this
2
(m-))
K
( (4)) (K
44
(1 7Ssb(()) =
Σ
KK)
2 (*)
j= +1
K
(
(slb(1) = 1 Σ
m
7
(25)
5= 4
m
and for any 12 K+1 2
this is
K
2 + (sub(1) =
Σ
2
2
j= +1
m
m
K-1
(4)
K-1
1
(1) =
m
(26)
Next, we show the above YSu is indeed symmetric around is odd,
For any 1 K-1 2
ttere is K - -12 K+1 If m
m-1
(x)
Tsub (K -1)=
Σ
m
=
-1
j= m+
m
j=1
m
m-1
(K-)
m
K m- 1
2 2
1
K
K
j=1
(!)
(27)
Similarly, if is even,
(K-1 ( (m)
(2) "
K
(4)
K
Nsw (K -K))= = Σ
j
1= 1-
Σ
3
(m-
K
(K)
2
(K)
j= T
1
K
K-h
K
1
(K-1
K
m 1
m
= =1-2
1 - 2
K
K
1=1
m
m
j= m
+1
m
19

---

Published in Transactions on Machine Learning Research (November/2005
(()
(28)
Now, combining Eq. 23 Eq.
24
and Eq. 27 if m is odd, sctting Ysub as
m
K-1
75ub (1) 78us(K - 1
Σ
m
(29)
K
makes RR-d have the same output distribution as SubMaj.
Similarly, combining Eq.
25 Eq.
26
and Eq. 28 if m is even, setting Ysub as
K-)
7Sb (1) = 7sub (K- -1) =1 Σ
(30)
makes RR-d have the same output distribution as SubMaj.
A.3 Proof of Lemma 3.2
Let A be an (e, -)diffeeryylialyy privale algorillo, where E (0, 5 and 8 E [0, 2, that computes the majority of K (c, diiffferrrrl private mechanisms MI...., MR, where
Lemma A.3 (Restatement of Lemma 3.2
Mi D + {0, }} on dataset 'D and (r[M,(D) = 1] = Pi, Vi E [K]. Then, the error E(A) 2 Pr(g(S)
11 K E 1 1
Pel, where 9(S) is the probability of the true majority output being 1 defined in Definition 1.1
Proof. Consider the setting where Mi's are ii.d. ie., Pr(M,(D) 1]= p. E [K] for some [0, any datasct D. Then, it suffices to show E(A) 2 [P][g(S]] = = - pl, because a lower bound in this special case would indicate a lower bound for the more general case, where p: 's can be different.
Construct a dataset Do and mechanisms {M such that (r(M = 1] = Pr(M,(Do) = oj and without loss of generality, we may assume Pr(A(Do) = 1] 1
Next, construct sequence of datasets D1, D2,..., Dr, such that D, and Dj+1 are neighboring datasets tha differ in one entry, for all j E [L - 1), and Pr(M,(D,) = 1] Je + -E= e'5, vi E [K], Vj [L]. Choose L E N such that Jele EL-1 e p, for some 1 2 p>>>
Now, by definition of differential privacy,
Pr(A(D:) = 1| s e Pr(A(Do)= = 1]+ +
Pr[A(D2) = 1| s e' Pr(A(D;) = = +8 dd Pr(A(D.) = =
1-1
Pr[A(Dr) 1] 11 L Pr[A(Do) = 1]
Σ 1=0
2 2 e
Σ
c =p
1=0
Since the probability of true majority being 1 on dataset Dz is Pr(g(S) 1] 2 >>> 111 there is
E(A) = Pr(g(() 1 Pr(A(D)) = I|l Pr(g(S) = 1] -
20

---

Published in Transactions on Machine Learning Research (November/2005
A.4 Proof of Lemma 3,3
Let A be any randomized algorithm to compute the majority function S such that for all S, Pr - 2 1/2 (i.e. A is at least as good a random guess). Then, there erists a a general function 7 10.1] + [0, 1] such that if one sets Py by 7(S) in DaRRM, the oulpul distribulion of DaRRM, is the same as the oulpul distribulion of A.
Lemma A.4 (Restatement of Lemma 3.3
Proof of Lemma 3.3 For some D and conditioned on S, that by definition Pr|DaRRM,,6 g 7(5) + (1/ - (S)). We want to set y such that Pr\DaRRM,(()) = ](S) = Pr[A(S) = g(S).. Therefore, we set 7(S) = -P - [S) 1.
Lastly, we need to justify that y E [0, 1]. Clearly, 7(8) 5 - since Pr(A(S) - [(S) - Note that the non-negativity follows from assumption.
A.5 Proof of Lemma 3.4
Lemma A.5 (Restatement of Lemma 3.4 Consider using DaRRM (Algorithm 7 to solve Problem 1.1 let = Pr(C(D)=
and af Pr[C !, where DD and D' are adjacent datasets and l E {0, .0,....Ky For noise function y {0, 1....... K} - [0, 1] such that 7(l)))))))))))) = 7(K - 1), Vl, DaRRM, is (me, 8 diffeeerrntllll private if and only if for all an, the following holds,
Kj.
f( I(p....,PKK PK, 11, P pkiT) me 1 28
(31)
where f is called the prinacy cost objective and
- Pk, Pi..... pki7)=
Σ Tm a4 (00)0))000 -7()
Σ Ki1 2
(on e eT -(1)
Proof of Lemma 3.4 By the definition of differential privacy (Definition
2.1
DaRRM, is (me, didiffrrrettially private
Pr[DaRRM, (D) 1] e Pr DaRRM, =1] +1]+6 8, and Pr[DaRRM, (D) 0] < e Pr[DaRRM, 0] + 8, V adjacent datasets D, D'
(32)
Let random variables L(D) ΣE= S(D) and L(D') ΣX1 S(D') be the sum of observed outcomes adjacent datasets D and D', based which one sets p, in DaRRM. Let a Pr(C(D) [ and = Pr(((')) = 2), vi E (0, 10.,....KK K}.
Consider the output being 1.
Pt(DaRRM,(D) 1) S Th (D(DRRM,. 1] +
(33)
(D) = = Pr(C((D = 1]
(34)
K
Pr (DDRRRM = ( = P:((( = 11) +
< e
1=0
(2(0) 1112 ) 11 Pr([(D) o]
K
(35)
K
< e me
(1(1) - 1il
K } + (1 -0()))) Pr(C(D) = 11) +
2
2
1=0
21

---

Published in Transactions on Machine Learning Research (November/2005
K
1-
(1(0) + 2 (1 -11)) Pr(C(D) =1 +
Σ
(1
=1]
(36)
2
1=0
S e me
K
(7(1) + 1 2 - -(0))
Pr(((D) = 11) + E me
K=1
2 (1- Pr(2(D') = =1) +
1=0
K
1
2 Σ
1
(1)aa
(1)aa
(37)
2
2
2
1= KH
1=0
S m
Σ
K
21))a - c
Σ
K 1
2
1
(1)at
eeme +6
2
K+1
1=0
2
R-1
K
(a) - e" e aina())()=
Σ
(al - em a1)())111)== s - 1 1 28
(38)
1=0
Similarly, consider the output being 0.
(D) =0] S TT Pr(DARRM,(D) = =0] +
(39)
K PD(DaRM,, =0 [(D) =]- Pr([(DD- = 1]
(40)
1=0
K
S me
PD) 00 2(D') 1 Pr[C(D') = =1) +
K
1 -1 Pr(C(D) = 1]
(1(1) 1111 < 2 2
(41)
K
701. 111 ? + (1- x0]) PPr[((D) 1] 0
K
1
K
1 (1(0) + ( -(0)) Pr(C(D) = 1| +
Σ
2
- (1-)(1))
Pr(C(D) = I]
(42)
1=
K
mE
(10)- + (1 x01) Pr([(D)) = 4 +
Σ
1
11) + 8
1=
K
2 7()an)
Σ
1 (1)a
+ 2/2
1
(43)
2
1=0
1= 1
11
K
< 6
2 (1)aa
-è me
Σ
1
71)
+ 1 me +6 5
2
2
1=0
K11
k
(a) e (m=aa(
Σ
(a) c a()((1)) S me 1- +8
(44)
-
1=0
1= K+1
22

---

Published in Transactions on Machine Learning Research (November/2004
Therefore, plugging Eq. 38 and Eq. 44 into Eq. 32
DaRRM, is (me, illlleerenel private
(as - cm am)(()))
aa c a()((())) - c -1+28
(45)
1=0
and
(a) me a/)((1))))
Σ
(at TT a()=((((1)) e 1 +
(46)
1=
where = Pr(C(D) = and af Pr( 11, 42 E {0, .,......) K} and D, D' any adjacent dalasets.
Next, we show if is symmetric around K 3, implics satisfying the other onc. Following Eq. 45
i.e. 7(1) = (K 1), satisfying either one of Eq. 45 or Eq.
46
K
K
(0) TTHc
(1((1))
(a: c a(n(((1))) S th 1
(47)
K+1
1=
K
[KK-1 e a' ,7(K -1)
Σ
-1+ (ax-1- - - dx-i) - 7(K - - t - + 26 (48)
1=
K
(Kk-1- - me -kx)))))))
Σ
(ak-1- - 2T a'x 7(1) S Te -1+
(49)
Since 7(1) 7( ()
For analysis purpose, rewrite Eq. 46 as
a mh
a1)
7(1)
Σ
( me "m -7(1) S me -1 25
(50)
and proceed by showing Eq. 49
Eq. 50
Recall P: (D) = 1] and p/ Pr(M((D') 1]. Observe L(D) Poisson (pt) and
C(D') Poisonn (1 Let Fi (A: |A| = 1, S [K]], for any I E {O...., K), denote the set
of all subsets of integers that can be selected from [K]. Let A [K] A be A's complement set. Notice FK-1 (A Fi).
Since a denotes the pmf of the Poisson Binomial distribution at I, it follows that
on Pr(C(D) = =| Σ
The - -P;)
(51)
AEF
Consider 8: = pt, Vi [K] and a new random variable L Poisonniiomiaa((3335.. and let ā
Pr[CS 1]. Observe that
a = Pr[C = Σ 1 -3,)= Σ ngEa(1 - Ps
AEP
ACF
Σ
11 P:)llIEAPP.
IHEAAILlYEA p.) AEFR-i
Σ
A-EFR-1
23

---

Published in Transactions on Machine Learning Research (November/2004 20224)
aK-i
(52)
Similarly, consider = = Vi [K] and new random variable C = Pr| 1]. Then, aj = d'K--
Poisson and let
Since Eq.
49 holds for all possible ak-t, 0K-1 Eq. 50 then holds for all ā,, az in the K-simplex, and Eq. 50 follows by relabeling ak- and dg-1 ar.
The above implics Eq. 45
Eq. 46 Therefore,
DaRRM, is (me, di-fefeereyt private
(ar e a()
Σ cn e a()7(1) S TT 28
(53)
== ==ppp.....KK PI PK-Pei---PPee
24

---

Published in Transactions on Machine Learning Research (November/2005
B Details of Section 4: Provable Privacy Amplification
In this section, we consider Problem 1.1 in the pure differential privacy and i..d. mechanisms setting. That is, 6= A = 0 and p p; = (D)
= 11 = p = Pr(M = 1], Vi E [K]. Our goal is to search for a good noise function 7 such that: 1) DaRRM, is me-DP, and 2) DaRRM, achieves higher utility than that of the baselines (see Section 3 under fixed privacy loss. Our main finding of such a y function is presented in Theorem 4.1 which states given privacy allowance m [K], one can indeed output the majority of 2m subsampled mechanisms, instead of just
indicated by simple composition. Later, we formally verify in that taking the majority of more mechanisms strictly increases the utility.
Lemma
B.
Section B.3
To start, by Lemma 3.4
for any noise function 7, satisfying goal 1) is equivalent to satisfying
-
(54)
where (())) = Eizo af 711) + Ex
ky1 xa= - a²) 71) refers to the privacy cost objective a{) (see Lemma 3.4 in the iid. mechanisms setting, and recall aj Pr][((D) = I] and af Pr[C(D)) = 1].
Vi E 10 10,1,...,,K)
K. Notice in this setting, L(D) ~ Binomial(y), and L(D') Binomial(yy).
Monotonicity Assumption. For analysis, we restrict our search for a function with good utility to the class with a mild monotonicity assumption: 7(1) 2 11, K-1 and 7(1 - 71+ 1), 44 2 K+1, This 2
2
matches our intuition that as L(D) E S; i.., the number of mechanisms outputting 1, approaches K, there is clearer majority and so not much noise is needed to ensure privacy, which implics a larger value of 7-
Roadmap of Proof of Theorem 4.1 Since needs to enable Eq. 54 to be satisfied for all p.p' E 10, we begin by showing characteristics of the worst case prob- abilitics, i.c., (p".p") = arg max f(p.'')), given any 7: 10.,,,..., K} + [0, 1] that is symmetric around K and that satisfics the above monotonicity assumption, in Lemma B.1 Sec- tion B.1 We call (p", pp") the worst case probabilities, since they incur the largest privacy loss. Later in Section B3.2 we present
Feasible Region F
(1,1)
1.0
1+ 0
e
p'ze-1p
p'
0.5
0'=1-e(11
D'sep
p1
the main proof of Theorem [41] where we focus on searching for good y that enables f(p",p":;2) I e - 1, based the
characteristics of (p', "p") ) in Temmaa B.1 to ensure DaRRM,, is mc-differentially private.
0)
1 1+
0.0
0.0
0.5
100
B.1
Characterizing the Worst Case Probabilities
First, note (p.p') are close to each other and lic in a fcasi- ble region F, due to each mechanism M, being eddifferentially private; and so does (p" (p",p""). The feasible region, as illus- trated in Figure 4 bounded by (a) p' S epp (b) p S etp' (c) 1- p' < c1 p), and (d) 1- S (111-p1 where the four boundaries are derived from the definition of differential privacy. Therefore, only need to search for (p",p"*) arg (px()))) f(p.p':))
Figure The feasible region F is plotted as the blue area. The four boundaries are implied by ppp' satisfying c-differential pri- vacy.
Next, we show that given satisfying certain conditions, (p", pp'' can only be on two of the four boundaries of Fi in Lemma B.1 that is, either p' = etp', i.e,, on the blue line in Figure or 1 - //' = e1 - p²), iee, on the orange line in Figure
Lemma B.1 (Characteristics of worst case probabilities). For any noise function 7: {0, 1, 1.... K) 10
that is 1) symmetric around $, 2) satisfies the monotonicity assumption, and 3) 7( {_ > O and 7( ( ( O,
the worst case probabilities given 7, (p", (p') arg max f(p p/:7), must satisfy one of the following two equalities:
D" = ='"
Vp" E E - - E E
1
1
25

---

Published in Transactions on Machine Learning Research (November/2005
1 e E cl 11,0"* E I+
1
or 1-p" = (1-p'),
Vp'
To show Lemma B.1 we first show in Lemma B.2 that the search of (p", can be refined to one of the four boundaries of F; via a careful gradient analysis of f(p,p's)) F, and then show in Lemma B.3 that the search of (p", p²*) can be further refined two of the four boundaries, due symmetry of p.p Lemma B.1
directly follows from the two.
Lemma B.2. For any noise function 7 (0.1,....KK) K} + [0. 1] that 1) symmeetric around K the monotonicity assumption, and 3) 7( - > O and 7( ا > O, the worst case probabilities given 7 (p", pp") = arg max (p.r')FF f f'p,p';") must satisfy one of the following four equalities:
2: 2) salisfies
p² = ='pp,
4y* E (0,
p'
E
E
1t
1te
D¹ = =
Vy" E 10,
E [00 1
+1
1-p' = =e((1 p)"),
Ap" El 1+e
11.p"
E 1+e-cil
1- 1- = é1 - p"),
vp' El 14e
1IPp"
E
Proof of Lemma B.2 Recall the privacy cost objective (as defined in Lemina 3.4 is now
K
f(p,''))) = Σ
(e me aa)
+
Σ
(an - t (0)aaa))))0 7()
1=0
where og Pr(C(D) 0 and af Pr([(D)) 1J, V {0, I,..... K}. Since L(D) Binomial(p) and L(D') Binomial(p/) in the iid. mechanisms setting, and using the pmf of the Binomial distribution, f can be written as
(p.1iin) = me K
11-0111))
(K) p' -4)
- x) 7()) + Σ (K)
(1)0'L - p) K-1 -)
(K) - - (K) -1))k-1)
The gradients w.rtt. p and p' are
K-1
K 100 -1)
vpf(D.di7) = Σ
(100-1(1 - -
(55)
1=0
K
K (17(0)
+
7(1) 11p00011111111 Kt pp
- p'(K-'((K'C --111
1)
and
vyl(pp''>>) Σ me (K) 7(0) (1)
(1p--1(1 (1-)) -
pk(K 1)(1 -p))k--)
(56)
k
me (K) (()) (4p"
Σ
11 -1- -1)( -1)
-
K+1
26

---

Published in Transactions on Machine Learning Research (November/200)
We show in the following Vp (0. Vpf(p.p':>)> > 0 and Vy'(p.p's < 0. This implics there is no local maximum inside F; and so (p', pf") = arg maxp.y' (';) must be on one of the four boundaries of F. Also, if p- = 0, then p' = 0, and (0,0) is a corner point at the intersection of two boundaries. Similarly, if = 1, then p' = 1, and (1, 1) is also a corner point. This concludes Vp E [0. 1], (p".p'' = arg p.x f(P p':7) must be on one of the four boundaries of F.
To show Vpf(p. > 0 for p E (0, 1), we write vpf(D.d'n)) - A B in Eq. 55 and show that A > and B > O.
To show A >>000 0, first note
K=1
711) (1)
Σ
(p'(K- - 1)(11 -p) - p) =0
(57)
1
(1) p/(K - (1)(1 - -p)
K
K
700
711)
1pp' -pp' (1 - p))
(58)
1
1=0
k-1
7()
K -1)
1) ))
K K- p'(K 1)(1 1-1
K
Σ 711)
(1-1) _ 1p'-- x))
K (K-1) 1) K
(59)
K=1
7(1 (K-
(K-1) - 1) 1) (1-p)) -- > K
K -K11) 1 - (1-11p
K
(1-
7(1)
(60)
1
|-1
1=0
1=1
K-1
X-1 -1
T())
K --1
1 p/(1 -p)k--1>
7(+
1)
(K 1 -p) 1-11
K (K-1)
(61)
1=0
Since 44 < K-1 7(1) 2 71 + 1) and E (0, 1), there is for 1 E {0,....
K-1 - 1},
7(1) (K, - 1)
1k-1) p1(1 - p) k-1-1 2 201++1 1)
K (K11) p0(1 1 -)
(62)
1
Furthermore, since r( (k=r1)
> 0 and p E (0,1),
7(
K
2
K
K-1
K-1 2
(1
- p)
- >
(63)
2
Eq.
62
and Eq.
63 combined implies
K
K-1
7(
K --1 1
K - 1 1-
p x 2
(1 p)
T(1)
(Kr pl p1(11 - p)
K -1
Σ
701 + 1)
(K- (K11)
1)p'
p'( K---
K-1
1=0
(64)
and hence, Eq. 61 holds. This further implies A >>0 O.
Next, to show B >>0 0, note that
K
K 1 100 (1)
B= =
(1p'-1(1-
- -x) p¹ (K- - -1((1 - (p) >0
(65)
K
(K) x00)
(K) (4) 1)(1-p)k--11
1
000() 1p0-1(( (1-)((11- K- >
Σ
(66)
X+1
1= K41
27

---

Published in Transactions on Machine Learning Research (November/2004
K
K 1) K 1-1 (1-1)²
Σ
2(1)
11 - p)) K-1
(67)
T
X+1
K-1
K-1
K
Σ 701)
K -1 p - 1)(1 - 1)
K (1-1) -p' - K-
K
7(1)
(68)
1= K+1
K
(x-1)
> KKK
7(1)
.p' - -p)
K
K (1-1)
K
(1-1) (1-11) (1-1(1-p) p)) k))
K (K-1)
4
Σ
7(1)
(1-))
Σ
a11 - 1)
7(1
k-1
(69)
1=
1= K +1
Since vl 2 K+1
711) 2 71 -1) and p E (0, 1), there is for 1 E
K++ 2
,,... K},
K -
1-1 (K-1) p/ (1 p) p)k= k-1
K K-1
7(1)
1-1 // 1 (1 p) k- 2 201 -
(70)
Furthermore, since >( + > 0 and p E (0,
7
K +
2
K
K-1 2
K-1
2
-1-
(1-p) _ 0
(71)
Eq.
70
and Eq.
combinod implics
K ++ 1
K -
[ -1- 1) (K-1)) (1-))_) k-
K -1)
7(
p (1 - p)
7(1)
>
Σ
7(1 1)
1 (1-1) p
-p)=-
_
+1
K+1 k+1+1 +1
(72)
and hence Eq. 69
holds. This further implics > 0.
Following Eq
55
for p E (0, 1) and y satisfying the three assumptions,
vpf(p,p'n)) A B 0
(73)
Following similar techniques, one can show for p E (0, 1) and y satisfying the three conditions,
V p': 7) <
(74)
This implies there no local minima or local maxima inside the feasible region F. Also recall (p.p') e {(0, 0), (1, 1)) are two special cases where (p.p') at the interscction of two boundarics. Hence, we conclude the worst case probability (p", f0*,""*) = arg pa (', is on one of the four boundaries of F that is, (p", ,p") satisfy one of the following:
aag
1
x² = ='pp
Vp [0,
+
1.p'
E
10,
-
1
D" = épp"
Vp E [0.
lip' [0, I+ee
c
1
1 1-p' c (1 p²²),
Vp
It
11,p''
I+e-c:4
1 1- (1- - -p"),
1 Vp
T
11,12'
_ 1]
28

---

Published in Transactions on Machine Learning Research (November/2005
Lemma B.3. For any noise function y : {0, 10,1,...,KK) K) - 10, 1] function that is 1) symmetric around 2 and 2) salisfies the monolonicily assumplion, the privacy cost objective ((p.p'>) is mazimized when 2 p/.
K
Proof of Lemma
B. Following Eq. 33 and Eq. 38 in the proof of Lemma 3.4 and that ó = 0,
Pr[DaRRM, = 1] e mh Pr(DaRRM, (D)) = 11
(75)
K
K-1
(ar e em ai)(()
Σ 1=0
(ay e a1))(1) S seme
(76)
K4
=((mp')))
where ag = Pr([(D) = 1] and af = Pr([((D) = 1). vI E (0, 10,1,....
K}. (......).. This implies
f(p.p':7) = Pr(DaRRM, (D)
(77)
Pr Pr.DaRRM, = 1]
Hence, (') is maximized when (r(DaRRM,(()) 1] 2 (D') 1].
(r(DaRRM,(D) = Σ
(D) = ((D) = 1| Pr[[(D) = 4
(78)
1=0
(1(0)-TQ) 1(1
2 + 2 -1)) Pr((C(D) = 1)
K
(79)
2
Σ (1)) au
Σ
(7(0) ( - x(0)) an
(80)
1=0
1= 1=111
K-1
1
Σ
7(1)
K (M)
p)) K-
K Σ x()) (K) pt (1-11111) p11
(81)
2
K+1
where the last line follows from the observation that in the i.i.d. mechanisms setting, L(D) Binomial(y) and ay is hence the pmf of the Binomial distribution at l.
Similarly,
K 1 2
Pr(DaRRM, (D') =]
Σ
7(1) (1)()))) 011111)11)))
7(1)
1 (1)
K
p²(1 (1 -p))--1111 +
2 (82)
1
K+1
1-0
Now define the objective
K-1
((3)
Σ 7(1) 80(1 (3)K- (1)
Σ
2
70)
(1)
1
K
311 111 + 1
(83)
1=0
for 3 E [0, 1] and it follows that Pr(DaRRM,(D) = 1] = h(p) and Pr|DaRRM, = =1y')(p)). We now analyze the monotonicity of h(3) in B.
A 21( Since 7(1) 2 71 + 1), VI < 1 and 7(1 + 1) >
For ease of presentation, define g(() =
(y(()
YI 2
7(), Vl 7, there is g(1 + 1) 2 g(), vl (O...., K}. And replacing 7()) with g(l) in Eq. 83
k M(B) Σ
K (K) 8² k-
9(1)
(84)
t=0
29

---

K+1 setting Published in Transactions on Machine Learning Research (November/2005
Vah(3)= = Σ 9(1) (1) (181-1(1- -3)
K
(K)
(K ( 118 - (1- 1-1
(85)
1=0
K - 1) K
K --1
K
Σ 9(1)
1,31-1(1 -B)K-1=
Σ
K - (K -K 1)3 3)
(86)
1-1 /
1=0
K
K
1 1-11 - 11 (1-))) -1 K
K 1)
K-1 Σ
K 1
3'(1 - B) k)--1--1
(87)
1
1=0
K}
K-1
Σ
9(1 1)
1 (KT)) 1)/1
K 11- 8(1 - -8))--11
K
K
Σ
9(1)
(
K -1) 80(1 - -11
(88)
1=0
(((+1)-9(1)) s((1) (K) (K-1)) 8
K
(9((+
B)K-
(89)
1
Since g(( 1) 2 g()) and ( - -3) 1-1 2 0, Vah(3) 2 0. This implies h(8) non-decreasing in and hence,
monotonically
Pr(DaRRM, (D) = = (DD = 1| = p2p
(90)
Therefore, f(p,p';7) is maximzied when p 2 p'.
B.2 Proof of Privacy Amplification (Theorem 4.1
Theorem B.4 (Restatement of Theorem 4.1 Consider using DaRRM (Algorithm 1 to solve Problem 1.1
with i.i.d. mechanisms {M.) i.e., Pi p, p p', vi E [K], the privacy allowance m. E [K] and ê = A A=0 0.
Let the noise function y {0, (0,1,..., K} + [0, 1] be that:
if m 2 2
K+1
7() =1
and if S K-1 2
[1 2h(1)
A K-1
7(1) = 22)(1) -1 44
2
K+1
2
where h([) = Σ
2m-1
2m
& then DaRRM,, is me-differentially private.
R-t
Li=m
(m-1)
Roadmap. Theorem 4.1 consists of two parts: y under a large privacy allowance m 2 K+1 and y under 2
a small privacy allowance m < K-1, We first show in Lemma B.5 Section B.2.1 that if m 2 2
= 1 suffices to ensure DaRRM,, to be me-differentially private, and hence one can always output the true majority of K mechanisms. In contrast, simple composition indicates only when m = K can one output the true majority of K mechanisms. Next, we show in Lemma B.10 Scction B.2.2 that if < K-1 one can set 7 to be 7DSub, which corresponds outputting the majority of 2m -1 subsampled mechanisms (and hence the name "Double Subsampling", or DSub). In contrast, simple compositon indicates one can only output the majority of m subsampled mechanisms to make sure the output is me-differentially private.
Theorem 4.1 follows directly from combining Lemma B.5 and Lemma B.10
B.2.1 Privacy Amplification Under A Large Privacy Allowance m Z
K+1 2
The proof of Lemma B.5 is straightforward. We show that given the constant Ymea (1) 1, if m 2 K+d, the worst case probabilities are (p",p'" arg (a f(p, (maz)) = (0.0) and notice that f(0, 0; 7max) =
me 1, 1, which satisfies the condition in Lemma 3.4 Hence, DaRRM...... is me-differentially private.
30

---

Published in Transactions on Machine Learning Research (November/2005
Lemma B.5 (Privacy amplification, m 2 1) Consider using DaRRM (Algorithm 1 to solve Problem 1.1 with i. mechanisms {M i.e., P: = P. p/ = p', Vi [K], the privacy allowance m Z K+1 m and 8 == A O. Let the noise function be the constant "maa (1) = 1, 14 10.1..... ...., K). Then, DaRRM is me mee-iifeerentially privale.
Proof of Lemma B.5 First, notice "man (1) 1, Vl E {0, 10, K} is: 1) symmetric around /x4 2) satisfies the monotonicity assumption, and 3) Ymoal 2 > 0 and Ymea {+1) > O. Therefore, by Lemma B.1 the worst case probabilities given Ymanx Le., (p" p²") = arg (p.p) f(p p'; Ymax), one of the two boundaries of F, satislying
E 10 1
p¹ = =Epp',
Ap- E 10,
E
1
or 1 1-p' = = - p²),
4p E T 111"" E
1]
1
We now find the local maximuns on the two possible boundaries, i.e.,
(Piocal: Plocal)
arg max (p.p'):p=e'r pElo,
[(pp' Imax)
and
(Focatt Plocat)
arg max (=0")=1-====((1-p)
(p, p': Tmaz)
separately.
Part I: Local worst case probabilities on the boundary p e'pl.
Plugging p = e'pp' into the privacy cost objective f(p, ?maz), one gets
(K) (1) Pd (1
11 (1- -1)pp))--11- (1-1)x-11 ( (E)
f(p': Mmaz)
Σ (e
(91)
1=0
Σ (1)copyC - - - -emm-ee( (t) -x)) -p))
K
(K)
Kt1
The gradient w.r.t. p' is
K me (K) 11p- (1-)) K p²(K
Vp ff f(': (max)
1)(1 - p
(92)
K
(((E88))) - e k- c P - 1)(1 - -
K
(er (c(())
Σ
(1 - ((
e MK( - () - ---1)-11-1
x+1
K
(lp" 11 - R- -D" p²(KK 1)(1 ,/)(-(-1))
K
mc (K
K (1 K 1² (K-1)
K
Σ
mc
(Ki 1² (1 K-1
(K - 1
(93)
1=0
I-
K - 1) (cp')((1 k - K
K-1
(65))"(1 ( -et))-k))))
(K-1)
K
Σ
1
K+1
31

---

Published in Transactions on Machine Learning Research (November/2005
+ K
K=
Σ
e me
(1 1
K - -11
p0 1 111-pp -1
K-11 - K Σ e
K-1
(KT p0a ( -1 -p))p-
K
1=0
R-1
K-1 -1
K 1 (Kr
K-1
Σ ee [K
(6
K
+ K
(1-
1=0
-r1
-2K c
K -
p
x (1
-
p')
+2K e¹
K -
(e'p') - (1 e'p')
(94)
K-1
K-1
2
==A
==B
Notice that
A B
me
(1 11) K (1-1)) _
e
1 p' exp
(95)
e =
T-etp Since 1- 2 and m 2 K+1 2 1. This implies Vy flp:: Mmaw) S Hence, f(p's7maz) Tmaz) is monotonically
non-increasing on the boundary, for p' E [0, I+e-
Therefore, arg magp 0. r(oo f(D Mmaz) = O. Since p = e'p', p' = 0 implics = 0.
Hence,
(Pioetts Plocal)
arg max pE(0
( Tmaz) (0,
and
max (p-r/ Dopmmop' pE 10.
= -00 0; Ymaz) ) = =6 me -
Part II: Local worst case probabilitics the boundary 1 1-p'=c
For simplicity, let q 1 - p and g' = 1 hence, q E [0, - and q' E [0, [.
11//// p/. Note on this boundary p E (=-=, 1) and p' E (1tor : 1J. and
Plugging q and of into the privacy cost objective f(p,'' Ymax); one gets a new objective in q, q as
(K) (1 ())' (4) (1 x)) 1) "maa (1)
f(g, 30 Imaz)
me
(96)
K
(1 g)ggk - me (1) (1 -0)) -mmas (1)
K-1
Σ Tm (1) (1 ())gkk (K) (1 - 2)-)
(K)
KK
(97)
1=0
(K)) ((1)
(1-9)' kt me (K) (+) (1))1- (()
K+1 1=
2
Since on this boundary, 1 - p' e² (1 p). writing this in q, o' this becomes g' e.q. Plugging g' e'q into
I [g, d' 7max), one gets
1
f(g ?maa)) = Σ ( (mme (K) (K) e -))( -K) (1-)""88-))
(98)
1=0
32

---

Published in Transactions on Machine Learning Research (November/2005
K Σ K+1
(1-1)"00"-1 (11) (K)) (1 - 0)'90~1 -emc (+) (1 - -
-))
The gradient w.r.t. q is
me (1) (--0)((0- x + (K - 1)(1 {()())))(--1))
Val(0)= =
(99)
K ( - 1(1 - 1 K- + (K - 1)(1 9)1(x-1-1))
K
(1) (- ( 1(1 9) K -1 + (K- - -1)(1 - -2)
+
eme (1) ((-e))(1 - =0g) (E - + eK( - -1)(1 - 1)((1)10))))
(()))))(()))))---)))
K-1
clmttyee
(K- (K-1) K
(1-1) 7 111
(e K-1 + Σ
clm+ (
1K-1)
K -7 (K - -1)(1 - (())))))))))
K
1=0
(100)
K - 1) K
111 T 1(1 - 9) |K
KK
K
K
(K-1)( 1)(1 -
-101--0)a---1 0)'9k~1-1
K
(k-1) [ 1(1 9) 11 1 k +
(K- 1) K
K-1
K -
K
Σ
(K- ( -1((1- - -9)
1
K-1
K+l
K
(m (K-1) K
7 1(1 - E9 (e))))
K-1
Σ
(m+1)e
-)(- ) (K -
(K [oKK K K-
K (K-1) K
+
L= اj
K
K
(K (K-1) (1 (K-1(1
(K (K- (1 (1- g)) -
= C-K KK)
(m+1)e
k-1 K
cm
(1-1)
1=1
1=0
(101)
K-1
KK)
K - 1)
(1 1) 7) K- K
K 1)
(1 - -2)0
1 1-1 1
E
1=0
K
Σ
K -
(1 - 9) 9 k + K
K-1
Σ
1 (K7)
K -
) (1 (1- 92)g
(-1 1
t= k=
K
(1 ( E 1-1 (6(g) K-1 -1 1 K
K K-1)
K-1
K (K-1) (1 - e ())
+ K
el 1m
Σ
l)e
11-
K-1
1= K-1
22 22eeemll lm+
K K-11 11
K-1
(1 - e'g) _ (e'g) " -2K
K 1
K-1
(1
K-1 K-1 4)
q 2
(102)
2
2
Recall q E 10. [-_ and so (1-6' 9) 2 (1- q)q. Furthermore, since c(m++))e 2 1, there is V₂f(g) 2 0. This implies f(q) is monotonically non-decreasing in q, and so the local maximum on this boundary is
(giocat: ((ocat =
arg max
flg. (a.zz)) Tmaz) = ( "Ite'' Ite-
(103)
(00 +
33

---

Published in Transactions on Machine Learning Research (November/2005
That is,
1
(Piocals Plocal)
arg max (p./
f(p. p': (m)aaa) = (1 Nocull Nlocel) = Iteee' lt
(104)
Part III: The global worst case probabilities.
Notice that (ite-c: 1+ee), ); the maximum the second boundary 1 - = c²(1 p), vp E lite-e: 1), is indeed the minimum on the first boundary p= e'p'p', Vp E [0, Ite s+1
Therefore, the global maximum given "mmax
arg max (p',p") = arg max f(p, (...p' Ymax) (p.')) pppppppppppppppppppppl 11 (p.F))FF
f(p. (mma) = (0,0)
(105)
and recall that f(0,00 0: Mmax) c
Hence, if m 2 K+1 by Lemma 3.4 DaRRM Tmoux is me-differenttallyy private.
B.2.2 Privacy Amplification Under A Small Privacy Allowance m S K-1
The proof of Lemma B.10 is slightly more involved. First, recall by Lemma 3.1 makes the output of DaRRM 75u and the subsampling bascline the same, is
7Sub, the noise function that
YSb (1) 7Sub (K
1 - 2 Σ
if m is odd
if is even
-= +1
for 1 E {0, 1.... KK. suppose the privacy allowance E Z.
(-1)
fimm odd
If we define h(1)= =
()(E))
())
then (l can be written 7Sub
if m is even
(M)
24(1) i K-1
21(1) 1 if1 K+1
This can be generalized lo a broader class of functions which we call the "symmetric form family" follows
Definition B.6. 7: 1, K} [0,1] is member of the "symmetric form family" if follows
x(1) 1 2h(1) 1-2h(!)
il - K-1
(106)
2h(1) - ifl K+1
where h: {0, I...,,,,J [0, and h(1) + hKKK - 1, 1(+112 Vl (0, 1.... K}. and 7( K -
K + 1
0,
It is easy verify any y function that belongs the "symmetric form family" satisfies: 1) symmetric around and 2) the monotonicity assumption. Hence, Lemma B.1 can be invoked to find the worst case probabilities
34

---

Published in Transactions on Machine Learning Research (November/2005
given such 7, i.c.; "o") = arg (px)) (p,)):)), which in turn gives us the guarantee of DaRRM, being me-differentially private.
Roadmap. In this section, we restrict our search of a good y that maximizes the utility of DaRRM, to in the "symmetric form family". To show the main privacy amplification result under a small m in Lemma B..0 Section B.2.4 we need few building blocks, shown in Section [.2.3] We first show Lemma 1.77 Section [.2.3 two clean sufficient conditions that if a "symmetrie form family" y satisfies, then DaRRM,, is mc-differentially private, in terms of the expectation of the function applied to Binomial random variables. The Binomial random variables appear in the lemma, because recall the sum of the observed outcomes on datasct D, L(D), follows a Binomial distribution in the i.i.d. mechanisms sctting, Next, we show a recurrence relationship that connects the expectation of Binomial random variables to Hypergeometric random variables Lemma B.9 This is needed because observe that for functions that makes DaRRM have the same output as the majority of subsampled mechanisms, the function is now a sum of pmfs of the Hypergeometric random variable.
Finally, the proof of the main result under small m (Lemma B.10 is presented in Section B.2.4 based Lemma B.7 and Lemma B.9 We show in Lemma B.10 that "DSub, i.e. the function that enables the output of DaRRM and outputting the majority of 2m subsampled mechanisms to be the same, belongs to the "symmetric form family" and satisfies the sufficient. conditions as stated in Lemma B.7 implying DaRRM being me-differnntially private.
B.2.3 Building Blocks
Lemma B.7 (Privacy conditions of the "symmetric form family" functions). Let random variables X
Binomial(K- L.''' Y Binomial( 1,,, e'p'), 8 ~ Binomial( 11, and Ý ~ Binomiall K 11p).
For function y 10.,,..., j0, 1] that belongs to the "symmetric form family" (Definátion B.6 if also salisfies both conditions as follows:
em 1/(xx + ( A(X)] 2 By +1)- Vp' E [0,
I Itedl
(107)
1)-1(()) 1) Eylh(P IN(8 + +1)-1(1))
Vp [
(108)
then Algorithm DaRRM,, is me-differentialby private.
Proof of Lemma B. 7 Since h((+1) 2 h() on / (O...,,,,y KJ, 7() 7(+1),, K and 2((+1) vl) K. 2. Furthermore, since h(I) [ -1) = 1, 7( (- 2h( K k=)) = 1- 211 K 2h( k Hence,
any 7 that belongs to the "symmetric form family" satisfies: 1) symmetric around 2 2) the monotonicity
assumption, and 3) 7( K-1 2 ( 0.
Therefore, by Lemma B.1 the worst case probabilities (p", arg max f(p,'' are on one of the two boundaries of F, satisfying
p" = =
Ap" E [0, e-r
1.p"
E 10,
(109)
1 1 ccl
or 1-p"= = e - p")),
Vp" E ( 11te0
1
11pp"
E
[+
1
(110)
We now derive the sufficient conditions that if any y from the "symmetric form family" satisly, then DaRRM, is me-differnntially private, from the two boundaries as in Eq, [09 and Eq. [10 separatte..
Part I: Deriving a sufficient condition from Eq. 109 for "symmetric form family" 7
Consider the boundary of F, p= e'p', Vp E [0, 1 1 E [0, ]
35

---

Published in Transactions on Machine Learning Research (November/2005
Given any 7, plugging p e'p'' into the privacy cost objective f(p, pl: :7), gets
K
(1)) (41 (6p')(( ()))))))))))))))
3(D':>) Σ
te
(111
1=0
+
Σ
K
(4)
KK)
-
ppp))=-
- (x)p²(( (1--1p (1 - 7(1)
e
The gradient w.r.t. p' is
K1-1
V 1D'':
K --1
p (1 (1(4+)) - me
K
(1-))
K-1
K
K
1
K-1
2
1=0
(112)
K
K -1 "1)'''' ('11-))
c me
Σ
-0(10)~01 (1++
1
K -1
1 ) ( (((0))>(++1)) + 20
-K-1
(e
_ (1 - _ 7
K K-1
K-1
2
2
K-1
KK 1--
+
(1-
Consider E (0, KJ in the above Eq. 112 For any function y that belongs to the "symmetric form lamily",
1. If 2 7() 1) (1 (1-2h(1) (1 2h(1 + 1)) 2h(1 + 1) 2h(1)
2. 1
K , 7(1 11 - -()) (2h(1 1) - 1) (2h(l) 1) = 2h(1 + 1) 2h(1)
3. Since 7( ( = 7( (
K
K
K *+1)
27(
77(-
+ 7(
(113)
2
2
K
K + 1 1 1)
1
2h
+22h
+ 2h
(114)
2
K + 1
K 1
2h
2h
(115)
2
Hence, following Eq. 112
the gradient, pp'(()) given a "symmetric form family" y can be written as
vp Sw''3)
- mee Σ
K-1
K
-1
pd (12)))<(22h(1+) 22((1)
(116)
K
1=0
K-1
+ E
Σ
- (2h(1+ + 1) -2h(1))
1)
)
1=0
- E (x + - -(X)) + 26 Ty (n 1) ((Y)
(117)
where X ~ (inomial(K-1) - 1,,p) and Y Binomial 1, The above implics
(wfliin)) 50 + e'Eylh(Y +1) +1) -oY)) <
-(x))
(118)
36

---

Published in Transactions on Machine Learning Research (November/2005
If V V (p':))) O, then we know the local worst case probabilities the boundary p=''p',ppE [0, + given any y is (Piocat Plocai) arg
T+.=] ((pp'':) (0,0). Furthermore, recall the
privacy cost objective given any is
f(ppp':))
K
_ aar) 7711
+
Σ
(an
K
= Σ eeme ( p'yk-1
(
(1-p) (L))))))))-)))) 7(1) +
Σ
K
(1) p¹ (1 -p) p)k-11
- -cm -cm(()) -
7(0
1-0
and so for any
027) (e - 1) - 7(0) S e 1
(119)
Also, notice the local minimum on this boundary is
1
(pmin: (pmin:Pmin Pmiin (pa"")p=="p p/ .e(0
arg min
(p.p'1:7) -( (T+e-e lte
(120)
Part II: Deriving sufficient condition from Eq. 110 for "symmetric form family" 7
Consider the boundary of F, 11-ppp c'(1 - p), vp lite 11,p' E litee, 1). For simplicity, let q= p E [0, + and q' = p' E [0, |. Plugging q' = e'g into the privacy cost objective, one gets, given any ?
me (1 (+)
-00-0-) 7(1)
7
(121)
K
(K)
(1- -
e u -((1)
+
The gradient w.r.t. is
IM
vgf(7))
(me (K u (7(1) 7(1 +((+1))
(122)
K
K 1 ) (1- é E) k-11 (7(1+ () 1)0) - (m+t)
K -
(1
E
=
K-1
(e5
K-1
77(
K
K-1
2
K - 11
1 )) (1 (1- -1-1 K-111 (,(1+1)-7(1) -01))
k (0(1)- -00+((11)))))))) -2 -2( (Kk=))
K -1
K -
9)
77(
K-1
For any function y that belongs to the "symmetric form family", the gradient (gf(g:)) can be written as
(gf(g)7)
K-1
K - (K-
(1=)co - () K-1-1 (2h(1 + 1) 2h(1)
= 1m+ Σ
(123)
K
1
1=0
37

---

Published in Transactions on Machine Learning Research (November/2004
K
K - (1 ()) (2h(1 +1) - -2h(1))
Σ
1=
1x 11(8 11)-h((8) 25y [h(8 + +1) - h())] (1-p)) where X ~ Binomial(K' -1,1 -1,1-1(11100 p))
2e (me+m11)
(124)
and y -BBnomiaa(K 1.p) The above implies
(al(sn)) 2 = (m=+)) 1n(X 1) - h(X)) 2 Ey [1(P 1) I(P)
(125)
If (4)() 2 O, then since q E [0, ] we know that the local maximum given any y is (Nooctt Hocaat arg max (g qe sed f'q.9'17) = (It Ite 2) That is,
1 f(p,p':7) (1 - Nooctt: (ooaat ( (1 e
1
Proents Pincett)
arg (p-"))=--'=ct(1 p)
Notice by Eq. 120 the above (Ite e Ifft is the local minimum on the first boundary e'p', Vp E 10, Itc c Therefore, given an arbitrary function, if it satisfics both of the following:
1. On the boundary = E'p', Vp E [0, |
00
On the boundary - p'= = E - p), vp E liteer 11, Vg f(d:n)) 2 where 1-1111
then the global worst case probabilities given this y is (p",p"") = arg max (x.")) f(P ((:))p')) (0, Further- more, since by Eq. 119 f(0,0;7) S the for any 7, this implies DaRRM, is me-differentially private by Lemma 3.4
Now, if y belongs the "symmetric form family", by Eq. 118 and Eq. 125 the sufficient conditions for y that enables DaRRM,, to be mc-differentially private are hence
Eh + +1) h(Y)) S e==Ex [h(X + 1) h(X),, Vp's E [0,
I+ e
1
and e (h((8 1) h(X) ż Ey. [h(8 +1 +1) -(M)).
Vp E 1 1
where X Binomial(K - 1,pd) Y Binomial 1, 1, x Binomial(K 1,1 1 e² - p)) and γ ~ Binomial( -1,pp)
Lemma B.8 (Binomial Expectation Recurrence Relationship (Theorem 2.1 of Zhang et al. (019))) )) Let
((K-1) Binomial( K 11, and X(K) Kinoomial(K,, p). Let g(x) be function with -oo < [[g(X((-)) <
0o and -o < g(-1) < 00, then
KpE Xix Ex ((K)g(X(X) 1)] -1]]
(126)
Lemma B.9. Given m, K E, K 1, K, let X(K) Binomial( for some p [0. 1], there is
(*)({=>)))))
- 1(1)
m p' -(m)'' p-
Ex
(127)
m
Proof of Lemma B.9
We show the above statement in Eq. 127 by induction on K and m.
Base Case: K- 1.
1. If m 0, then i= 0.
1 Ex (1)xx= Ex,, [1] 1, and (r p))
(
38

---

Published in Transactions on Machine Learning Research (November/2005
2. If m 1,
(a) = 0,
1 xx (:)
= Ex [1 X] =1-p. p, and (1)p((1 - [p)'' = =1-p
(b) i = 1. (1) Ex (xxx)] Ex [X] = P, and (1)²(( pp) p.
Hence, Eq. 127 holds for the base case.
Induction Hypothesis: Suppose the statement holds for some K 2 1 and 0 S i S m S K. Consider
sissss m K 1,
(?)({t) K (
mii// [
Ex Ex(x11
(128)
1
1
X!
(K 1 XY!
Ex i!(X - ii]! (m - -i)!(K +1 - -Im i))!
(129)
)
(X-1)! 1)!
(K - (X - 1))!
(k+)) (()))i((m jil(m - -i)! Ex(e+1) X
(130)
((X 1) - (i - 1))! (K (X 11 ((m 1) - (2
X!
(K-X)
Ex(Ks] (X - -1)1 (K - X ((m - 1) - (i 1)))!
(131)
(K+)) p1(mm - i)!
(By Lemma B.S
(i 1)1(m - 1)!
X ) ( (1-1)
(m - 1) - (i - -1)1
K-X
(r)))a(mme -i)! Ex(xy
(132)
(i-1)
(i- 1)! (K + +1)p
K )) (m (#-1) p²-1(1
m amn-1 1)
(1 - p) mー
(133)
(K=))
m - 1
(By Induction Hypothesis)
m!(K + 1 - m)!
K!
(m- - 1)!
(K + +1)p'(1 - m
(134)
(K + 1)1i (m - 1)!(K
m + 1)! (i - 1)m( - i)!
al(m m-."" (1 - (1-p)m p)m==
m!
m
p² (1 - p)m
(135)
i
Now we consider the edge cases when 0 = i S m.
i = 0 and m = 0,
Ex Ex (7)
[K+1 + (k)
x) x) 1- Ex [1] = = ( (1-
(136)
1
0
If 0 and m > 0,
1
K + X
EX
(137)
(K+1)
m
K + 1 x
)
(K +1
p² p=11 (1)p))+t3 K
(138)
K+1
m
x
K+1
KK + 1
x (
(K))
K
1s 2 11) (1) (1-)) K+1- + (K)
K
(139)
(K+T)
m
x-
K
K +
K
1
K+1
+ 111
K ) p² - (pppp -p)xp1=-= K+1-= (140)
(T(1 - -p) x +
m
ktl
m
x -
0=
m
r=1
K +++ - x = 0)
(Since when x= = K + 1 and m >0, 0,
m
39

---

Published in Transactions on Machine Learning Research (November/2005
K
K 2
K
K I
K
p² (1 pp
p (1 p) -)
(141)
K+11
m
m
m
2=0
2=0
1
K -
K
+
(1 p) K-
(K+1)
m
==0
K + 1 - x
K -
m -1)
K - x
(Since
+
m
K -
(
K -xx))
K - -X
(1- (1-p)_x((o)]
| + (1 -D)DLxx(
plE p
(142)
K+1
m
m
(K*1)
m
(K+1) Ex(xy|
K - -X
) + - -p))Ex(s
K -X
(143)
m7 07-1
K
(1 p) + (1-p) p)
m - ) (1 -p)) -)
K
(144)
(K+1)
m
(By Induction Hypothesis)
(145)
K + 1
p)m
(146)
(K+1)
m
(1 p)m
(147)
Hence, Eq. 127 holds for all K 2 1 and Osis K.
B.2.4 Main Result: Privacy Amplification Under Small m
Lemma B.10 (Privacy amplification, m I K-1). Consider using DaRRM (Algorithmm) 7 salve Problem
with i.i.d d. mechanisms {M.) pt Ps p/= = v', Vi E [K], the privacy allowance S m S K-
2 m E and
A 0. Let the noise function be that
1 2h(()
VI (0. 1, K-1
DD)
(148)
2h(()) - VI E ( 2
K-1
K}
()) (:)mm-1-))
where 10,1....,KK K) [0, 1] and h(1) Σizm DaRRM me- diedifferrntially private.
Vl 10, K), then Algoritlmm
2m
Proof of Lemmaa B.10 First, note 7DSub belongs to the "symmetric form family". We show 7DSub satisfies the two sufficient conditions in Lemma B.7 and hence by Lemma B.7 DaRRM is me-differentially private.
Specifically, we consider h(()) = Σ 2m-1m
2m
Vl E 1..,, and 1 I m S K.
i=m
(2
Two show the first condition is satisfied, let X(K-1) Binomial(K 1, p) and Y(K-1) Binomial 1,, e, and consider p [0, +
1
2m
X (X+1)
K (K x
E Exix [h(X +1]]
Exxx- 13
2m 11-1)
(149)
K
i
2m
i=m
2m
(X)
K x-1 -1) + *(xx)
K (K- K-x-1 -
Exxx-19
(150)
K
1
2m 1-i)
2m 2m
2m
1=
X X+1
X
(Since
=
+
T(i 1})
i
i --
40

---

Published in Transactions on Machine Learning Research (November/2005
2m
2m - - (
(K K x)
+ Ex(x-1) ( (1-1) (
(2m (22m 1- X
E [x(x-1) (
K
2) - (i 1)
2m
==
(151)
1
2m-1
K - 1
(2m= (2m-1)
-1 1) 1) p²(1 -p)mm-1- -) + K- -
(2m -2 (2m-2)
2m 1 1
i-1 (1 p)2m-
2m - 2
2m
==
(152)
(yy Lemma B.9
2m
(X) ( K -X
(i) 2m 1 )
Ex Ex Ex(x-1, 1,[h(X]] =
E Ex(x-D) 1)
(153)
2m
i=m
K - X
2m - (2m-1-;) + (K- 1 -
K - - X)
-K-1-1
(m 12m-2-1 )
(Since
2m - 1 11-1)
2m-1
EEx(--11 11
(1)
K - 1 1-x)
2m 1 --)) + Ex(x to (t)
(2mm 2 -1) 2-1) I[ S 2m - 21)
K 1- X
2m
i=m
(154)
2m-1
K KK- 1)
(amm
(2m 10n-11 1)D' (p(1-p)am---i
2m - - (zm) (mm-)) 22) ")x7 p'(1 p)) 12-22-1p I-f - 2m - -27)
K K-1)
2m
2m
i=m
(155)
(By Lemma B.9
Hence, following Eq. 155 and Eq. 152
E (1 [h(X 1) h(X]]
(156)
2m 1
K -
(2m -2) 2)
2m-2 Σ
K -1
22m 2)
(i-1 ) pr- - 2m)2m-1--
p'(1 - p) ) 2-1)
2m 2)
2m - 2
i
2m
i=m
==
(157)
2m-2
K 1
10'11 (zm--) -2) 2)
2m-2 Σ
K -111 11
(2m - 2)
2
p0(1 2m 2-1
2m 2
22m -2 2)
(2m1 1
i=m-1
(158)
2m 1/2mm - 2))
m - 1 pm 1 - p
(159)
K
Similarly,
Ey [6 + +1) -())] = 2m /2m - 2)
K m - (e5p)m--(( - ppp)m-1
(160)
Since p E [0, 1 there is p(1 - p) 2 E - -epp). Hence,
e( ( [x(X +1 - M(X)
2m 1
2m - 2)
e(m m1m-11epmm-1 11(1 - -p) pp)
(161)
K
m 1
2m 1
22m - 2
e (m- (m-- ( - -e(p))
(162)
K
1
2m
12m - 2
(e (e - m
(163)
K
m 1
41

---

Published in Transactions on Machine Learning Research (November/2005
By In(Y + 1) h(Y)
(164)
implying
é Ex [1(X + - - 2 e 1x + +1) - -h(Y)
[b((
(165)
and the first condition is satisfied.
To show the second condition is satisfied, let X(K-1) ~ Binom [K - (1(-p))) and I(--) ~ Binom 1, p), and consider p E 1 1].
2m
E (Exx--D (7)) (K 1K-1- 8)
2m - 11 1 + Ex (==1) (
K K-1-x 8
Ex (xx) [M{8 + +1] =
K
-
(2m 2) - (i 1)
2m
(166)
1
2m-1
K - 1
1)
22m - 1) (2m-1) ) (1
e1- p)) (11-))) - p)) (1)))mm) 2m)
(167)
2m -0 1)
2m-1 1
i=
K 1 1
2m -2 2)
i-1 1 (1 (1- p))- (e -)))
2m 2
By Lemma
B.9
and
E Ex(x-1 11 [1(8]]
2m-1
E [x (1)
(8)
K 16-1-1 1- 1 (K-1-
2m (2mm11 - - +E Ex (:)
(K
22m i M1 s 2m - 2])
K - 1-11-1 8)
2m
i=
(168)
2mn
2m 1) 1)
K -
22m (2m-1] 1) (1 - é - (1 (--p)11-)000)))) -p))am-t-
(169)
i
imm
- 1
2m -
i (1 (1 - p)) - 2m 2 ip{L S 2m 2))
+
2m - 2)
By Lemma B.9
Hence, following Eq. 167 and Eq. 169
E
[x8x + 1) - (x))
(170)
1
2m-1 1 K -1) (2m 22)
(i-1) )(1 (1 (-m-)(1-- -1 p))) (6 - pm) 2m-11- 1-1
(c(1))))*
(171)
K
2m -
2m
2m
K
(2m- 2)
i ) (1- (1- - (c) p))2m-22-)
2m - 2
i m
1
2m-2
K - -1)
(2m- - 22)
i 911 - e- (e) p)) 2m)
(172)
K
2m - 2)
2m
i=m-1
2m-
K -
)
(
(2m- 2)
i )
(1 - e²(1 (p)))(e(((11111 p)) 2m)2
2mm- - 2)
2m-
(2m- - 2)
(1 - e0(1 p)) m- ( - -))
(173)
K
m - 1
Similarly,
2m - 1 1/2mm - 2)
E Fy [1(P+ +1 -h(() (1)(+1))((7))
m - 1 pm 1m1111 (1-p)--- mp
(174)
K
42

---

Published in Transactions on Machine Learning Research (November/2005
Hence,
e( ( 11(8 1) -N()) em++1e 2m -
2m - 2
m (1 e1 (1- (m
m)
(175)
K
2m 1
(2m= 2
e' p)) (00-)((m-1rr -)
(176)
K
m
2m 1
22 2)
(er e²t(1 -p) p)) 1 p-
(177)
K
m1
Note that
- e p) 6-
2² + + -
2p
(178)
- (e' + +)(E - 11pp 2 éeee" - -1)
(179)
e¹
1
p> et ++ 1
(180)
and the condition needs to hold for E 11.
Therefore, following Eq. 177
2m - /2m - 2)
( x x1) 1((+1)-((8)1>
K - pm 1m- - mp)m-
(181)
E B [((Y+1) ((X+1)--(Y))
(182)
implying the second condition is satisfied.
Therefore, by Lemma B.7
DaRRM is me-diffcrentially private.
B.3 Comparing the Utility of Subsampling Approaches
Intuitively, if we subsample 2m - 1 mechanisms, the utility is higher than that of the naive subsampling approach which outputs the majority based on only m mechanisms. To complete the story, we formally compare the utility of tutputting the majority 2m-1 subsampled mechanismi (Theorem 4.1 and outputting the majority of subsampled mechanisms (simple composition, Theorem 2.2 in the ii.d. mechanisms and pure differential privacy setting, fixing the output privacy loss to be mc.
Lemma B.11. Consider Problem 1.1 with i.i.d. mechanisms {M) i..., p P: p= P P = PP') 1j, Vi E [K]. Let {0, 10 I..., KJ + [0, 1], {0, 10,1,... K} - [0 be two functions that are both symmetric around K. If f (1) 2 (1) 2 0, VI E [o..... K), then E (DaRRMM,,) s (DDRRRM))).
=
2
Proof. Recall S = {S1. Sk]. where S; ~ MDD), is the set of observed outcomes from the mechanisms KK [M By Definition 2.4 for any y that is symmetric around & 2 the error of DaRRM, is
{(DRRRM,) Pr[DaRRM, (D) 1] Pr(g(S)= = =1
(183)
K-1
K Σ
(x(0) + (1- a. +
2 (1-7(1) 04
ay
(184)
1=0
(5(00) - - aq + Σ
2
/
70)
at
(185)
1=0
(1-700 (1))(1) (ar ax-i)
(186)
2
K+1
43

---

Published in Transactions on Machine Learning Research (November/2005
where a; (1) - p) (1)p((1-p)++ , 44 E (0. K} and recall p Pr(M,(D) 1]. Vi E [K].
For any 2 K+1
p= = or p= 1, ai = a--I-
2. Otherwise, for p E (0, 1),
(a) p 2
21 K
p' (1 p) k-1
=p² k(-
K-21
21, 3 2 0K-1
(187)
pk-l( p)²
0K
(b) If < 1
21 -
K
P
20
S1, 7 az S aK-1
(188)
OK-I
21
Hence, if 2 3, then at 2 ak-i,
1A 2
K+1 2
K}, 1 1 (1) S 1-22(4, and so Since 71(1) 2 (2), 1I E {0, (O....,K)
K
1 (1 (2)) (ar -a
g(DaRRM,,)) Σ
(1-1((1))
(ar ak-1) S
Σ
&(DaRRM..) (189) ak-i) (a-akki)
2
K+1
K-1
Similarly, if p 1 then ai Sak-i, v2 K+1 and
K
E(DRRRM,,) = Σ (1 (1) (ax-1 - an) s
Σ
(1 72()) (ak-) a,) = E(DaRRM,..) (190)
2
1=
Therefore,
E(DaRRM,,) S ((DaRRM)g)
(191)
Since (D)ww(() (I), W E (0, K}, by Lemma B.11 (DDRRMM S &(DaRRM ysus) that is, outputting 2m mechanisms has higher utility than outputting mechanisms.
44

---

Published in Transactions on Machine Learning Research (November/2005
C Details of Section 5: Optimizing the Noise Function y in DaRRM
C.1 Deriving the Optimization Objective
For any function that is symmetric around 2 we can write the optimization objective as
Ep.. (DaRRM,)]
(192)
P2......... Pr Pr(DaRRM, = 1| Pr(g(S) =1]]
(193)
K
an (1((1(1) + 1 (11->(0)) as) + Σ
-(1-
(194)
K+1
1-0
= =Ep..t......
aul (212
1 )
Σ
0n 2
200
(195)
2 2
The above follows by conditioning L C=1 - f0, 1, ..... K}, i.c. the sum of observed outcomes in S
Ep PP......px PK-T T
Σ (a-- - ak-)))))(1--(0))
(196)
2
1= 2
The above follows by symmetry of y
Furthermore, notice the objective is symmetric around 0, and can be written as
Eyp P2....
(ar ax-
(197)
1
K
2 Pp..p....PPNT
E
Σ
(al - ak-1) - (at - ax-in())
(198)
K
K
E P1 P2.......... .R..P.....PPTTTTTTTT
(ar - ga-ak-ll aK-
B PII.Pa...PPPTT T
(or ax-1))(1)
(199)
2
Since expression in Eq.
199 does not involve 7, we only need to optimize expression B Eq. 199 That is,
2 P.....pPPTT
Ep
Σ (ar ax-i)(1))) K+1
(200)
K
PxT -ooa-aa-i)) -())
(201)
2
Eq. 201 is the optimization objective use in the experiments. We see the optimization objective is linear
in 7.
Note the general setting, C(D) ~ Poisson P2..... .K), where recall C(D) is the sum of observed outcomes on dataset D, and hence, on = Pr[[(D) = is the pmf of the Poisson Binomial distribution at E (0.1....,
C.2 Practical Approximation of the Objective
Since the optimization objective in Eq. 200 requires taking an expectation over PI..... ......PK. PK. and this invovles integrating over K variables, which can be slow in practice propose the following approximation to
45

---

Published in Transactions on Machine Learning Research (November/2004
efficiently compute the objective. We start with simple idea to compute the objective, by sampling pi's from [0, 1] and take empirical average of the objective value over all subsampled sets of . as the approximation of the expectation in Section C.2.1 However, we found this approach is less numerically stable. We then propose the second approach to approximate the objective Section C.2.2, which approximates the integration over p, ss using the rectangular rule instead of directly approximating the objective value. We use the second approximation approach our experiments and empirically demonstrates its effectiveness. Note approximating the optimization objective does not affect the privacy guarantee.
C.2.1 Approximation via Direct Sampling of p;'s
One straightforward way of efficiently computing an approximation to the optimization objective is as follows:
Algorithm 4 Straightforward Approximation of the Optimization Objective
Input: # mechanisms E N, # iterations N, noise function y {0, ..,, . - [0.
for = 1.2....,7 do
Sample P1, fa. ...
L - PoissonBinomaill1) (
âi - Pr[C 1], Vl{0, .... K}
6:
9t - - Σ xyu (āi âK -1) -1 (1)
7: end for
8: Return $ + 9t
However, found this approximation is not very numerically stable even for 7 10000 in the experiments and we propose to adopt the second approximation follows.
C.2.2 Approximating the Integration Over p.'s
Consider the following surrogate objective:
K
( f(... ... 0.5 0.5
[ (a: (a1- dox-)))didp2...ooe ... : 7(1)
(202)
where approximate the integration instead of directly approximating the objective value. The approximation of the integration is based on the rectangular rule and that the Poisson Binomial distribution is invariant to the order of its probability parameters.
First, we discrotize the integration over p. 's pick r = 50 points representing probabilitics between [0.5, 1) with equal distance = 0.5 Denote this set of points as W. We pick only - 50 samples to ensure the distance between each sample, i.e., 0, not too small; or this can cause numerical instability. For each K+1 K+1 K,, want to compute an approximated coefficient for 7(1) as follows:
I..'a.. (o ((u--x-a ox-))ddppppppp ... dpk ΣΣ PIEW PeW
Σ (a) ak-1) PREW
(203)
which approximates integration over K K-dimensional grid w
The idea is then to sample points from this K K-dimensional grid WK and compute empirical mean of the integration based on the sample probabilities for PI,..., from W as the approximation of the integration in the objective.
Let (81, . : sk) be randomly sampled probability values from W and we want to compute (ar - ax-) for all | based on (P1....,PP .Pk) (Si...., To apply the rectangular rule, since the grid of probabilities is K-dimensionall, the weight of (ar ax--)) in the approximate integration is 0k Furthermore, observe
46

---

Published in Transactions on Machine Learning Research (November/2004
that aj is the pmf at / from a Poison Binomial distribution in our case, and Poisson .K) Doisson Pk)), where æ denotes a permutation of Pi..... Pk and diet. denotes "the same distribution". Hence, with single probability sample ($1...., sK), we can indeed compute ay - ak-i for each at K! points from the grid W since they all have the same value. Therefore, ox- in the approximate integration not affect the objective value, there is a total of (7 choose K with replacement) = -** K- ")= := P different points in the grid WK.
dist.
should set the weight of = 0* k!. Furthermore, since the order of (pl,...,PKK does
In summarr, the integration based approximation of the objective proceeds as follows:
Algorithm Integration Based Approximation of the Optimization Objective
Input: # mechanisms K N, # iterations T 10000 E N, noise function 7 {0, 1....... ..... K} - (0, 1].
50: # samples between [0.5, 1) to form the set W
2: f + 0.5/T distance between samples
3: - 0² K!
4: P - ( (-+
for 1= 1.2...... do
Sample probabilities (51, 82. ..... sk) WK
7: Č ?~ PoissonBinomial( $1, $2 8k)
8:
6i + Pr(C = 1], vI {0, 1, K}
9t + - Σ K+1 (å) âσ 71)
10: end for
11: Return
P ΣT N
E gt
C.3 Reducing # Constraints from co to Polynomial Set
Lemma C.1 (Restalement of Lemin 5.1 Consider using DaRRM (Algorilhmm) 7 to solve Problem 1. and
let f be the privacy cost objective as defined in Lemma 3.4 Given an arbitrary noise function let the worst case probabilities be
Pk ..... .P) arg f(p...... .(p.....,PKy PK.pP.....PP''"
((m.))))
Then, each pair (p. p.), Vi E [K] satisfies
(pT. (100) (A, A,
+
1-4
1-A E
(1, (1,1-A),
+1
e1
et
++
c++
Furthermore, when 8 > 0, there exists finite vector set P of size O(K7) such that if B = max ((ma)))) EP f(p,,..,,PK .r....,,p' P can be reduced to O(K3).
.....,Pg))) p)in), then f(p, Pk.
S B. When d = 0, the size of
47

---

Published in Transactions on Machine Learning Research (November/2004
Feasible Region F.
(1.1)
1.0
(1-11)
(1.1-A) A)
P
0.
(0.4)
(0.0)50
0.0
(3.0)
3/2
Pi
Figure 5: An illustration of the feasible region Fi.
Proof. Part I: Reducing # privacy constraints from oo to exponentially many.
Consider (px,p%) for an arbitrary E [K] and fixing (0j,P4),V Vj + i. Given any noise function ,, recall the (see Lemma 3.4
privacy cost objective f(p,,..., ,K,
K-1
K
,K. 7)
(e al -7)) +
Σ
(al - CTT cTTr(()) -11)
K+1
and the privacy constraints are of the form
f(p PK. Po..,'....,,pi111 S 5 -1+21 28
where recall that a Pr([(D) tion of (p/) VI E (0. K} and L(D), L(D') are the sum of observed outcomes on neighboring datasets D and D'. By Lemma 3.4 y needs make the above privacy constraint hold for all possible PD) to make DaRRM, (me, 8 diifferrentlll private. This is equivalent to saying, 7 needs to ensure (ax f(pi..... PK. .i.....,P'':: Pkin) S e 1+ 28.
is a function of {pil and aj Pr[[(D') I] is func-
Notice that the sum of observed outcomes follows Poisson Binomial distribution, i.c., L(D) Diisooninoomia(pp.... PKK and L(D') ~ Poisson Binomiallg.......//// son Binomial d the privacy cost objective f is linear in each and p/, fixing all (0,.Pf, Pf). Vj 4 i. Since each mechanism M. is (e, A)dlifferrnttiall private, by definition, (pi,p() satisfies all of the following:
Hence, by the pmf of the Pois-
p p 5
1 5- p,) AA 1 1- se
That is, (p..1) lies in feasible region F, (see Figure 5) Note the constraints on (pr, p(), that is, the boundaries of F,, are lincar in pi and p/. And so the optimization problem (pl.p(") arg (ax(p))))) (P1,...,,PP PK..Pp
which finds the worst case probabilities in (pr,P(), is a Linear
Programming (LP) problem in (px, (p).p)) for i [K]. This implies p)") has to be one of the eight corners of F: that is (pi,1() E (), (1, (0, A), (A.0), (1 A, 1), (1, 1- A), (5+A 1-A), ( ++A))= := C. Since all (p.,p() and (p),P/), for i j, are independent, we can search for the worst case probabilities by searching for (p" pf") E C, instead of searching for (p., Pb) E F, Vi E [K]. Therefore, the infinitely many privacy constraints are now reduced to only 8 to optimize for the best y function that maximizes the utility of DaRRM,, while ensuring the output me-differentially private.
Part II: Reducing # privacy constraints from exponentially many to a polynomial set.
To further reduce the number of privacy constraints in optimization, observe that the Poisson Binomial distribution is invariant under the permutation of its parameters. That is, Poisoon
dist.
6See, egg. https://en httpee//eeeiiiiiiii..oo sicippdiis.org/iiki/Poeeeeee binomial distribution the pmf Poisson Binomial distribution.
48

---

Published in Transactions on Machine Learning Research (November/2004
Poissou for some permutation πT and dist- means "follows the same distribution". Similarly, PoissonBinomiappp.... pxx) diat. PoissonBnnoiia((((p..... Pkk)).
The above observation implics if have privacy constraint f(p 01,..., PK uK p/ v/,..... ,/.....PKK. 7 e 1 1 26, for some {(v, v E ECK then any privacy constraint f(1 -11....,P. ..K sK
P
,P. =k: S e 1 + 26, where (81,...,,8k) m (Kk).... (6'))).,'')) = (V1) ,,k..,,,,)))) for permutations π1 and T2, is redundant.
Therefore, there is a vector set P. where each probability vector (pi....,PP. PK. PI.... Pxx in P is constructed by setting (PI.1) p1), (p2, p2)...., (KK)Pk) = (V1, U2, .2,..... UK), where et E EC, E [K], such that vectors constructed (PK, px) = (11, ......,..
by (pI, p4 ) (p2,P2), O(K). If we restrict our search for the worst case probabilities to this set P that is, solving for 3 = max((axxpp))))) (p..)))) f(1....., ,K PK.PPP P(ki)) then f' .... S B. This implies we only need O(K)) privacy constraints to optimize for the best noise function 7 in DaRRM, while making sure DaRRM, me-differentially private.
UK) , not in P. Note [P] (8 chooses K with replacement)
(K+
Note if A 0, i.c., the mechanism M,'s 's are pure difforentially private, the feasible region F; in which (pc, pb) lies has only 4 corners instead of 8. This implies (p',p(") E C {00, 0), (1, (G-4I) -+1), (a44i eft)): ) Hence, in this case, |P| (4 choose K with replacement) = (**=-) O(K*), which implies we only need ( privacy constraints to optimize for the best noise function y in DaRRM.
49

---

Published in Transactions on Machine Learning Research (November/200)
D
Full Experiment Results
D.1
Optimized y in Simulations
D.1.1
Comparison Using General Composition
The general compasition (Theorem 2.3 indicates less total privacy loss than simple composition (Theorem 2.2 when the number of folds, m, is large, or when the failure probability is large. To enable meaningful comparison against general composition, we consider a larger and a larger failure probability
Consider K 35, e 0.1, A 10- By general composition, if one outputs the majority of M subsampled mechanisms for some M < K, the majority output is (Copt, Supt) diffeeerrfe private, where
(e' (c'-1)cM 1)cM e ++1 + +ep22 log(e+
VM2 ) - 1)eM e +el
2M log( }) óopt =1 -1 (1 8))
Copt min Me,
2
for some 8' O. We set this as the privacy guarantee of all majority ensembling algorithms. That is, if we want the majority output to be (me, 8) diffferrryt private, we set
Copt c
(e (e5-117 -1MM min M,
2M log(e + VMe2 (e- -1M
+
V 2M
1 8 2 log
+1
+1
and 8 = 1- 8) M( -8) accordingly. The parameters and to compute Peonst in RR (sce Section (11-(18)
A.1
set to be
(e--1)K T min { K,
VKe (e* 1IK
ce + (2Kloe(
+ 2K log(e+
c +1
and À = - (1
In the experiments, we consider M (10, 13, 15, 20) and 8' 0.1; and Topt computed using a uniform prior T.
All values of the parameters of the private ensembling algorithms use in the experiment are listed in the table:
# Subsampled mechanisms
M
10
13
15
20
Privacy allowance
m
6.4521
7.5742
8.2708
9.8823
Parameter of constant y
T
14.0328
14.0328
14.0328
14.0328
Parameter of constant y
À
0.1003
0.1003
0.1003
0.1003
Overall privacy loss
me 5
0.6452
0.7574
0.8271
0.9882
Overall failure probability
0.1001
0.1001
0.1001
0.1002
Table All parameter values. Note that all the private ensembling algorithms we compare in the experiment is required to be (mc, diiiifeernytially private. Here, 35, 0.1,
10-5 and 8' 0.1.
50

---

Published in Transactions on Machine Learning Research (November/2004
Shape y functions
M 10
M 13
2(DaRRM,)
= 10
13
0.10
0.5
0.05
0.05
values
Error
0.00
0.00
15
M 20
1
0.05
0.04
0.5
0.02
0.00
0.00
17.5
35 Support /E (0, 1...... K}
17.5
y functions
Yopt (Ours)
Vsue (Baseline)
Yoonst (Baseline)
Figure 6: Plots of the shape and E(DaRRM,) of different 7 functions: the optimized 7sub, and the baselines TSub (corresponding to subsampling) and Yoonst (corresponding to RR). Here, K 35, M E {10, 13, 15, 20),
A 10-5 0.1, 8' 0.1.
D.1.2 Comparison in Pure Differential Privacy Settings
Consider the pure differential privacy setting, where A = 5 = 0. Note in this setting, it is known that simple composition is tight.
To compute an optimized Topt in DaRRM, since we have shown the number of constraints O(K)) if A = (see Lemma 5.1b, we can set be larger. Here, we present results for K {11, 101} and
0.1.
Again, compare the shape of different and the corresponding E(DaRRM,) under those y functions, fixing the total privacy loss to be me. Topt is computed using a uniform prior T.
Since the subsampling mechanism from Section with privacy amplification applics to this sctting, wo compare four different y noise functions here:
Topt (Ours): optimized 7 function using our optimization framework
2. 7Sub (Baseline): the y function that corresponds to outputting the majority of m out K subsampled mechanisms
3. 7pSwh (Baseline): the 7 function that corresponds to outpulting 2m subsampled mechanisms from Theorem 4.1 aka., Double Subsampling (DSub)
Tconet (Baseline): the constant y function that corresponds to the classical Randomized Response (RR) algorithm
Setting 1. K= 11, 11,11,,
51

---

Published in Transactions on Machine Learning Research (November/200) 22024)
Shape y functions
(DaRRM,)
m
m
m =
m =
3
0.2
0.5
0.1
m =
m = 7
5
values
0.10
0.05
0.5
0.05
m = 9
m 11
0.00
m =
0.00
m 11
0.05
0.5
0.02
0005
5.5
11
0
5.5
11
Support E {0, .,
y functions
Vopt (Ours)
Ysub (Baseline)
Yosub (Baseline)
Yeonst (Baseline)
Figure 7: Plots of shape and ((DRRRM.) of different Y functions: the optimized 'Opt: the baselines Ysub and "DSubb (Theorem 4.1 and the constant Yeonst (corresponding to RR). Here, K = 11, E (1,3,5, 7,9, 11), = 0.1 and = A = O. Note when m E {7.9), 9), the cyan line (YDsat) and the red line (Tope) overlap. When m = 11, all lines overlap. Observe that when m 2 2
K+1 that is, m E (7,9, 17,9,113 in this case, the above plots suggest both Yope and TDSub achieve the minimum error at 0. This consistent with our theory.
Setting 2. K = 101, m E {10, 20, 30, 40, 60, 80}.
Shape of functions
{(DRRM,))
m 10
m 20
0.10
0.10
0.5
0.05
m = 30
m 40
0.00
m
30
0.00
m = 40
0.10
values
0.5
Error
0.05
0.05
m = 60
m 80
0.00
0.00
0.04
0.02
0.5
0.02
0.01
0.00
0.00
50.5
50.5
101
Support EE 1...,,
functions
Vopt (Ours)
Ysub (Baseline)
YDsub (Baseline)
Yconst (Baseline)
Figure 8: Plots of shape and {(DaRRM,) of different. functions: the optimized TOpt, the baselines
TSub and 7DSub (Theorem 4.1. and the constant Yconst (corresponding to RR). Here, = 101, m E (10, 20, 30, 40, 60, 80), 0.1 and A
52

---

Published in Transactions on Machine Learning Research (November/2004 22024)
D.1.3 Comparison Using Different Prior Distributions
When optimizing Y that maximizes the utility DaRRM, recall that the objective takes an expectation over p:'s for pi T, where T is some distribution and pt Pr(M,(D) I]. The previous experiments assume do not have access any prior knowledge about p; and hence is the uniform distribution, i.e., Uniform([, 1].. However, when has knowledge about the mechanisms, one can set proper prior T to further maxinize the utility of DaRRM.
In this section, let To denote Uniform((0, 1]) and we present results considering a different prior distribution, which we call TP, as follows. Suppose our prior belief that each mochanism M, has a clear tendency towards voting or 1, i.e, P4 lar from 0.5. Let Tp be Uniform( (0, 0.3] [0.7,
To optimize Y under Tp, we change the approximate optimization objective in Eq. 202 which optimizes y under Tú, to be the following,
K
[-' J.7
Σ
(at - ox ax- ... dpk (1)
(204)
2
K=1
0.7 J..7
Setting.
== 11, (3,5), 0.1, d = A = 0.
We compare the shape and (DDRRRM,) of different 7 functions:
1. Topt-U denote the function optimized under ~ To
2. P denote the y function optimized under ps Tp
"/Sub,
corresponding to the subsampling baseline
4. Tconst:
corresponding to the RR baseline
Note when compute the error, we take the expectation w.r.l. the actual distributions, regardless of the prior used to optimize In the experiments, we consider three different actual p, distributions:
1. "Actual: Uniform((0, 1))" pi To, Vi [K]
2. * "Actual: pt 0.5": p: 0.5, Vi [K]
This setting implies the mechanisms do not have a clear majority
3. "Actual: Uniform(10.0.11 0: p; Uniform([0.0.1]] Vi E [K]
This setting implies the mechanisms have clear majority (i.e., 0)
Since our prior Tp is closer to (0,.0))((0,0.1))) (i.e., there is clear majority), we would expect (DaRRMM 2.) to be the lowest when p; ~ Uniform(0. 0.1], but to be higher than ((DaRRM Yops v) when p. ~ Uniform (10, 1]) or = 0.5. The results are presented in Figure g
D.2
Private Semi- Supervised Knowledge Transfer
D.2.1 More Details about the Baseline GNMax Papernot et al. (2018)
The GNMax aggregation mechanism for majority ensembling of non-private teachers proceeds follows (Section 4.1 of Papernot et al. (2018) ); on input 2,
Mz(x) = arg max ( +N1(0,
(205)
where nx(x)) # teachers who vote for class i.
How to set in GNMax?
53

---

Published in Transactions on Machine Learning Research (November/205) 22024)
K=11, m=3, E=0.1
Shape of y functions
Actual: p Uniformi[O, 1])
Actual: = 0.5
Actual: p Uniform([O, 0.11)
1.00
0.15
0.075
0.3
Y values
0.75
Error
0.10
Error
0.050
Error
0.2
0.50
0.05
0.025
0.1
0.25
0.00
0.000
0.0
functions
functions
functions
Support E (0, 1, .,
K=11, m=5, c=0.1
Shape y functions
Actual: p - Uniform((O, 1))
Actual: p; = 0.5
Actual: p Uniform([O, 0.1])
0.06
0.10
Y values
0.75
Error
Error
0.04
Error
0.2
0.50
0.05
0.02
0.1
0.25
0.00
0.00
0.0
10
y functions
y functions
functions
Support E (0,
.,
Vopt-u (Ours)
Vopt- (Ours)
Ysub (Baseline)
Veonst (Baseline)
Figure 9: Comparison of the shape and (DaRRM,,) of different y functions: 1) optimiized under prior Tr,, 2) "y optimized under prior Tp, 3) 7Sub (corresponding to the subsampling baseline) and 4) Yconst (corresponding to the RR bascline). Here, K = 11, m E {3, 5). 0.1. Observe that if the prior Tp used in optimizing is closer to the actual distribution of p; ps's, there is additional utility gain (i.e., decreased error); otherwise, we slightly suffer a utility loss (i.e., increased error), compared to optimize y under the To prior. Furthermore, regardless of the choice the prior distribution T in optimizing 7, DaRRM, with an optimized y achieves a lower error compared the the basclines.
54

---

Published in Transactions on Machine Learning Research (November/2004
Section 4.1 of Papernot al. 2018)) states the GNMax mechanism is -A. differentially private (RDP), for all 2 1. RDP bounds can be converted to DP bounds as follows:
Theorem D.1 (RDP to DP (Theorem of Papernot et al. 2018))). mechanism M guarantees (A,c)-RDP, then guaranlees (e + log 1/6 >-1 - -)-differelltal privacy for å (0, 1).
Therefore, GNMax with parameter o² guarantees ( want to choose À and o² here that the output of GNMax is (me, -dd-differnntilllly private. Here, mA.
1/4 o)-differential privacy, AA 2 1. Given m, e, A, X-1
We first obtain a valid range of x. Since me 2 O, 2 + log log 2 and so A 2 log 1/4 = Amin- And 0²
X-1
Since the smaller o² is, the higher the utility, we perform a grid search over À E [Amin 500],
with discretized A values of equal distance 0.5, to find the minimum of For the (me, mA) values used in the experiments, we observe o² decreases first and then increases as À increases, as shown in Figure 10 The À and minn values in the RDP bound of Gaussian noise to compute the privacy loss of GNMax's 's output we use in the experiments are presented in Table
Dataset: MNIST
Dataset: Fashion-MNIST
2000
2000
1800
1800
1600
1600
1400
1400
1200
6
1200
1000
1000
800
800
600
600
400
100
200
300
400
500
100
200
300
400
500
A
Figure 10: Plots of X vs. o² in the Gaussian RDP privacy bound. The goal is to choose À value that minimizes x²_ It is not hard to see the value of o² decreases at first and then increases as À increases.
Privacy Loss Per Query
(mc, mA)
A
min
MNIST Fashion-MNIST
(0.2676, 0.0003) (0.2556, 0.0003)
34.31
21.46
35.74
22.46
Table 4: Parameters of the RDP bound of Gaussian noise to compute the privacy loss of GNMax's output.
A Note on the Data-dependent Privacy Loss Bound
Papernot et al. (2018) gives potentially lighter data-dependent bound on the privacy loss using GNMax to output the majority of non-private teacherss votes. We give a clean pseudo-code on computing the data-dopendent privacy loss bound Algorithm 6 based on the lemmas and theorems [Papernot al. (2018). Given privacy parameters a, and the teacher votes per class [n,){] for C classes, the data-dependent bound be empirically evaluated and compared against the Gaussian privacy loss bound. The smaller one is the final privacy loss. We empirically find that the condition of the data-dependent bound (line 8 in Algorithm 6 is not satisfied when K and the number of classes C' are small, e.g., K = 11, C = 2 as in our case, even if all teachers agree on the same output. And so in the experiments, we can only apply the Gaussian privacy loss bound (line 14).
D.2.2 Additional Results for Private Superviee Knowledge Transfer
1.
55

---

Published in Transactions on Machine Learning Research (November/2005
Algorithm Compute Tighter Privacy Loss
Input: Std. of Gaussian noise 0, Privacy parameter X, # teachers K, classes C, votes per class {m:);-]
B <-- O bound candidates
3: for i= 1.2.... K do
4: ((0) + -ipi erfe Bym
20
5: M2 to. -o.v Vlog 1/((0,
pi t 12 +1
(8)
(0) (9
(1)
oF, 3
7: Lub + exp((12
(0)
1
(6) )/(
14
j
(9)
M1
1/2
8:
if (0 < 1 and 11 2 A and #2 > 1 and
g(
S
( then qab
-1
A (1 - (1)) g()) exp(e2 (1)
#2
B + exp(c ( (1(0)
10:
11:
DataDependenntBound -
(11- ((--))))(A(()>>-- + (160)-11
(A
12:
B B DuDDaaDDeendennBon
13: else
14:
GaussianBound +
15: B Bu GaussianBound
16: end if
17: end for
18: Return min B
Privacy loss per query
Total privacy loss over Q queries
Dataset
# Queries
(Equerys Squery)
(erotal, Ororat) (1.704, 0.002)
Q 20
MNIST
Q = 50
(0.0892, 0.0001)
(2.837, 0.005)
Q = 100
(4.202, 0.010)
Q 20
(1.620, 0.002)
Fashion MNIST
Q 50
(0.0852, 0.0001)
(2.695, 0.005)
Q 100
(3.988, 0.010)
Table 5: The privacy loss per query to the teachers and the total privacy loss over Q queries. Note the total privacy loss is computed by general composition, where we set 8' 0.0001.
Dataset
MNIST
Dataset
Fashion Mashioon-MISST
MNIST
GNMax (Baseline)
DaRRM 7
DaRRM
GNMax
DaRRM a
DaRRM
# Queries
(Baseline)
(Ours)
Queries
(Baseline)
(Baseline)
(Ours)
Q 20
0.54 (0.11)
0.68 (0.07)
0.74 (0.08)
20
0.56 (0.10)
0.92 (0.05)
0.89 (0.06)
Q 50
0.51 (0.07)
0.67 (0.05)
0.66 (0.05)
Q 50
0.52 (0.05)
0.89 (0.04)
0.92 (0.03)
100
0.57 (0.03)
0.71 (0.03)
0.69 (0.04)
100
0.56 (0.04)
0.89 (0.04)
0.91 (0.04)
Table Accuracy of the predicted labels of Q query samples on datasets MNIST (on the left) and Fashion-MMIST (on the right). We report the mean and one std. in parentheses over 10 random draws of the query samples from the test dataset. Note each prediction private. Note in this case where m 1, by Lemma 3.2 subsampling achieves the optimal error error/utility Hence, there is not much difference in terms of accuracy between DaRRM and DaRRM Top: as expected.
the query sample is (Etotal, dcotal) diffferenttll
5.
56

---

Published in Transactions on Machine Learning Research (November/2005
Privacy loss per query
Total privacy loss
over Q queries
Dataset
# Queries
(equerys Squery)
(frotal Orotat) (8.920, 0.010)
Q 20
MNIST
Q = 50
(0.4460, 0.0005)
(18.428, 0.025)
Q 100
(28.926, 0.049)
Q = 20
(8.520, 0.010)
Fashion MNIST
Q = 50
(0.4260, 0.0005)
(17.398, 0.025)
Q 100
(27.223, 0.049)
Table The privacy loss per query to the teachers and the total privacy loss over Q queries. Note the total privacy loss is computed by general composition, where we set 8' 0.0001.
Dataset
MNIST
Dataset
Fashion-MNIST
GNMax
DaRRM 7aus
DaRRM
GNMax
DaRRM yaua
DaRRM Topt
# Queries
(Baseline)
(Baseline)
(Ours)
# Queries
(Baseline)
(Baseline)
(Ours)
Q 20
0.73 (0.11)
0.76 (0.09)
0.84 (0.07)
Q 20
0.72 (0.10)
0.96 (0.04)
0.97 (0.04)
Q 50
0.75 (0.07)
0.82 (0.04)
0.83 (0.04)
Q = 50
0.72 (0.08)
0.96 (0.02)
0.97 (0.02)
100
0.72 (0.04)
0.79 (0.05)
0.83 (0.03)
Q 100
0.72 (0.06)
0.97 (0.01)
0.97 (0.01)
Table Accuracy of the predicted labels of Q query samples on datasets MNIST (on the left) and Fashion-MVIST (on the right). We report the mean and one std. in parentheses over 10 random draws of the query samples from the test dataset. Note each prediction private. With the same per query privacy loss (and hence the same total privacy loss over Q samples), DaRRM Topt
the query sample is (Ctotal, Stotal ) J-differentially
achieves the highest accuracy compared to the other two baselines.
m = 7.
Privacy loss per query (equery: 6 Qquery)
Total privacy loss over Q queries
Dataset
# Queries
(Etotal rcoal) (12.488, 0.014)
Q 20
MNIST
Q = 50
(0.6244, 0.0007)
(28.392, 0.035)
Q = 100
(45.683, 0.068)
Q 20
(11.928, 0.014)
Fashion MNIST
Q = 50
(0.5964, 0.0007)
(26.738, 0.035)
Q 100
(42.873, 0.068)
Table The privacy loss per query to the teachers and the total privacy loss over Q queries. Note the total privacy loss is computed by general composition, where we set 8' 0.0001.
Dataset
MNIST
Dataset
Pashion-MNIST
GNMax
DaRRM
DaRRM
GNMax
DaRRM Yaua
DaRRM Nopt
# Queries
(Baseline)
(Bascline)
(Ours)
# Queries
(Bascline)
(Baseline)
(Ours)
Q 20
0.79 (0.07)
0.80 (0.09)
0.85 (0.08)
20
0.79 (0.07)
0.95 (0.04)
0.96 (0.04)
Q 50
0.80 (0.05)
0.82 (0.05)
0.85 (0.04)
Q = 50
0.79 (0.05)
0.96 (0.03)
0.97 (0.03)
100
0.80 (0.04)
0.80 (0.04)
0.83 (0.03)
Q 100
0.79 (0.03)
0.96 (0.02)
0.96 (0.02)
Table 10: Accuracy of the predicted labels of Q query samples on datasets MNIST (on the left) and
MaSSi (on the right). We report the mean and one std. in parentheses over 10 random draws of the query samples from the test dataset. Note each prediction on the query sample is (Etotal: (rotal--iiferreniall) private. With the same per query privacy loss (and hence the same total privacy loss over samples), DaRRM Toy achieves the highest accuracy compared to the other two baselines.
57


Reviews:
[{"review_id": "QOsfBQjFwv", "reviewer": "Reviewer_kUU3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\ni) The proposed RR variant seem interesting: it seems to have a nice theoretical motivation (at least when looking at it without properly going through all of the proofs), and the reported performance is good under specific parameter ranges.\n\nii) General DP mechanism optimality results are very interesting and important, both in theory and for practical use cases.\n\n\n### Weaknesses\n\ni) The paper is generally not easy to read and could be clearly improved by clarifying the writing (e.g., there are plenty of breaks in the flow of thought [such as the first sentence of Sec1.1: what question is this talking about?], parts of the related work and many basic defs etc. are only in the appendix, in several places it is claimed that something is \"hard\", and then in the next sentence it is claimed that the hard problem can be easily solved). While shortening the paper by pushing most content into the Appendix is somewhat understandable, if lamentable, in a short-format conference paper, TMLR does not have such limits.\n\nii) I am not sure if all the claims about the optimality and efficiency of the proposed method are well-founded.\n\niii) There is not much discussion about the scalability of the proposed approach beyond some mentions, or on how the quality of the approximations depends on the available compute. Given that it seems to be maybe the most important bottle-neck for the proposed method, this seems a bit odd.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of releasing a majority vote from $K$ $(\\epsilon, \\Delta)$-DP algorithms that satisfies $(m \\epsilon, \\delta)$-DP for $1 <=m <=K$ and $0 <= \\Delta <= \\delta <1$. The authors propose a new randomized response (RR) variant, which uses a parameterized noise function. The main novelty in the formulation is that the noise function can be optimized for different queries, which allows RR to add differing amounts of noise depending on the input (i.e., it allows to add less or no noise when there is a clear-enough majority). The authors show that the proposed formulation is quite general, and can be in some sense optimal. The paper also includes some empirical experiments showing that the proposed method tends to work better than some existing baselines.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In more or less decreasing order of importance:\n\n1) On the optimality and efficiency of the proposed method: in several places (e.g., in the abstract, Sec 1.1 on p2 and p3, Sec 5 on p7, Sec7 on p11) it is claimed that the noise function $\\gamma$ can be optimized efficiently, and as a result, the proposed method achieves optimal utility. However, looking at the comments in Lemma 5.1 about the optimization (Linear Optimization Objective on p7, Appendix E.2), finding the optimal value involves calculating a multidimensional integral, and since this is not really doable with larger $K$, an approximation is discussed in the Appendix and used in the experiments. To me this looks like the proposed method with any larger $K$ is not actually tractable, and hence when the noise function is only approximately optimal, the proposed method has no optimality guarantees (furthermore, the non-optimality does not seem to be only a theoretical possibility, as under some settings e.g. in Fig. 8 and in Table 6 the proposed method can perform worse than the baselines).\n\n2) Please move at least the entire Related work discussing the closely-related existing methods to the main body of the text.\n\n3) Please add missing existing RR optimality results in the related work and when discussing your results (at least Kairouz et al. 2015, Holohan et al. 2016).\n\n4) On composition: besides basic and advanced composition, there is also the exact bound from Kairouz et al. 2015. Is there some reason for not using it in the experiments? Please also use the exact composition bound when stating results on the provable privacy amplification (Sec 4).\n\n5) Can you characterize how does your optimality results relate to optimal count query release (which seems also like a natural baseline, i.e., directly release the (subsampled) noisy count with geometric mechanism, see e.g. Kairouz et al. 2015 for optimality discussion)?\n\n6) Please state the neighborhood relation (e.g. replace?) explicitly, or that your results do not depend on the exact relation, to avoid misunderstandings.\n\n### References:\n\nHolohan et al. 2016: Optimal Differentially Private Mechanisms for Randomised Response.\n\nKairouz et al. 2015: The Composition Theorem for Differential Privacy.", "broader_impact_concerns": "I have no broader impact concerns for this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BRE2Vhfdfa", "reviewer": "Reviewer_Fx2m", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Studying privacy-utility trade-offs and developing an optimization framework for it is a compelling effort. \n\nWeaknesses\n- Limited experimental evaluation \n- Some sections require clarification and revision", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript proposes a randomized response framework that optimizes utility for differentially private majority ensembling algorithms. The proposed approach employs a data-dependent noise function, and its utility optimization is evaluated in the context of differential private label ensembling for image classification applications.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1)  Although the authors provide a thorough overview of the background on private aggregation of predictions, the motivation for applying private prediction in data-adaptive settings needs to be better explained. Including a real-world example involving a data-adaptive setting where the prediction ensembling should preserve privacy would significantly enhance the audience's understanding of the importance of the problem.\n\n\n2)  The first sentence of the section “1.1 Our Contributions” needs clarification: “We give a (perhaps surprising) affirmative answer to this question: by using ..”. It is not clear which question the authors are referring to. \n\n3) Although this work is theoretically supported, and the authors claim they “demonstrate the strong empirical effectiveness” of the proposed framework, the only datasets used for empirical evaluation are MNIST and FashionMNIST. I strongly suggest the authors extend their experiments by including more complex datasets such as SVHN. \n\n4) The “Introduction” section mentions that this work focuses on “ data-adaptive settings where the underlying dataset is changing slowly over time.” However, it is unclear to me how this setting is incorporated into the experiments conducted on MNIST and FashionMNIST.  Could you please clarify how the experiments address this online dataset scenario? \n\n5)  As a minor point, the readability of the sentence, “We emphasize in data-adaptive settings where the underlying.. ”  (on page 2, Introduction section), would improved by either removing “in” or replacing it with “on”.", "broader_impact_concerns": "No concerns about the ethical implications of the work", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XY3xrXYCD3", "reviewer": "Reviewer_KYVF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#### Strengths:\nThey give effective algorithm for differentially private majority problem.\n\n#### Weakness:\n1. The contributions should be summaried as short and to the points.\n2. The notations of $\\gamma$ and $\\gamma_{sub}$ are mixed used. In some cases, they denote for the same.\n3. Theorem 4.1 says it amplifies privacy by 2, the baseline is not clear here.\n4. There are no error bounds analysis for the algorithm.\n5. I have a question for Theorem 4.1. It say when $m \\ge \\frac{K+1}{2}$, just set $\\gamma(l)=1$ to output the true majority with no noise. Can this protect $m\\epsilon$ differential privacy? I try to understand that. This may because of Lemma 3.1, which says \"the majority of m out of K-subsampled mechanisms without replacement and the output of data-dependent RR algorithm have the same distribution.\" So the algorithm's output distribution is the same as m samples' distribution, then how is it to get $e^{m\\epsilon}$\n6. The title is \"optimized tradeoff for ...\", and it doesn't show and prove the optimal results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a classical problem for computing a differentially private majority from K-differentially private algorithms. They introduce a Data-dependent Randomized Response Majority (DaRRM) algorithm.\n\nThey show that an (mϵ, δ)-private majority algorithm with maximal utility can be computed tractably for any m ≤ K by a novel structural result that reduces the privacy constraints. In some settings, They show DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines. They demonstrate the strong empirical effectiveness of the algorithm when compared against several baselines.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In Algorithm 1 Step 5, it should be $\\gamma(L)$ rather than $\\gamma(S)$. What is the function for $\\gamma(L)$? as the $\\gamma_{sub}$ in Lemma 3?\n2. It says the DaRRM has a non-constant success probability $p_\\gamma$, the success probability should be as least $p_\\gamma$, since Step 10 also has$\\frac{1}{2}(1-p_\\gamma)$ success probability.\n3. Why the probability use some combinations? Please explain intuitively. \n\nOverall, the contribution of this paper is that it gets a better algorithm for privacy majority problem compared with traditional algorithms. But the comparisons are not clear, such as authors can show the error bound for this algorithm and previous algorithms.", "broader_impact_concerns": "This paper works for privacy, and it doesn't have ethical problems.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: While I think the paper is generally well written, I want to authors to provide some final clarifications to the camera ready, which I will list below.

- You mention that if there is a clear majority of outcomes (either 0s or 1s) in $\mathcal{S}$, then it should remain so even for an adjacent data set. Please clarify why that is in the final version. I would imagine this depends somehow on the individual mechanisms.
- Proof of Lemma 3.2 is not clear, and needs to be clarified for the final version (NOTE: since Lemma 3.2 is not a crucial part of the other theoretical contributions of this work, I don't see it as a breaking chance)
    * First of all, the Lemma 3.2 in the main paper is titled "Lower Bound on Error when $m=1$". However, the statement of the Lemma, neither in the main paper of appendix, specifies that the Lemma is specific to $m=1$ or even subsampled mechanism. Hence I read the Lemma as a general guarantee for $(\epsilon, \delta)$-DP aggregation algorithm $\mathcal{A}$. I believe the $m=1$ result just shows that the Lemma is tight in this case. If I'm correct in my assessment, please consider dropping the ".. when $m=1$" from the title of the Lemma.
    * In the beginning of the proof you seem to focus on setting where $p_i = p, \forall i \in [K]$, but this doesn't assumption does not seem to be generalized for the differing $p_i$ anywhere in the proof. It needs to be clarified if and why studying this case is sufficient for the general statement of the Lemma.
    * Next, you say "Consider a dataset $\mathcal{D}_0$ such that $\Pr[\mathcal{M}_i(\mathcal{D}_0)=1] = \frac{1}{2}$". Is there any guarantee that such data set exists for arbitrary mechanism $\mathcal{M}_i : \mathcal{D} \rightarrow \{0, 1\}$?
    * Regarding the way you choose $p$ in the 3rd paragraph: I'm not sure if such $L$ is guaranteed to exist, and depends on the $\epsilon$ value. E.g. if $\epsilon = 1$ then even $L = 1$ would set $p > 1$.
- Proof of Lemma 3.4: The last bit of the proof, eq. 45 implying 46, is bit challenging to follow. I wonder if it would help the exposition if you would write the $\alpha$s in eq. 50 as $\tilde{\alpha}$, corresponding to the $\Pr[\mathcal{L}^\beta = l]$. Since the eq. 45 would hold for all $\alpha$, the eq. 50 would hold for all $\tilde{\alpha}$ in the K-simplex, and therefore also for $\alpha$ and thus you would get your claim.
- While the paper is mainly theoretical, I agree with reviewer Fx2m that further experiments on different data sets would strengthen the claims. Instead of using a computationally expensive model, authors could e.g. employ a simple CNN model to evaluate their approach on SVHN data set as suggested by the reviewer.

Typos:
- Proof of Lemma 3.2:
    * 1st paragraph of the proof $\Pr[g(\mathcal{S}] = 1$ should be $\Pr[g(\mathcal{S}) = 1]$.
    * Should the first $\mathcal{A}(\mathcal{D}_0)$ after $\Pr[\mathcal{A}(\mathcal{D}_2)=1] \leq $ be $\mathcal{A}(\mathcal{D}_1)$?
- Step 3 of Alg. 1, lower case $k$ in subscript
- Proof of Lemma 3.4
    * Eq. 34 is has conditional probability with condition $\mathcal{L}(\mathcal{D}) = 1$, while I believe this should be $\mathcal{L}(\mathcal{D}) = l$. The same mistake is in all the proceeding equations.
    * Eq. 40 uses similarly wrong condition but now it is both parts of the law of total probability.
- "maixmizes"
Decision: Accept (poster)