Private Multi-Winner Voting For Machine Learning
Authors: Adam Dziedzic
Christopher A. Choquette-Choo
Natalie Dullerud
Vinith Menon Suriyakumar
Ali Shahin Shamsabadi
Muhammad Ahmad Kaleem
Somesh Jha
Nicolas Papernot
Xiao Wang
Venue: ICLR 2022 Submitted (2022)
Keywords: multi-label
privacy
voting
confidentiality
differential privacy
disributed collaboration
collaboration

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, $\tau$, and Powerset voting. Binary voting operates independently per label through composition. $\tau$ voting bounds votes optimally in their $\ell_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.

Under review as a conference paper at ICLR 2022
PRIVATE MULTI-WINNER VOTING FOR MACHINE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Private multi-winner voting is the task of revealing k-hot binary vectors that sat- isfy bounded differential privacy guarantee. This task has been understudied in the machine learning literature despite its prevalence in many domains such healthcare. We propose three new privacy-preserving multi-label mechanisms: Binary, 7, and Powerset voting. Binary voting operates independently per label through composition. voting bounds votes optimally in their lg 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 enable the canonical single-label technique: PATE. We empirically compare niques with DPSGD on large real-world healthcare data and standard multi-label benchmarks. We find that techniques outperform all others in the centralized setting. We enable multi-label CaPC and show that our mechanisms can used to collaboratively improve models in multi-site (distributed) setting.
multi-label learning by extending
tech-
INTRODUCTION
Differential privacy techniques for machine learning have predominantly focused on two types of mechanisms: for given query, release either noisy estimate using the Gaussian mechanism (Abadi) et al. 2016b) or the noisy arg max (Papernot et al., (017). These two mechanisms appeal well to single-label classification per input (a.k.a. multi-class classification), which is widely studied setting of supervised learning where 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 al. (017).
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 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 candidates. Though simple, we prove that it is optimal when there is lack of correlation among the outcomes of particular candidates. We then derive tighter data- inteainndeendenn privacy bounds for multi-winner elections by considering the situation where each voter is limited in their (4z) votes for candidates, which call t voting. By casting multi-winner elections to an analogous task of single-winne elections, we create third mechanism termed Powerset voting, which reveals the result for all k candidates jointly.

---

Under review as a conference paper at ICLR 2022
By replacing the noisy arg max mechanism used in (single-label) PATE, create multi-label PATE which enables multi-label
classification with semi cemi-supervised machine learning.
We empirically evaluate our algorithms 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 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 Chooquette Choo it al. (202T). 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: 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.
Binary voting,
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.
We enable multi-labed collaborative learning in the multi-site scenario by integrating our mecha- nisms into CaPC. We find that multi-label CaPC significantly improves model performance.
BACKGROUND
2.1 DIFFERENTIAL PRIVACY FOR MACHINE LEARNING
Differential Privacy (DP) is canonical framework for measuring the privacy leakage of a randomized algorithm (Doork 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 's outputs.
Definition 1 (Differential Privacy). A randomized mechanism M with domain 'D and range R satisfies (e, -ddifferrenti privacy if for any subset S C R. and any adjacent datasets d, d' E DD i.e. ||d - d'
the following inequality holds: Pr [M(d) E S] S PF E 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 generalization of pure, O-DP we convert and report final budgets using OP.)
Definition 2. Rényi Differential Privacy (Mironov 2017/. We say that a mechanism M is (A, c)- RDP with order X (1, 00) for all neighboring datasets X, X':
( >"
(M)X) x
1 Dx(M(X)IIM(X)) x log Fo-MiX)
SE
It is convenient to consider RDP in its functional form as (A), which is the RDP e of mechanism
M at order X. We now state the result which our privacy analysis builds on.
Lemma 2.1. RDP-Gaussian mechanism (for a single-label setting) MMrronvv 2017). Let f x X R have bounded lg sensitivity for any two neighboring datasets X, X', L.e f(X)) A2. The Gaussian mechanism. M(X) = f(X) + +N(0,02) obeys RDP with (M)
Ad
2
Another notable advantage of RDP over (s, d)-DP is that it composes naturally. This will be helpful when analyzing approach which repeatedly applies the same private mechanism to dataset.
Lemma 2.2. EDP-Composition (Mironov 2017, Let mechanism M (M, MM) where M, can potentially depend on outputs of M1,.... Mi-1. 1. M obeys RDP with eM()) = Ei= (.).
2

---

Under review as a conference paper at ICLR 2022
2.2 PATE AND CAPC
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 dataset, PATE trains an ensemble of models from (disjoint) partitions of the dataset. Each model, called a teacher, is then asked to predict on test input and to vote for one class. Teacher votes are collected into a histogram where ny (z) indicates the number of teachers who voted for class i. To preserve privacy, PATE relies on the noisy argmax mechanism and only reveals noisy aggregate prediction (rather than revealing each prediction directly): argmax (n, + (OO, o&)}. where the variance of of the Gaussian controls the privacy loss of revealing this prediction. A student model learns in semi-supervised fashion by querying the ensemble of teachers for noisy labels, where each label incurs additional privacy loss. Loose fata--indeenndent guarantees are obtained through advaee composition (Dwork et al. 2014) and tighter fata-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: max, In } is compared against a noisy threshold also sampled from a Gaussian with variance o². PATE was created for single-label classification; our work extends the multi-label setting.
CaPC (Confidential and Private Collaboration) is a distributed collaborative learning framework that improves on PATE (Choquette-Choo et al. 202T 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. Confidentialityy 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 DP vote to the querying party. The detailed CaPC protocol can be found in Algorithm of Appendix [
2.3 PRIOR WORK ON MULTI-LABEL CLASSIFICATION
The closest our work is that of Zhu et al. 2220)), which provides a seivacy-preserviin nearest neighbors algorithm formulated using PATE. The nearest-neightt 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 publicly-available embedding model, which is used to project high-dimensional data onto a sufficiently- careeiientl-loowdmmeee -imeniienii 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 E ball, as done in Zhu et al. (2020). is not optimal-ginn that noise is sampled from Gaussian distribution. Instead, bounds by clipping votes to an & ball. The multi- voting problem can also be formulated as simultancously 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. (2)1 and applied to the multi-label setting by Zhang et al. (021)) to train small multi models (k= labels). We compare directly with their work and find that our methods perform better. We present 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.
obtain tighter
3 DIFFERENTIAL PRIVACY MECHANISMS FOR MULTI-WINNER ELECTION
multi-winnerr 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
3

---

