PRIVATE MULTI-WINNER VOTING FOR MACHINE LEARNING
Year: 2021

Abstract:
Private multi-winner voting is the task of revealing k-hot binary vectors that satisfy a bounded differential privacy guarantee. This task has been understudied in the machine learning literature despite its prevalence in many domains such as healthcare. We propose three new privacy-preserving multi-label mechanisms: Binary, τ , and Powerset voting. Binary voting operates independently per label through composition. τ voting bounds votes optimally in their `2 norm. Powerset voting operates over the entire binary vector by viewing the possible outcomes as a power set. We theoretically analyze tradeoffs showing that Powerset voting requires strong correlations between labels to outperform Binary voting. We use these mechanisms to enable privacy-preserving multi-label learning by extending the canonical single-label technique: PATE. We empirically compare our techniques with DPSGD on large real-world healthcare data and standard multi-label benchmarks. We find that our techniques outperform all others in the centralized setting. We enable multi-label CaPC and show that our mechanisms can be used to collaboratively improve models in a multi-site (distributed) setting.

text: Private multi-winner voting is the task of revealing k-hot binary vectors that satisfy a bounded differential privacy guarantee. This task has been understudied in the machine learning literature despite its prevalence in many domains such as healthcare. We propose three new privacy-preserving multi-label mechanisms: Binary, τ , and Powerset voting. Binary voting operates independently per label through composition. τ voting bounds votes optimally in their `2 norm. Powerset voting operates over the entire binary vector by viewing the possible outcomes as a power set. We theoretically analyze tradeoffs showing that Powerset voting requires strong correlations between labels to outperform Binary voting. We use these mechanisms to enable privacy-preserving multi-label learning by extending the canonical single-label technique: PATE. We empirically compare our techniques with DPSGD on large real-world healthcare data and standard multi-label benchmarks. We find that our techniques outperform all others in the centralized setting. We enable multi-label CaPC and show that our mechanisms can be used to collaboratively improve models in a multi-site (distributed) setting.