Under review as a conference paper at ICLR 2022
in Elkind et al. (2017) and Faliszewski al. (2017). Here, we formally define multi winner system and propose DP mechanisms to facilitate the private release of the outcome of multi-winner election.
Compared singlo-winner elections, multi- elections more challenging for designing DP mechanism: instead of outputting a single scalar, multi- winner elections output a higher-dimmne dimensional vector and thus require more noise achieve the same level of privacy. DP mechanisms for single- winner voting have been well studied before, where the noisy arg max achieves minimal privacy loss due its tight sensitivity as result of information minimization (Dwork al. 2014). However, to the best of our knowledge, no prior work formally defines and analyzes DP mechanisms for election systems, hence we provide Definition 3 and the analysis. We provide formal deta-depnnd and data-indepen independent privacy loss bounds in Section
Definition 3. 0-multi-winnee election. Given set of n. voters, each with a ballot of k candidates (coordinates) b E {0. 1}* such that ||b]|2 I The outcome of multi-winnee election with threshold T is defined as
5(bi. bn) 2
i: Σ b
T E 10,
where T = and with the binary decision per label i, E}= byll] represents the number of positive votes.
3.1 DP MECHANISMS FOR Oc-MULTI- WINNER ELECTION
In an oo-multi- w election, each elector can vote for any candidates their ballots. We propose to decompose the muulti-winnee election into & separate single-winner elections, where we instead apply the well-studied noisy arg max separately each of the k single-winner elections. We call this Binary voting and state formally in Definition 4 below. For instances of ox-multi-winner elections, total privacy loss this mechanism follows Lemma 2.2 which can then tightly expressed as (c, DDD guarantee for chosen 8.
Definition 4 (DP (Noisy Argmax) Binary Voting Mechanism). For an oc- election, the binary voting mechanism is
n
Mo bn) e
+N(00 Eb,0+++0000 bo
T, 10.11*
where 7; n -2 bi] is the number of negative votes, which enables more noise to be added than when T = 3. 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-relent (Dwork & Lei 2009) shown in Algorithm of Appendix K Next, we show that Binary voting is optimal in the coordinate-indeeenne
setting.
Definition 5. A function f(X): R" + Rk is coordinate coordinate-indeeendee independennd if the i'th output coordinate of f. fo, is determined by unique subset P((X) of the input X, such that D = 0. P.(X) indexes (partitions) the input X uniquely for each i and returns the chosen subset; the chosen columns are dependent only 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 function P
- of max Definition 6. Sensitivity is the maximum deviation Apf (XxX":IIX-xIIIe)))
f's output for any adjacent pair of inputs X and X', i.e., have a Hamming distance ||X - 1X 1f on their rows (woork et al. 2014).
We use oo to emphasize that any vote b E {0, 13*h is allowed but tighter hound exists: |lbl|2 S Vic 80. Because the random mechanism differs minimally from the function, we the interchangeably.
4

---

Under review as a conference paper at ICLR 2022
Observe that output fa of Binary voting mechanism for coordinate i depends only the corresponding i-th coordinate the input ballot because we apply Binary voting independently to each candidate. For any mechanism f. A,f is maximized when the mechanism's 's output for each coordinate 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-independee indeeeeeeeeendeeeedeeent mechanism has sensitivity at least as large as the one of Binary voting mechanism because all k coordinates can be flipped. If' there were peardiinateddpedddeee (e.g., if the output coordinates 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 formally states our result. For more intuition, example functions, as well as the full proof, see Appendix and Proposition A.2 therein.
Proposition 3.1. For coordinate-independer independent multi-label function fmadts(X) R R², the & sensitivity A fmulti is equal to that of Binary voting applied per label and thus fmulti does not provide better privacy guarantee than k applications of Binary voling.
Note that Proposition 3.1 is exactly applicable to Binary voting if we assume candidate independence: then each candidate on all ballots only influences single winner. Analyzing these assumptions. we also readily see two scenarios when a Binary voting mechanism can be outperformed. The first scenario when any input coordinate X; explains > output (coordinate dependence). Proposi- tion A.4 of Appendix provess that for fmalts to achieve strictly lesser sensitivity, we necessarily require coordinate dependence. 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 (Dition the Appendix). The second case 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 & norm.
there is coordinate dependence, then there is some correlation
3.2 DP MECHANISMS FOR - MULTII-UNNNE ELECTION
When the average ballot does not vote for all & candidates. it is possible to obtain tighter privacy guarantees by considering the r-multi-winng election. Here, we bound the l norm of each ballot, limiting the individual impact of ballot. For this problem be meaningful, we assume T < Vl; 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 (DP r Voting Mechanism). Mechanism for T-Multi- Winner Election. For a r-multi- winner election the T Voting mechanism is
MM(b,....... ..... bn) bn) e
Σ o 2,11i+((00003))
m E (0,1)*, ,, A min(1, ||b,ll2 )6r
where we choose T: = n n En v,[i]. which represents the number of clipped negative votes. To analyze the privacy loss this new mechanism, we propose an extension of Lemma 2. to make applicable to this multi-voting task.
Lemma 3.2. RDP-Gaussian mechanism for a multi-label setting. Let f X + R² obey
[I((X) f(X) S A2 for neighboring datasets X, X'. The Gaussian mechanism M(X) f(X) + (0, obeys RDP with (A) 20
X13
We present proof in the Appendix C Next, we illustrate how our mechanism offers superior privacy guarantees to the similar ε 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 ε norm. We can see this by comparing the privacy loss of the two methods in the case of max possible change (as in Definition 6p: (AM Ard
AA? AAA 2( A2r?
- where in the first inequality we use the fact that ||ا||, < | Empirically, we confirm that F voting achieves a much tighter bound many multi-label datasets. Take 71 to represent clipping in the l norm and similarly for 72. On Pascal VOC, which has &o = 20 labels, we find that we can set T2 = 1.8 and T = 3.4 without deteriorating the utility of the mechanism (as measured using the balanced accuracy). In general,
2nt 2
5

---

Under review as a conference paper at ICLR 2022
select to be marginally larger than the average p-norm of labels in the training data. For example, there are on average fewer than positive labels out of 20 per query in the Pascal VOC dataset. Here, & norm clipping achieves >6x tighter privacy loss compared to Zhu et al. (2020) and the multi-voting of Section 3.1
3.3 CASTING co- OO-MULTI- WINNER ELECTIONS AS SINGLE- WINNER ELECTIONS
also possible to approximate multi-winner elections using dingle-winne voting mechanisms by encoding each of the 2 different outcomes as separate candidate for single-winner voting mechanism. We call this mechanism the powerset voting mechanism.
Definition 8 (DP Powerset Mechanism for Multi- Hulti-Winner Elections). Denote the Powersel operator as P()). For a oc-multi-winner election with ordered outcomes P([0, 1)a), where [P((0, =2"
} (0.1)*,
Mo ,.. bn) A arg max (((0, 11");
Σ LR P((o.1))) +
-1(0 -(00.)).
where 1 represents the indicator function. We first note that this is approximation of the Multi- Winner problem. The outcome of the mechanism may differ from the plurality per candidate if there no ballot cast with those votes. When 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 mulli-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 E [1, ..... 2* has some probability P; of being selected. Then, each of the ballots is an independent ball being thrown these bins. We can estimate the probability of each of the 2* single-winner outcomes. Doing if the likelihood of single i-th outcome is much higher than the rest, results in decreased privacy loss.
The second regime is when neither mechanism can leverage stronger data-dependent privacy guar- antees. When the distribution of multi-winner outcomes and single-winner outcomes approaches a uniform distribution, the best guarantec either 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 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 bellow for detailed analysis of the inteeindeeen and data-dependent privacy bounds of Binary voting and Powerset voting.
FROM PRIVATE ELECTIONS TO PRIVATE MULTI-LABEL CLASSIFICATION
In addition to the obvious application of making elections private, DP voting mechanisms play an machine learning. Notably, PATE adopted the noisy arg max
important role in 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-labe 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-winnel mechanisms. We then train a student model on the newly DP labeled data, preserving DP of the non- non-private teachers' training data. We call the corresponding forms Binary PATE, pate, and Powerset PATE.

---

Under review as a conference paper at ICLR 2022
Pascal
CheXPert
MIMIC-CXR
PadChest
1.0
Valie of metrio
0.8
0.6
0.4
ACC
0.2
BAC
0.0
of answered queries
1000
400
Binary PATE
800
Binary PATE-DI
300
600
L2-DI
1.PATE
200
400
200
100
10 20
10 20
10 20
0.0 2.5
5.0
7.5 10.0
0 (Gaussian noise scale)
or (Gaussian noise scale)
a (Gaussian noise scale)
a (Gaussian noise scale)
Figure I: With sufficient consensus, the best query-utility tradeoff obtained lies in a regime of OG where the data-dependent bound is used. In the 1st row, we maximize the aG of PATE while maintaining sufficiently high values of the performance metrics. The chosen values for (ag. T) are 9, 1.8 for Pascal VOC, 10,3 3 for MIMIC-CRR, and 7, 2.8 for CheXPert and 2.7 PadChest. When there is lack of consensus (on PadChest), we see that the data-independent & (L2-DI) mechanism bound outperforms all others. For a well chosen т, there is little-to-no impact on the consensus of the data data-dependent regime (c.f. Binary PATE and PATE which leverage the data-dependent bound when it reduces privacy loss). Because of this, T PATE achieves a competitive query-utility tradcoff. See Figure 14 in Appendix 1.5 for tuning of Binary PATE an oo-Winner Election.
Pasca VOC
CheXpert
NIHIC
PadChest
1.0
0.9
you Hash
0.8
677
Al CA
AI
PM
CACUHDSFEM FI-E MANOPI
Label
label
Label
Label
Figure 2: Using CaPC to improve model performance. Dashed lines represent mean balanced accuracy (BAC). We retrain a given model using additional data labelled by all other models from the same ensemble. We observe a mean increase of BAC by 2.0 percentage points on CheXpert.
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 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). absence of this empirical observation, when the noisy arg max mechanism satisfies E (A)-RDP, our Binary voting and Binary PATE algorithm achieves a data-independent bound of Σ (A);, r-voting and PATE of Xr" and Powerset voting and Powerset PATE of (A), all per election (query). Note that 7 PATÉ also leverages data-dependent analysis as with Binary PATE, but with the additional clipping of votes.
5 EXPERIMENTAL EVALUATION
We carry out the evaluation on three medical datasets CheXpert (Irvin et al.) 2019). MIMIC- CXR (Johnson et al.) 2219), 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) Hann & Till 2001). and (4) mean average precision (mAP). We use DenseNet-121 121 (Huang et al.) 2017) for the medical datasets and ResNet-50 (He et al. 2016) for the vision dataset. See Supplement Section for dataset and model descriptions. We experiment with
7

---

Under review as a conference paper at ICLR 2022
Table I: Model improvements through retraining with multi-label CaPC
# OF MODELS
DATASET
STATE
PB (s)
ACC
BAC
AUC
MAP
INITIAL
.97
.85
.97
.85
50
BEFORE CAPC
.931.02
.59..01
.88201
.54..01
PASCAL VOC
AFTER CAPC
.941.01
.621.01
.88.01
.54..01
50
AFTER CAPC
.94+.01
.64+.01
.89-001
.55+.00
INITIAL
.79
.78
.86
.72
CHEXPERT
50
BEFORE CAPC
.771.06
.661.02
.752.02
.581.02
50
AFTER CAPC
.76+.07
.69t.01
.77=.01
.59t.01
INITIAL
.90
.74
.84
.51
MIMIC
50
BEFORE CAPC
884.07
.631.03
.781.03
.431.02
50
AFTER CAPC
20
.851.05
.641.01
.79_.01
.451.03
INITIAL
.86
.79
.90
PADCHEST
10
BEFORE CAPC
90.1.01
.641.01
.792.01
.661.01
10
AFTER CAPC
20
.881.01
.641.00
.75
.141.01
E 8 for 5 labels on CheXpert (see Appendix [.3
10 for predictions on PascalVOC, 20 for
11 labels on CheXpert or MIMIC, and also E for 15 labels on CheXpert (see also Section I.9)
5.1 ANALYZING THE QUERY-UTILIT TRADEOFF IN PATE
In comparing how the privacy parameter dg impacts the query-utility tradeoff of each mechanism, under fixed E 20 across all datasets, we find that under high consensus Binary voting performs best and under lower consensus T voling performs best. In Figure [ we compare each multi-winner election mechanism used in PATE and find that each mechanism has range of ag where performs best. In particular, as OG - O, no queries can be answered by any mechanism due to a lack of noise satisfy the chosen For sufficiently small og and with suitable consensus amongst voters, which is the case for Pascal VOC, CheXPert, and MIMIC-XRR, we find the data deleedeennddnt analysis for Binary voting outperforms all others while remaining in regime of high- rerforerfrrmncce metrics. As og xc, the t voting mechanism outperforms all others, though in most cases at decrease in the performance metrics; however, on PadChest, this is the best bound. This can be explained only train 10 teachers before each individual model's accuracy
by the fact that on PadChest degrades too much. An important distinction is that 7 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 r we observe only marginal decrease in the number of queries answered and the performance metrics (c.f. Figure T with Figures [3] 12 and 14d1iinn in Appendix [T). Inspecting the tradeoff of Powerset PATE (see Figure 8 in Appendix [.I. we find that much lower noise can be tolerated before steep decline performance metries. Because of this, find that much fewer
queries can be answered (see Tables and MadSiin in Appendix I.1). Thus, we recommend 5 PATE as the de-facto mechanism.
5.2 PRIVATE CENTRALIZED LEARNING USING MULTI-LABEL PATE
We now show that even in the centralized setting, 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 single private model via DPSGD (Abadi et al.) 2016a). For our multi-label PATE we instead train 50 teachers each on separate disjoint partition of the centralized training set (and thus, with 1/50 number of samples compared with DPSGD and the non con-private model). We use these teacher models to privately train a student model using semi-supers supessueee 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 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. (021), and cannot directly leverage public unlabeled data. On the other hand, our PATE-based approaches leverage public pool of unlabeled samples that have noisy labels provided by the ensemble of teachers. The added noise protects the privacy the centralized training data. We then train the student the newly labeled samples. The student model, non-private
train single non-private model and
8

---

Under review as a conference paper at ICLR 2022
baseline, and DPSGD baseline were all pre-trained on ResNet-50 models. Observing Table we that our Binary PATE algorithm outperforms all other margin. Our Binary PATE does not use clipping the confident GNMax improvement so 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 Pow- erset PATE, falls short of the non-private model by a wide margin, indicating much room for improvement in multi-label srivacy-rreserving techniques- in par- ticular, in extreme multi-label settings, which we mo- tivate and expand on Appendix D We observe that Powerset PATE answers much fewer queries (leading to less training data for the student model) than Bi- nary 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).
techniques by a significant
Table 2: DPSGD vs PATE. Comparison be-
tween standard non-private model, DPSGD, Powerset and Binary multi-label PATE on the
Pascal VOC dataset in terms of utility,
METHOD
ACC
BAC
AUC
MAP
NON PRIVATE
.97
.85
.97
.85
DPSGD
.92
.50
.40
POWERSET PATE
.94
.58
.70
.29
BINARY PATE
.94
.62
.85
.57
5.3 MULTI-LABEL CAPC
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 multi- label 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 (Choqueetee et al. (2021) using the source code provided.
We train I model per participant separate distinct portions of the training set and then use multi- label CaPC to improve the performance of participants. Details are in Supplement Section H Observing Table [ improvement of considerable 5 percentage point increase on Pascal VOC and improvement across all other metrics. These improvements and MIMIC-XRR datasets; however, we observe some performance degradation on PadChest, likely because of the degraded vote utility compared the original training data. As 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.
we see that multi-label CaPC consistently improves the BAC, with the greatest
echoed in the larger and more wrivacy-sensitee
XheXpert
Inspecting Figure 2 we see that multi-label CaPC leads to significant improvements in low-sample, www-performance labels (c.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 multi- label 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 cdbpopulations-weeee Suriyakumar et al. (202I) show that differentially private can hurt perfor- mance 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 Appendix G
6 CONCLUSIONS
We address the need for privacy in the multi-label setting with three new multi-label voting mecha- nisms. 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- inteeedddeendnnt bounds for our T 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 -ftthe--rtttttt results for private learning in multi-label settings and demonstrate a need for further exploration to lessen the gap between private methods and non- non-private baselines.

---

Under review as a conference paper at ICLR 2022
7 ETHICS STATEMENT
Our work aims the protection of privacy and from this perspective, should benefit society. More specifically, work aims to provide private multi-label classification in collaborative setting and therefore any concerns of it being integrated into applications deemed harmful to humans or the environment are smaller subset of those which exist in regular multi-label classification- 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 e 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 value, which although is not tight, is reasonable bound for our multi-label setting because it in the range of values considered by most empirical evaluations (of order 10). We also test other E values, for for the first labels from the
instance, show 10 for the Pascal VOC dataset in Table and
XheXpert 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 model extraction, where the number of queries answered by answering party can be sufficient to replicate the party's 's model and steal its intellectual property. We should make sure that the privacy guardian, which is responsible for the privacy protection, is trusted institution, for example, party designated by a government.
REPRODUCIBILITY STATEMENT
For theoretical results, we provide clear explanations of assumptions and complete proofs are included in the Appendix C. We submit our code in the supplementary material. In the README file provide the main commands needed to 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.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318, 2016a.
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS 16, pp. 308 318. New York, NY, USA, 2016b. Association for Computing Machinery. ISBN 978 445434133444 doi: 10.1145/
0976749.2978315 URL htt.h:ttt:///oot .rgg 10. 11 97 6749 . 2978318
Rahul Agrawal, Archit Gupta, Yashoteja Prabhu, and Manik Varma. Multi-label learning with millions of labels: Recommending advertiser bid phrases for web pages. In Proceedings of the 22nd international conference on World Wide Web, pp. 13 24,2,,7 2013.
Tal Ridnik, Naday Zamir, Asaf Noy, Itamar Friedman, Matan Protter, and Lihi Emanuel Asymmetric loss for multi-label classification. In 2021.
Manni.-Manor.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. Mixmatch: A holistic approach to semi-supervised learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL
10

---

Under review as a conference paper at ICLR 2022
Mariusz Bojarski, Anna Choromanska, Krzysztof Choromanski, and Yann LeCun. Differentially- and non-differentially--iiaaa random decision trees. CoRR, abs/1410.6973, 2014. ?
7/arxiv. wwt.o/////ooo.o. htrg/aba/14100 6973
Matthew R Boutell, Jiebo Luo, Xipeng Shen, and Christopher M Brown. Learning multi-label scene classification. Pattern recognition, 37(9):155--1771 2004.
Kay Henning Brodersen, Cheng Soon Ong, Klaas Enno Stephan, and Joachim M Buhmann. The balanced accuracy and its posterior distribution. In 2010 20th international conference on pattern recognition, pp. 3121-3124 IEEE, 2010.
Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated edp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 74-86, New York, NY, USA, 2018. Association for doi: 10.1145/3188745.318888 URL https
Computing Machinery. ISBN 9781450355599
//doi.org/10.. 11A.11111113155501 3188945
Aurelia Bustos, Antonio Pertusa, Jose-Maria Salinas, and Maria de la Iglesia Padchest: A large chest x-ray image dataset with multi-label annotated reports. Medical Image Analysis, 66:101797, Dec 2020. ISSN 1361-8415. doi: 10.1016/j..editt mt..ii..200..011997... URL http:
//dx. doi.oo...o meet:///.......mmmmmimiaaa.aa..a
media. 2020. 101797
Dingfan Chen, Tribhuvanesh Orekondy, and Mario Fritz. Gs-wgan: A gradient-sanitized approach for learning differentially private generators. In H. Larochelle, M. Ranzato. R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 12673 12684. Curran Associates, Inc., 2020. BRLLhttps::/proceeiingg. pttp://prccceeennn...er.r..p...p cc/ paper 2ttper/2020/f1le/////
Christopher A. Choquette-Choo Natalie Dullerud, Adam Dziedzic, Yunxiang Zhang, Somesh Jha, Nicolas Papernot, and Xiao Wang. CaPC Learning: Confidential and Private Collaborative Learning. In International Conference on Learning Representations, 2021. URL https:/7
Openreview.nee wtt.:nnte/oommmmm//mull...l _
Amrita Roy Chowdhury, Theodoros Rekatsinas, and Somesh Jha. Data-dependent differentially private parameter learning for directed graphical models. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1939-1951. PMLR, 13-18 Jul 2020. URL hhttps://proceedinn
wresspres///ee satess/vvilee vv1// chowdhury20aa html,
Joseph Paul Cohen, Mohammad Hashir, Rupert Brooks, and Hadrien Bertrand. On the limits of cross-domain generalization in automated x-ray prediction. In Tal Arbel, Ismail Ben Ayed, Marleen de Bruijne. Maxime Descoteaux, Herve Lombaert, and Christopher Pal (eds.), Proceedings of the Third Conference on Medical Imaging with Deep Learning, volume 121 Proceedings of Machine Learning Research, pp. 136-155, Montreal, QC, Canada, 06-08 Jul 2020. PMLR. URL mir. press httpvvv1///////// wwwllvlleeeeeee www.//oa.e.o.cccoeo htmll
Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, Entong Shen, and Ting Yu. Differentially private spatial decompositions. 2012 IEEE 28th International Conference on Data Engineering, pp. 20-31, 2012.
Yuval Dagan and Gil Kur. A bounded-noise mechanism for differential privacy. arXiv preprint orXiv:2012.03817, 2020.
Deng, W. Dong, R. Socher, Li, Li, and L. Fei-Fei. Imagenet: large-scale hierarchical image database. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Miami Beach, Florida, USA, June 2009.
Emily Denton, Jason Weston, Manohar Paluri, Lubomir Bourdev, and Rob Fergus. User conditional hashtag prediction for images. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1731-1740, 2015.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium Theory of computing, pp. 371-380, 2009.

---

Under review as a conference paper at ICLR 2022
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-26622222 284. Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2014.
Edith Elkind, Piotr Faliszewski, Jean-Francois Laslier, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. What do multiwinner voting rules do? an experiment over the two-dimensional euclidean domain. In Proceedings of the Thirty-Firss AAAI Conference on Artificial Intelligence, AAAI 17, pp. 494-501. AAAI Press, 2017.
Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. International journiaal of computer vision, 88(2):
303-338, 2010.
Piotr Faliszewski, Arkadii M. Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory. In Trends in compulational social choice, 2017.
Sam Fletcher and Md Zahidul Islam. Differentially private random decision forests using smooth
sensitivity. Expert Systems with Applications, 78:16-31, 2017. ISSN 0957-4174. doi: https://doi.
org/10.1016/j.esaaaa000 21w.:6/i..saaa2217.1....... .034. URL htttst http:://ww.wciiiee. www.scciieccccccc rect com/ science/
atricie//11/S0954444733000
Craig Gentry. A fully homomorphic encryption scheme, volume 20. Stanford university Stanford, 2009.
David Hand and Robert. J Till. A simple generalisation of the area under the curve for multiple class classification problems. Machine learning, 45(2):171-186, 2001.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Las Vegas, Nevada, USA, June 2016.
Otto Hölder. Ueber einen mittelwerthabsstz. Nachrichten von der Königl. Gesellschaft der Wis- senschaften und der Georg-Augusts- Angiggsutttt-suiiisiittttt zu Göttingen, 1889:38-49 1889.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
Jeremy Irvin, Pranav Rajpurkar, Michael Ko, Yifan Yu, Silviana Ciurea-Ileus, Chris Chute, Henrik Marklund, Behzad Haghgoo, Robyn L. Ball, Katie S. Shpanskaya, Jayne Seekins, David A. Mong. Safwan S. Halabi, Jesse K. Sandberg, Ricky Jones, David B. Larson, Curtis P. Langlotz, Bhavik N. Patel, Matthew P. Lungren, and Andrew Y. Ng. Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison. CoRR, abs/1901.0700 007031, 2019. URL http: /ttt:://axxiv aawaiiiivvv.//... org/ abs/ 1901. 07031
Alistair E. W. Johnson, Tom J. Pollard, Nathaniel R. Greenbaum, Matthew P. Lungren, Chih ying Deng, Yifan Peng, Zhiyong Lu, Roger G. Mark, Seth J. Berkowitz, and Steven Horng. Mimic-cxr-jpg, a large publicly available database of labeled chest radiographs. arXiv preprint 1rXiv:1901.07042, 2019.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pp. 1376-1385 PMLR, 2015.
Yunhui Long, Suxin Lin, Zhuolin Yang, Carl A. Gunter, and Bo Li. Scalable differentially private generative student model via pate, 2019.
Zelun Luo, Daniel J. Wu, Ehsan Adeli, and Li Fei-Fei. Scalable differential privacy with sparse network finetuning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 5059-5068, June 2021.
12

---

Under review as a conference paper at ICLR 2022
Dahlia Malkhi, Noam Nisan, Benny Pinkas, and Yaron Sella. Fairplay-a secure two- poo-party computation system. In Proceedings of the 13th Conference on USENIX Security Symposium Volume 13, SSYM'04, 04, pp. 20, USA. 2004. USENIX Association.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275, IEEE, 2017.
Payman Mohassel and Yupeng Zhang. Secureml: A system for scalable learning. 2017 IEEE Symposium on Security and Privacy (SP), pp. 19-38. IEEE, 2017.
machine
Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, lan J. Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Confer- ence Track Proceedings, 2017.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with PATE. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018
Ioannis Partalas, Aris Kosmopoulos, Nicolas Baskiotis, Thierry Artieres, George Paliouras, Eric Gaussier, Ion Androutsopoulos, Massih-Reza Amini, and Patrick Galinari. Lshte: A benchmark for large-scale text classification. arXiv preprint arXiv: 1503::5000088: 085801 2015.
Hieu H Pham, Tung T Le, Dat Q Tran, Dat T Ngo, and Ha Q Nguyen. Interpreting chest x-rays via cnns that exploit hierarchical disease dependencies and uncertainty labels. Neurocomputing, 437: 186-194, 2021.
Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. Psi from paxos: Fast, malicious private set intersection. Annual International Conference on the Theory and Applications of Cryptographic Techniquex, pp. 739-767. Springer, 2020.
Michael O. Rabin. How to exchange secrets secrets with oblivious transfer. Cryptology ePrint Archive, Report 2005/187, 2005.
iacr. org/2005/187
Adi Shamir. How to share a secret. Communications of the ACM, 22(11):612-613, 1979.
Yanyao Shen, Hsiang-fu fu Yu, Sujay Sanghavi, and Inderjit Dhillon. Extreme multi-label classification from aggregated labels. In International Conference on Machine Learning, pp. 8752-8762. PMIR, 2020.
Pranav Subramani, Nicholas Vadivelu, and Gautam Kamath. Enabling fast differentially private sgd via just-in-time compilation and vectorization. arXiv preprint arXiv:2010.09063 2020.
Vinith M Suriyakumar, Nicolas Papernot, Anna Goldenberg, and Marzyeh Ghassemi. Chasing your long tails: Differentially private prediction in health care settings. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 723-734, 2021.
Grigorios Tsoumakas and loannis Katakis. Multi-label classification: An overview. International Journal of Data Warehousing and Mining (IJDWM), 3(3):1-13, 2007.
Salil Vadhan. The Complexity of Differential Privacy, pp. 347-450. Springer International Publishing, Cham, 2017. ISBN 977-3-319-55048--5 //doi.org// /10 100 0t..////...10/788.81
doi: 10. 100100079788---11-5770------8 URL https
Stephan Van Eeden, Jonathon Leipsic, SF Paul Man, and Don D Sin. The relationship between lung inflammation and cardiovascular disease, American journal of respiratory and critical care medicine, 186(1):1 11-16, 2012.
Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network, 2018.
13

---

Under review as a conference paper at ICLR 2022
Bangzhou Xin, Wei Yang, Shaowei Wang. and Liusheng Huang. Differentially private greedy decision forest. ICASSP 2019 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2672-2676, 2019. doi: 10. (0.1190CCASSPP21111662222
Chao-Han Huck Yang, Sabato Marco Siniscalchi, and Chin-Hui Lee. Pate-aae: Incorporating adver- sarial autoencoder into private aggregation of teacher ensembles for spoken command classification. In Interspeech, 2021.
Andrew Chi-Chih Yao. How to generate and exchange secrets (extended), pp. 162-167, 1986a.
Andrew Chi-Chih Yao. How to generate and exchange secrets. In Proceedings of the IEEE Symposium on Foundations of Computer Science, 1986b.
Jinsung Yoon, James Jordon, and Mihaela van der Schaar. PATE-GAN: Generating synthetic data with differential privacy guarantees. In International Conference on Learning Representations, 2019. /ttptttttss//opeeeeeeeee
Xinyue Zhang, Jiahao Ding, Maoqiang Wu, Stephen T.C. Wong, Hien Van Nguyen, and Miao Pan. Adaptive privacy preserving deep learning algorithms for medical data. In Proceedings of the IEEF/CVF Winter Conference on Applications of Computer Vision (WACV), pp. 1169-1178, January 2021.
Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba. Scene parsing through ADE20K dataset. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition (CVPR), Honolulu, Hawaii, July 2017.
Yuqing Zhu, Xiang Yu, Manmohan Chandraker, and Yu- Yu-Xiang Wang. Private-knn: Practical differen- tial privacy for computer vision. In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition (CVPR), June 2020.
A OPTIMALITY OF BINARY PATE
Intuition behind Proposition 3.1
Intuitively, a coordinate-indeeendeer function will be bounded below by Binary PATE because a single pair of databases (X, will lead to the maximum sensitivity of each output coordinate. If the function were coordinate- coordinate-dependeet, this is not guaranteed, i.e., 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. database with 2 columns, i.e., X E R². We will consider Aıf. Take f(X)
Let X be [sin (Xo), cos((x))) Because this function is coordinate-in indeeeedenn.dee... we can pick X = - and X' = 2 π] independently achieve the worst-case sensitivity of 4. However, inspection of (xin, (Xo)] will show Aig = 2/2 Ago Agi =
the coordinate-dependent g( where two databases X and X' can ever achieve 2 because the minimums and maximums of sin and cos do not occur at the same values X.
Lemma A.1. (X) RD > R² is ccordinute-iddepeneenn, there exists a pair of databasses (X, X') with ||X - X'Il1 = 1 (a change in only one row) which achieves the worst-cuse sensitivity for each of the coordinates fr-
Proof. We consider the is output coordinate of f. We know that (x.(X) Six([X X,)) for
= fo fe=(([X X algg P.,. by Definition ??. We define the corst-case sensitivity for fi.. Aifi. as in Dwork et al. (2014) Then
AIfa- = max (X.X)
(X) (xx
-
I1fi ([XIEEP Xqjign:..) - fi. (X.) X X,
[1 ([X.NER... Xqiep...)) Si. [ X.)ep...)lb
Therefore we can choose the members in P., (X) arbitrarily and independently to achieve the worst case sensitivity for St. while the members not in (X) can take any value because they do not
14

---

Under review as a conference paper at ICLR 2022
affect the output. Using the fact that the P,'s are disjoint, can continue this over all values of i* from to & to get the desired result.
Proposition A.2. For coordinate-independeer multi-label function f (X) R RR and single-output function fiinary (X) R2 - R applied once for each of the k labels such that Jiinary, = J mustii, the & sensitivity & fmutti is equal that of binary PATE applied per label and thus does not provide a better privacy guarantee. Note that fbinary. fmults,a 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 E R" be databases such that |X -1II 1 and let fbinary (X) R² > R. Fmults (X): R" + R be arbitrary coordinate coordinate-independen functions. Let f., and X; represent the i'th coordinate of the output and input respectively. As in Definition ??, let P.(X) represent the partition of input coordinates that determine the output coordinates Iinoory. multiad such that additionally U = X. We define the sensitivity of f. Af as in Dwork et al. 2014). We now consider the E, sensitivity of fmuiss:
A A imutes
I1fmalts(X) - fmmuse((())
X.X
IXX -X=x111==1
((fmaits,1(X) fmmutet,1 (X')) (fmultax(X) Fmoutes.(xX')))" #
max X.X
||X =1
((fmults, ([X,,,,,, fmults, ([X,,..., +...
max X.X
I|X -X1I1==1
(fmalts,k( (X...... X,,)) fmmlts xx) X
max
(fmmater, ( -
+...
I|X XX
+ (fmults, LIAA - x (XXXX(XXXXXX)XXXXXX))))))))))))) $
max X.X
+...
|X- -1
+ (fmutt..((PPAXX) UittP,(X))) -
by Definition ??
(Ubinary,1((PP)( Ux P.())) Shinary. (P P(())))
max X.X
+ (Jbinary. (PP((X), Uipx, (((XX()))))-nnrrre Jbinary, ((Pa(X"),
((A fbinary, .... + (A (binary. by Lemma A.I Afbinry, + Abinary, with =
Where the third last line follows since fmultiss = fvinary.-
In the case where p 1, have that ((A (Aabinary, ) +... (A fbinary,k)) )P < Afbnaryy11
+ A fuinory,k by a consequence of Hölder's inequality and thus equivalently that Afmalti S A fiinry, + A fhinary,k
Lemma A.3. If a function f(X): R + R is coordinate deppendet,,, the worst-case sensitivity is not guaranteed.
15

---

Under review as a conference paper at ICLR 2022
Proof. We prove by counterexample. Assuming that all coordinate coordinate-dependent functions guarantee
the worst-case sensitivity, we must find a function that does not satisfy this claim. Take the coordinate-
dependent function f (sin(Xp): cos where f(X): R + R² and Xo determines >> 1 output. The worst-case sensitivity of each coordinate is since -1 1 - sin Xo). cos( (Xo) I 1 and therefore the worst-case sensitivity of function with two coordinates is 2 2 = 4. However, since sin² + cos?
single choice of Xu and X² gives worst-case sensitivity for f as 2 4. We arrive at this by taking the derivative of [Xin(Xo), cos(Xo)) [sin(()) cos (X(]]] and set it to get for example Xo = and X br
Proposition A.4. For a multi-label function fmulte (X): : RD Rh to have lower sensitivity than the sum of the worst-case sensitivities for each coordinate, i.e., A Smsutt 1 A fiinary,o. Smutti must be coordinate-dependler
Proof. We proceed by contradiction. Let fmatts be a coordinate-independde function. By Propo- sition A.2 fmfttt = A1 ftinary. + ... + D fbinary. = Σ A1 fbinary. which contradicts Amfult < Σ Aifosnor... Therefore fmults must be coordinate -eeeedatt-deeeddent.
B POWERSET VS BINARY MULTI-LABEL PATE
B. PRELIMINARIES
Recall that Binary PATE has 2 l events: the presence or absence independently for each of the labels. Powerset differs from Binary PATE in that (1) has a number of events that grows exponentially (2*) in the number of labels, because each subset of the binary vector's powerset is separate event, (2) returns the entire binary vector of & labels simultancously, 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 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 influ- encing the this privacy loss is the gap, (ft) which we calculate using Proposition B.1 from Papernot et al. (2088, Proposition 10). It shows how to select ideal higher order moments μL, and E 82, using the data-dependent value for (n) (thus making the RDP bound a nonlinear function of (n)) solely).
Proposition B.1. For a GNMax aggregator Ma. the teachers' votes histogram (ni -r: ;kk) and any i' E PP((, 13²), where P(-) denotes the Powerset, we have
Pr(Mo + 10) q(n).
and
q(n)
2
Σ fc
n nz
2
20
Where this is a minimal modification of Paapernot et al. PATE to multi-label Powerset PATE.
2018
Proposition 7) to go from single-label
Theorem B.2 (From Papernot et al. (0118). Let M be a randomized algorithm with (1),,1)-RDD and (12, (u2,62)-RI) RDD guarantees and suppose that there exists likely outcome i given dataset D) and bound q S such that q 2 Pr(M(D) * i). Additionally suppose the X S bh and #2 Then for any neighboring dataset D' of D, we have: -21)
q S e(ua- 1)ea H1
DA(M(D))(M(D') S - log ((1 - A (2, 2- 4 (1)(())
where A (2,)) 2 (1-1)/ (1) ) and B( - 2///q/i1
(qGF2) n2-1
16

---

Under review as a conference paper at ICLR 2022
When the top 3 vote counts, n1 n2 > ny satisfy n1 n2 ns (the gap is sufficiently large), the RDP bound can be well approximated as
powersel (A) S exp(-22/o") //A where = M,
(n1 W -22)/4,
(I)
which is from Papernot et al. 2018 Corollary 11). Observing Figure of Appendix !| that this is indeed the regime we are 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.
B.2 POWERSET
We define the Powerset mechanism in Definition 9 We sort n(x); such that n, 2 nyVi > j. Denote gup _ 111 n2.. We seek to upper bound our best-case expected privacy loss for Powerset PATE. get
Using Equation
I
Ma Ele MeMerrs [X)] = expl
2. 0² ddgp.
gap
powersst (A)] - when gap - 0o. The base case gap with O(1) probability can be found El M.
by viewing Powerset PATE as non-uniform balls and bins problem. We have 2 subsets, i.c., [P({O, 1}x) = 2* Each subset (instance of an output binary vector) is represented by a bin with probability P: of having ball land in it (be voted on by teacher). The t teachers (Ea f) 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 r the load of the maximally loaded bin. Then, gap = 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 sample x and & classes, let fz(z)= E {0, 1)sh denote the j-th teacher model binary vector prediction. Let n,(x) be the vote count for the i-th subset (class), i.e., nz(x) Ki: fz(x) = P((0, P((0,1)*),) We
define the powerset PATE mechanism as
Mo (z) A arg max (
To upper-bound the max load, we use an indicator random variable C. representing the event of c collisions occurring in any bin. Using Markov's 's inequality followed by Stirlings approximation, get
Pr.Ca 2 1] < F(Ce]
p
because S (()
le (9)9.
As with nt we sort our probability [PI.... Pa1] such that P1 2 P2 ... 2 P2u. Because n1 > 122 we have that P1 > P.V * 1. Therefore, we have that D PT and Pr[C. 2 S (LE)ePF. In particular, we care about the regime where the max load occurs with high-probability (Pr(c.] + 1).
Pr|C. 2 1] t.e. P.
t.
+
exp(In( l.e.P. P
)o +
- c.In(t P1) + c c. In(c) +
c- Pı) + c In(c)
17

---

Under review as a conference paper at ICLR 2022
Specifying and P1, 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 Pi from the analysis below.
B.3 BINARY PATE
Here, we aim to specify probability for success of Binary PATE, p (note the lowercase, opposed to uppercase 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 similar analysis for Binary PATE, we can model each teacher's independent label prediction as a Bernoulli trial of probability pt. i 1.... k. With f independent trials, binomial distribution of probability pt- To simplify our exposition, and since this will favour the Powerset method over Binary PATE, we assume p p.Vi. Using composition, get expected privacy loss of
model the gap
4 P(gap g)-exp
-9
Shinary
= k
2 0.02
0=0
g=t
9
k
pO(1 - p))
exp
02
9=0
(p 1- 4
k
(3)
ge
9=0
B.4 PRIVACY ANALYSIS COMPARISON: BINARY VERSUS POWERSET PATE
From the assumptions above, we can directly calculate each P:, for Powerset PATE. We do this by recognizing that a single teacher's 's binary vector can be modeled as binomial distribution of (the number of labels) trials and probability p. To calculate the probability of any one of the 2 possible binary vectors from the Powerset vector, we express each one as /-hot binary vector labels present, independent of their coordinate position). Each possible subset satisfying hot will have equal probability of occurring (because we fixed for all labels) Then, the maximum probability binary vector, when sufficiently large (A: >> 5, approximately) and - 0 or p + is when / or I = 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 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 I's or 0's.
Impact of random labels To model more complex distributions where in general p; * P. we can bucket the ranges of p present and analyze these buckets separately. Let us operate under the assumption of nordinate-indeeendeene. In this case, we have the maximal variance for the binomial distribution and thus largest gaps for Powerset and Binary PATE. In this case, expect both methods to perform poorly: however, because the independetnn bound for Powerset PATE is tighter than for Binary PATE, Powerset PATE performs better, shown in Figure This gives our first two observations: (1) Powerset PATE has a better worst-case privacy loss (data- Mluta-independen bound) and (2) both Powerser and Binary PATE degrade their data-indh intta-independentt bounds as p - 0.5.
Impact of Correlation (Coordinate Dependence) Even when a bucket of labels has s 1 or p (but not equal), we can still have a varying distribution of outcomes. In particular, with we can directly use our binomial analysis above and find that there is uniform probability for all outcomes in each /-hot vector. In particular, there are factorially many outcomes each with equal probability. This drastically degrades the gap by reducing Pt. However, when there is coordinate- serddintteddeeeddenneeee e.g., the best-case when each label's value directly implies the rest, then we have only two outcomes for each hot vector. This improves the gap by reducing the possible subsets and improving P,. We formalize this as follows: if we have some subset of d vectors that are dependent, then reduce l in above analyses to (I d). This gives our third
18

---

Under review as a conference paper at ICLR 2022
300
Number answered queries
binary
powerset
250
200
150
100
50
0
2
10
Number of random (p=0.5) labels
Figure 3: Powerset PATE outperforms Binary PATE as more labels are generated randomly, Le., p=0.5. We use 50 teachers. privacy noise OGNMoz and the privacy budget E 20. If all votes are random, then both Binary and Powerset PATE fall back on the data independent bound.
4000
binary
powerset
Number of answered queries
3000
2000
1000
2
5
10
Number of labels
Figure Binary PATE outperforms Powerset PATE when they both have similarly high gap. We use 50 teachers, privacy noise OGNMar = 7, and privacy budget e set to 2. Here, all teachers always output 0 for all labels.
observation: (3) coordinate dependence has a combinatoric improvement for Powerset PATE and at best linear improvement for Binary PATE.
Impact of Higher Noise Multipliers Appealing back to the data-dependent ( calculation of Proposition B.I we see that Binary PATE has gap calculated as 2P - 1/2o for teachers. This gives g hinory(n) er fc(2 t/2o) However, for a similar gap, which is bounded for both to
max(gap) = t, we see that Powerset PATE will have binary(A) Σ always worse when the gaps are equal. We can see this effect in Figure Further, because union bound across the 2* classes, a higher noise multiplier has a larger impact on Powerset PATE, shown in Figure These give our fourth and fifth observations: equal gaps, Powerset PATE has a higher privacy loss, and (5) higher noise multipliers will impact Powerset PATE more for similar gaps.
2* er fe(gap/2o)) which is
(4) in the best case, and for any
19

---

Under review as a conference paper at ICLR 2022
C RDP-GAUSSIAN MECHANISM FOR A MULTI-LABEL SETTING
Proof.
DX(M(X)IM(XX)) = (
log
1
exp
-X
10 -(X))1
exp (-U-~) 110 - 5(X')13 )a0)
ak (2T)
20
20
1
(>110- - f(X011 - (1 - 2) 110 f(X')11) d0
log
exp
t (2
202
(2
(A - 1)x
(l)f(x) - -1(0011
1
log
exp
1 S(X0)1
(2TT)
20²
202
20²
D TOWARDS PRIVATE EXTREME MULTI-LABEL CLASSIFICATION
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. 2013), product categorisation (Agrawal 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 privacy- aceuracy 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 R 3, 000, for a relative "small" image of size 200 200, ze 40, 000 pixels. We conclude this section by proposing future directions to alleviate the priacc--accuage tradeoff's 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 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 ResNer5O-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 og between O and 5 varies from 67% to 47% We observe that the level of noise must be quite small, a < 3, or there is steep drop in accuracy of more than 10 percentage points. The privacy cost is too high to provide meaningful guarantees e, due to the small a and large number of pixels required to be labeled.
We believe that privacy analysis extreme multi-label settings can be tight- ened 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 group- ing 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 hicrarchies 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.
Opacity
Consolidation
Pneumonia
Figure 5: Example hierarchical struc- ture of labels in Chest radiography setting.
20

---

Under review as a conference paper at ICLR 2022
Table Dependency Matrix for the first labels form the CheXpert dataset.
Atelectasis
Cardiomegaly
Consolidation
Edema
Effusion
Atelectasis
0.975
0.987
0.976
0,983
Cardiomegaly 0.736
0.836
0.784
0.869
Consolidation
0.527
0.591
0.631
0.790
Edema 0.625
0.665
0.758
0.822
Effusion
0.485
0.567
0.731
0.633
Table 4: Exploit label dependencies for the multi-label classification.
OF QUERIES ANSWERED
ACC
BAC
AUC
MAP
ANSWER ALL LABELS INCRESE PRIVACY NOISE EXPLOIT NEGATIVE DEPENDENCIES
0.84
0.82
0.82
0.64
127
0.63
0.61
0.61
0.44
127
0.68
0.72
0.72
0.48
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 tailored to the multi-label classifications. For example, k-fold adaptive bounds Kairouz al. (2015) that draw tighter (< sublinear) privacy bounds for homogenous privacy settings can be extended to heterogeneous e per label and per query settings of multi-label classification. However, it is unclear if and under what scenarios
achieve tighter bound. For instance, it is possible to take the maximum E across all queries, but if there 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 small fraction of the whole dataset. This because there are many more negative than positive examples in the CheXpert dataset, which is caused by a class imbalance, common problem medical datasets. For instance, we find that 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% samples of the dataset. Thus, we consider negative instead positive dependencies. For example, if Atelectasis is absent then Consolidation is absent well in 98.79 08.7% of the cases. After ignoring samples for which at least one of Atclectasis or Consolidation have missing values, the percentage of samples where both labels negative is 83%. We obtain the negative dependencies using the training set and generate the dependency matrix
We compare multi-label PATE executed for each label using the semantics and querying the first label (Atelectasis) only, followed by (1) skipping the remaining labels and setting them as negative the first label is negative, (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=
of at the cost of lower performance (less accurate answers the queries). However, increasing the number of answered queries by adding more privacy noise (a = 67.5) causes the answered queries to less accurate than by exploiting the label dependencies. We show detailed comparison in Table 4
Note that 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 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).
E DETAILED COMPARISON WITH RELATED WORK
The main contributions from Zhang et al. I on Adaptive DPSGD are two fold: (1) adaptive differentially private deep networks proposed by adding Gaussian noise gradients whose scale
21

---

Under review as a conference paper at ICLR 2022
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 (CDP 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 not centralized to 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 performant feature extractor. The comparison between our proposed multi-label PATE and Adaptive DPSGD can be found in Section [.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 (diseriminate 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 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. (202l) follows the same algorithm as PATE-GAN except that the generative models used 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 lulti-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 differentially private aggregation mechanism that directly uses information from teacher discriminators to train student generator. Both, G-PATE and GS-WGAN train the discriminator(s) non non-privately while only training the generator with DP guarantees. They differ in the way the gradient is sanitized. GS- -S-N points that G-PATE has two main limitations: (1) gradients have to be discretized using manually selected bins, and (2) nigh-diimnssonal gradients in the PATE framework incur a high privacy cost, which requires dimensionality reduction techniques.
Luo et al. 202I) leverage additional, public datasets to instill strong representations in large models, which are then adapted private datasets at 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-IO. and for the standard single-label classification only.
Although there exist many differential privacy tree-based ensemble methods, including random forests, their non- 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 & Ilam 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.
22

---

Under review as a conference paper at ICLR 2022
F NORMS FOR CLIPPING
Using Lo norm bound does not achieve tighter RDP benefits because cannot upper-bound the l norm of the mechanism's outputs (since [x Σ (z|2) as required to achieve an RDP benefit. This analogous why achieved tighter RDP privacy loss bounds compared with Private kNN (Zhu et al. 2020): they use the & norm to bound the l2 norm from above, whereas we adapt the analysia directly operate over the lg norm. Note that we are required to bound the E2 norm because use the Gaussian mechanism (that satisfies RDP for an Eg norm bound).
We carried out theoretical analysis the bounded noise mechanism from (Dagan & Kur 2020) for the multi-label classification. The bounded noise in terms of f noom has theoretical properties that could lower the probability of an incorrect prediction for label. However, the method had a very limited practical application, and for standard multi-labe, datasets, such as Pascal VOC or CheXpert, 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.
G DATASETS AND MODEL ARCHITECTURES
MIMIC-CXR
PadChest
60000
Number of samples
8000
40000
6000
4000
20000
2000
AT
CA
ED
EF
EN
FR
LL
PN
PX
AT CO EF EM
HR IN MANO PT PN PX
CheXpert
PascalVOC
4000
Number of samples
3000
60000
2000
40000
20000
1000
0
0
AT
CA
CO
ED
EF
EN Label
FR
LL
LO
PN
PX
2
3
5
10 12 13 Label
14
15
161118
Figure 6: The label distribution for each multi-label dataset (Pascal VOC, CheXpert, MIMIC-CXR, and PadChest).
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 MI. for healthcare: CheXpert (Irvin et al. 2019),, MIMIC- CXR (Johnson et al. 2019) and PadChest (Bustos et al. 2020).. These medical datasets present realistic and large-scale application for multi-label CaPC.
140 540 images that are split into 5, 717 images for training and 5, 823 images for validation (Everingham et al. 22110). 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), (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)
Pascal VOC 2012 contains 11,
that pre-trained ImageNet (Deng al.
2009
23

---

Under review as a conference paper at ICLR 2022
Medical datasets contain chest radiographs (X-ray) images. CheXpert (Irvin al. 2019) has 224, 316 radiographs. MIMIC-CXR-JIP (Johnson et al., 2019) contains 377, 110, and PadCh- est (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- Atelectssis,,,, Cardiomegaly, Consolidation, Edema, Effusion, Enlarged Cardiomediastinum, Fracture, Lung Lesion, Lung Opacity, Pneumonia and Pneu- mothorax. MIMIC-CXR-JPG includes 11 pathologies- Enlaade 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, Nheural_Thicenninn
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-JGG use the CheXpert labelling system, which is a rule based approach. PadChest obtains reports annotated by trained radiologists, then trains 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. (017) 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 The label distribution for medical datasets is more unbalanced than for Pascal VOC, due to prevalence or rarity of certain diseases.
H EXPERIMENTAL DETAILS
Our experiments were performed on machines with VeeelSeennSiilvr 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 1000 epochs. As an optimiser, we use SGD with learning rate and weight decay of 0.001 and le 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-CRR, and PadChest using the standard DenseNet- 121 architecture trained for 100 epochs, with weight decay of le 5, Adam optimizer (learning rate=0.001) with the adam_amsgras 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. 202T). Note that because we are in sparse-hot multi-label setting (where a sample has many O's negative labels) the accuracy 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 D; 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 their private data D., then simulate lalti-
24

---

Under review as a conference paper at ICLR 2022
CaPC learning by having each querying party complete the protocol with all other parties answering parties. Using the new labelled data provided by multi-label CaPC, we retrain each querying party's model on their original data D, plus the labelled data. We average metrics over least 3 runs with each using a different random seed.
1 ADDITIONAL EXPERIMENTS
1.1 MULTI-LABEL PATE: BINARY VS POWERSET
We compare Binary vs Powerset multi-label PATE in Tables and Figure For each data point, we check how the performance of the Binary and Powerset PATE degrades Gaussian noise Man and select the scale that preserves high values of the metrics (ACC, BAC, AUC, MAP), with maximum performance drop by few percentage points arbitrarily. We align both Binary and Powerset methods according to the performance metrics. For given values of the metries, we find the GGN Maz 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 PATE, while the values of the metries are ACC=.95, AUC=,66, and MAP .37. For CheXpert, we OGN Man 5 for Powerset PATE and OGN Mar 20 for Binary PATE, while the values of the metrics are ACC=.71, AUC=.68, and MAP .45.
increase the scale of
select this threshold
select GN Maz 4 for Powerset PATE and GGN 11 for Binary
Table CheXpert: Performance Binary PATE vs Powerset PATE w.r.t. number of answered queries, ACC, BAC, AUC, and mAP (as measured the test with the specified GGNMax. PB (e) is the privacy budget. We use 50 teacher models. When we limit number of labels per dataset, we select the first k labels.
OF LABELS
QUERIES
DATASET
MODE
ANSWERED
PB (E)
JONMAX
ACC
BAC
AUC
MAP
CHEXPERT
BINARY
988
20
.71
.63
CHEXPERT
POWERSET
988
20
.71
.71
.71
.63
CHEXPERT
BINARY
898
20
18
.73
.72
.72
.62
CHEXPERT
POWERSET
872
20
12
.72
.72
.72
.60
CHEXPERT
BINARY
399
20
13
.75
.77
.77
.55
CHEXPERT
POWERSET
10
CHEXPERT
BINARY
554
20
17
.74
.75
.75
.60
CHEXPERT
POWERSET
323
20
5
.76
.78
.78
.60
CHEXPERT
BINARY
320
20
17
.74
.76
.76
.59
CHEXPERT
BINARY
932
.70
CHEXPERT
POWERSET
582
10
.76
.76
CHEXPERT
BINARY
299
20
18
.74
.75
.75
.56
CHEXPERT
POWERSET
392
20
.74
.75
.75
.55
CHEXPERT
BINARY
157
20
12
.73
.74
.74
.51
CHEXPERT
POWERSET
338
.72
CHEXPERT
BINARY
145
20
13
.73
.73
.73
.51
CHEXPERT
POWERSET
200
20
5
.73
.71
.71
.50
CHEXPERT
BINARY
159
20
16
.71
.70
.70
.50
CHEXPERT
POWERSET
241
.50
CHEXPERT
BINARY
.72
CHRXPERT
POWERSET
10
146
20
4
.73
.71
.71
.50
CHEXPERT
BINARY
11
201
20
5
.71
.68
.68
.45
CHEXPERT
POWERSET
11
152
20
20
.71
.68
.68
.44
I.2 POWERSET WITH T-VOTING
We present how to incorporate r-voting into the Powerset method. A given teacher allowed to set up positive labels for given query sample. This approach limits the number of positive classes from C 2 to C ()) ( +... (*) classes. Since have fewer classes: (1) it increases the possibility achieving a consensus between teachers (a higher gap between max and runner-up numbers of votes be achieved), (2) the data independent bound is lower (computed as:
25

---

Under review as a conference paper at ICLR 2022
Table 6: Pascal VOC: Performance Binary PATE Powerset PATE w.r.t number of answered queries, ACC, BAC, AUC, and mAP as measured on the test set with the specified dGNMax- PB (:) is the privacy budget. We use 50 teacher models. When we limit number labels per dataset, we select the first & labels.
OF LABELS
QUERIES
DATASET
MODE
ANSWERED
PB (E)
JGNMAX
ACC
BAC
AUC
MAP
PASCAL VOC
BINARY
5464
20
2
.98
.84
.84
.75
PASCAL VOC
POWERSET
5464
20
2
.98
.84
.84
.75
PASCAL VOC
BINARY
5442
.74
.74
.54
PASCAL VOC
POWERSET
5464
20
5
.97
.74
.74
.55
PASCAL VOC
BINARY
3437
20
7
.97
.72
.72
.51
PASCAL VOC
POWERSET
3416
20
7
.97
.72
.72
.51
PASCAL VOC
BINARY
2398
20
8
.96
.66
.66
.39
PASCAL VOC
POWERSET
2040
8
.96
.65
.65
.33
PASCAL VOC
BINARY
1543
20
7
.96
.69
.69
.46
PASCAL VOC
POWERSET
8
1192
20
7
.95
668
.68
.37
PASCAL VOC
BINARY
1190
20
11
.95
66
.66
.37
PASCAL VOC
POWERSET
702
4
.66
66
.37
PASCAL VOC
BINARY
14
888
20
12
.95
.65
65
.36
PASCAL VOC
POWERSET
14
417
20
3
.95
.65
65
.37
PASCAL VOC
BINARY
15
465
20
8
.94
.66
.66
.36
PASCAL VOC
POWERSET
15
165
20
3
.94
.66
.66
.36
PASCAL VOC
BINARY
16
.65
.38
PASCAL VOC
POWERSET
16
94
20
2
.95
.65
.65
.38
PASCAL VOC
BINARY
18
446
20
2
.95
.65
.65
.36
PASCAL VOC
POWERSET
18
94
20
2
.95
.65
.65
.36
PASCAL VOC
BINARY
20
427
.95
.65
.65
.37
PASCAL VOC
POWERSET
20
2
.95
.65
.65
.33
Pascal VOC
CheXpert
3500
1000
Number of answered queries
Mode
Number of answered queries
Mode
3000
Binary
Binary
Powerset
800
Powerset
2500
2000
800
400
1000
500
5
10
15
20
2
6
8
10
Number of labels
Number of labels
Figure 7: Binary vs Powerset PATE: number of answered queries. We compare the number of answered queries number of & first labels selected from the Pascal VOC and CheXpert datasets. We keep the privacy budget E = 20. The private multi-label classification with Binary PATE performs better (answers more queries) than Powerset PATE for Pascal VOC. The CheXpert dataset is more noisy (in terms of labeling, the pathologies are sparse and difficult to detect) and does not give clear preference
multi-label PATE method.
1 (L/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
Intuitively, up to positive labels could be selected based on the confidence of the positive value for label, where we would choose the top v labels with the highest confidence being positive. However, given that most deep multi-label models use independent predictive heads (i.e., separate sigmoid
26

---

When the 7-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 ie 5, for 5 the number of classes is 16 instead of 32 clipping) and we are able to answer 5% queries more, for r 1, we have only 6 classes and almost 14% more answered queries. For 7 = 5 there is only more class than for T = and we observe 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 7 = (the number of classes is C k 1). Under review as a conference paper at ICLR 2022
Pascal VOC
CheXpert
Binary
Powerset
Binary
Powerset
ACC
ACC
0.8
AUC
AUC
Velue matiic
MAP
MAP
0.8
0.6
0.4
10.
62
a rolse scale)
(Gaussian noise scale)
0 (Gaussian scale)
(Gaussian noise scale)
Figure 8: Binary vs Powerset PATE: performance. We compare the drop in performance in terms of accuracy (ACC), area under the curve (AUC), and mean average precision (MAP) between Binary PATE and Powerset PATE as we increase the scale of the Gaussian noise MaN- We select the first 11 labels in Pascal VOC and all 11 labels from CheXpert. We keep the privacy budget 20. The private multi-label classification with PATE performs better (preserves higher values of the metrics) using the Binary approach.
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 > T 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 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
Table 7: More statistics about the positive labels per data point in the Pascal VOC dataset.
NUMBER POSITIVE LABELS
NUMBER OF TRAIN SAMPLES
5
17
4
105
484
1677
3539
0
0
5, which equivalent to no
27

---

Under review as a conference paper at ICLR 2022
Table 8: Pascal VOC: Performance of Powerset PATE with 7-clipping w.r.t. number answered queries with the specified 6GNMax The ACC, BAC, AUC, and mAP are measured on the answered queries from the test the number of labels per dataset, we select the first & labels. The r denotes maximum number of positive labels that a teacher allowed return per data sample.
PB (c) the privacy budget. We use teacher models. When limit
# OF LABELS
QUERIES
ANSWERED
PB (E)
OGNMAX
ACC
BAC
AUC
MAP
5464
20
2
.98
.84
.84
.75
2
5464
20
5
.97
.75
.75
.55
2
2
5464
20
5
.97
.74
.74
.55
3437
20
.71
.71
.48
3
2
3421
20
.97
.71
.71
.49
3
3416
20
.97
.72
.72
.51
4
2547
20
7
.97
.68
.68
.43
2527
20
.97
.69
.69
.43
2485
.97
.69
.69
.43
4
2485
20
.7
.69
.69
.43
5
2321
20
.96
.65
.65
.36
2151
20
8
.96
.65
.65
.34
2077
.96
.65
2048
20
8
.96
.65
.65
.33
5
2040
20
8
.96
.65
.65
.33
1192
20
.95
.68
.68
.37
10
947
.97
.65
.65
.36
10
2
896
20
.96
.65
.5
.36
10
895
20
5
96
.65
.65
.33
10
4
885
20
96
.65
.65
.33
10
877
20
96
.65
.65
.33
10
.96
.64
.64
10
849
20
5
.96
.64
.64
.29
10
848
20
.96
.66
.66
.34
10
848
20
.96
.64
.64
.32
10
.96
.64
.64
.30
11
11
702
20
4
.95
.66
66
.37
14
14
417
20
3
.95
.65
.65
.37
15
15
165
20
3
.94
.66
.66
.36
16
94
.65
.38
18
18
94
20
.95
.65
.65
.36
20
111
20
2
.95
.63
.63
.33
20
99
20
2
.96
.67
.67
.41
.96
.61
20
78
20
2
.96
.63
.63
.33
20
5
78
20
2
.96
.63
.63
.34
20
10
78
20
2
.95
.65
.65
.34
20
20
78
20
2
.95
.65
.65
.33
I.3 DPSGD vs PATE ON CHEXPERT
There few key differences between PATE and DPSGD in 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 Mixhatch). The centralization of data is strong requirement for DPSGD which is often not applicable the tasks we consider (e.g., medical or financial data) because these institutions may be blocked from centralizing data due regulations.
The Adaptive DPSGD method from Zhang et al. (2021) does not publish the code, thus the following our best effort. The results presented below come from Figure 5 in Zhang et al. (202I) Similar to their experimental setup. we use DenseNet- 121 1 pre- trained on ImageNet and tine-tune only the last fully connected layer while keeping all the other (convolutional) layers fixed. Across all of the experiments, we use as the privacy budget. We use the whole CheXpert test set, and here report results for 8 10-4 To evaluate the performance of the models,
the CheXpert test set (from
28

---

Under review as a conference paper at ICLR 2022
the valid.csv file in CheXpert-v1..-smalll As shown in the Table 9 in this setting, outperform the Adaptive DPSGD.
We use the following parameters obtain results for the Binary multi-label PATE:
sigma gnmäx 7.0 s sigma threshold threshold =
method = multilaben
batch size 20
learning rate 0.001
epochs 100
weight decay 0
x-ray views ['AP', '
Multilabel prwpbbeeepoootthehhtthooe [0.53, 0.5, 0.18, 0.56, 0.56]
Table 9: DPSGD PATE on Chexpert for the first 5 labels.
METHOD
AT
CA
CO
ED
EF
AVERAGE
NON-PRIVATE
0.84
0.80
0.87
0.90
0.97
0.87
DPSGD
0.56
0.53
0.66
0.56
0.62
0.58
ADAPTIVE DPSGD
0.75
0.73
0.84
0.79
0.79
0.78
BINARY PATE
0.78
0.75
0.84
0.76
0.81
0.79
1.3.1 CDF GAPS
We show the Cumulative Distribution Function (CDF) for the gaps in Figure 9 ensemble of teachers is confident about the answers for most labels for the Binary PATE and there very small gaps for most queries when using Powerset PATE, which shows much lower confidence of teachers in choosing the same (super) classes, which created from aggregated label predictions (the values the labels are collected in a binary vector that constitutes a class).
We observe that the
CheXpart
1.0
Mode
1.0
Mode
Bineyy
Birary
Powerset
Powerset
0.8
0.8
0.6
0.8
0.4
20 Sorted
40
20
Sorted
Figure 9: Binary vs Powerset PATE: CDF gaps (differences between vote counts). We use 50 teacher models trained the Pascal VOC and CheXpert datasets. These any noise to the vote histograms. Most of the gaps are relatively large (> 40) for the Binary PATE per label, which shows that teachers confident about the answers queries. The average gap for the Powerset method is relatively low (only 18 for Pascal VOC and 13 for CheXpert).
gaps without adding
1.3.2 GAPS AND PERFORMANCE METRICS
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 the difference between the maximum number
29

---

Under review as a conference paper at ICLR 2022
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 II] we plot the average gap (on the y-axis) for the test set across all histograms for given number of labels (presented (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 the exponential growth 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.
the x-axis). We compare the Powerset PATE
Pascal VOC
Basury
Powernt
097
0.48
0.88
0.88
Figure 10: Binary vs Powerset PATE: gaps and metries for Pascal VOC. We use 50 teacher models. These are raw gaps without adding any noise the vote histograms.
1.4 GENERAL TUNING OF PAIPER--RRAMETESS
We set the hyper-parameten 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 7 parameters. In Figure 1, we tune the value of the a parameter of the Gaussian noise based the utility metrics: accuracy (ACC), balanced accuracy (BAC), mean average precision (MAP). We set a as 9, 10, and for Pascal VOC, MIMIC, and CheXpert datasets, respectively. This allows us answer many queries with high performance in terms of ACC, BAC, and MAP.
Similarly, we tune the 7 values for & norm in Figure 12 and for & norm in Figure 13
Regarding the values of parameters dG. T, and or, follow the original work PATE (Papernot et al. 2017) and perform grid search over a range of plausible values for each of the hyper- parameters.
30

---

Under review as a conference paper at ICLR 2022
CheXpert
0.8
676
679
699
696
Figure 11: Binary vs Powerset PATE: gaps and metries for CheXpert. We 50 teacher models. These are raw gaps without adding any noise to the vote histograms.
The detailed analysis of tuning the hyper-parameters are for: T-s in Section 1.5 OG in Section [.6
PATE's thresholding (T, and oT) in Section 1.7 and probability thresholds in Section I.10)
1.5 TUNING T-CLIPPING
We determine the minimum value of 7 for clipping in b2 and & 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
1.6 TUNING MaN
We determine how much of the privacy noise, expressed as the scale of Gaussian noise a, can be added that the performance measured by accuracy, BAC, AUC, and mAP, is preserved. The experiment is run using the binary PATE per label and presented in Figure 14
1.7 TUNING PATE
There are three parameters to tune: the differential privacy Gaussian noise standard deviation ae, the count threshold T, and the thresholding Gaussian noise standard deviation Ør. We first disable the thresholding (aT and 7') and tune og to achieve high BAC of the noisy ensemble while maximizing the number of answered queries. In Figure 19 we tune the aG parameter from PATE for different configurations retraining. The goal to maintain a high accuracy while selecting OG with high value that many queries possible Thresholding is useful if we want to add a relatively small amount of Gaussian noise (aa) in the noisy max. For example, for og 7 and 50 teacher models trained on CheXpert, the maximum
answered. After tuning dg. grid-search dy and T.
31

---

Under review as a conference paper at ICLR 2022
Pascal VOC
CheXpert
0.7
Value of the metric
Value of the metric
0.8
0.6
0.6
0.5
0.4
ACC
ACC
0.4
BAC
0.2
MAP
MAP
0
5
10
15
20
0
2
10
I (clipping of votes)
(clipping of votes)
MIMIC-CXR
PadChest
1.0
0.8
Value of the metric
Value of the metric
0.7
0.8
0.6
0.6
0.5
0.4
0.4
ACC
ACC
0.3
BAC
0.2
BAC
MAP
MAP
0.2
0.0
0
10
0.0
2.5
5.0
7.5
10.0
12.5
15.0
т (clipping of votes)
(clipping of votes)
Figure 12: Value of the metric vs r-clipping votes in & norm. For a given т, we plot accuracy (ACC), balanced accuracy (BAC), and mean average precision (mAP).
number of labels answered without thresholding is 737 (67 queries) with 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 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-negart vote difference of 40 of max 49. Also note that the BAC can be higher on easier queries.
also help reduce dG. which is the major inftuencing factor the final BA
1.8 COMPARE DIFFERENT METHODS
Figure 15 we directly compare the Binary PATE (denoted as PATE), T-PATE, and clipping l and é, norms. The error regions are for the three querying parties.
1.9 VARYING PRIVACY BUDGET
In Table 12 we show the performance of the retrained models when using CaPC with various privacy budgets s. Figure 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 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.
privacy budget is set
We also compare the performance after re-training with and without the (confidence) thresholding mechanism used in PATE (represented by dy and threshold T parameters). We observe that in case of the medical datasets, there can 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 for AUC and mAP, for BAC we see drop by one percentage point, and there is no difference in terms of accuracy (remains the level of about 0.86). This requires further investigation. Intuitively, observe that the metrics
32

---

Under review as a conference paper at ICLR 2022
Pascal VOC
CheXpert
0.7
Value of the metric
Value of the metric
0.8
0.6
0.6
0.5
0.4
ACC
ACC
0.4
BAC
0.2
MAP
MAP
0
5
10
15
20
0
2
10
I (clipping of votes)
T (clipping of votes)
MIMIC-CXR
PadChest
1.0
0.8
Value of the metric
Value of the metric
0.7
0.8
0.6
0.6
0.5
0.4
0.4
ACC
ACC
0.3
BAC
0.2
BAC
MAP
MAP
0.2
0.0
0
10
0.0
2.5
5.0
7.5
10.0
12.5
15.0
I (clipping of votes)
T (clipping of votes)
Figure 13: Value of the metric vs r-clipping votes in & norm. For a given т, we plot accuracy (ACC), balanced accuracy (BAC), and mean average precision (mAP).
Voc
1.0
0.6
0.2
10
20
20
22
10
20
20
20
(Gaaoolian rolve stale)
O(Gasssddn nolee stale)
[Gaaakiinn Talve stalle
(Geutaien nolee scall))
Figure 14: Value of the metric versus noise standard deviation ø. For given ar, we plot accuracy (ACC), balanced accuracy (BAC), and mean average precision (mAP).
can increase substantially with thresholding for the labels (pathologies) that are easy to classify. However, the most difficult predict pathologics are left without answer and no improvement is made on them. On the other hand, without thresholding, we have to answer labels and correct predictions the hardest labels can produce substantial improvement in the classification of these hard labels.
I.10 TUNING PROBABILITY THRESHOLD
We tune the global (applied to all labels) probability threshold y that determines if given probability denotes positive (P > 7),, negative (P Σ 7) 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.
33

---

Under review as a conference paper at ICLR 2022
PATE
t-PTE
L2
800
# of answered queries
600
400
200
0
5
10
15
20
25
a (Gaussian noise scale)
Figure 15: Compare methods: number of answered queries using the Pascal VOC dataset,
with r = 3.4 (set for ( -oorm clipping, and 72 = 1.8 set for T-PATE and - clipping. The red vertical line denotes the selected value of
1.0
Before CaPC Mean
Before CaPC
Ensemble Mean
Ensemble After CaPC
0.9
After CaPC Mean
Balanced accuracy
0.8
0.7
0.6
0.5
2
3
5
6
9 10
12 13
14
15 16 17 18 19 20
Label
Figure 16: Retraining with privacy budget for the Pascal VOC dataset.
We also tune the threshold per label for CheXpert. We find the follow- ing probability thresholds per label using the validation set 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 mod- els with the lowest BAC and retrain them with CaPC. The average metrics BAC, AUC, and mAP
34

---

Under review as a conference paper at ICLR 2022
Table 10: Pascal VOC with 20 labels: Performance of Binary PATE for different values of w.r.t. number of answered queries, ACC, BAC, AUC, and mAP as measured on the test set with the specified GNNMa- PB (e) the privacy budget. We use 50 teacher models. When we limit number of labels per dataset, we select the first labels. We set OGNMax
QUERIES
PB (E)
ANSWERED
ACC
BAC
AUC
MAP
0
86
.62
.62
.44
3
13
.93
.67
.67
.53
4
22
-93
.64
.64
.44
5
31
.95
.63
.63
.39
6
40
.55
.67
.67
.45
64
.55
.64
.35
8
81
.95
.66
.66
.40
9
101
.95
.60
.60
.28
10
113
96
.63
.63
330
11
135
96
.64
.64
.33
12
165
.96
.65
.65
.35
13
199
.96
.63
.63
.32
14
217
.96
.64
.64
.35
15
239
.96
.63
.63
.32
16
272
.96
.63
.63
17
306
.96
.63
.63
.30
18
332
.96
.63
.63
.31
19
362
.96
.63
.63
.30
20
403
.96
.63
.63
.30
Table 11: Performance of multi-label CaPC w.r.t. ACC, BAC, AUC, and mAP, Paseal VOC (PA), CheXpert (CX), MIMIC (MC), and PadChest (PC). (-) denotes N/A. PB (8) is the privacy budget.
# OF MODELS
DATASET
STATE
PB (s)
ACC
BAC
AUC
MAP
1
INITIAL
.97
.85
.97
.85
50
BEFORE CAPC
.931.02
.591.01
881.01
.541.01
PA
50
AFTER CAPC
.941.00
.62.1.01
.88.001
.541.01
50
AFTER CAPC
20
.94+.01
.64t.01
.89+.01
.55+.01
1
INITIAL
.79
.78
.86
.72
CX
50
BEFORE CAPC
.771.06
.66.1.02
.751.02
.58..02
50
AFTER CAPC
20
.769.07
.694.01
.77t.01
.59t.01
1
INITIAL
.90
.74
.84
.51
MC
50
BEFORE CAPC
841..07
.6311.33
.781..3
.431.02
50
AFTER CAPC
20
.855.05
.644.00
.79t.01
.45+.03
INITIAL
.86
.79
.90
.37
PC
10
BEFORE CAPC
.904.01
.644.01
.794.01
.161.01
10
AFTER CAPC
20
.884.01
.644.01
.75+.001
.141.01
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 metries Figure
1.11 CROSS-DOMAIN RETRAINING
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
35

---

Under review as a conference paper at ICLR 2022
Table 12: Performance of multi-label CaPC with 7-PATE w.I.. ACC, BAC, AUC, and mAP, on Pascal VOC (PA), CheXpert (CX), MIMIC (MC), and PadChest (PC). (-) denotes N/A. PB (E) is the privacy budget. T (Y/N) the table refers the PATE thresholding i.e. corresponding to the parameters T and being used (Y) or not used (N). Note that the probability thresholding per layer was used in these experiments (as described in Section[I.10)
# OF
DATASET MODELS
STATE
T(Y/N) PB (e)
ACC
BAC
AUC
MAP
1
INITIAL
.88
.97
.91
PA
50
BEFORE CAPC
.3+.01
.59t.01
.89..01
.54..02
50
AFTER CAPC
N
20
.94+.01
.604.01
.894.01
.54.002
1
INITIAL
.79
.78
.86
.72
50
BEFORE CAPC
.75+.02
.69H.0
.77.00
.59..01
CX
50
AFTER CAPC
Y
.73.001
.699.01
.76.001
.59+.01
50
AFTER CAPC
N
20
.70..01 744.01
.77..01
.592.01
1
INITIAL
.90
.74
.84
.31
MC
50
BEFORE CAPC
844.07
.33.03
784.03
.43:.02
50
AFTER CAPC
Y
844.02 .44.00
.77.002
.44.001
1
INITIAL
866
.79
.90
.37
10
BEFORE CAPC
824.01
.64.001
.791.0
.17.01
PC
10
AFTER CAPC
Y
20
.861.04
661..01
711.03
144.02
10
AFTER CAPC
.861.02
.601.01 .721.02 .15.03
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 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 additional benefits. The models trained this dataset achieve a higher BA (particularly on the first 5 shared pathologies as presented in Figure I7}. Thus, the ensemble of all models engage in multi-label CaPC and the models trained CheXpert act as answering parties to provide labels for querying parties from PadChest. Using ag = 9, T = 50, and Øy 30, observe higher BAC on all of those pathologies, where we do not significant decrease on the other pathologies. Thus, multi-label CaPC provided benefits for the PadChest models in this cross-domain scenario.
36

---

Under review as a conference paper at ICLR 2022
1.0
Before CaPC Mean
Before CaPC
PC Ensemble Mean
PC Ensemble
0.9
Balanced accuracy
CX Ensemble Mean
CX Ensemble
After CaPC CX Mean
After CaPC CX
0.8
0.7
0.6
0.5
AT
CA
CO
ED
EF
EM
FI
FR
HE
IN
MA
NO
PT
PN
PX
Label
Figure 17: Cross-domain retraining with CaPC. train 10 models on PadChest (PC) and compare their performance PadChest test set against the ensemble of these models (PC Ensemble), ensemble of 50 CheXpert models (CX Ensemble), and finally retrain the 10 PadChest models via binary lulti-label PATE using the CheXpert ensemble (after CaPC on CX).
0.90
1.0
Before CaPC Mean
Before CaPC
Mean
0.9
After CaPC Mean
Aftar CaPC
0.80
Balanced accuracy
0.75
0.8
0.70
0.7
0.56
0.5
0.50
AT
CA
GO
LO
PN
PX
AT
CA
CO
LO
PN
PX
Label
Label
Figure 18: Using CaPC to improve the weakest models. Dashed lines represent values of the metrics: Balanced Accuracy (BAC) and AUC. We retrain a given model using additional CheXpert data labelled by the ensemble of all the other models trained on CheXpert. All metries improved after retraining by around 0.05 on average.
37

---

Under review as a conference paper at ICLR 2022
Figure 19:
The analysis of the balanced accuracy (y-axis) of votes from the ensemble as we increase the (sigma of the Gaussian) noise (x-axis) from the binary multi-label PATE. We search for variance of the noise Og that can preserve high BAC for the ensemble. Left: 50 CheXpert models with train and test on CheXpert, aa < 9.0 preserves more than 0.69 of BAC. Middle: 50 CheXpert models with train on CheXpert and test on PadChest test set, OG S 9.0 preserves more than 0.75 BAC. Right: 10 PadChest models with train and test on PadChest, og S 5.0 preserves more than 0.75 of BAC
38

---

Under review as a conference paper at ICLR 2022
J THE CAPC PROTOCOL
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 random vector and subtracts it from the vector of logits r. Then, each answering party sends the encrypted result: Enc(r - f) to the querying party who decrypts the message to obtain (r ar- f).
(c) One-hot encoding of the logits. The answering parties provide and the querying party provides (r-f) 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 and 8. The share is returned to the querying party and the share is to the Privacy Guardian (PG). The PG is common facilitator in these setups, i.e., a trusted third- party, and canest-but-curious. The sum of shares and & 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 the argmax. In CaPC, Gaussian noise is added the sum of 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 sum the noisy values with the values. The result is noisy histogram representing the number of votes for each class. The argmax of this determines which class received the maximum number votes. This class is returned the querying party as the final predicted label.
In CaPC learning Choquette- -hhuo et al. 2021), the main tool for confidentiality secure multi-party computation (MPC) (Yao) 1986a) and homomorphic encryption. MPC is used when distrusting parties want to jointly evaluate 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 more efficient in terms of the execution time. Protocols in both categories similar cryptographic building blocks, including (fully) homomorphic encryption (Gienry) 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.
computain
39

---

Under review as a conference paper at ICLR 2022
Algorithm CaPC protocol
Input: Querying Party QP. x query (unlabeled data item) from QP. Answering Parties AP!...,AP, with MI models f(( y. where {1, ..., n), and y is the vector of logits. Privacy Guardian PG. Output: label for query x (QP receives E for its x.).
1: QP encrypts to Enc(z).
2: QP sends Ene(x:) to AP,....APP.
3: for all AP; do
4: Ene(r) < (:En(()))
5: Generate random f;
6: Enc(r; - f.) + Enc(r:) -;
Enabled by Homomorphic Encryption
7: Send Enc(r; fz) to QP
8:
for AP, and QP do
2PC (Secure 2-Party Computation) between each AP and the QP QP decrypts - f; +- Decrypt(Enccfr - f:))
9:
10: QP sends r; - f; to 2PC
11:
AP, sends f; 2PC
12:
2PC: r; t (r: P.) + (f:) hol; + argmarr(ra)
2PC:
14:
2PC: &; + 4- one - hol;
b Secret Sharing
15:
AP; receives & from 2PC
16: QP receives s, from 2PC
17: for all AP; do
18: Send 6; PG.
QP: ->= 8i
20: QP sends 9 to 2PC
21: PG: -
22: PG: Generate Gaussian noise <- (0,
23: PG sends S and â to 2PC
24: 2PC: h e S â
Noisy histogram
2PC: f t argmax ())
26: 2PC sends & to QP
40

---

Under review as a conference paper at ICLR 2022
K ALGORITHMS FOR THE MULTI-LABEL CLASSIFICATION
Algorithm 2 Multi-label classification with 7-clipping é2-norm and with the Confident GNMax.
Input: Data point z, clipping threshold 72, Gaussian noise scale JG. Gaussian noise scale for Confident GNMax dr, teachers, each with model f (a) E 1) where E [n]
Output: Aggregated vector with V = if returned label/feature present, otherwise Vj = 0.
I: for all teachers j E [n] do
2:
1/ 4 mim, (z) (z)
T-clipping in & norm
3: V = =ド==
Number of positive votes per label
4: yo =n-
5: for all labels i E [k] do
6:
if mmaxx (V7, V (O oT) < <T then
7:
Vi2 =1
Confident-GNMAR
8:
else
9:
VO +- V + +NO0 GG)
Add Gaussian noise for privacy protection
V < V1 N(0,
11:
if V V. then
Decide on the output vote
12:
13:
else
14:
V =
Algorithm Multi-label classification with 7-clipping in fi-norm from Private kNN by /Zhu al.
(2020).
Input: Data point x, clipping threshold Tı, Gaussian noise scale ag, teachers, each with model [x() E (0, 13 where j E [n]].
Output: Aggregated vector V E {0, 13 with V = 1 if returned label present, otherwise Vi = 0,
where E [k].
for all teachers j E do
2:
"y + min(1, [[5 (x)
r-clipping in & norm
3: Vl -E
Number of positive votes per label
4: vo =n- V1
5: po 10 +N(0 0G)
Add Gaussian noise for privacy protection
6: +V+++00 oG)
7: for all labels E [k] do
8:
if! 1/0 then
Decide on the output vote
9:
V
10:
else
11:
V =
41

---

Under review as a conference paper at ICLR 2022
L DATA-DEPENDENT PRIVACY ANALYSIS
Our binary voting mechanism does leverage both the smooth sensitivity and propose-test-relasee methods. For example, the Confident GNMax (proposed by Papernot et al. (2018) form of the
propose-test-reicase method described in Section 3.2 in (Vadhan 2017).
First explored by Cormode al. (2012). differential privacy guarantees be data-dependent. These guarantees can lead to better utility with long history, with several works using them (Cormode 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. PPapernot et al. (2018) provide 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 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.
42


Reviews:
[{"review_id": "vBuOXuHRb25", "reviewer": "Reviewer_jFrr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Differentially private multi-label classification is an interesting and well-motivated problem. \n\nThe Binary voting mechanism is quite naive in the sense that separating the problem into k separate elections, each to be evaluated in a differentially private manner (i.e., with Gaussian noise). It’s somewhat surprising that this seems to be optimal among the mechanisms (in the case where voters aren’t constrained in how many candidates they can approve) unless there is a lot of correlation between votes, at which point the (exponentially-sized?) powerset voting method becomes better. \n\nIs it correct to interpret the thresholds T in Definitions 4 and 6 as the cutoff point at which the sum term is at least n/2 (intuitively corresponding to a majority vote)? It could be useful to the reader to have a bit more explanation here.\n\nTo me, the most interesting contribution is that of \\tau voting, where all votes are assumed to have \\ell_2 norm at most \\tau. I have a few questions here: (1) how did you go about choosing \\tau in practice, and do you have proposals for how to choose it on new datasets; and (2) have you thought about an “average-case” approach where the average vote has \\ell_2 norm at most \\tau instead of requiring all votes to have \\ell_2 norm at most \\tau? \n\nI found the writing quality to have some issues (some minor comments below).\n\nMinor comments: \nDefine CaPC\nSection 2.2, CaPC paragraph: model's --> models\nSection 3.2, first paragraph: it is a popular method --> is a popular method\nBefore Definition 6: missing period\nThere are also many missing articles (a/an/the) throughout the paper", "summary_of_the_paper": "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.", "summary_of_the_review": "The problem is interesting and the results seem to be quite comprehensive. My main concern is that the voting mechanisms proposed are relatively naive (separate into independent elections or run one big single-winner election). However, the technical results seem robust.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "srV2CAbgb9", "reviewer": "Reviewer_3vmh", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Final update: After the discussion period, I still vote for rejection. There are two main reasons.\n1) The authors do not seem to understand the issue I raised and clarified over and over again. Now I started to doubt whether the algorithm implemented in the experiment is end-to-end differentially private with the designed privacy budget. (I) I do not agree that data-dependent privacy is a different privacy guarantee or a relaxed version of differential privacy. I believe it is not private and give my reasons through the Alice Bob example. I understand this is not the first paper to do it under data-dependent privacy and I have made it clear that I strongly disagree with all the other works especially Papernot et al. (II) The authors responded by citing the monograph by Dwork and Roth, which clearly shows that they do not understand the work they quoted and the issue I raised here. In the entire monograph, the differential privacy is based on the worst-case dataset (data-independent). The authors claim that \"data-dependent analysis is an improvement over propose-test-release\". The propose-test-release is an algorithm. The data-dependent privacy guarantee is a weak privacy notion. The data-dependent analysis referred to as data-dependent accuracy bound in this book is about utility analysis, not privacy. I do understand how privacy notion can be an improvement on an algorithm. Most importantly, this paragraph by Dwork and Roth is saying, you can improve your utility with local sensitivity because privacy has to be for the worst-case dataset, but the utility is only for the good dataset. Typically, to propose a private algorithm, you first prove the privacy for any dataset without any assumptions on the data and then prove the utility for some good datasets like Gaussian data. (This monograph explicitly used the word data-dependent **Accuracy** bounds not privacy bounds)  (II) The authors claim that they can fix it by controlling different numbers of queries. However, the authors did not formally prove it. More specifically, in the authors' data-dependent analysis, each query (each sample in the public unlabeled dataset) has a different privacy cost.  I do not see how Alice could determine the number of queries before running it. Now suppose the privacy budget is 10, and Alice has reached 9.9. when Alice found that her last query has privacy cost 0.2 and exceeds the overall privacy budget, she cannot hide it from the public anymore. Thus, the overall process would break the eps=10 privacy promise. I believe this is fixable since there is some new work on private hyper-parameter tuning. But like I said, the main point here is you have to prove it satisfies (data-independent)-DP. (III) My main concern is about the released data being non-private not the epsilon. (IV) The comparison with Bayesian DP is not helpful here. As long as you privacy depends on the dataset, the same problem arises here for both notions. That is why all the other privacy notions are all data-independent. \n\n2)The main contribution is to generalize PATE to multi-label. I think this is a valid problem setting. But the novelty is not enough for being a separate paper considering the fact that the three proposed methods are either minor modifications of prior works or simple generalizations of PATE. The tau mechanism is just a simple l2 generalization of Zhu et al 2019.\n\nUpdate: You are missing the point. Like I said previously, there are many ways to make a \"data-dependent mechanism\" be provably data-independently differentially private. As long as you can prove your end-to-end algorithm is eps-10 differentially private for any input dataset, then you can make the promise. But it is not here in the current version. For example, you could spend some budget checking the dataset first. If it is good, run your mechanism. If it is bad, output fail. And this is exactly propose-test-release. The methods I mentioned below are all end-to-end data-independently differentially private. You could run your algorithm on all the possible input dataset S and find the largest one, i.e. $\\max_S \\varepsilon(S)$. This would also satisfy data-independent DP. The point is you have to prove that your algorithm is data-independently DP. Alice as a privacy engineer cannot make any assumptions about the nature that generates the dataset. There is a nice blog post https://differentialprivacy.org/average-case-dp/. It has a discussion about the pitfalls of Bayesian DP, which is (in my opinion) similar to data-dependent DP (data-dependent DP: $\\varepsilon(S)$, Bayesian DP: $E_{S\\sim P}[\\varepsilon(S)])$, data-independent DP: $\\max_S\\varepsilon(S)$).  I believe the proposed algorithm in this paper can be proved to be data-independently private even without any change to the algorithm itself. You might want to prove the data-independent RDP of Confident GNMax. (Theorem B.2 is data-dependent). Another caveat I forgot to mention is about comparisons with other works. The gap between data-dependent DP and data-independent DP can be huge (also reported in this paper). It is really unfair to compare with data-independent DP methods like DP-SGD.\n\nUpdate regarding DP and data-dependent DP: This is already **irrelevant** to the contributions of this paper and the proposed algorithm since the proposed method can also be analyzed by traditional (data-independent) DP. First of all, I never claimed that the proposed algorithm is not differentially private(or completely vulnerable against membership inference attacks). And I never said data-dependent DP is not formal. My main concern is about the definition of privacy and the wording. My critique of data-dependent DP is based on the fact that this notion is a function of the dataset. Now suppose we are the nature that generates the dataset. Alice is the privacy engineer who runs some private algorithm and releases the output to the public. Bob is the adversary who tries to attack the sensitive information in the dataset with the released information. Differential privacy is a promise made by Alice to defend against attacks such as membership inference attack. Now when Alice claims that her algorithm is eps=10-DP. We would expect that the output to be eps=10-DP differentially private with respect to whatever the dataset we give to Alice. If not, the next time, when we generate a \"bad\" dataset such that it is not eps=10-DP, Bob can perform a membership inference attack with higher accuracy than promised by Alice. Stability-based methods/propose-test-release/smooth-sensitivity-based methods are all adaptive to the dataset by using local sensitivity but satisfy promised privacy budget for whatever input dataset. Different variations of differential privacy like RDP/CDP/zCDP are all with respect to any input datasets(data-independent). However, if you calculate and output an epsilon of your algorithm for a particular dataset (even if it is private with respect to the dataset), you get different epsilons for different datasets (even if you assume the same number of queries). Then how can you make that promise? This is why I believe data-dependent privacy notions are useless. You could and should get a tight and data-independent epsilon by exactly the same algorithm (Confident GNMax). Listing previous papers do not make things correct. Please answer my doubts directly. \n\nAfter the authors' response: 1) I understand this is not the main subject of this paper.  I still think data-dependent privacy is useless. Theoretically, you could come up with a mechanism and a dataset such that data-dependent epsilon is around 1 and data-independent epsilon is 1000, which is practically useless in defending say membership inference attack. I know this may raise some controversy since there are some prior works that compute some data-dependent epsilon, but I would like to emphasize that the reason why differential privacy is used as a gold standard for private data analysis is that it is a worst-case definition. 2) Overall, I think for this specific problem, this paper might be doing the correct thing with the correct analysis. But the technical contributions are not enough. \n\nStrengths: \n1. this problem is an extension of PATE to a multi-label setting, which is practically interesting. \n2. The authors compare three mechanisms empirically. The empirical analysis is solid.\n\nWeaknesses: \n1. Although the considered problem is practically useful, the proposition 3.1 and appendix A are not theoretically interesting. Basically it says there exists example such that the sensitivity is achieved. (Any private algorithm should have tight analysis of sensitivity) The authors claim that this shows binary mechanism is optimal. However, even for single winner setting, we do not know if Report noisy Argmax is optimal or not. (You could potentially improve it by stability-based methods/ propose-test-release, depending on the problems.)\n\n2. It would be better if this paper contains a preliminary section for \"data-dependent privacy bounds\". In general, differential privacy should not be data dependent. So I am a little bit confused when I first read this concept. If I understand this correctly, I think this is related to local sensitivity/ or stability based methods (see Section~3 of [1]). For example, when the top candidate and the second candidate has large gap (high consensus), the local sensitivity can be small. You could potentially improve it by stability-based methods. But the end-to-end algorithm must satisfy data-independent differential privacy.\n\n3. The emprical comparisons with DP-SGD is not fair. DP-SGD algorithms do not assume a public unlabeled dataset. I understand this comparison exists in prior works. It would be better if the authors could acknowledge it. \n\n4. The discussion about related work Zhu et al seems confusing. As far as I know, Zhu et al (2020) is also model agnostic. The only thing different from original PATE is that they replace teacher model with k nearest neighbor classifiers. Unlike DP-SGD, the privacy mechanism does not scale with the architecture of teacher models. Also the improvement of Tau mechanism is from l2 clipping, which is straightforward. As Zhu et al pointed out in their appendix, they do not use stability-based methods( or they called noisy screening/ Confident GNMax) because it is hard for a data sample to have high consensus for every label. I am just curious how this is resolved in this paper.\n\nSome minor comments:\n1. Is there a typo in equation (2)? I am a little bit confused about the brackets.\n\n[1] Vadhan, Salil. \"The complexity of differential privacy.\" Tutorials on the Foundations of Cryptography. Springer, Cham, 2017. 347-450.", "summary_of_the_paper": "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. ", "summary_of_the_review": "Although this is a good practical problem, I think this paper needs some revision.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cJdYz_ltou", "reviewer": "Reviewer_6iWo", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper is relatively clearly written (see also the \"Further comments\" part though)\n- The theoretical results related to privacy are interesting, and are discussed in sufficient depth and details.\n- The solutions are clean and reasonably simple.\n\nWeaknesses:\n- The MLC learning part is not treated carefully. First of all, the canonical MLC metrics are not calculated in the experiments. (In fact, they are not even discussed in the paper.) This is important though, because this is one of the crucial, distinctive aspect of MLC. Therefore, it is not clear, how the proposed solutions perform in terms of these metrics.\n- The proposed algorithms are not compared to the state of art MLC solutions, and thus we don't know how much we lose in terms of the MLC metrics when we want to DP guarantees.\n\nBecause of these two shortcomings, it is hard to assess the contribution of the paper. The main goal of the authors was to show how DP can be enforced in MLC but the results presented in the paper are not sufficient to draw any conclusion: although the DP requirements are analyzed, the MLC performance remains unclear.\n\nFurther comments:\n- The acronym CaPC is used already on p1, but is only explained on p3.\n- Why do you use different notations (d resp. X) for the same notion (datasets) in Def. 1 and Def. 2?\n- What does p_{M(X)}(\\theta) denote in Def. 2?\n- Shouldn't Lemma 2.2 be stated with an inequality?\n- Def. 4 mixes sets with their membership vectors. Which is fine, but this should be mentioned explicitly.\n- Def. 5 is confusing. The meaning of the math formulation is that there is no element appearing in each of the P_i sets, whereas the text means that the P_i sets are all disjoint.\n- Below Def. 6: \"For any mechanism f, \\Delta_p f 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.\" Aren't we supposed to work here with teacher votes that differ only by one bit?", "summary_of_the_paper": "The paper is proposing differential privacy (DP) solutions for multi-label classification (MLC). In particular, it introduces three novel noisy perturbation methods for the MLC setup, analyzes them in terms of DP, and test them experimentally for accuracy, AUC, and other metrics.", "summary_of_the_review": "The DP results are solid, but the MLC aspects of the work has serious shortcomings.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GYp1p0zMlwf", "reviewer": "Reviewer_Fb19", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper introduce mechanisms for private multi-winner voting and multi-label learning, which in important in machine learning. The paper structure and the writing are good. These three mechanisms are shown clear, but for the experiment, the choose of privacy term epsilon is somewhat larger than the common privacy requirements. ", "summary_of_the_paper": "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. \nThey 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. \n", "summary_of_the_review": "It's good but may be not enough", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "88glTCoYVc8", "reviewer": "Reviewer_47xz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The authors consider an interesting problem as designing a privacy preserving mechanism with multi-label outcomes would be applicable in many contexts.\n- I also like the design choices as the proposed mechanisms can be easily implemented with existing DP aggregation mechanisms like PATE. Moreover, the theoretical bounds can be derived by building on top of the existing DP guarantees.\n\nWeaknesses:\n- As far as I understand, the parameter $\\tau$ in the $\\tau$-voting needs to be set based on the domain and there is no automatic way to choose a value.\n- Powerset voting becomes intractable to implement when $k$ is large. But probably there is a way to combine $\\tau$-voting and the powerset voting for large values of $k$.\n\nSome questions for the authors.\n1. From definition 3, it seems like the threshold T is independent of the candidate $i$. However, in definition 4, the constant $T$ depends on the index $i$ and it seems that the mechanism picks an index whose votes exceed $n/2$ (upto noise). So I think the presentation and the definition here is misleading.\n2. How do you define the threshold $T$ in definition 7?\n3. I think there is a range of design options between $\\tau$-voting and powerset voting. For example, you can ask each voter to vote on the best subset of size b. Did the authors consider other alternatives?\n\n", "summary_of_the_paper": "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. \n\nBinary 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.\n\nThe 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.", "summary_of_the_review": "I think the paper considers an important problem as the design of differentially private aggregation mechanism for multi-label outcomes is applicable in a lot of domains. The proposed mechanisms are also simple and build on top of the existing DP aggregation mechanisms. However, I felt that the experiments were not quite exhaustive. For example, it's not clear if it is beneficial to apply powerset voting on real datasets.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an interesting paper discussing differential privacy for multi-label classification. The initial reviews rated the paper with rather extreme scores, therefore I have invited an additional reviewer. This review did not clarify the issues raised by the most critical reviewer, but pointed out that the goal of showing how DP can be enforced in MLC is not fully obtained as there is a lack of the discussion concerning the MLC performance. This is also a problem raised in my comments. Taking this into account, I need to state that the paper is not ready for publication.
Decision: Reject