heading: 1 INTRODUCTION
text: Differential privacy techniques for machine learning have predominantly focused on two types of mechanisms: for a given query, release either a noisy estimate using the Gaussian mechanism (Abadi et al., 2016b) or the noisy arg max (Papernot et al., 2017). These two mechanisms appeal well to single-label classification per input (a.k.a. multi-class classification), which is a widely studied setting of supervised learning where a given input has only one class present. The Gaussian mechanism can enable arbitrary queries of data, for instance, differentially private stochastic gradient descent (DPSGD), which returns noisy gradients (Abadi et al., 2016b). Instead, the Gaussian noisy arg max mechanism can only reveal the max count, which is used in the canonical Private Aggregation of Teacher Ensembles (PATE) (Papernot et al., 2017).
In contrast, more real world tasks, such as multi-label classification (Tsoumakas & Katakis, 2007), can be modeled using multi-winner elections (Elkind et al., 2017; Faliszewski et al., 2017), where more than one candidates may win, simultaneously. Outside of the obvious situation of elections, other multi-winner election scenarios include canonical computer visions tasks like object recognition, which require models to recognize all the objects present in an image (Boutell et al., 2004). Further, multi-winner problems arise when inferring the topics written about in a corpus of text (document): e.g., a news article may discuss one or more topics like politics, finance, or education. Another principal setting is healthcare, in which patient data (e.g., symptom reports or X-rays) may be indicative of multiple conditions (Irvin et al., 2019; Johnson et al., 2019).
We thus focus on creating private mechanisms for releasing the outcome of a multi-winner election. We first formalize the multi-winner election and then provide a solution, termed Binary voting, where we apply a single-winner election mechanism independently to each of the k candidates. Though simple, we prove that it is optimal when there is a lack of correlation among the outcomes of particular candidates. We then derive tighter data-independent privacy bounds for multi-winner elections by considering the situation where each voter is limited in their (`2) votes for candidates, which we call τ voting. By casting multi-winner elections to an analogous task of single-winner elections, we create a third mechanism termed Powerset voting, which reveals the result for all k candidates jointly.
By replacing the noisy arg max mechanism used in (single-label) PATE, we create multi-label PATE which enables multi-label privacy-preserving classification with semi-supervised machine learning.
We empirically evaluate our algorithms on large-scale datasets, including the common multi-label benchmark Pascal VOC and three healthcare datasets, CheXpert (Irvin et al., 2019), MIMIC (Johnson et al., 2019), and PadChest (Bustos et al., 2020). We compare our work against DPSGD, which can be directly applied to multi-label machine learning, and find that our approaches achieve new state-of-the-art privately trained models, with 85% AUC (17% better than DPSGD) on the Pascal VOC dataset. Because many multi-label settings may benefit from distributed, multi-site learning (e.g., healthcare), we further integrate our methods with the collaborative protocol of Choquette-Choo et al. (2021). We find that training with our mechanisms can improve model performance significantly on large, real-world healthcare data with sensitive attributes.
Our main contributions are as follows:
1. We create three new DP aggregation mechanisms for private multi-winner voting: Binary voting, τ voting, and Powerset voting. We theoretically analyze the privacy guarantees of these mechanisms, finding that Binary voting performs better unless there is high correlation among labels.
2. We integrate our mechanisms with PATE, enabling private multi-label semi-supervised learning that achieves SOTA performance on large real-world tasks: Pascal VOC and 3 healthcare datasets.
3. We enable multi-label collaborative learning in the multi-site scenario by integrating our mechanisms into CaPC. We find that multi-label CaPC significantly improves model performance.

heading: 2 BACKGROUND

heading: 2.1 DIFFERENTIAL PRIVACY FOR MACHINE LEARNING
text: Differential Privacy (DP) is a canonical framework for measuring the privacy leakage of a randomized algorithm (Dwork et al., 2006). It requires the mechanism, the training algorithm in our case, to produce statistically indistinguishable outputs on any pair of adjacent datasets, i.e., datasets differing by only one and any data point. This bounds the probability of an adversary inferring properties of the training data from the mechanism’s outputs.
Definition 1 (Differential Privacy). A randomized mechanism M with domain D and range R satisfies (ε, δ)-differential privacy if for any subset S ⊆ R and any adjacent datasets d, d′ ∈ D, i.e. ‖d− d′‖1 ≤ 1, the following inequality holds: Pr [M(d) ∈ S] ≤ eεPr [M(d′) ∈ S] + δ.
We use Rényi Differential Privacy (RDP) (Mironov, 2017) which enables tighter accounting for our mechanisms using Gaussian noise because of its use of the Rényi-divergence to bound privacy loss. RDP is a generalization of pure, δ = 0-DP so we convert to and report final budgets using (ε, δ)−DP . Definition 2. Rényi Differential Privacy (Mironov, 2017). We say that a mechanismM is (λ, ε)RDP with order λ ∈ (1,∞) if for all neighboring datasets X , X ′:
Dλ(M(X)||M(X ′)) = 1
λ− 1 logEθ∼M(X′)
[( pM(X)(θ)
pM(X′)(θ)
)λ] ≤ ε
It is convenient to consider RDP in its functional form as εM(λ), which is the RDP ε of mechanism M at order λ. We now state the result which our privacy analysis builds on. Lemma 2.1. RDP-Gaussian mechanism (for a single-label setting) (Mironov, 2017). Let f : X → R have bounded `2 sensitivity for any two neighboring datasetsX,X ′, i.e., ‖f(X)− f(X ′)‖2 ≤ ∆2. The Gaussian mechanismM(X) = f(X) +N (0, σ2) obeys RDP with εM(λ) = λ∆ 2 2
2σ2 .
Another notable advantage of RDP over (ε, δ)-DP is that it composes naturally. This will be helpful when analyzing our approach which repeatedly applies the same private mechanism to a dataset.
Lemma 2.2. RDP-Composition (Mironov, 2017). Let mechanismM = (M1, . . . ,Mt) whereMi can potentially depend on outputs ofM1, . . . ,Mi−1.M obeys RDP with εM(·) = ∑t i=1 εMi(·).

heading: 2.2 PATE AND CAPC
text: PATE (Private Aggregation of Teacher Ensembles) is a model agnostic algorithm for training ML models with DP guarantees (Papernot et al., 2017). Rather than training a single model on a dataset, PATE trains an ensemble of models from (disjoint) partitions of the dataset. Each model, called a teacher, is then asked to predict on a test input and to vote for one class. Teacher votes are collected into a histogram where ni(x) indicates the number of teachers who voted for class i. To preserve privacy, PATE relies on the noisy argmax mechanism and only reveals a noisy aggregate prediction (rather than revealing each prediction directly): argmax{ni(x) + N (0, σ2G)}, where the variance σ2G of the Gaussian controls the privacy loss of revealing this prediction. A student model learns in a semi-supervised fashion by querying the ensemble of teachers for noisy labels, where each label incurs additional privacy loss. Loose data-independent guarantees are obtained through advanced composition (Dwork et al., 2014) and tighter data-dependent guarantees (see Appendix Section L) are possible when there is high consensus among teachers on the predicted label (Papernot et al., 2018). To further reduce privacy loss, Confident GNMax only reveals predictions that have high consensus: maxi{ni(x)} is compared against a noisy threshold also sampled from a Gaussian with variance σ2T . PATE was created for single-label classification; our work extends it to the multi-label setting.
CaPC (Confidential and Private Collaboration) is a distributed collaborative learning framework that improves on PATE (Choquette-Choo et al., 2021). In addition to protecting the privacy of training data through differential privacy, CaPC also protects the confidentiality of test data and model parameters by introducing new cryptographic primitives. Confidentiality refers to the notion that no other party (or adversary) can view, in plaintext, the data of interest—it protects the inputs to our mechanism. This differs from differential privacy which protects what can be inferred (in our case about the training set for PATE models) from the outputs of our mechanism. Both protect data privacy in different ways. In CaPC, each teacher model is trained by a distinct (and different) protocol participant. The querying party initiates the protocol by (1) encrypting unlabeled data and the other (answering) parties return an encrypted label. Then, (2) the encrypted vote is secretly shared with both the answering party and the Privacy Guardian, where the Privacy Guardian follows PATE to enforce DP. Finally, (3) the Privacy Guardian engages in the secure computation with the querying party and returns a DP vote to the querying party. The detailed CaPC protocol can be found in Algorithm 1 of Appendix J.

heading: 2.3 PRIOR WORK ON MULTI-LABEL CLASSIFICATION
text: The closest to our work is that of Zhu et al. (2020), which provides a privacy-preserving nearest neighbors algorithm formulated using PATE. The nearest-neighbor training points are used as teachers, where their labels are the votes. While this work is applicable to the multi-label setting, it assumes the existence of a publicly-available embedding model, which is used to project high-dimensional data onto a sufficiently-low-dimensional manifold for the meaningful computation of distances (to determine the nearest neighbors). Instead, our approach does not make this assumption. Furthermore, we also show in Section 3 that clipping votes to the `1 ball, as done in Zhu et al. (2020), is not optimal—given that noise is sampled from a Gaussian distribution. Instead, we obtain tighter bounds by clipping votes to an `2 ball. The multi-label voting problem can also be formulated as simultaneously answering multiple counting queries which has been studied extensively in the theoretical literature. Though data-independent optimal error bounds for the privacy loss were proven by Dagan & Kur (2020), these mechanisms do not generally have data-dependent bounds and have yet to show promise empirically in settings such as multi-label voting. Another alternative multi-label method is differentially private stochastic gradient descent (DPSGD), which was proposed by Abadi et al. (2016a) and applied to the multi-label setting by Zhang et al. (2021) to train small multi-label models (k = 5 labels). We compare directly with their work and find that our methods perform better. We present a detailed description of the related work in Appendix E. Finally, we stress that our evaluation includes large-scale healthcare datasets with a natural need for privacy and the additional challenge of being severely imbalanced.

heading: 3 DIFFERENTIAL PRIVACY MECHANISMS FOR MULTI-WINNER ELECTION
text: Multi-winner election systems are direct generalizations of popularly used single-winner elections. They are adopted commonly in real-life elections and their comprehensive analysis can be found
in Elkind et al. (2017) and Faliszewski et al. (2017). Here, we formally define a multi-winner system and propose DP mechanisms to facilitate the private release of the outcome of a multi-winner election.
Compared to single-winner elections, multi-winner elections are more challenging for designing a DP mechanism: instead of outputting a single scalar, multi-winner elections output a higher-dimensional vector and thus require more noise to achieve the same level of privacy. DP mechanisms for singlewinner voting have been well studied before, where the noisy arg max achieves minimal privacy loss due to its tight sensitivity as a result of information minimization (Dwork et al., 2014). However, to the best of our knowledge, no prior work formally defines and analyzes DP mechanisms for multi-winner election systems, hence we provide Definition 3 and the analysis. We provide formal data-dependent and data-independent privacy loss bounds in Section 4.
Definition 3. θ-multi-winner election. Given a set of n voters, each with a ballot of k candidates (coordinates) b ∈ {0, 1}k such that ‖b‖2 ≤ θ. The outcome of a θ-multi-winner election with threshold T is defined as
f(b1, . . . , bn) , i : n∑ j=1 bj [i] > T  ∈ {0, 1}k, where T = n2 and with the binary decision per label i, ∑n j=1 bj [i] represents the number of positive votes.

heading: 3.1 DP MECHANISMS FOR∞-MULTI-WINNER ELECTION
text: In an∞-multi-winner1 election, each elector can vote for any candidates in their ballots. We propose to decompose the multi-winner election into k separate single-winner elections, where we instead apply the well-studied noisy arg max separately to each of the k single-winner elections. We call this Binary voting and state formally in Definition 4 below. For m instances of∞-multi-winner elections, the total privacy loss of this mechanism follows Lemma 2.2 which can then be tightly expressed as (ε, δ)-DP guarantee for a chosen δ.
Definition 4 (DP (Noisy Argmax) Binary Voting Mechanism). For an∞-multi-winner election, the binary voting mechanism is
Mσ(b1, . . . , bn) , i :  n∑ j=1 bj [i] +N (0, σ2G)  > Ti  ∈ {0, 1}k,
where Ti = n− ∑n j=1 bj [i] is the number of negative votes, which enables more noise to be added than when T = n2 . Though there are many potential per-candidate Binary voting mechanisms, we base ours on the noisy argmax mechanism because of its advantageous privacy guarantees stemming from its well-understood sensitivity: changing the training set to any adjacent one can only modify a single ballot. We also leverage propose-test-release (Dwork & Lei, 2009) shown in Algorithm 2 of Appendix K. Next, we show that Binary voting is optimal in the coordinate-independent setting.
Definition 5. A function f(X) : Rn → Rk is coordinate-independent if the i’th output coordinate of f , fi, is determined by a unique subset Pi(X) of the input X , such that ∩ki=1Pi = ∅. Pi(X) indexes (partitions) the input X uniquely for each i and returns the chosen subset; the chosen columns are dependent only on i, not the particular dataset X .
We first build an intuition for our guarantee and then provide the formal statement (in Proposition 3.1). Recall from Section 2 that the crux of DP analysis is to bound the sensitivity of the random mechanism M, which is the noisy output of the function2 f . Definition 6. Sensitivity is the maximum deviation ∆pf = max
(X,X′):||X−X′||1=1 ||f(X)− f(X ′)||p of
f ’s output for any adjacent pair of inputs X and X ′, i.e., have a Hamming distance ||X −X ′||1 of 1, on their rows (Dwork et al., 2014).
1We use∞ to emphasize that any vote b ∈ {0, 1}k is allowed but a tighter bound exists: ‖b‖2 ≤ √ k <∞. 2Because the random mechanism differs minimally from the function, we use the two interchangeably.
Observe that output fi of a Binary voting mechanism for a coordinate i depends only on the corresponding i−th coordinate of the input ballot because we apply Binary voting independently to each candidate. For any mechanism f , ∆pf is maximized when the mechanism’s output for each coordinate i is flipped from predicted to not predicted or vice versa. The pair of teacher votes achieving this differ in each coordinate i. This also means that any coordinate-independent mechanism has sensitivity at least as large as the one of Binary voting mechanism because all k coordinates can be flipped. If there were coordinate-dependence (e.g., if the output coordinates i and j both solely depended on the input coordinate i), it may not be possible to find such a single pair of databases across all coordinates, simultaneously, which would decrease the sensitivity and thus the privacy loss. Proposition 3.1 below formally states our result. For more intuition, example functions, as well as the full proof, see Appendix A and Proposition A.2 therein. Proposition 3.1. For a coordinate-independent multi-label function fmulti(X) : Rn → Rk, the `1 sensitivity ∆1fmulti is equal to that of Binary voting applied per label and thus fmulti does not provide a better privacy guarantee than k applications of Binary voting.
Note that Proposition 3.1 is exactly applicable to Binary voting if we assume candidate independence: then each candidate on all ballots only influences a single winner. Analyzing these assumptions, we also readily see two scenarios when a Binary voting mechanism can be outperformed. The first scenario is when any input coordinate Xi explains > 1 output (coordinate dependence). Proposition A.4 of Appendix A proves that for fmulti to achieve a strictly lesser sensitivity, we necessarily require coordinate dependence. If there is coordinate dependence, then there is some correlation between the outputs of the mechanism (in our case, the labels). When this is the case, it may be possible to achieve a tighter privacy loss bound by leveraging their correlations, especially if these correlations are high (see Section D in the Appendix). The second case we observe is whenever p > 1 for the sensitivity, which is a direct result of Hölder’s Inequality (Hölder, 1889). We explore this in Section 3.2 by clipping the sensitivity in the `2 norm.
3.2 DP MECHANISMS FOR τ -MULTI-WINNER ELECTION
When the average ballot does not vote for all k candidates, it is possible to obtain tighter privacy guarantees by considering the τ -multi-winner election. Here, we bound the `2 norm of each ballot, limiting the individual impact of a ballot. For this problem to be meaningful, we assume τ < √ k; otherwise, we could always use the Binary voting mechanism from Definition 4. Note that norm clipping is a popular method for bounding the influence of an individual’s vote on the sensitivity of the mechanism (Abadi et al., 2016b). We integrate this method into Binary voting in Definition 7. Definition 7 (DP τ Voting Mechanism). Mechanism for τ -Multi-Winner Election. For a τ -multiwinner election the τ Voting mechanism is
Mσ(b1, . . . , bn) , { i : ( n∑ j=1 vj [i] +N (0, σ2G) ) > Ti } ∈ {0, 1}k,vj [i] , min(1, τ ‖bi‖2 )bi,
where we choose Ti = n− ∑n j=1 vj [i], which represents the number of clipped negative votes. To analyze the privacy loss of this new mechanism, we propose an extension of Lemma 2.1 to make it applicable to this multi-voting task. Lemma 3.2. RDP-Gaussian mechanism for a multi-label setting. Let f : X → Rk obey ‖f(X)− f(X ′)‖2 ≤ ∆2 for neighboring datasets X,X ′. The Gaussian mechanism M(X) = f(X) +Nk(0, σ2I) obeys RDP with εM(λ) = λ∆ 2 2
2σ2 .
We present proof in the Appendix C. Next, we illustrate how our mechanism offers superior privacy guarantees to the similar `1 clipping proposed in Zhu et al. (2020), which is not optimal for Gaussian mechanisms. Our bound is no larger, and often much smaller, than the privacy bound in the `1 norm. We can see this by comparing the privacy loss of the two methods in the case of max possible change (as in Definition 6): M(λ) = λτ22 σ2 = λ∆22 2σ2 ≤ λ∆21 2σ2 = λ(2τ1) 2 2σ2 = λ2τ21 σ2 where in the first inequality we use the fact that ‖x‖2 ≤ ‖x‖1. Empirically, we confirm that τ voting achieves a much tighter bound on many multi-label datasets. Take τ1 to represent clipping in the `1 norm and similarly for τ2. On Pascal VOC, which has k = 20 labels, we find that we can set τ2 = 1.8 and τ1 = 3.4 without deteriorating the utility of the mechanism (as measured using the balanced accuracy). In general, we
select τ to be marginally larger than the average p-norm of labels in the training data. For example, there are on average fewer than 2 positive labels out of 20 per query in the Pascal VOC dataset. Here, `2 norm clipping achieves a >6x tighter privacy loss compared to Zhu et al. (2020) and the multi-voting of Section 3.1.

heading: 3.3 CASTING∞-MULTI-WINNER ELECTIONS AS SINGLE-WINNER ELECTIONS
text: It is also possible to approximate multi-winner elections using single-winner voting mechanisms by encoding each of the 2k different outcomes as a separate candidate for a single-winner voting mechanism. We call this mechanism the powerset voting mechanism. Definition 8 (DP Powerset Mechanism for Multi-Winner Elections). Denote the Powerset operator as P(·). For a∞-multi-winner election with ordered outcomes P({0, 1}k), where |P({0, 1}k)| = 2k,
Mσ(b1, . . . , bn) , arg max i P({0, 1}k)i : n∑ j=1 1bj=P({0,1}k)i +N (0, σ 2 G)  ∈ {0, 1}k, where 1 represents the indicator function. We first note that this is an approximation of the MultiWinner problem. The outcome of the mechanism may differ from the plurality per candidate if there is no ballot cast with those votes. When we compare our two voting mechanisms, we find that there are two regimes where Powerset voting outperforms Binary voting.
The first regime is when there are high correlations between the multi-winner candidates, i.e., there is strong coordinate dependence (see Section B.4). The distribution over outcomes can be approximated by viewing the collection of single-winner outcomes as non-uniform balls and bins problem: each distinct outcome i ∈ [1, . . . , 2k] has some probability Pi of being selected. Then, each of the n ballots is an independent ball being thrown at these bins. We can estimate the probability of each of the 2k single-winner outcomes. Doing so, if the likelihood of a single i−th outcome is much higher than the rest, it results in decreased privacy loss.
The second regime is when neither mechanism can leverage stronger data-dependent privacy guarantees. When the distribution of multi-winner outcomes and single-winner outcomes approaches a uniform distribution, the best guarantee either can achieve is data-independent privacy bound based on the sensitivity of either mechanism and the amount of noise added. Because Binary voting composes k separate DP queries, the privacy loss using this approach is necessarily higher than from Powerset voting which only releases a single outcome. Instead, when there is coordinate independence, or when each individual multi-winner candidate has a high probability of winning, or when the most likely outcomes are approximately the same between Binary voting and Powerset voting, we find that Binary voting performs better. See Appendix B.4 for our detailed theoretical analysis and supporting empirical evidence. See Sections 4 below for a detailed analysis of the data-independent and data-dependent privacy bounds of Binary voting and Powerset voting.

heading: 4 FROM PRIVATE ELECTIONS TO PRIVATE MULTI-LABEL CLASSIFICATION
text: In addition to the obvious application of making elections private, DP voting mechanisms play an important role in privacy-preserving machine learning. Notably, PATE adopted the noisy arg max mechanism, a canonical DP single-winner election mechanism, for training private single-label models by transferring knowledge with semi-supervised learning. In this section, we discuss how to use our proposed DP multi-winner mechanisms to build systems for private multi-label classification.
4.1 BINARY PATE, τ PATE AND POWERSET PATE
By replacing the noisy arg max mechanism in single-label PATE with one of our multi-winner election mechanisms, we can enable multi-label PATE. In doing so, non-private multi-label models can be trained on the private centralized dataset and used as teachers for semi-supervised learning. We leverage a bank of unlabeled data, which is often widely available, and label m of these data points with noisy estimates from the ensemble of teachers using our multi-winner mechanisms. We then train a student model on the newly DP labeled data, preserving DP of the non-private teachers’ training data. We call the corresponding forms Binary PATE, τ pate, and Powerset PATE.
Because we only replace aggregation mechanism in PATE, our new multi-label PATE algorithms (and their corresponding voting mechanisms) can directly leverage the tight data-dependent analysis of Papernot et al. (2018). In particular, when there is an empirically observed highly likely outcome, we can often draw a much tighter bound on the privacy loss. Note that the privacy budget must be sanitized before being released which can be done using smooth sensitivity, as shown by Papernot et al. (2018, Algorithm 2). In absence of this empirical observation, when the noisy arg max mechanism satisfies εM(λ)-RDP, our Binary voting and Binary PATE algorithm achieves a data-independent bound of ∑k i εM(λ)i, τ -voting and τ PATE of λτ2
σ2 , and Powerset voting and Powerset PATE of εM(λ), all per election (query). Note that τ PATE also leverages data-dependent analysis as with Binary PATE, but with the additional clipping of votes.

heading: 5 EXPERIMENTAL EVALUATION
text: We carry out the evaluation on three medical datasets CheXpert (Irvin et al., 2019), MIMICCXR (Johnson et al., 2019), PadChest (Bustos et al., 2020), and on a vision dataset Pascal VOC 2012 (Everingham et al., 2010). We use the following metrics: (1) accuracy, (2) mean recall per class denoted as balanced accuracy (BAC) (Brodersen et al., 2010), (3) area under the receiver operating characteristic curve (AUC) (Hand & Till, 2001), and (4) mean average precision (mAP). We use DenseNet-121 (Huang et al., 2017) for the medical datasets and ResNet-50 (He et al., 2016) for the vision dataset. See Supplement Section G for dataset and model descriptions. We experiment with
ε = 8 for 5 labels on CheXpert (see Appendix I.3), ε = 10 for predictions on PascalVOC, ε = 20 for 11 labels on CheXpert or MIMIC, and also ε = 20 for 15 labels on CheXpert (see also Section I.9).

heading: 5.1 ANALYZING THE QUERY-UTILITY TRADEOFF IN PATE
text: In comparing how the privacy parameter σG impacts the query-utility tradeoff of each mechanism, under a fixed ε = 20 across all datasets, we find that under high consensus Binary voting performs best and under lower consensus τ voting performs best. In Figure 1, we compare each multi-winner election mechanism used in τ PATE and find that each mechanism has a range of σG where it performs best. In particular, as σG → 0, no queries can be answered by any mechanism due to a lack of noise to satisfy the chosen ε. For sufficiently small σG and with suitable consensus amongst voters, which is the case for Pascal VOC, CheXPert, and MIMIC-CXR, we find the data-dependent analysis for Binary voting outperforms all others while remaining in a regime of high-performance metrics. As σG → ∞, the τ voting mechanism outperforms all others, though in most cases at a decrease in the performance metrics; however, on PadChest, this is the best bound. This can be explained by the fact that on PadChest we can only train 10 teachers before each individual model’s accuracy degrades too much. An important distinction is that τ pate can perform worse than Binary PATE when the chosen τ bound is too small (because ballot clipping can change the vote distribution). For well-chosen values of τ we observe only marginal decrease in the number of queries answered and the performance metrics (c.f. Figure 1 with Figures 13, 12, and 14 in Appendix I). Inspecting the tradeoff of Powerset PATE (see Figure 8 in Appendix I.1), we find that a much lower noise can be tolerated before a steep decline in performance metrics. Because of this, we find that much fewer queries can be answered (see Tables 5 and 8 in Appendix I.1). Thus, we recommend τ PATE as the de-facto mechanism.

heading: 5.2 PRIVATE CENTRALIZED LEARNING USING MULTI-LABEL PATE
text: We now show that even in the centralized setting, our multi-label PATE methods outperform the competitive baselines. We train models on Pascal VOC and CheXpert which include 20 and 11 labels, respectively. We leverage the entire training set to train a single non-private model and a single private model via DPSGD (Abadi et al., 2016a). For our multi-label PATE we instead train 50 teachers each on a separate disjoint partition of the centralized training set (and thus, with 1/50 number of samples compared with DPSGD and the non-private model). We use these teacher models to privately train a student model using semi-supervised learning with MixMatch (Berthelot et al., 2019) (where modifications were made to adapt MixMatch to the multi-label setting). Though the DPSGD algorithm does not assume a public unlabeled dataset, we compare it with our methods because DPSGD can be directly applied to this multi-winner setting. DPSGD for multi-label was studied in prior work (Zhang et al., 2021), and cannot directly leverage public unlabeled data. On the other hand, our PATE-based approaches leverage a public pool of unlabeled samples that have noisy labels provided by the ensemble of teachers. The added noise protects the privacy of the centralized training data. We then train the student on the newly labeled samples. The student model, non-private
baseline, and DPSGD baseline were all pre-trained on ResNet-50 models. Observing Table 2, we see that our Binary PATE algorithm outperforms all other privacy-preserving techniques by a significant margin. Our Binary PATE does not use τ clipping or the confident GNMax improvement so as to fairly compare with Powerset PATE. The non-private model achieves strong performance across all metrics where the model trained using DPSGD incurs significant degradation across all metrics.
Though Binary PATE outperforms DPSGD and Powerset PATE, it falls short of the non-private model by a wide margin, indicating much room for improvement in multi-label privacy-preserving techniques—in particular, in extreme multi-label settings, which we motivate and expand on in Appendix D. We observe that Powerset PATE answers much fewer queries (leading to less training data for the student model) than Binary PATE, at only 78 compared to 427. Though the student model only trains on 427 samples compared to 5717 for DPSGD, Binary PATE has the benefit of
using non-private learning on this data whereas DPSGD must add noise in training which impedes model learning. Finally, DPSGD incurs a high computational cost (which multi-label PATE does not) due to the expensive per-example gradient computations (Subramani et al., 2020).

heading: 5.3 MULTI-LABEL CAPC
text: By replacing the single-label PATE in Choquette-Choo et al. (2021) with our multi-label PATE mechanisms, we enable multi-label learning in a multi-site setting: the framework of CaPC allows for distributed collaboration across models located at different sites. We scale the evaluation of multilabel CaPC learning to real-world datasets and models by providing a decentralized (independent) evaluation of each answering party, enabling large models. Our multi-label CaPC experiments replicate the setup of Choquette-Choo et al. (2021) using the source code provided.
We train 1 model per participant on separate distinct portions of the training set and then use multilabel CaPC to improve the performance of 3 participants. Details are in Supplement Section H. Observing Table 1, we see that multi-label CaPC consistently improves the BAC, with the greatest improvement of a considerable 5 percentage point increase on Pascal VOC and improvement across all other metrics. These improvements are echoed in the larger and more privacy-sensitive CheXpert and MIMIC-CXR datasets; however, we observe some performance degradation on PadChest, likely because of the degraded vote utility compared to the original training data. As one of the main applications for CaPC is the healthcare domain, the on-average performance improvements and associated privacy guarantees demonstrate the utility of multi-label CaPC in a realistic use case.
Inspecting Figure 2, we see that multi-label CaPC leads to significant improvements in low-sample, low-performance labels (e.g., labels EN and FR on CheXpert). Thus, poorer performing models and classes can gain from the noisy aggregation of more performant teacher models through multilabel CaPC. This has potential ramifications for fairness because our experiments consistently demonstrate that private multi-label CaPC can improve model performance on its poorer performing subpopulations—where Suriyakumar et al. (2021) show that differentially private can hurt performance on these subpopulations. We reiterate that these subpopulations are common in many settings such as healthcare due to imbalanced labels, e.g., rarer diseases (see Figure 6 of Appendix G).

heading: 6 CONCLUSIONS
text: We address the need for privacy in the multi-label setting with three new multi-label voting mechanisms. We show and prove that, while simple, our Binary voting cannot be outperformed without strong candidate correlations. When these correlations exist, we prove new data-independent bounds for our τ voting mechanism and theoretically analyze when Powerset voting performs better. Using these mechanisms, we create multi-label PATE which outperforms DPSGD in the centralized private learning setting. We further enable multi-label learning in multi-site scenarios by creating multi-label CaPC. Our results achieve new state-of-the-art results for private learning in multi-label settings and demonstrate a need for further exploration to lessen the gap between private methods and non-private baselines.

heading: 7 ETHICS STATEMENT
text: Our work aims at the protection of privacy and from this perspective, it should benefit society. More specifically, our work aims to provide private multi-label classification in a collaborative setting and therefore any concerns of it being integrated into applications deemed harmful to humans or the environment are a smaller subset of those which exist in regular multi-label classification—a common machine learning application.
It is not well understood what the value of ε should be and therefore improper usage and large values of epsilons could leak private information. This risk can be mitigated by setting an upper threshold for the possible values of ε which can be used. The values of ε used in our experiments (8, 10, and 20) could be considered high. However, since our work provides multi-label classification, there are many labels that need to be released and therefore the privacy budget will naturally be higher than for single-label classification. Our common choice of ε = 20 is empirical. We select a value, which although is not tight, is a reasonable bound for our multi-label setting because it is in the range of values considered by most empirical evaluations (of order 10). We also test other ε values, for instance, show ε = 10 for the Pascal VOC dataset in Table 1 and ε = 8 for the first 5 labels from the CheXpert dataset in Section I.3 in the Appendix.
The worst scenario in the collaborative setting and for our method is when the querying party colludes with the privacy guardian. In this situation, the labels from each answering party are revealed. There are many possible attacks that can take advantage of such information. One of them is model extraction, where the number of queries answered by an answering party can be sufficient to replicate the party’s model and steal its intellectual property. We should make sure that the privacy guardian, which is responsible for the privacy protection, is a trusted institution, for example, a party designated by a government.

heading: 8 REPRODUCIBILITY STATEMENT
text: For theoretical results, we provide clear explanations of assumptions and complete proofs are included in the Appendix (e.g., C). We submit our code in the supplementary material. In the README.md file we provide the main commands needed to run our code. We also describe the pointers to the crucial parts of the code that directly reflect the implementation described in the main part of the submission. For Pascal VOC and medical datasets used in the experiments, we provide complete data processing steps in the code uploaded as supplementary materials.

heading: A OPTIMALITY OF BINARY PATE
text: Intuition behind Proposition 3.1. Intuitively, a coordinate-independent function will be bounded below by Binary PATE because a single pair of databases (X,X ′) will lead to the maximum sensitivity of each output coordinate. If the function were coordinate-dependent, this is not guaranteed, i.e., it is possible that some output coordinate will have a smaller sensitivity because we can only pick one pair of databases for all coordinates simultaneously. We motivate this intuition with two examples. Let X be our database with 2 columns, i.e., X ∈ R2. We will consider ∆1f . Take f(X) = [sin(X0), cos(X1)]. Because this function is coordinate-independent, we can pick X = [−π2 , 0] and X ′ = [π2 , π] independently to achieve the worst-case sensitivity of 4. However, inspection of the coordinate-dependent g(X) = [sin(X0), cos(X0)] will show ∆1g = 2 √ 2 < ∆g0 + ∆g1 = 4, where no two databases X and X ′ can ever achieve ∆1g = 4 because the minimums and maximums of sin and cos do not occur at the same values of X . Lemma A.1. If f(X) : Rn → Rk is coordinate-independent, there exists a pair of databases (X,X ′) with ||X −X ′||1 = 1 (a change in only one row) which achieves the worst-case sensitivity for each of the coordinates fi.
Proof. We consider the i∗ output coordinate of f . We know that fi∗(X) = fi∗([X1, . . . , Xn]) = fi∗([Xi|i∈Pi∗ , Xi|i/∈Pi∗ ]) = fi∗([[Xi|i∈Pi∗ , X ′ i|i/∈Pi∗ ]) by Definition ??. We define the worst-case sensitivity for fi∗, ∆1fi∗ as in Dwork et al. (2014). Then
∆1fi∗ = max (X,X′)
||X−X′||1=1
||fi∗(X)− fi∗(X ′)||1
= ||fi∗([Xi|i∈Pi∗ , Xi|i/∈Pi∗ ])− fi∗([X ′ i|i∈Pi∗ , X ′ i|i/∈Pi∗ ])||1 = ||fi∗([Xi|i∈Pi∗ , Xi|i/∈Pi∗ ])− fi∗([X ′ i|i∈Pi∗ , Xi|i/∈Pi∗ ])||1
Therefore we can choose the members in Pi∗(X) arbitrarily and independently to achieve the worst case sensitivity for fi∗ while the members not in Pi∗(X) can take any value because they do not
affect the output. Using the fact that the Pi’s are disjoint, we can continue this over all values of i∗ from 1 to k to get the desired result.
Proposition A.2. For a coordinate-independent multi-label function fmulti(X) : Rn → Rk and a single-output function fbinary(X) : Rn → R applied once for each of the k labels such that fbinary,i = fmulti,i , the `1 sensitivity ∆1fmulti is equal to that of binary PATE applied per label and thus does not provide a better privacy guarantee. Note that fbinary,i = fmulti,i means that they are the same function; we include this to make clear the comparison between the multi-label and binary functions.
Proof. Let X,X ′ ∈ Rn be databases such that ||X − X ′||1 = 1 and let fbinary(X) : Rn → R, fmulti(X) : Rn → Rk be arbitrary coordinate-independent functions. Let f·,i and Xi represent the i’th coordinate of the output and input respectively. As in Definition ??, let Pi(X) represent the partition of input coordinates that determine the output coordinates fbinary,i, fmulti,i, such that additionally ∪ki=1Pi = X . We define the sensitivity of f , ∆f as in Dwork et al. (2014). We now consider the `p sensitivity of fmulti:
∆fmulti = max X,X′
||X−X′||1=1
||fmulti(X)− fmulti(X ′)||p
= max X,X′
||X−X′||1=1
( (fmulti,1(X)− fmulti,1(X ′)) p + · · ·+ (fmulti,k(X)− fmulti,k(X ′)) p) 1p = max
X,X′
||X−X′||1=1
( (fmulti,1([X1, . . . , Xn])− fmulti,1([X ′1, . . . , X ′n]) p + . . .
+ (fmulti,k([X1, . . . , Xn])− fmulti,k([X ′1, . . . , X ′n])) p) 1p
= max X,X′
||X−X′||1=1
(( fmulti,1([P1(X),∪ki 6=1Pi(X)])− fmulti,1([P1(X ′),∪ki 6=1Pi(X ′)]) )p + . . .
+ (fmulti,k(Pk(X),∪i 6=kPi(X)])− fmulti,k([Pk(X ′),∪i 6=kPi(X ′)])) p) 1p
= max X,X′
||X−X′||1=1
(( fmulti,1([P1(X),∪ki 6=1Pi(X)])− fmulti,1([P1(X ′),∪ki 6=1Pi(X)]) )p + . . .
+ (fmulti,k([Pk(X),∪i 6=kPi(X)])− fmulti,k([Pk(X ′),∪i6=kPi(X)])) p) 1p by Definition ??
= max X,X′
||X−X′||1=1
(( fbinary,1([P1(X),∪ki6=1Pi(X)])− fbinary,1(P1(X ′),∪ki 6=1Pi(X)]) )p + . . .
+ (fbinary,k([Pk(X),∪i 6=kPi(X)])− fbinary,k([Pk(X ′),∪i 6=kPi(X)])) p) 1p
= ((∆fbinary,1) p + · · ·+ (∆fbinary,k)p) 1 p by Lemma A.1
= ∆fbinary,1 + · · ·+ ∆fbinary,k with p = 1
Where the third last line follows since fmulti,i = fbinary,i.
In the case where p > 1, we have that ((∆fbinary,1)p + · · ·+ (∆fbinary,k)p) 1 p ≤ ∆fbinary,1 + · · · + ∆fbinary,k by a consequence of Hölder’s inequality and thus equivalently that ∆fmulti ≤ ∆fbinary,1 + · · ·+ ∆fbinary,k Lemma A.3. If a function f(X) : Rn → Rk is coordinate-dependent, the worst-case sensitivity is not guaranteed.
Proof. We prove by counterexample. Assuming that all coordinate-dependent functions guarantee the worst-case sensitivity, we must find a function that does not satisfy this claim. Take the coordinatedependent function f = [sin(X0), cos(X0)], where f(X) : R → R2 and X0 determines > 1 output. The worst-case sensitivity of each coordinate is 2 since −1 ≤ sin(X0), cos(X0) ≤ 1 and therefore the worst-case sensitivity of a function with two coordinates is 2 + 2 = 4. However, since sin2 + cos2 = 1, a single choice of X0 and X ′0 gives a worst-case sensitivity for f as 2 √ 2 < 4. We arrive at this by taking the derivative of ||[sin(X0), cos(X0)] - [sin(X ′0), cos(X ′0)]||1 and set it to 0 to get for example X0 = π4 and X ′ 0 = 5π 4 .
Proposition A.4. For a multi-label function fmulti(X) : Rn → Rk to have a lower sensitivity than the sum of the worst-case sensitivities for each coordinate, i.e., ∆1fmulti < Σki=1∆1fbinary,i, fmulti must be coordinate-dependent.
Proof. We proceed by contradiction. Let fmulti be a coordinate-independent function. By Proposition A.2, ∆1fmulti = ∆1fbinary,1 + · · · + ∆1fbinary,k = Σki=1∆1fbinary,i which contradicts ∆1fmulti < Σ k i=1∆1fbinary,i. Therefore fmulti must be coordinate-dependent.

heading: B POWERSET VS BINARY MULTI-LABEL PATE

heading: B.1 PRELIMINARIES
text: Recall that Binary PATE has 2 · k events: the presence or absence independently for each of the k labels. Powerset differs from Binary PATE in that it (1) has a number of events that grows exponentially (2k) in the number of labels, because each subset of the binary vector’s powerset is a separate event, (2) returns the entire binary vector of k labels simultaneously, and thus benefits from correlations and deteriorates with the lack thereof, and (3) only adds noise once to the entire binary vector. Here, we analyze under what scenarios Powerset is better or worse than binary PATE.
Recall that there are two bounds for PATE. The data-independent bound is a function only of the noise added to the vector. The data-dependent bound is a function of the probability distribution between events, estimated using the gaps between each predicted event. These gaps are influenced by (1) the number of labels, (2) the amount of noise added, and (3) the amount of correlation between labels, as we will now show.
To analyze PATE, we upper bound the RDP using Theorem B.2. The main (random) variable influencing the this privacy loss is the gap, q(n̄) which we calculate using Proposition B.1 from Papernot et al. (2018, Proposition 10). It shows how to select ideal higher order moments µ1, µ2 and ε1, ε2, using the data-dependent value for q(n̄) (thus making the RDP bound a nonlinear function of q(n̄) solely). Proposition B.1. For a GNMax aggregatorMσ, the teachers’ votes histogram n̄ = (n1, · · · , nk), and for any i∗ ∈ P({0, 1}k), where P(·) denotes the Powerset, we have
Pr[Mσ(D) 6= i∗] ≤ q(n̄), and
q(n̄) , 1
2 ∑ i6=i∗ erfc ( n∗i − ni 2σ ) Where this is a minimal modification of (Papernot et al., 2018, Proposition 7) to go from single-label PATE to multi-label Powerset PATE. Theorem B.2 (From Papernot et al. (2018)). LetM be a randomized algorithm with (µ1, ε1)-RDP and (µ2, ε2)-RDP guarantees and suppose that there exists a likely outcome i given a dataset D and bound q̃ ≤ 1 such that q̃ ≥ Pr[M(D) 6= i]. Additionally suppose the λ ≤ µ1 and q̃ ≤ e(µ2−1)ε2 ( µ1 µ1−1 · µ2 µ2−1
)µ2 . Then for any neighboring dataset D′ of D, we have: Dλ(M(D)||M(D′)) ≤ 1 λ− 1 log ( (1− q̃) ·A(q̃, µ2, ε2)λ−1 + q̃ ·B(q̃, µ1, ε1)λ−1
) where A(q̃, µ2, ε2) ∆ = (1− q̃)/ ( 1− (q̃eε2) µ2−1 µ2 ) and B(q̃, µ1, ε1) ∆ = eε1/q̃ 1 µ1−1 .
When the top 3 vote counts, n1 > n2 > n3 satisfy n1 − n2, n2 − n3 σ (the gap is sufficiently large), the RDP bound can be well approximated as
εpowersetMσ (λ) ≤ exp(−2λ/σ 2)/λ,whereλ = (n1 − n2)/4, (1)
which is from Papernot et al. (2018, Corollary 11). Observing Figure 9 of Appendix I, we see that this is indeed the regime we are in for Binary PATE. Assuming Powerset PATE can attain this regime as well, we analyze under what circumstances Powerset PATE outperforms Binary PATE. To do this, we will analyze the respective data-dependent bounds under the expected gap.

heading: B.2 POWERSET
text: We define the Powerset mechanism in Definition 9. We sort n(x)i such that ni ≥ nj∀i > j. Denote gap , n1 − n2. We seek to upper bound our best-case expected privacy loss for Powerset PATE. Using Equation 1, we get
E[εpowersetMσ (λ)] =
∫ exp(
−gap 2 · σ2 )dgap.
E[εpowersetMσ (λ)] → 0 when gap → ∞. The base case gap with O(1) probability can be found by viewing Powerset PATE as a non-uniform balls and bins problem. We have 2k subsets, i.e., |P({0, 1}k)| = 2k. Each subset (instance of an output binary vector) is represented by a bin with probability Pi of having a ball land in it (be voted on by a teacher). The t teachers (Σin̄i = t) each vote independently for a bin (output binary vector).
To calculate the gap, we will calculate the load of the maximally loaded bin (most voted vector) and assume a best-case scenario for powerset PATE where each other bin has only 1 ball. Denote by τ the load of the maximally loaded bin. Then, gap = τ − 1 in our best-case scenario. By upper-bounding τ , we get an upper bound for the gap. Definition 9 (Mechanism for powerset PATE). Denote the powerset operator as P(·). For a sample x and k classes, let fj(x) ∈ {0, 1}k denote the j−th teacher model binary vector prediction. Let ni(x) be the vote count for the i−th subset (class), i.e., ni(x) , |{j : fj(x) = P ({0, 1}k)i}|. We define the powerset PATE mechanism as
Mσ(x) , arg max i
{ ni(x) +N (0, σ2) } .
To upper-bound the max load, we use an indicator random variable Cc representing the event of c collisions occurring in any bin. Using Markov’s inequality followed by Stirlings approximation, we get
Pr[Cc ≥ 1] ≤ E[Cc]
=
( t
c ) 2k∑ i P ci
≤ ( t · e c )c 2k∑ i
because ( ( t
c
) ≤ t! ≤ ( te
c )c).
As with n̄, we sort our probability [P1, · · · , P2k ] such that P1 ≥ P2 · · · ≥ P2k . Because n1 n2, we have that P1 Pi∀i 6= 1. Therefore, we have that ∑2k i ≈ P c1 and Pr[Cc ≥ 1] ≤ ( t·e c )
cP c1 . In particular, we care about the regime where the max load occurs with high-probability (Pr[Cc]→ 1).
Pr[Cc ≥ 1] ≤ ( t · e · P1
c )c → 1
exp(ln( t · e · P1
c )c)→ 1
=⇒ c · ln(t · P1) + c− c · ln(c)→ 0 =⇒ c · ln(t · P1) + c = c · ln(c) (2)
Specifying t and P1, we can then directly calculate the max collisions c, then the gap, and finally the best-case expected privacy loss. To compare directly with Binary PATE, we will directly calculate P1 from the analysis below.

heading: B.3 BINARY PATE
text: Here, we aim to specify a probability for success of Binary PATE p (note the lowercase, as opposed to uppercase P for Powerset PATE). This will directly control the expected gap of Binary PATE. Further, from it, we calculate the same gap for powerset PATE to compare the two. Performing a similar analysis for Binary PATE, we can model each teacher’s independent label prediction as a Bernoulli trial of probability pi, i = 1 · · · k. With t independent trials, we can model the gap as a binomial distribution of probability pi. To simplify our exposition, and since this will favour the Powerset method over Binary PATE, we assume p = pi∀i. Using composition, we get an expected privacy loss of
E[εbinary] = k · g=t∑ g=0 ( P (gap = g) 4 g exp ( −g 2 · σ2 ))
= k · g=t∑ g=0 (( t g ) pg(1− p)1−g 4 g exp ( −g 2 · σ2 )) = k · g=t∑ g=0 (( t g ) (pe)g(1− p)1−g 4 ge 1 2σ2 ) . (3)

heading: B.4 PRIVACY ANALYSIS COMPARISON: BINARY VERSUS POWERSET PATE
text: From the assumptions above, we can directly calculate each Pi, for Powerset PATE. We do this by recognizing that a single teacher’s binary vector can be modeled as a binomial distribution of k (the number of labels) trials and probability p. To calculate the probability of any one of the 2c possible binary vectors from the Powerset vector, we express each one as a l−hot binary vector (l labels present, independent of their coordinate position). Each possible subset satisfying l−hot will have equal probability of occurring (because we fixed p for all labels) Then, the maximum probability binary vector, when k sufficiently large (k > 5, approximately) and p→ 0 or p→ 1 is when l = 0 or l = k as otherwise the combinatorics leads to a probability split amongst too many choices. This implication may appear unnatural at first; however, it well models our output label distribution: when there are a set of label coordinates that share similarly high (or low) probabilities of predicting presence (or absence) of that label, then their most likely binary vector is all 1’s or 0’s.
Impact of random labels To model more complex distributions where in general pi 6= p, we can bucket the ranges of p present and analyze these buckets separately. Let us operate under the assumption of coordinate-independence. In this case, we have the maximal variance for the binomial distribution and thus largest gaps for Powerset and Binary PATE. In this case, we expect both methods to perform poorly: however, because the data-independent bound for Powerset PATE is tighter than for Binary PATE, Powerset PATE performs better, as shown in Figure 3. This gives us our first two observations: (1) Powerset PATE has a better worst-case privacy loss (data-independent bound) and (2) both Powerset and Binary PATE degrade to their data-independent bounds as p→ 0.5.
Impact of Correlation (Coordinate Dependence) Even when a bucket of labels has p ≈ 1 or p ≈ 0 (but not equal), we can still have a varying distribution of outcomes. In particular, with coordinate-independence, we can directly use our binomial analysis above and find that there is a uniform probability for all outcomes in each l−hot vector. In particular, there are factorially many outcomes each with equal probability. This drastically degrades the gap by reducing P1. However, when there is coordinate-dependence, e.g., the best-case when each label’s value directly implies the rest, then we have only two outcomes for each l−hot vector. This improves the gap by reducing the possible subsets and improving P1. We formalize this as follows: if we have some subset of d vectors that are dependent, then we can reduce k in our above analyses to (k − d). This gives us our third
observation: (3) coordinate dependence has a combinatoric improvement for Powerset PATE and at best a linear improvement for Binary PATE.
Impact of Higher Noise Multipliers Appealing back to the data-dependent q(n̄) calculation of Proposition B.1, we see that Binary PATE has a gap calculated as 2P − t/2σ for t teachers. This gives qbinary(n̄) = erfc(2P − t/2σ) However, for a similar gap, which is bounded for both to a max(gap) = t, we see that Powerset PATE will have qbinary(n̄) = ∑2k i erfc(gap/2σ), which is always worse when the gaps are equal. We can see this effect in Figure 4. Further, because we union bound across the 2k classes, a higher noise multiplier has a larger impact on Powerset PATE, as shown in Figure 8. These give our fourth and fifth observations: (4) in the best case, and for any equal gaps, Powerset PATE has a higher privacy loss, and (5) higher noise multipliers will impact Powerset PATE more for similar gaps.

heading: C RDP-GAUSSIAN MECHANISM FOR A MULTI-LABEL SETTING

heading: Proof.
text: Dλ(M(X)||M(X ′)) = Dλ(Nk(f(X), σ2I)||Nk(f(X ′), σ2I)
= 1
λ− 1 log
{ 1
σk √ (2π)k ∫ ∞ −∞ exp ( −λ 2σ2 ‖θ − f(X)‖22 ) exp ( −(1− λ) 2σ2 ‖θ − f(X ′)‖22 ) dθ } = 1
λ− 1 log
{ 1
σk √ (2π)k ∫ ∞ −∞ exp ( −λ ‖θ − f(X)‖22 − (1− λ) ‖θ − f(X ′)‖ 2 2 2σ2 ) dθ } = 1
λ− 1 log
{ σk √ (2π)k
σk √ (2π)k exp (λ− 1)λ 2σ2 ‖f(X)− f(X ′)‖22
} = λ ‖f(X)− f(X ′)‖22
2σ2 ≤ λ∆
2 2 2σ2

heading: D TOWARDS PRIVATE EXTREME MULTI-LABEL CLASSIFICATION
text: We face extreme multi-label classifications (Shen et al., 2020) in many real-world applications such as semantic segmentation (Zhou et al., 2017), hash-tag suggestions for user images (Denton et al., 2015), product categorisation (Agrawal et al., 2013) and webpage annotation (Partalas et al., 2015) where both input size and label size are extremely large. In this section, we investigate the privacyaccuracy tradeoffs of private semantic segmentation (a common and underlying example in extreme multi-label settings) that links each image pixel to its corresponding object class (an integer value) with a reasonable accuracy of above 60% but an expensive privacy cost of ε ≈ 3, 000, for a relative "small" image of size 200× 200, or ≈ 40, 000 pixels. We conclude this section by proposing future directions to alleviate the privacy-accuracy tradeoffs in extreme multi-label settings.
We consider MIT ADE20K semantic segmentation dataset (Zhou et al., 2017) that contains 150 objects including 35 stuff objects (e.g. sky, building) and 115 discrete objects (e.g. person, car). The label size for each image pixel is fixed (=150). However, the number of predicted labels for each image is the number of pixels, which varies across the dataset. To perform private semantic segmentation, we use PATE to label each image pixel. We split the training set of MIT ADE20K dataset into equally sized partitions for 20 teachers and train a Pyramid Pooling ResNet50-Dilated architecture of the Cascade Segmentation Module. The test accuracy of the ensemble of teachers (using 2000 of the test images) with respect to the PATE noise standard deviation σG between 0 and 5 varies from 67% to 47%. We observe that the level of noise must be quite small, σ < 3, or there is a steep drop in accuracy of more than 10 percentage points. The privacy cost is too high to provide meaningful guarantees ε, due to the small σ and large number of pixels required to be labeled.
We believe that privacy analysis in extreme multi-label settings can be tightened by exploiting the semantics of inputs. For example in the semantic segmentation task, we can reduce the privacy costs by taking advantage of the dependency between pixels so that instead of releasing an answer per pixel, we can release only a single label per semantic region (a grouping of pixels). Exploring label dependence, rather than assuming label independence, may also enable tighter privacy loss analysis and improve accuracy, as our analysis of Proposition 3.1 suggests. Label dependence is prevalent in many tasks, e.g., in healthcare labels are naturally organised into tree-like hierarchies such that domain experts (e.g. doctors) perform observations and diagnoses conditioned upon their parent node Van Eeden et al. (2012). Figure 5 shows an example of the label structure where the root label node corresponds to the most generic disease of Opacity, while the leaf label node represents the most specific disease of Pneumonia Pham et al. (2021). Pneumonia implies the presence of both Consolidation and
Opacity diseases. Thus, there exist many possible methods to optimize the answering of queries. It may be possible to tighten the privacy loss due to the implications (or, correlations) between labels; or, to query labels in a specific order such that the all dependent nodes (Consolidation and Opacity) can be inferred by the agreed presence of parent nodes (Pneumonia) by the teacher ensemble.
In addition to exploiting the knowledge of input and label domains, our analysis of the optimal settings for Binary PATE shows that privacy mechanisms can be tailored to the multi-label classifications. For example, k-fold adaptive bounds Kairouz et al. (2015) that draw tighter ( sublinear) privacy bounds for homogenous privacy settings can be extended to heterogeneous ε per label and per query settings of multi-label classification. However, it is unclear if and under what scenarios we can achieve a tighter bound. For instance, it is possible to take the maximum ε across all queries, but if there is a large gap k-fold adaptive composition may yield looser bounds. These settings of coordinate dependence, high label correlations, and heterogeneous k-fold adaptive composition are interesting for future work.
We design an experiment where the baseline method obtains answers to all the labels while the new proposed method exploits the semantics and queries labels selectively.
We find that the positive dependencies (e.g., if disease A is present then disease B is present as well) constitute a small fraction of the whole dataset. This is because there are many more negative than positive examples in the CheXpert dataset, which is caused by a class imbalance, a common problem in medical datasets. For instance, we find that if both Pneumonia and Pneumothorax are present then Lung Opacity occurs in 83.3% of the cases. However, both Pneumonia and Pneumothorax are present in only 0.06% of samples of the dataset. Thus, we consider negative instead of positive dependencies. For example, if Atelectasis is absent then Consolidation is absent as well in 98.7% of the cases. After ignoring samples for which at least one of Atelectasis or Consolidation have missing values, the percentage of samples where both labels are negative is 83%. We obtain the negative dependencies using the training set and generate the dependency matrix 3.
We compare multi-label PATE executed for each label vs using the semantics and querying the first label (Atelectasis) only, followed by (1) skipping the remaining labels and setting them as negative if the first label is negative, or (2) querying the other labels if the first label is positive. As expected, leveraging the semantics increases the number of answered queries from 35 to 127 for the same privacy budget ε = 8 of at the cost of lower performance (less accurate answers to the queries). However, increasing the number of answered queries by adding more privacy noise (σ = 67.5) causes the answered queries to be less accurate than by exploiting the label dependencies. We show a detailed comparison in Table 4.
Note that in the above example we consider the first five labels from the CheXpert dataset. We use the same setup as for the comparison between DPSGD and multi-label PATE I.3. The metrics are computed on the same 127 queries (to obtain 127 answered queries for the Answer all labels we increase its privacy budget from 8 to 26.5).

heading: E DETAILED COMPARISON WITH RELATED WORK
text: The main contributions from Zhang et al. (2021) on Adaptive DPSGD are two fold: (1) adaptive differentially private deep networks proposed by adding Gaussian noise to gradients whose scale
is linearly decaying instead of being static as in DPSGD, and (2) an analysis of the privacy loss using tCDP (truncated Concentrated Differential Privacy) (Bun et al., 2018), which is a refinement of differential privacy and of concentrated differential privacy, instead of using Moments Accountant (MA) (Abadi et al., 2016a) or Rény Differential Privacy (RDP) (Mironov, 2017). tCDP provides a tighter bound on the privacy leakage compared to MA because it can leverage privacy amplification via sub-sampling. Similarly to RDP, the analysis of Gaussian noise is particularly simple in tCDP and the composition of the randomized mechanism is straightforward. Adaptive DPSGD is applied to CheXpert, CIFAR-10, and MNIST datasets, where data is centralized. Our work is applicable in this centralized setting and the distributed collaborative setting where data is not centralized to a single database. We focus on the collaborative learning where multiple parties (e.g., hospitals) can collaborate via private inference. Another major difference between our approach and Adaptive DPSGD is that we do not reveal any intermediate results because of the use of cryptography, whereas the model trained using DPSGD is also a valuable asset that is released publicly. Finally, we note that Adaptive DPSGD only considers tuning of the model’s last layer (the head layer). This task is much easier (it has fewer parameters and is linear) and thus incurs less privacy leakage but requires the assumption of a relevant public dataset to train a performant feature extractor. The comparison between our proposed multi-label PATE and Adaptive DPSGD can be found in Section I.3. The results show that the student models from the proposed multi-label PATE outperform DPSGD.
PATE can be used in different tasks, for example, single-label classification, multi-label classification, generative models based on GANs (discriminate fake from real images, and generate samples privately). The original PATE framework (Papernot et al., 2017; 2018) is only applicable to a single-label classification. We extend PATE to the multi-label classification and show how it can be applied in a collaborative setting. Another line of work applies PATE to the training of GANs. PATE-GAN (Yoon et al., 2019) uses an ensemble of teacher discriminators to create a student discriminator. To ensure differential privacy, the student discriminator is trained solely on inputs produced by the generator and labeled by the teacher discriminators. The final task is a binary classification to discriminate fake from real images, while our task is the multi-label classification. Yang et al. (2021) follows the same algorithm as PATE-GAN except that the generative models used are adversarial autoencoders instead of GANs. This algorithm demonstrates promising results on synthetic speech generation but was not demonstrated on vision tasks. GS-WGAN (Chen et al., 2020) allows releasing a sanitized form of the sensitive data with rigorous privacy guarantees. It reduces gradient sensitivity using the Wasserstein distance and applies gradient sanitization to ensure differential privacy for the generator. However, it considers the task of generating differentially private synthetic data, which is orthogonal to our multi-label classification. G-PATE (Long et al., 2019) is also a method for generating differentially private datasets, which diverges from previous methods such as DP-GAN (Xie et al., 2018) or PATE-GAN by creating a differentially private aggregation mechanism that directly uses information from teacher discriminators to train a student generator. Both, G-PATE and GS-WGAN train the discriminator(s) non-privately while only training the generator with DP guarantees. They differ in the way the gradient is sanitized. GS-WGAN points that G-PATE has two main limitations: (1) gradients have to be discretized using manually selected bins, and (2) high-dimensional gradients in the PATE framework incur a high privacy cost, which requires dimensionality reduction techniques.
Luo et al. (2021) leverage additional, public datasets to instill strong representations in large models, which are then adapted to private datasets at a minimal privacy cost. For the medical domain datasets, we train the models from scratch without using pre-trained models. In contrast to our large-scale medical domain and vision datasets, their method is applied to small-scale datasets, such as CIFAR-10, and for the standard single-label classification only.
Although there exist many differential privacy tree-based ensemble methods, including random forests, their non-private variants fall short of the SoTA performance achieved by deep neural networks on the vision tasks we consider. These methods are typically applied to tabular datasets (Fletcher & Islam, 2017; Bojarski et al., 2014; Xin et al., 2019). To approach the results achieved by deep neural networks, these works require the use of feature engineering (which incurs additional privacy loss) or public labeled data (which is a strong assumption that we do not use). For this reason, it is unlikely that these results will perform comparably to differentially private neural networks, so we limit our evaluation to neural networks. We remark that for the reasons above, DPSGD ensembling of neural networks is also not a viable approach for these tasks.

heading: F NORMS FOR CLIPPING
text: Using an `∞ norm bound does not achieve tighter RDP benefits because we cannot upper-bound the `2 norm of the mechanism’s outputs (since |x|∞ ≤ |x|2) as required to achieve an RDP benefit. This is analogous to why we achieved tighter RDP privacy loss bounds compared with Private kNN (Zhu et al., 2020): they use the `1 norm to bound the `2 norm from above, whereas we adapt the analysis to directly operate over the `2 norm. Note that we are required to bound the `2 norm because we use the Gaussian mechanism (that satisfies RDP for an `2 norm bound).
We carried out a theoretical analysis of the bounded noise mechanism from (Dagan & Kur, 2020) for the multi-label classification. The bounded noise in terms of `∞-norm has theoretical properties that could lower the probability of an incorrect prediction for a label. However, the method had a very limited practical application, and for standard multi-label datasets, such as Pascal VOC or CheXpert, the method performed much worse than the binary PATE per label. We removed the bounded noise mechanism from consideration and focused on the binary PATE per label that was performing very well in the empirical evaluation.

heading: G DATASETS AND MODEL ARCHITECTURES
text: We experiment on four multi-label datasets. First, we use the common computer vision multi-label dataset, Pascal VOC 2012. Three other of these datasets are privacy sensitive large-scale medical datasets that are commonly used in ML for healthcare: CheXpert (Irvin et al., 2019), MIMICCXR (Johnson et al., 2019) and PadChest (Bustos et al., 2020),. These medical datasets present a realistic and large-scale application for multi-label CaPC.
Pascal VOC 2012 contains 11, 540 images that are split into 5, 717 images for training and 5, 823 images for validation (Everingham et al., 2010). There are 20 classes of object labels (with their index in parentheses) – aeroplane (1), bicycle (2), bird (3), boat (4), bottle (5), bus (6), car (7), cat (8), chair (9), cow (10), dining table (11), dog (12), horse (13), motorbike (14), person (15), potted plant (16), sheep (17), sofa (18), train (19), and tv monitor (20). We use ResNet-50 model (He et al., 2016) that was pre-trained on ImageNet (Deng et al., 2009).
Medical datasets contain chest radiographs (X-ray) images. CheXpert (Irvin et al., 2019) has 224, 316 radiographs. MIMIC-CXR-JPG (Johnson et al., 2019) contains 377, 110, and PadChest (Bustos et al., 2020) has 160, 868. The goal in each dataset is to predict presence of pathologies. However, there are differences between pathology labels across these three datasets. X-ray images of CheXpert are annotated with 11 pathologies– Atelectasis, Cardiomegaly, Consolidation, Edema, Effusion, Enlarged Cardiomediastinum, Fracture, Lung Lesion, Lung Opacity, Pneumonia and Pneumothorax. MIMIC-CXR-JPG includes 11 pathologies– Enlarged Cardiomediastinum, Cardiomegaly, Lung Opacity, Lung Lesion, Edema, Consolidation, Pneumonia, Atelectasis, Pneumothorax, Pleural Effusion, Pleural Other, Fracture, Support Devices. PadChest includes 15 pathologies– Atelectasis, Cardiomegaly, Consolidation, Edema, Effusion, Emphysema, Fibrosis, Fracture, Hernia, Infiltration, Mass, Nodule, Pleural_Thickening, Pneumonia and Pneumothorax.
The pathology and its code (in parenthesis) is as follows: Atelectasis (AT), Cardiomegaly (CA), Consolidation (CO), Edema (ED), Effusion (EF), Emphysema (EM), Enlarged Cardiomediastinum (EN), Fibrosis (FI), Fracture (FR), Hernia (HE), Infiltration (IN), Lung Lesion (LL), Lung Opacity (LO), Mass (MA), Nodule (MO), Pleural_Thickening (PT), Pneumonia (PN), Pneumothorax (PX).
All datasets obtain labels from associated reports. Both CheXpert and MIMIC-CXR-JPG use the CheXpert labelling system, which is a rule based approach. PadChest obtains reports annotated by trained radiologists, then trains an attention-based recurrent neural network to predict on these annotations, and labels the remaining data. On all three datasets, we train a DenseNet-121 (Huang et al., 2017) model and filter only frontal images (AP and PA). The main difference between our setup and the one from Cohen et al. (2020) is that we use both frontal views AP and PA, while the cited work uses only one of the frontal views, thus either AP and PA.
The label distribution for each multi-label dataset (Pascal VOC, CheXpert, MIMIC-CXR, and PadChest) is presented in Figure 6. The label distribution for medical datasets is more unbalanced than for Pascal VOC, due to prevalence or rarity of certain diseases.

heading: H EXPERIMENTAL DETAILS
text: Our experiments were performed on machines with Intel®Xeon®Silver 4210 processor, 128 GB of RAM, and four NVIDIA GeForce RTX 2080 graphics cards, running Ubuntu 18.04.
We train ResNet-50 (He et al., 2016) on the Pascal VOC 2012 (Everingham et al., 2010) dataset by minimizing multi-label soft margin loss function in 1000 epochs. As an optimiser, we use SGD with learning rate and weight decay of 0.001 and 1e− 4, respectively. In case of 50 Pascal VOC models, we split the 5, 717 images of the training set to 50 private training sets in order to train 50 teacher models.
We train the medical datasets CheXpert, MIMIC-CXR, and PadChest using the standard DenseNet121 architecture trained for 100 epochs, with weight decay of 1e − 5, Adam optimizer (learning rate=0.001) with the adam_amsgrad paremeter set. We reduce the learning rate when it plateaus, batch size is 64. The loss type is BCE (Binary Cross Entropy) with logits, and probability threshold is adjusted per label (where the standard value is 0.5). For 50 CheXpert models, each model is trained on 3750 private train samples. PadChest uses 9223 private samples per each of 10 teacher models.
Regarding the metrics, balanced accuracy (BAC), area under the curve (AUC), and mean average precision are common metrics used to asses performance of the multi-label classification (Ben-Baruch et al., 2021). Note that because we are in a sparse-hot multi-label setting (where a sample has many 0’s - negative labels) the accuracy is not a preferred metric because a model can achieve high accuracy by returning all 0’s; we include the accuracy metric for completeness.
For our CaPC experiments, we sample uniformly, without replacement, data points from the respective training data distribution to create disjoint partitions Di of equal size for each party i. We use 50 total parties for Pascal VOC, CheXpert, and MIMIC-CXR, as well as 10 for PadChest; this choice depended on the sizes of the datasets and the performance of the models on the resulting partitioned data (here, we ensured no single model dropped below 60% BAC). We use Q = 3 querying parties and sample (without replacement) at least 1000 data points from the test distribution to form the unlabeled set for each querying party. We leave at least 1000 held-out data points for evaluating models. We first train party i’s model on their private data Di, then simulate multi-label
CaPC learning by having each querying party complete the protocol with all other parties as answering parties. Using the new labelled data provided by multi-label CaPC, we retrain each querying party’s model on their original data Di plus the new labelled data. We average metrics over at least 3 runs with each using a different random seed.

heading: I ADDITIONAL EXPERIMENTS

heading: I.1 MULTI-LABEL PATE: BINARY VS POWERSET
text: We compare Binary vs Powerset multi-label PATE in Tables 5, 8, and Figure 7. For each data point, we check how the performance of the Binary and Powerset PATE degrades as we increase the scale of Gaussian noise σGNMax, and select the scale that preserves high values of the metrics (ACC, BAC, AUC, MAP), with maximum performance drop by a few percentage points - we select this threshold arbitrarily. We align both Binary and Powerset methods according to the performance metrics. For a given values of the metrics, we find the σGNMax starting from 1 to the highest possible value that gives performance above the chosen threshold and allows us to answer maximum number of queries. For example, in Figure 8, we select σGNMax = 4 for Powerset PATE and σGNMax = 11 for Binary PATE, while the values of the metrics are ACC=.95, AUC=.66, and MAP = .37. For CheXpert, we set σGNMax = 5 for Powerset PATE and σGNMax = 20 for Binary PATE, while the values of the metrics are ACC=.71, AUC=.68, and MAP = .45.
I.2 POWERSET WITH τ -VOTING
We present how to incorporate τ -voting into the Powerset method. A given teacher is allowed to set up to τ positive labels for a given query sample. This approach limits the number of positive classes from C = 2k to C = ( k 0 ) + ( k 1 ) + · · · + ( k τ ) classes. Since we have fewer classes: (1) it increases the possibility of achieving a consensus between teachers (a higher gap between max and runner-up numbers of votes can be achieved), (2) the data independent bound is lower (computed as:
1− (1/C)), and (3) the method has higher performance (faster run-time). On the other hand, it does not lower the sensitivity of the Powerset mechanism because changing one of the teachers potentially decreases the vote count from one class and increase it in another one. Thus, the sensitivity remains 2.
Intuitively, up to τ positive labels could be selected based on the confidence of the positive value for a label, where we would choose the top τ labels with the highest confidence of being positive. However, given that most deep multi-label models use independent predictive heads (i.e., a separate sigmoid
Pascal VOC
CheXpert
activation per output label), naively comparing these values may not lead to the best performance. Thus, no clear notion of what the desired subset is in the case that > τ candidates are present.
For the Pascal VOC dataset, the same threshold of 0.5 probability is used per label, so the prediction heads for each label are aligned. For the CheXpert dataset, different probability thresholds are set per label, so the problem of deciding which of the labels should remain positive (if there are more positive labels than the max τ of positive labels) is difficult to resolve. This would likely require some form of domain knowledge.
For the original train set of the Pascal VOC dataset (with 5823 samples), the average number of positive labels per example is 1.52, with 20 total labels. More detailed statistics on the train set are presented in Table 7.
When the τ -voting is applied with the fixed privacy budget, we are able to answer more queries, while the performance metrics (e.g., accuracy) remain comparable. When the initial number of labels is set to k = 5, for τ = 2 the number of classes is 16 instead of 32 (τ = 5, which is equivalent to no clipping) and we are able to answer 5% queries more, for τ = 1, we have only 6 classes and almost 14% more answered queries. For τ = 5 there is only 1 more class than for τ = 4 and we observe a very small difference in the number of answered queries (namely 8). The number of answered queries using the Binary method is still higher than with Powerset even when τ = 1 (the number of classes is C = k + 1).

heading: I.3 DPSGD VS PATE ON CHEXPERT
text: There are a few key differences between PATE and DPSGD in a direct comparison. DPSGD requires centralization of data whereas PATE does not, while only additionally assuming some pool of public unlabeled samples to be used for labeling by teachers and for the semi-supervised learning (e.g., with MixMatch). The centralization of data is a strong requirement for DPSGD which is often not applicable to the tasks we consider (e.g., medical or financial data) because these institutions may be blocked from centralizing data due to regulations.
The Adaptive DPSGD method from Zhang et al. (2021) does not publish the code, thus the following is our best effort. The results presented below come from Figure 5 in Zhang et al. (2021). Similar to their experimental setup, we use DenseNet-121 pre-trained on ImageNet and fine-tune only the last fully connected layer while keeping all the other (convolutional) layers fixed. Across all of the experiments, we use ε = 8 as the privacy budget. We use the whole CheXpert test set, and here report results for δ = 10−4. To evaluate the performance of the models, we use the CheXpert test set (from
the valid.csv file in CheXpert-v1.0-small). As shown in the Table 9, in this setting, we outperform the Adaptive DPSGD.
We use the following parameters to obtain our results for the Binary multi-label PATE:
sigma gnmax = 7.0 sigma threshold = 0 threshold = 0 method = multilabel batch size = 20 learning rate = 0.001 epochs = 100 weight decay = 0 X-ray views = [’AP’, ’PA’] Multilabel_prob_threshold = [0.53, 0.5, 0.18, 0.56, 0.56]

heading: I.3.1 CDF OF GAPS
text: We show the Cumulative Distribution Function (CDF) for the gaps in Figure 9. We observe that the ensemble of teachers is confident about the answers for most labels for the Binary PATE and there are very small gaps for most queries when using Powerset PATE, which shows much lower confidence of teachers in choosing the same (super) classes, which are created from aggregated label predictions (the values of the labels are collected in a binary vector that constitutes a class).

heading: I.3.2 GAPS AND PERFORMANCE METRICS
text: With more labels for the Powerset method, we have more possible classes and the votes become more spread out. This can be measured by the gap, which is the difference between the maximum number
of votes per class and the runner-up (the number of votes for the next class with the highest number of votes). In Figures 10 and 11, we plot the average gap (on the y-axis) for the test set across all histograms for a given number of labels (presented on the x-axis). We compare the Powerset PATE (denoted as Powerset) vs the Binary PATE per label (denoted as Binary). The average gap between votes is comparable for different number of labels of Binary PATE since this method considers each label separately and there are always only two classes. The average gap between votes decreases very fast for Powerset because of the exponential growth of number of classes with more labels considered. Additionally, the performance metrics: acc (accuracy), bac (balanced accuracy), aread under the curve (auc), and mean average precision (map), are also higher for the Binary than Powerset method in case of CheXpert dataset and comparable for Pascal VOC.
Pascal VOC

heading: I.4 GENERAL TUNING OF HYPER-PARAMETERS
text: We set the hyper-parameters by considering the utility and privacy of our proposed method. Based on Lemma 3.2, we minimize the privacy budget by maximizing the σ parameter of the Gaussian noise and minimizing the τ parameters. In Figure 1, we tune the value of the σ parameter of the Gaussian noise based on the utility metrics: accuracy (ACC), balanced accuracy (BAC), mean average precision (MAP). We set σ as 9, 10, and 7 for Pascal VOC, MIMIC, and CheXpert datasets, respectively. This allows us to answer many queries with high performance in terms of ACC, BAC, and MAP.
Similarly, we tune the τ values for `2 norm in Figure 12 and for `1 norm in Figure 13.
Regarding the values of parameters σG, T , and σT , we follow the original work on PATE (Papernot et al., 2017) and perform a grid search over a range of plausible values for each of the hyperparameters.

heading: CheXpert
text: The detailed analysis of tuning the hyper-parameters are for: τ -s in Section I.5, σG in Section I.6, PATE’s thresholding (T , and σT ) in Section I.7, and probability thresholds in Section I.10.
I.5 TUNING τ -CLIPPING
We determine the minimum value of τ for clipping in `2 and `1 norms for each dataset so that the performance as measured by accuracy, BAC, AUC, and mAP, is preserved. We present the analysis in Figures 12 and 13.
I.6 TUNING σGNMax
We determine how much of the privacy noise, expressed as the scale of Gaussian noise σ, can be added so that the performance as measured by accuracy, BAC, AUC, and mAP, is preserved. The experiment is run using the binary PATE per label and presented in Figure 14.

heading: I.7 TUNING PATE
text: There are three parameters to tune: the differential privacy Gaussian noise standard deviation σG, the count threshold T , and the thresholding Gaussian noise standard deviation σT . We first disable the thresholding (σT and T ) and tune σG to achieve a high BAC of the noisy ensemble while maximizing the number of answered queries. In Figure 19 we tune the σG parameter from PATE for different configurations of retraining. The goal is to maintain a high accuracy while selecting σG with high value so that as many queries as possible are answered. After tuning σG, we grid-search σT and T . Thresholding is useful if we want to add a relatively small amount of Gaussian noise (σG) in the noisy max. For example, for σG = 7 and 50 teacher models trained on CheXpert, the maximum
number of labels answered without thresholding is 737 (67 queries) with a BAC above 0.69. With thresholding, e.g., at T = 50 and σT = 30, we can answer an average of 756 labels, up to 834. A well tuned threshold can also help reduce σG, which is the major influencing factor on the final BA of the noisy ensemble. Note that tuning the threshold benefits from a confident ensemble: here, we find the ensemble is often confident with a positive-negative vote difference of 40 of max 49. Also note that the BAC can be higher on easier queries.

heading: I.8 COMPARE DIFFERENT METHODS
text: In Figure 15, we directly compare the Binary PATE (denoted as PATE), τ -PATE, and clipping in `2 and `1 norms. The error regions are for the three querying parties.
I.9 VARYING PRIVACY BUDGET
In Table 12, we show the performance of the retrained models when using CaPC with various privacy budgets ε. In Figure 16 we show the detailed per label change in BAC for the retraining with privacy budget ε = 10. We observe an increase in average BA by around 0.03 after retraining when the privacy budget is set to ε = 10. We present detailed analysis of the Binary PATE performance in Table 10 on the Pascal VOC dataset when selecting the privacy budget ε in the range from 1 to 20.
We also compare the performance after re-training with and without the (confidence) thresholding mechanism used in PATE (represented by σT and threshold T parameters). We observe that in case of the medical datasets, there can be a slightly higher increase of the metrics (accuracy, BAC, AUC, mAP), when we do not perform the thresholding. For example, for the CheXpert dataset, when thresholding is not used, the improvement is higher by about one percentage point across all metrics when compared to the option with thresholding. For PadChest, such increase is for AUC and mAP, for BAC we see a drop by one percentage point, and there is no difference in terms of accuracy (remains at the level of about 0.86). This requires further investigation. Intuitively, we observe that the metrics
can increase substantially with thresholding for the labels (pathologies) that are easy to classify. However, the most difficult to predict pathologies are left without answer and no improvement is made on them. On the other hand, without thresholding, we have to answer all labels and correct predictions on the hardest labels can produce substantial improvement in the classification of these hard labels.

heading: I.10 TUNING PROBABILITY THRESHOLD
text: We tune the global (applied to all labels) probability threshold γ that determines if a given probability denotes positive (P > γ), or a negative (P ≤ γ) vote. The best global γ for the 50 models trained on the CheXpert dataset is 0.32 with the balanced accuracy of 0.702 and the µ value of 0.45, where µ is the average probability of predictions after applying the element-wise sigmoid function to the logits.
We also tune the γ threshold per label for CheXpert. We find the following probability thresholds per label using the validation set on the ensemble: 0.53, 0.5, 0.18, 0.56, 0.56, 0.21, 0.23, 0.46, 0.7, 0.2, 0.32. Next, we select the 3 teacher models with the lowest BAC and retrain them with CaPC. The average metrics BAC, AUC, and mAP
before retraining are 0.63, 0.70, 0.53, and after retraining, we observe a significant improvement to 0.68, 0.75, 0.58, respectively. Thus, the value for each metric increases by around 0.05. We find the biggest performance improvement for these weakest models after learning from better teachers and retraining. We present detailed results per label and for BA as well as AUC metrics in Figure 18.

heading: I.11 CROSS-DOMAIN RETRAINING
text: In real-world healthcare scenarios, there are often rare diseases that may be difficult to accurately model with machine learning. Even coalitions of hospitals sharing similar data distributions of the same domain may not see benefits, due to poor aggregate performance. However, cross-domain collaboration through multi-label CaPC can help improve performance in these cases. The hospital
annotation discrepancies may pose barriers: here, we simulate this by the different X-ray image labels between PadChest and CheXpert (see Supplement Section G).
To overcome this, we take the union of labels between the medical datasets and follow the experimental setup of Cohen et al. (2020). We observe poor performing models on the PadChest dataset, with a low average performance of BAC = 0.57. Because of this, the benefits of multi-label CaPC within this coalition of hospitals are limited, since the ensemble is only marginally better. However, if this group of hospitals collaborated with another from a different but related domain, here represented by CheXpert, they may be able to see additional benefits. The models trained on this dataset achieve a higher BA (particularly on the first 5 shared pathologies as presented in Figure 17). Thus, the ensemble of all models engage in multi-label CaPC and the models trained on CheXpert act as answering parties to provide labels for querying parties from PadChest. Using a σG = 9, T = 50, and σT = 30, we observe a higher BAC on all of those 5 pathologies, where we do not see a significant decrease on the other pathologies. Thus, multi-label CaPC provided benefits for the PadChest models in this cross-domain scenario.

heading: J THE CAPC PROTOCOL
text: The CaPC protocol is as follows:
1. Private inference is run for each answering party. (a) Compute logits. A querying party (or, student) sends an encrypted query (unlabeled x)
to each answering party (or, teacher). The teachers run the private inference and upon completion return encrypted logits: Enc(r).
(b) Secret sharing between the answering and querying parties. Each answering party generates a random vector r̂ and subtracts it from the vector of logits r. Then, each answering party sends the encrypted result: Enc(r − r̂) to the querying party who decrypts the message to obtain (r − r̂).
(c) One-hot encoding of the logits. The answering parties provide r̂ and the querying party provides (r− r̂) to run Yao’s garbled circuit protocol (Yao, 1986b). They compute the argmax of the logits and transform them into one-hot representations. Each one-hot vector is split into shares s and ŝ. The s share is returned to the querying party and the ŝ share is sent to the Privacy Guardian (PG). The PG is a common facilitator in these setups, i.e., a trusted third-party, and is honest-but-curious. The sum of shares s and ŝ is the one-hot encoding of the predicted label.
2. DP mechanism. This step follows PATE to provide privacy for each teacher’s data. In PATE, Gaussian noise is added to the argmax. In CaPC, Gaussian noise is added to the sum of ŝ shares by the PG, after being collected from each of the answering parties.
3. Noisy argmax to compute the final label. The PG and the querying party run Yao’s garbled circuit to sum the noisy ŝ values with the s values. The result is a noisy histogram representing the number of votes for each class. The argmax of this determines which class received the maximum number of votes. This class is returned to the querying party as the final predicted label.
In CaPC learning Choquette-Choo et al. (2021), the main tool for confidentiality is secure multi-party computation (MPC) (Yao, 1986a) and homomorphic encryption. MPC is used when distrusting parties want to jointly evaluate a function on their input without revealing anything beyond the output. The MPC protocols can be divided into two main classes: (1) generic protocols, which compute any function with the Malkhi et al. (2004) security goal, and (2) specialized protocols, which are used to compute selected functions, for instance, the private set intersection (Pinkas et al., 2020) or secure machine learning (Mohassel & Zhang, 2017). Even though the specialized protocols are less general, they are more efficient in terms of the execution time. Protocols in both categories use similar cryptographic building blocks, including (fully) homomorphic encryption (Gentry, 2009), secret sharing (Shamir, 1979), oblivious transfer (Rabin, 2005), garbled circuits (Yao, 1986a). Private inference can be computed in many ways and is a component of the CaPC protocol that directly scales with improvements in these techniques: CaPC used the HE-transformer library that uses both MPC as well as the homomorphic encryption but the private inference library can be immediately swapped with others.
Algorithm 1 CaPC protocol Input: Querying Party QP. x - query (unlabeled data item) from QP. Answering Parties AP1,...,APn with ML models fi(x) = y, where i ∈ {1, ..., n}, and y is the vector of logits. Privacy Guardian PG. Output: label ` for query x (QP receives ` for its x).
1: QP encrypts x to Enc(x). 2: QP sends Enc(x) to AP1,...,APn. 3: for all APi do 4: Enc(r)i ← fi(Enc(x)) 5: Generate random r̂i 6: Enc(ri − r̂i)← Enc(ri)− r̂i . Enabled by Homomorphic Encryption 7: Send Enc(ri − r̂i) to QP 8: for all APi and QP do . 2PC (Secure 2-Party Computation) between each AP and the QP 9: QP decrypts ri − r̂i ← Decrypt(Enc(ri − r̂i)) 10: QP sends ri − r̂i to 2PC 11: APi sends r̂i 2PC 12: 2PC: ri ← (ri − r̂i) + (r̂i) 13: 2PC: one− hoti ← argmax(ri) 14: 2PC: ŝi + s← one− hoti . Secret Sharing 15: APi receives ŝi from 2PC 16: QP receives si from 2PC 17: for all APi do 18: Send ŝi to PG. 19: QP: S ← ∑n i=1 si 20: QP sends S to 2PC 21: PG: Ŝ ← ∑n i=1 ŝi 22: PG: Generate Gaussian noise n̂← N(0, σG) 23: PG sends Ŝ and n̂ to 2PC 24: 2PC: ĥ← S + Ŝ + n̂ . Noisy histogram ĥ

heading: 25: 2PC: `← argmax(ĥ)
text: 26: 2PC sends ` to QP

heading: K ALGORITHMS FOR THE MULTI-LABEL CLASSIFICATION
text: Algorithm 2 Multi-label classification with τ -clipping in `2-norm and with the Confident GNMax. Input: Data point x, clipping threshold τ2, Gaussian noise scale σG, Gaussian noise scale for Confident GNMax σT , n teachers, each with model fj(x) ∈ {0, 1}k, where j ∈ [n] Output: Aggregated vector V with Vj = 1 if returned label/feature present, otherwise Vj = 0.
1: for all teachers j ∈ [n] do 2: vj ← min(1, τ2‖fj(x)‖2 )fj(x) . τ -clipping in `1 norm 3: V 1 = ∑n j=1 vj . Number of positive votes per label 4: V 0 = n− V 1 5: for all labels i ∈ [k] do 6: if max{V 0i , V 1i }+N (0, σT ) < T then 7: Vi =⊥ . Confident-GNMax 8: else 9: V 0i ← V 0i +N (0, σG) . Add Gaussian noise for privacy protection 10: V 1i ← V 1i +N (0, σG) 11: if V 1i > V 0i then . Decide on the output vote 12: Vi = 1 13: else

heading: 14: Vi = 0
text: Algorithm 3 Multi-label classification with τ -clipping in `1-norm from Private kNN by Zhu et al. (2020). Input: Data point x, clipping threshold τ1, Gaussian noise scale σG, n teachers, each with model fj(x) ∈ {0, 1}k, where j ∈ [n]. Output: Aggregated vector V ∈ {0, 1}k with Vi = 1 if returned label present, otherwise Vi = 0, where i ∈ [k].
1: for all teachers j ∈ [n] do 2: vj ← min(1, τ1‖fj(x)‖1 )fj(x) . τ -clipping in `1 norm 3: V 1 = ∑n j=1 vj . Number of positive votes per label 4: V 0 = n− V 1 5: V 0 ← V 0 +N (0, σG) . Add Gaussian noise for privacy protection 6: V 1 ← V 1 +N (0, σG) 7: for all labels i ∈ [k] do 8: if V 1i > V 0i then . Decide on the output vote 9: Vi = 1
10: else 11: Vi = 0

heading: L DATA-DEPENDENT PRIVACY ANALYSIS
text: Our binary voting mechanism does leverage both the smooth sensitivity and propose-test-release methods. For example, the Confident GNMax (proposed by Papernot et al. (2018)) is a form of the propose-test-release method described in Section 3.2 in (Vadhan, 2017).
First explored by Cormode et al. (2012), differential privacy guarantees can be data-dependent. These guarantees can lead to better utility with a long history, with several works using them (Cormode et al., 2012; Papernot et al., 2017; 2018; Chowdhury et al., 2020). One main caveat is that the released epsilon score must now also be noised because it is itself a function of the data. Papernot et al. (2018) provide a way to do this via the smooth sensitivity (Section B in Appendix). Indeed our data-dependent differential privacy guarantees are formally proven and are based on the following intuition. Take the exponential mechanism which gives a uniform privacy guarantee. For instance, when the top score and the second score are very close, applying the exponential mechanism to this data there is a nearly uniform chance of picking either coordinate. However, for some inputs, the utility can be very strong—when the top score is much higher than the second score, then this mechanism is exponentially more likely to pick the top score than the second. This does not require local sensitivity of stability based methods, but is rather derived from the likelihood of picking either coordinate for this mechanism given the gap in the scores.

Review summaries:
This paper considers differentially private multi-winner voting. This problem is a generalization of single-winner voting, which is widely used in PATE type private semi-supervised learning. The authors give three private mechanisms and perform empirical comparisons on multi-label semi-supervised learning settings.  Specifically, when there is no total votes constraint on each ballot, the binary mechanism performs report noisy argmax for each candidate. When there is a total votes constraint, the tau mechanism performs l2 clipping first and then performs report noisy argmax for each candidate as the binary mechanism. The powerset mechanism converts the multi-label problem into a single label problem and performs regular report noisy argmax. 

This paper considers the design of differentially private multi-label mechanisms. In particular, the authors employ multi-winner voting protocols to existing differentially private single-label learning algorithms e.g. PATE. They consider three multi-label voting protocols -- binary voting, $\tau$-voting and powerset voting.   Binary voting works by independently applying majority voting on each coordinate. It is obvious that such an aggregation mechanism has does not provide a better privacy guarantee than $k$ applications of binary voting. The privacy guarantee can be improved when the coordinates are dependent. This motivates the authors to consider $\tau$-voting where the $\ell_2$-norm of each ballot is bounded by $\tau$. Finally, in the powerset voting, the voting is done over the universe of all subsets of the alternatives i.e. $2^k$ alternatives.  The authors make two important observations through experiments. First, when there is high consensus and $\sigma_G \rightarrow 0$, binary voting performs best. On the other hand, $\tau$-voting outperforms with lower consensus and larger values of $\sigma_G$. Second, even in centralized setting, multi-label methods outperform existing benchmarks.

The authors study differentially private multi-winner voting, which is designed for multi-label learning subject to a privacy constraint meant to limit information leakage about training data to an adversary. They propose three mechanisms: Binary, which essentially runs an existing differentially-private election for each label independently, \tau voting, which works with votes that have bounded \ell_2 norm, and powerset voting, which explicitly encodes each possible subset of winners as an alternative in an election and then votes over them. They show that Binary voting (the naive approach) generally outperforms powerset voting as long as there aren’t strong correlations between votes. Lastly, they show that they can use these multi-winner DP techniques to a extend single-label technique, PATE, and empirically demonstrate the effectiveness of their approach.

Private multi-winner voting is the task of revealing k-hot binary vectors that satisfy a bounded differential privacy guarantee. They propose three new mechanisms. 1. Binary voting operates independently per label through composition. 2. \tau voting bounds votes optimally in their l2 norm.  3. Powerset voting operates over the entire binary vector by viewing the possible outcomes as a power set. They prove that Powerset voting requires strong correlations between labels to outperform Binary voting.  They also use these mechanisms to enable privacy-preserving multi-label learning. They empirically compare techniques with DPSGD on large real-world healthcare data and standard multi-label benchmarks. Their techniques outperform all others in the centralized setting, and show that mechanisms can be used to collaboratively improve models in a multi-site (distributed) setting.