Incentives in Private Collaborative Machine Learning
Authors: Rachael Hwee Ling Sim
Yehong Zhang
Trong Nghia Hoang
Xinyi Xu
Bryan Kian Hsiang Low
Patrick Jaillet
Venue: NeurIPS 2023 poster (2023)
Keywords: Incentives
Privacy
Shapley fairness
Collaborative machine learning
data valuation
reward
sufficient statistics
TL;DR: We propose how to value and reward parties while ensuring incentives like individual rationality, fairness and privacy (but deter excessive privacy demands).

Abstract: Collaborative machine learning involves training models on data from multiple parties but must incentivize their participation. Existing data valuation methods fairly value and reward each party based on  shared data or model parameters but neglect the privacy risks involved. To address this, we introduce _differential privacy_ (DP) as an incentive. Each party can select its required DP guarantee and perturb its _sufficient statistic_ (SS) accordingly. The mediator values the perturbed SS by the Bayesian surprise it elicits about the model parameters. As our valuation function enforces a _privacy-valuation trade-off_, parties are deterred from selecting excessive DP guarantees that reduce the utility of the grand coalition's model. Finally, the mediator rewards each party with different posterior samples of the model parameters. Such rewards still satisfy existing incentives like fairness but additionally preserve DP and a high similarity to the grand coalition's posterior. We empirically demonstrate the effectiveness and practicality of our approach on synthetic and real-world datasets.

Incentives in Private Collaborative Machine Learning
Rachael Hwee Ling Sim Yehong Zhang", Trong Nghia Hoang?
Xinyi Xu' BBrynn Kian Hsiang Low', and Patrick Jaillet*
Department of Computer Science, National University of Singapore. Republic Singapore Peng Cheng Laboratory, People's Republic of China
School Electrical Engineering and Computer Science, Washington State University, USA Dept. of Electrical Engineering and Computer Science, MIT, USA {rachaels, xxbinayyysxxxiiii Lowwkhwwoooognn mus. edu. sg, "zhangyh020pcl.co ac.
3 trongnghia. hoang@wsu. edu, "jaillete welleeeemit...... edu
Abstract
Collaborative machine learning involves training models on data from multiple parties but must incentivize their participation. Existing data valuation methods fairly value and reward each party based on shared data or model parameters but neglect the privacy risks involved. To address this, we introduce differential privacy (DP) as an incentive. Each party can select its required DP guarantee and perturb its sufficient statistic (SS) accordingly. The mediator values the perturbed ss by the Bayesian surprise it elicits about the model parameters. As our valuation funetion enforces a privacy-valuation excessive DP guarantees that reduce the utility of the grand coalition's 's model. Finally, the mediator rewards each party with different posterior samples of the model parameters. Such rewards still satisfy existing incentives like fairness but additionally preserve DP and a high similarity to the grand coalition's 's posterior. We empirically demonstrate the effectiveness and practicality of our approach on synthetic and real-world datasets.
valuation trade-off. parties are deterred from selecting
Introduction
Collaborative machine learning (ML) seeks build MI. models of higher quality by training more data owned by multiple parties [47] (62]. For example, a hospital can improve its prediction of disease progression by training on data collected from more and diversified patients from other hospitals [6]. Likewise, a real-estate firm can improve its prediction of demand and price by training on data from others (9. However, parties have two main concerns that discourage data sharing and participation in collaborative ML: (a) whether they benefit from the collaboration and (b) privacy.
Concern (a) arises each party would expect the significant cost that it incurs collect and share data (c.g., the risk of losing its competitive edge) to be covered. Some existing works [T] among other data valuation methods! have recognized that parties require incentives collaborate, such as a guaranteed fair higher reward from contributing more valuable data than the others, an individually rational higher reward from collaboration than in solitude, and higher total reward (i.e., group welfare) whenever possible. Often, parties share and are rewarded with information (e.g., gradients (88 or parameters [47 of parametric ML models) computed from the shared data. However, these incentive-aware reward schemes expose parties to privacy risks.
Data valuation methods study how much data is worth. explained in a party's data first valued independently using performance metric (e.g., see Def. (.. and then relative to data contributed by others (e.g., Shapley value (Sec. 4)) The latter value is helptul to (i) model interpretability and (ii) deciding how much to compensate the data owners
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

On the other hand, some federated learning (FL) works [4] have addressed the privacy concern (b) and satisfied strict data protection laws (e.g.. European Union's General Data Protection Regulation) by enforcing differential privacy (DP) [ 36 during the collaboration. Fach party injects noise before sharing information to ensure that its shared information would not significantly alter a knowledgeable collaborating party's ' or mediator's s belief about whether datum was input to the algorithm. Injecting more noise leads to a stronger DP guarantee. As raised in [64], adding DP can invalidate game-theoretic properties and hence affect participation. For example, in the next paragraph, we will see that adding DP may lead to the collaboration being perceived as unfair and a lower group welfare. However, to the best of our knowledge (and as discussed in Sec. 7 and Fig. E there are no works that address both concerns, i.e., ensure the fairness, individual rationality, and group welfare incentives (see Sec. D. alongside privacy. Thus, we aim to fill in this gap and design an incentive-aware yet
reward scheme by addressing the following questions:
If a party (e.g,, hospital) requires a stronger DP guarantee, what should the impact be on its valuation and reward? Our answer that, on average, its valuation and reward should decrease. Intuitively, it is unfair when this party gets a higher valuation due to randomness in the DP noise. More importantly parties require guaranteed higher rewards to consider a weaker privacy guarantee 22 64 which will help maximize the utility of the collaboratively trained model(s). As observed in 14 65]. the weaker the DP guarantee, the smaller the loss in model accuracy from enforcing DP. Thus, we will (i) assign value to each party to enforce parties against unfetteredly selecting an excessively strong DP guarantee H and (ii) flexibly allow each party to enforce different DP guarantee without imposing party's 's need for strong DP on others. This new perspective and its realization is our main contribution.
prrvacy-valuation trade-off and incentivize
To enforce privacy-valuation trade-off, how should DP be ensured and party's data be valued (Sec.By) B] Initially, valuation using validation accuracy seems promising as the works of [8 25 have empirically shown that adding noise will decrease the valuation. However, parties may be reluctant to contribute validation data due to privacy concerns and disagree on the validation set as they prioritize accurate predictions based on the quality of inference of the model parameters under DP. Bayesian inference is a natural choice as it quantifies the impact of (additional DP) noise. In Sec. 2 we will explain how each party ensures DP by only sharing perturbed sufficient statistic (SS) with the mediator. The mediator values the perturbed SS by the surprise it elicits relative to the prior belief of model parameters. Intuitively, noisier perturbed SS is less valuable as the posterior belief of the model parameters will be more diffuse and similar to the prior. As parties prioritize obtaining a model for future predictions and may face legal/decision difficulties in implementing monetary payments, we reward each party with posterior samples of the model parameters (in short, model reward) instead.
different inputs (e.g.. patient demographics). So. we revert to valuing parties
How should the reward scheme be designed to satisfy the aforementioned privacy, individual rationality, and fairness incentives (Sec. ?)? Our scheme will naturally satisfy the privacy incentive as any post-process processonn of the perturbed SS will preserve DP. To satisfy fairness and individual rationality. set the target reward value for every party using p-Shapley value [47]. Lastly, to realize these target reward values, how should the model reward be generated for each party (Sec.5)) Instead of rewarding all parties with samples from the same (grand coalition's 's) posterior of the model parameters given all their perturbed SS (which would be unfair if their valuations differ), our reward control mechanism generates a different posterior for each party that still preserves high similarity to the grand coalition's 's posterior. Concretely, the mediator scales the SS by factor between and before sampling to control the impact of data on the posterior (by tempering the data likelihood). Scaling the SS by a factor of 0, 1, and between 0 and yield the prior, posterior, and their interpolation, respectively. We then solve for the factor to achieve the target reward value.
By answering the above questions, our work here provides the following novel contribution
A new vallaccyvlluatin trade-off criterion for valuation functions that is provably satisfied by the combination of our Bayesian surprise valuation function with DP noise-aware inference (Sec. 3
New incentives including DP (while deterring excessive DP) and similarity to grand coalition model (Sec. 4
"The work of (30) describes problems posed by excessive data privacy and "the need to balance privacy with fuller and representative data collection" " (instead of privileging privacy). But, parties are still free to seek DP. See App. for the key differences of our work here vs. data valuation and DP/FL works.
2

---

Reward control mechanisms (Sec. 5 to generate posterior samples of the model parameters for each party that achieve a target reward value and the aforementioned incentives; one such mechanism tempers the likelihood of the data by scaling the SS and data quantity.
2 Collaborative ML Problem with Privacy Incentive
Our private collaborative ML. problem setup comprises mediator coordinating information sharing, valuation, and reward, and n parties performing a common ML task (e.g.. predicting disease progres- sion). Let the set N _ {1,...,' n denote the grand coalition of n parties. Each party i owns a private dataset D; which cannot be directly shared with others, including the mediator. What alternative information should each party provide to the mediator for collaborative training of an ML model?
To ease aggregation, this work focuses only Bayesian models with sufficient statistic (SS), such as exponential family models [5). Bayesian linear regression [39], and generalized linear models, including Bayesian logistic regression [2] (with approximate SS).
The statistic s; is a SS for the dataset D; the model parameters 9 and dataset D, are conditionally independent given 8,, i.e., p(0) s,, D.) p(0) s.).
Definition 2.1 (Sufficient Statistic (SS) 48 52
We propose that each party i shares its SS s, for and in place of its dataset D; to protect the privacy of Dj. We assume that the parties have agreed to adopt a common Bayesian model with the same prior p(0) of model parameters 0, and each party i's dataset 'D; is independently drawn from the likelihood (() that is conjugate to the prior p(0) (i.e., belonging to an exponential family). The mediator can compute the posterior belief
(Dx > of model parameters @ given the grand coalition N's datasets using function fo of the sum over shared SS: ((((())))eN) x p(0) fo(Eie 8;). We give concrete example and the mathematical details of SS in Apps. A. and respectively.
Privacy Incentive. However, sharing the exact SS AN - {si)ieN will not ensure privacy as the mediator can draw inferences about individual datum in the private datasets DN - {D.JieN To mitigate the privacy risk, each party should choose its required privacy level 6; and enforce (X, (x,4)) Ré)né differential privacy In Def. 2.2 smaller 6 corresponds to stronger DP guarantee
Definition 2.2 (Rényi Differential Privacy (DP) 38 randomized algorithm R D - o (A. Rénny differentially private if for all neighboring datasets D and D', the Rényi divergence of orde is (D) || R(D")) S..
0
Party i can enforce (example-level) D (), DP by applying the Gaussian mechanism: It generates perturbed SS o; _ s, 2; by sampling Gaussian noise vector z, from the distribution p(Z,) = (O, 0.5 (A/ea) (3(g)) I) where (2
g) is the squared fz-sensitivity" of the function g that maps the dataset D; to the SS 8;. We choose Rényi DP over the commonly used (e, 6DP as it gives a stronger privacy definition and allows a more convenient composition of the Gaussian mechanisms
38 as explained in App. A.2
Each party i will share (i) the number A |D: of data points in its dataset D., (ii) its perturbed SS o, 5 and (iii) its Gaussian distribution p(z;) with the mediator. As DP algorithms are robust to post-processing, the mediator's subsequent operations of o; (with no further access to the dataset) will preserve the same DP guarantees. The mediator uses such information to quantify the impact of the DP noise and compute the DP noise-award posterior p(0) via Markov Chain Monte
Carlo (MCMC) sampling steps outlined by 3 27
In this section, we have satisfied the privacy incentive. In Sec. we assign a value te to each coalition C' C N's perturbed SS oc - (o, that would decrease, on average, as the DP guarantee strengthens. In Secs. 4 and 5 we outline our reward scheme: Each party will be rewarded with model parameters sampled from (0) (in short, model reward) for future predictions with an appropriate reward value r; (decided based on (UC)CCN) to satisfy collaborative MIL incentives (e.g.. individual
we will define/explain the DP-related concepts and other DP notions. "A benefit of sharing perturbed SS is that each party only incurs the privacy cost once regardless of the number samples drawn or coalitions considered.
$ 'Parties agree on X. In App. A.2
'Here, o, should be interpreted as random vector taking the value of its sample. Non- con-noise-awar inference incorrectly treats o, and computes p( o. oieie)) instead. See App.
3

---

rationality, fairnsss). Our work's 's main contributions, notations, and setup are detailed in Fig. main steps involved are detailed in Algo.
The
inference, Boyestan surprise,
compune
Want better model r,
l
strogerr privacy
of overcuttin
Perturbed
Every other party its (0p Gr p(Z))
Data quantity,
DP noise distribution, p(Z))
Rewarded model parameters drawn from (()))
Achieves a fal,, rational target reward value /
Ensures (2, 6)) DP for any other party
Is similar to the grand coalition's posterior (See Fig. 7)
Shapley fairness, DP poss processing, scale 58 temper data likelihood
Figure An overview of our private collaborative ML problem setup from party i's perspective and our novel contributions (ideas in blue, novel combination of solutions in blue). We (i) enforce privacy-reward trade-off (using each party i's desire for a higher-quality model reward in collaborative ML) to deter party from infetteredly/oveecaatttus// selecting excessive DP guarantee (small cs), (ii) ensure DP valuation and rewards, and (iii) preserve similarity of its model reward ((()) to the grand coalition N's posterior p(0lox) to achieve a high utility.
3 Valuation of Perturbed Sufficient Statistics
The perturbed SS oc of coalition C' is more valuable and assigned higher value ve if it yields model (in our work here, the DP noise-awar awarr posterior p(f)oc)) )) of higher quality. Most data valuation methods [24] 18 63 measure the quality of an ML model by its performance on a validation set. However, may be challenging for collaborating parties (e.g., competing healthcare firms) to create and agree on large, representative validation set as they may prioritize accurate predictions on different inputs (e-g. patient demographics) 47). The challenge increases when each firm requires privacy and avoids data sharing. Other valuation methods 47 [5] have directly used the private inputs of the data (e.g., design matrix). Here, we propose to value the perturbed SS og of coalition C based on the surprise [23] that it elicits from the prior belief of model parameters, as defined below: Definition 3.1 (Valuation via Bayesian Surprise). The value of coalition C or its surprise uo is the KL divergence DKL (p(OO)c): p(O)) between posterior p(Oloc) vs. prior p(0).
From Def. 3.1 greater surprise would mean that more bits will be needed to encode the information in p(0 oc) given that others already know p(0). Otherwise, a smaller surprise means our prior belief has not been updated significantly. Moreover, as the valuation depends on the observed oc- the surprise elicited by the exact SS and data points will indirectly influence the valuation. Next, by exploiting the equality of the expected Bayesian surprise and the information gain on model parameters 0 given perturbed SS oc (i.e., Eoc [vc] = I(0; oc)), we can establish the following essential properties of our valuation function:
VI Non-negativity. AC Ç N Voc 2 0. This is due to the non-negativity of KL divergence.
V2 Party monotonicity. In expectation w.r.t. oc, adding a party will not decrease the valuation: VC C' C Bog [vor] 2 Fog [vc] The proof (App. C.I uses the "information never hurts" property.
V3 Privacy-valuation trade-off. When the DP guarantee is strengthened from e, to a smaller ef and independent Gaussian noise is added to o, to generate of, in expectation, the value of any coalition C' containing will strictly decrease: Let vi denote the value of coalition C with the random variable and realization of o; replaced by of Then, (i E C'A(E, < <e,) + Eoc [vc] Eog lvål
The proof of V3 (App. CT independence between and of given Together, these properties address an important question of how to ensure DP and value a party's data enforce a privacy-valuation trade-off (Sec. [T]. Additionally, in App. C.2 we prove that in expectation, our Bayesian surprise valuation is equivalent to the alternative valuation that measures the similarity of p(0loc) to the grand coalition N's DP noise-aware posterior p.
uses the data processing inequality of information gain and the conditional

---

Implementation. Computing the Bayesian surprise valuation is intractable since the DP noise-aware posterior oc) and KL divergence from p(0) do not have closed-form expression. Nonetheless. there exist approximate inference methods like the Markov chain Monte Carlo (MCMC) sampling to estimate p(() (c) efficiently, as discussed in App. A.3 As our valuation function requires estimating the value of multiple coalitions and the posterior sampling step is costly, we prefer estimators with a low time complexity and a reasonable accuracy for a moderate number m of samples. We recommend KL estimation to be performed using the nearest-neighbors method [45) and repeated and averaged to reduce the variance of the estimate (see App. C.3 for a discussion). The nearest-neighhor KL estimator is also asymptotically unbiased: drawing more samples would reduce the bias and variance of our estimates and is more likely to ensure fairness - for example, party i's sampled valuation is only larger than j's if i's true valuation is higher.
Remark. Our valuation is based on the submitted information {cz, Os pl Ze) without verifying or incentivizing their truthfulness. We discuss how this limitation is shared by existing works and can be overcome by legal contracts and trusted data- sharing platforms in App.
4 Reward Scheme for Ensuring Incentives
After valuation, the mediator should reward each party i with model reward (i.e., consisting of samples from (f)) for future predictions. Concretely, (f) is a belief of model parameters after learning from the perturbed SS ON- As in Sec. [3] we value party i's model reward as the KL
divergence from the prior: r; A DRL. (q: (0); The mediator will first decide the target reward value r for every party E N using ("C JCCN to satisfy incentives such as fairness. The mediator will then control and generate a different 9: for every party i N such that r; -r using reward control mechanisms from Sec. [3] We will now outline the incentives and desiderata for model reward (0) and reward values r; and r3 for every party i Nwhen the grand coalition forms
PI Ueaaiiiibility. In party i's reward, any other party k is still guaranteed at least its original (x, 4x)-DP guarantee or stronger. The implication is that the generation of party i's reward should not require more private information (e.g., SS) from party k.
P2 Efficiency.
There is party i N whose model reward the grand coalition N's posterior, i.e., (0) p(O)ox). It follows that r; UN P3 Fairness.
The target reward values Jee) must consider the coalition values {uCJogN and satisfy properties FT 14 given in 47 and reproduced in App. D.2 The monotonicity axiom F4] ensures using a valuation function which enforces that privacy- trade-off off will translate to a privacy-reward trade-off and deter parties from selecting excessive DP guarantees.
P4 Individual Rationality. Each party should receive model reward that is more valuable than the model trained on its perturbed SS alone: Vi E N r 2 0;-
P5 Similarity to Grand Coalition's Model. Among multiple model rewards (0) whose value тi equates the target reward ri. we secondarily prefer one with a higher similarity rf = -DL (p(flon): ); q: (0)) to p(0)ox)
P6 Group Welfare. The reward scheme should maximize the total reward value Σi= T to increase the utility of model reward for each party and achieve the aims of collaborative MI.
Choice of desiderata. We adopt the desiderata from [77 but make PI and P2 more specific (by
considering each party's 's actual reward q: (0) over just its values r; and UN) and introduce P5 Firstly, for our Bayesian surprise valuation function, the feasibility constraint of 47 is inappropriate as removing a party or adding some noise realization may result in r; > uN P so we propose (P1 instead. Next, we recognize that party is not indifferent to all model rewards q, (0) with the same target reward value as they may have different utility (predictive performance). Thus, we propose our more specific P2 and a secondary desideratum P5
As P5 is considered after other desiderata, it does not conflict with existing results, e.g., design for (r) keN to satisfy other incentives.
Remark on Rationality. In P4 a party's model reward compared to the model trained its perturbed SS instead of its exact SS alone. This is because the mediator cannot access (and value the model
See App. D.1 for the modifications needed when the grand coalition does not form. $ "Exeectation propagation, a common approximate inference technique, also maximizes r/. 5
The valuation fn. is only monotonic in expectation V2 V3 See further discussion in App. Question 9.
5

---

trained on) the private exact SS. Moreover, with no restrictions on the maximum DP noise, the value of some party's exact SS may exceed the grand coalition's 's perturbed SS when parties require strong DP guarantees. P4 is sufficient when parties require DP when alone to protect data from curious users of their MI. model 1 27 For example, hospital may not want doctors to infer specific patients' data. When parties do not require DP when alone, our reward scheme cannot theoretically ensure that the model reward from collaboration is better than using the exact SS. We further discuss this
limitation in App. D.3
Design of (r.) To satisfy the desiderata from (including our fairesss P3 and ratio- nality P4 incentives), we adopt their p-Shapley fair reward scheme with p E [0,1] that sets
r = ( maxkeN ox)" with Shapley value 10 oe (1/n) Eogra ((a))) (*cu()) - -c)
Shapley value's consideration of marginal contribution (MC) to all coalitions is key to ensuring strict desirability F3 such that party i obtains a higher reward than party k (despite eq = v.. if i's perturbed SS adds more value to every other non-empty coalition. Applying Theorem of 47], the mediator should set p between 0 and min log(u,/uu (g(u:/UN), (tx)/lo((d /log(ée/ max; Φx) to guarantee rationality, Selecting a larger p incentivizes a party with high-qualit perturbed SS share by fairly limiting the benefits to parties with lower-quality ones. Selecting smaller p reward parties more equally and increase group welfare [66] Refer to Sec. 4.2 of [4 for a deeper analysis of the impact of varying p.
These results hold for any choice of (X, G).
After explaining the desiderata for model reward (() and reward values 77 and rg for every party i E N, we are now ready to solve for (0) such that r2 re.
5 Reward Control Mechanisms
This section discusses two mechanisms to generate model reward (0) with different attained reward value r; for every party E N by controlling a single continuous parameter and solving for its value such that the attained reward value equates the target reward value: r; rī- We will discuss the more obvious reward mechanism in Sec. 5. reward mechanisms do not request new information from the parties; thus, the DP post- processcenssngg property applies, and every party lo is still guaranteed at least its original DP guarantee or stronger in all model rewards (i.e.. P holds).
Sec.5.1 to contrast its cons with the pros of that in Sec. 5.2 Both
5.1 Reward Control via Noise Addition
The work of 47
controls the reward values by adding Gaussian noise the data outputs. We adapt it such that the mediator controls the reward value for party i E N by adding Gaussian noise to the perturbed SS of each party E N instead. To generate the model reward for party (superscripted), the mediator will reparameterize the sampled Gaussian noise vectors {el ~ ~NO0, I) TEN to generate the further perturbed S
on + (0.5 ( A3()))))))))))))) T:) 1/2
KEN
where A3(gk) the squared fe-seiiitvv of function Ik that computes the exact SS sy from dataset DE (Sec. D. Then, the mediator rewards party i with samples of model parameters 0 from the new DP noise-aware aware posterior 9: (0) = p(0tt ).))
Here, the scalar T; 2 0 controls the additional noise variance and can be optimized via root-finding to achieve r; r The main advantage of this reward control mechanism is its interpretation of strengthening party k's DP guarantee in all parties' model rewards (see PT For example, it can be derived that if e = oc, then party k will now enjoy (A, 1/T,)-DP guarantee in party i's reward instead. If E < co. then party k will now enjoy a stronger (A, e + Tre)))-DP guarantee since <x/(1 + T3E2)= EG.
However, this mechanism has some disadvantages. Firstly, for the same scaled additional noise variance Tú, using different noise realizations {cl hEE will lead model reward (() with varying
Party i's MC some coalitions and Shapley value oi may be negative, which results in unusable negative/undefined rf. This issue can be averted while preserving P3 by upweighting non nogatvettive MC's such as to the empty set. 'oo ease notation, we slightly abuse ti represent both random vector and its sample.

---

similarity rf to the grand coalition Nss posterior. The mechanism cannot efficiently select the best model reward with higher r ( Secondly, the value of ri computed using such ti may be non- monotonic P in Tj (see Fig. 20), which makes it hard to bracket the smallest root Tı that solves for = r. To address these disadvantages, we will propose the next mechanism.
5.2 Reward Control via Likelihood Tempering
Intuitively, a party who assigned a lower target reward value rf UN should be rewarded with posterior samples of model parameters 0 that use less information from the datasets and SS of all parties. Sparked by the diffuse posterior algorithm [T6], we propose that the mediator can generate such "less informative" samples for party i using the normalized posterior 13
(0) x p(0) [p()x
(I)
involving the product of the prior p(0) and the data likelihood p (0) to the power of (or, said in another way, tempered by a factor of) Kę Notice that setting K; 0 and K; 1 recover the prior p(0) and the posterior p(0) Dx)), respectively. Thus, setting K; E (0, 1) should smoothly interpolate between both. We can optimize K; to control qe (0) so that ri = r VN.
But, how do we temper the likelihood? We start by examining the easier, non-private setting. In See.2 we stated that under our assumptions, the posterior p [x)) can be computed by using the sum of data quantities {ck JEEN and sum of exact SS 8N In App. E, we further show that using the tempered likelihood [p(Dx(0)]* is equivalent to scaling the data quantities and the exact SS SN by the factor K; beforehand. In the private setting, the mediator can similarly scale the data quantities, the perturbed SS in ON (instead of the inaccessible exact SS), and the fg-sensitivity by the factor K; beforehand; see App. E.3 for details. This likelihood tempering mechanism addresses both disadvantages of Sec. 5.1
There is no need to sample additional DP noise. We empirically show that tempering the likelihood produces model reward that interpolates between the prior posterior (in App. G and preserves a higher similarity r to the grand coalition N's posterior (P5 and hence, more group welfare P6) and better predictive performance than noise addition (see Sec. (
Using a smaller tempering factor E [0, 1] provably decreases the attained reward value r; (see App. B.. Thus, as the relationship between r; and k; is monotonic, we can find the only root by searching the interval [0, IJ.
Remark. Our discussion on improving the estimate of ve in the paragraph on implementation in Sec. 3 also applies to the estimate of T3 in Secs. [.]] and [5.2] Thus, solving for or K2 to achieve ri r using any root-finding algorithm can only be accurate up to the variance in our estimate.
Experiments and Discussion
This section empirically evaluates the privacy-valuation and privacy-reward trade-offs (Sec. 6.1. reward control mechanisms (Sec. (6.2), and their relationship with the utility of the model rewards (Sec. 6.3). (Sec.66.3). The time complexity of our scheme is analyzed in App. F and baseline methods are discussed in App. H.3 We consider Bayesian linear regression (BLR) with unknown variance on the Syn and CaliH datasets, and Bayesian logistic regression on the Diab dataset with collaborating parties (see App. H.l A for details) and enforce (2, 6,) R-)-ééni i DP. For Synthetic BLR (Syn), we select and use a normal riverse-gamma distribution (i) to generate the true regression model weights, variance, and 2D-dataset and (ii) as our model prior p(0). We consider 3 parties with C1 = 100, as in 47, 60% of the CaliH data is deemed "public/historic" and used to preitrain a neural network without DP. Real estate firms may only care about the privacy of their newest transactions. As the parties' heatures-house values relationship may differ from the "public" dataset, we do transfer learning and selectively retrain only the last layer with BLR using the parties' data. Parties I to have,
22 200, C3- 400 data points, respectively. For Californian Housing dataset (CaliH)
"Increasing 7: (i.e.. using ti that diverges more from st.) can instead increase the surprise: The privacy- valuation trade-off (Sec. 3 only holds in expectation across all noise and SS realizations.
"The normalized posterior is also known as the power posterior. (37) discuss useful interpretation and benefits such as syuthetically reducing the sample size, increasing the ease of computation/MCMC mixing and robustness model misspecifications.
7

---

MA
10
0.5
0.5
10
(c) Ne. T5
(a) Syn
Cahll
Diah
(1)
(Non-monotonic in 7g)
(Monotonic in T2)
Figure (a-c) Graphs party 2's valuation b2. Shapley value Φ2. attained reward value r2 vs. privacy
guarantee for various datasets. (d-e) Graphs of attained reward value vs. (Sec. 5.2 and тą (Sec. 5.1 for 2 different noise realizations. (f) Graph of similarity ry grand coalition N posterior O[ vs. r; for Syn dataset corresponding to (e).
respectively, 20%, 30%, and 50% of the dataset with 6581 data points and 6 features. For PIMA Indian Diabetes classification dataset (Diab) [50]. we use Bayesian logistic regression model to predict whether a patient has diabetes based on sensitive inputs (e.g.. patient's age, BMI, number of pregnancies). To reduce the training time, we only use the PCA main components features (to generate the approximate SS) 227 Parties 1, 2, and 3 have, respectively, 20%, 30%, and 50% of the dataset with 614 data points. As we are mainly interested in the impact of one party controlling its privacy guarantee E,, for all experiments, we only vary party 2's from the default 0.1. We fix the privacy guarantees of others (ej é3 0.2) and 0.2 in the p-Shapley fair reward scheme, and analyze party 2's reward and utility. Note that as e2 increases (decreases), party 2 becomes the most (least) valuable of all parties.
6.1 Privacy-valuation and Privacy-reward Trade-offs
For each dataset, we only vary the privacy guarantee of party [0.004, 0.02, 0.1, 0.5, 2.5, 12.5) and use the Gaussian mechanism and fixed random seed to generate the perturbed SS 02 from the exact SS 82. Fig. Pp-c plot the mean and shades the standard error of U/ UN. 6i, and over 5 runs. The privacy-valuatie As the privacy guarantee weakens (i.e., é2 increases), party 2's valuation 12, Shapley value Φ2, and attained reward value increase. When é2 is large, party 2 will be the most valuable contributor and rewarded with p())or), hence attaining r; = UN. App. H.5 shows that the trade-offs do not hold for non-noise-an aware inference.
2 with E2
and privacy-rewart trade-offs can be observed:
6.2 Reward Control Mechanisms
We use the Syn experiment to compare the reward mechanisms that vary the noise addition using (Sec.5. 5.1) vs. temper the likelihood using K; (Sec. (.2c. The mechanisms control (0) (i.e., used to generate party i's model reward) to attain the target reward values. For each value of 7; and R; considered, we repeat the posterior sampling and KL estimation method 5 times. Figs. 2 and 2 use different sets sampled noise (ef KEN to demonstrate the stochastic relationship between and т, In Fig. 21, the non-monotonic disadvantage of noise addition can be observed: As т; increases, r; does not consistently decrease, hence making it hard to solve for the smaller т; that attains r 3. In contrast, Kù decreases from 1, r; consistently decreases. Furthermore, in Fig. 2). we demonstrate the other advantage of likelihood tempering: For the same rú, tempering the likelihood leads to a higher similarity r to the posterior p(Olow) than noise addition. In App. H.6 we report the relationship between F3 vs. Ki and т; for the other real-world datasets.
6.3 Utility of Model Reward
The utility (or the predictive performance) of both Bayesian models can be assessed by the mean negative log probability (MNLP) of a non-private test set 15) In short, MNLP reflects how unlikely the test set is given the perturbed SS and additionally cares about the umcertainty/confidencc in the model predictions (e.g., due to the impact of DP noise). MNLP will be higher (i.e., worse) when the model
MWe defer analysis valuation function (e.g., impact varying coverage of input space) to App. H.4 Such test set is hard obtain practice and are only using for evaluation purposes.

---

0.0
MNLE
0.00
(8) Syn (VS.
(b) CaliH (vs.
(0) Diab (vs. 62)
(d) Syn (v) CaliH (VS. r
(1) Diab (vs.
Figure 3: (a-c) Graphs of utility party 2's model reward measured by MNLP, vs. privacy guarantee 6g for various datasets. (d-f) Graphs of utility of model reward measured by MNLP, attained reward value rę under the two reward control mechanisms for various datasets.
more uncertain of its accurate predictions or overconfident inaccurate predictions on the test set; see App. H.2 for an in-depth definition.
Privacy trade-offs. Figs. - illustrate the privacy-utility trade-off described in Sec. 1 As e2 decreases (i.e., privacy guarantee strengthens), the MNLPx of grand coalition N's collaboratively trained model and the MNLPP, of party 2's individually trained model generally increase, their utilities drop (t). This motivates the need to incentivize party 2 against selecting an excessively small e2 by enforcing privacy-valuation and privacy-reware trade-off's. From Figs. Ba-c, the impact of our scheme enforcing the trade-off's can be observed: As decreases, the MNLP, of party = 2's model reward increases.
Remark. In Fig.Bh. B. an exception to (f) is observed. The exception illustrates that the privacy- valuation trade-off may not hold for valuation function based on the performance a validation set.
Individual rationality. can be observed from Figs. - that as <2 decreases, the MNL.P, of party i == 2's model reward increases much less rapidly than the MNLP; of its individually trained model. So, is rational for party = 2 to join the collaboration to get a higher utility.
Remark. Party i = 2's utility gain appears small when 62 is large due to parties 1 and 3's selection of strong privacy guarantee e 0.2. Party can gain more when other parties require weaker privacy guarantees such as e 2 instead (see App. H.S
Likelihood tempering is better reward control mechanism. Extending Sec. 6.2
compare the utility of party i's model reward generated by noise addition vs. likelihood tempering in Figs.Btt Across all experiments, likelihood tempering (with x;)) gives (i) lower MNLP, and hence higher utility, and (ii) lower variance in MNLP, than varying the noise addition (with Tz).
7 Related Works
Fig. 5 in App. ggives diagrammatic overview showing how our work fills the gap in existing works.
Data Valuation. Most data valuation methods are not differentially private and directly access the data. For example, computing the information gain [47] or volume [59] requires the design matrix. While possible make these valuation methods differentially private (see App. H.3) or value DP trained models using validation accuracy (on an agreed, public validation set), the essential properties of our valuation function V2 V3) may not hold.
Privacy Incentive. Though the works of (00 600 reward parties directly proportional to their privacy budget, their methods do incentivize data sharing as party does not fairly receive higher reward value for contributing larger, more informative dataset. While the work of (28) artificially creates privacy-reward trade-off by paying each party i the product of its raw data's ' Shapley value Φ; and monotonic transformation of 6; it neither ensures DP w.r.t. the mediator nor fairly considers how stronger DP guarantee may reduce party i's marginal contribution to others (hence Φi). The work of 13 considers data acquisition from parties with varying privacy requirements but focuses on mean estimation problem and designing payment and privacy loss functions to get parties to report their true unit cost of privacy loss. Our work here distinctively considers Bayesian models and fairness and allows parties to choose their privacy guarantees directly while explicitly enforcing privacy-reward trade-off.

---

Difficulties ensuring incentives with existing DP/FL works. The one posterior sampling (OPS) method [56] [6] proposes that each party can achieve DP by directly releasing samples from the posterior p (()) (if the log- log-likelihood is bounded). However, OPS is data inefficient and may not guarantee privacy for approximate inference [15]. is unclear how we can privately value a coalition C' and sample from the joint posterior p(0) (D, Nec)) DP DP-FedAvg/DDD Deeet//vgDD-FeeeOO [36] or DP-SGD []] enable collaborative but private training of neural networks by requiring each party i to clip and add Gaussian noise to its submitted gradient updates. However (in addition to the valuation function issue above), is tricky to ensure that the parties' rewards satisfy data sharing incentives, In each round of FL. parties selected will receive the (same) latest model parameters to compute gradient updates. This setup goes against the fairness
(P3) incentive as parties who share less informative gradients should be rewarded with lower quality model parameters instead. Although the unfairness may potentially be corrected via gradient-based (58) or monetary rewards, there no DP reward scheme to guarantee party better model reward from collaboration than in solitude a higher monetary reward than its cost of participation, hence violating individual rationality.
8 Conclusion
Unlike existing works in collaborative ML that solely focus on the fairness incentive, our proposed scheme further (i) ensures privacy for the parties during valuation and in model rewards and (ii) enforces privacy-valuation trade-off deter parties from unfetteredly selecting excessive DP guaran- tees to maximize the utility of collaborativlyy trained models To This involves novelly combining our proposed Bayesian surprise valuation function and reward control mechanism with DP noise-awe aware inference. We empirically evaluate our scheme several datasets. Our likelihood tempering reward control mechanism consistently preserves better predictive performance.
Our work has two limitations which future work should overcome. Firstly, we only consider ML models with SS (see App. A.. App.[A.I for applications) and a single round of sharing information with the mediator as a case study to show the incentives and trade-offs can be achieved. Future work should generalize our scheme to ML models without an explicit SS.
Next, like the works of [8 17 25 40 47 51 and others, we do not consider the truthfulness of submitted information and value data as-is. This limitation is acceptable for two reasons. 1) Parties such as hospitals and firms will truthfully share information as they are primarily interested in building and receiving model reward of high quality and may additionally be bound by the collaboration's legal contracts and trusted data-sharing platforms. For example, with the use of X-road ecosystem 17 parties can upload a private database which the mediator can query for the perturbed SS. This ensures the authenticity of the data (also used by the owner) and truthful computation given the uploaded private database. Each party would be more inclined to submit true information as any party & who submits fake SS will reduce its utility from the collaboration This is because party k's submitted SS is used to generate k's ss model reward and cannot replaced locally as party l will only receive posterior samples. Future work should seek to verify and incentívize truthfulness.
Acknowledgments and Disclosure of Funding
This research/project is supported by the National Research Foundation Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: AISG2-RP-2020-0188) This work is also supported by the National Natural Science Foundation of China (62206139) and the Major Key Project of PCL (PCL2023AS7-I).
16 App. discusses ethical implications and limitations of our work, and other questions a reader may have.
/ttttps:/joonupp europa. http:o/lecccoo////ceeaaaa/o////e
x-road- data- exchange-
wat.a--ercaagg--aarrraboooo 1ayer https://x-road.gln
10

---

References
[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proc. ACM CCS, pages 308-318, 2016.
[2] B. Balle and Y.-X. Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Proc. ICML, pages 394 403,440332 2018.
[3] G. Bernstein and D. Sheldon. Differentially private Bayesian inference for exponential families. In Proc. NeurlPS, pages 9924,2934, 2018.
[4] G. Bernstein and D. Sheldon. Differentially private Bayesian linear regression. In Proc. NeurIPS, pages 525-535, 2019.
[5] C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
[6] Center for Open Data Enterprise. Sharing and utilizing health data for Al applications. Roundtable report, 2019.
[7] Y. Chen, Y. Shen, and S. Zheng. Truthful data acquisition via peer prediction. In Proc. NeurIPS, 2020.
[8] K. Choi, M. Liao, and S. Ermon. Featurized density ratio estimation. In Proc. UAI, pages 172-182, 2021.
[9] Conway, Artificial Intelligence and Machine Learning: Current Applications in Real Estate. PhD thesis, Massachusetts Institute of Technology, 2018.
[10] T. Cover and J. Thomas. Elements of Information Theory. John Wiley & Sons, Inc., 1991.
[11] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proc. TCC, pages 265-284, 2006.
[12] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):211-407, 2014.
[13] A. Fallah, A. Makhdoumi, A. Malckian, and A. Ozdaglar. Optimal and differentially private data acquisition: Central and local mechanisms. arXiv:2201.03968. 2022.
[14] T. Farrand, F. Mireshghallah, S. Singh, and A. Trask. Neither private nor fair: Impact of data imbalance utility and fairness in differential privacy. In Proc. ACM CCS Workshop Privacy-Preserving Machine Learning in Practice, pages 15-19, 2020.
[15] J. Foulds, J. Geumlek, M. Welling, and K. Chaudhuri. On the theory and practice of privacy- preserving Bayesian data analysis. In Proc. UAI, pages 192-201, 2016.
[16] Geumlek, S. Song, and K. Chaudhuri. Rényi differential privacy mechanisms for posterior sampling. In Proc. NIPS, pages 5289-5298, 2017.
[17] A. Ghorbani, M. P. Kim, and J. Zou. A distributional framework for data valuation. In Proc. ICML, pages 3535-3544, 2020.
[18] A. Ghorbani and J. Zou. Data Shapley: Equitable valuation of data for machine learning. In Proc. ICML, pages 2242-2251, 2019.
[19] M. D. Hoffman and A. Gelman. The No-U-Turn sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo. JMLR. 15(1):1593-1623 2014.
[20] R. Hu and Y. Gong. Trading data for learning: Incentive mechanism for on-device federated learning. In Proc. GLOBECOM, pages 1-6, 2020.
[21] J. Huggins, R. P. Adams, and T. Broderick. PASS-GLM, polynomial approximate sufficient statisties for scalable Bayesian GLM inference. In Proc. NIPS, pages 611--6611, 2017.
[22] N. Hynes, D. Dao, D. Yan, R. Cheng, and D. Song. demonstration Sterling: A privacy- preserving data marketplace. Proc. VLDB Endowment, 2012))00882089) 2018.

---

[23] L. Itti and P. Baldi. Bayesian surprise attracts human attention. Vision Research, 49(10):229- 1306, 2009.
[24] R. Jia, D. Dao, B. Wang. F. A. Hubis, N. M. Gurel, B. Li, C. Zhang, C. Spanos, and D. Song. Efficient task-specific data valuation for nearest neighbor algorithms. Proc. VLDB Endowment, 12(11):1610-166)
2019.
[25] R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gurel, B. Li, C. Zhang, D. Song, and C. Spanos. Towards efficient data valuation based on the Shapley value. In Proc. AISTATS, pages 1167-1176, 2019.
[26] Kulkarni, J. Jälkö, S. Kaski, and A. Honkela. Locally differentially private Bayesian inference. arXiv:2110. 10: 14426, 2021.
[27] T. Kulkarni, J. Jälkö, A. Koskela, S. Kaski, and A. Honkela. Differentially private Bayesian inference for generalized linear models. In Proc. ICML, pages 5838-5849, 2021.
[28] J. Liu, J. Lou, J. Liu, L. Xiong, J. Pei, and J. Sun. Dealer: an end-to-end model marketplace with differential privacy. Proc. VLDB Endowment, 14(6):957-969, 2021.
[29] Y. Liu and Wei. Incentives for federated learning: A hypothesis clicitation approach. #xXiv:207.105590 2020.
[30] O. Lobel. The problem with too much data privacy. Time Magazine, 27 Oct 2022.
[31] H. Lx, Z. Zheng, Luo, Wu, S. Tang, L. Hua, R. Jia, and C. Lv. Data-free evaluation of user contributions in federated learning. In Proc. IEEE WiOpt, 2021.
[32] L. Lyu, Li, K. Nandakumar, Yu, and X. Ma. How to democratise and protect AI: Fair and differentially private decentralised deep learning. IEEE Transactions on Dependable and Secure Computing, 19(2): 1003-10777 2022.
[33] M. Maschler and B. Peleg. characterization, existence proof and dimension bounds for the kernel of game. Pucific J. Mathematics, 18(2):289-328, 1966.
[34] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communicationn-fficceenn learning of deep networks from decentralized data. In Proc. AISTATS, pages 1273-1282, 2017.
[35] B. McMahan and A. Thakurta. Federated learning with formal differential privacy guarantees. Google AI Blog, Google Research, Feb 2022.
[36] H. B. McMahan, D. Ramage, K. Talwar, and L. Zhang. Learning differentially private recurrent language models. Proc. ICLR, 2018.
[37] J. W. Miller and D. B. Dunson. Robust Bayesian inference via coarsening. Journal of the American Statistical Association, 2018.
[38] I. Mironov. Rényi differential privacy. In Proc. 30th IEEE Computer Security Foundations Symposium (CSF), pages 263 223-275,222 2017.
[39] K. Murphy. Probabilistic Machine Learning: An Introduction. MIT Press, 2022.
[40] Q. P. Nguyen, B. K. H. Low, and P. Jaillet. Trade-off between payoff and model rewards in Shapley-fair collaborative machine learning. In Proc. NeurIPS, 2022.
[41] Nielsen and Nock. Entropies and cross-entropies of exponential families. Proc. IEEE ICIP, pages 3621-3624, 2010.
[42] Y.KK. Noh, M. Sugiyama, S. Liu, M. C. Plessis, F. C. Park, and D. D. Lee. Bias reduction and metric learning for nearest-neighhor estimation of Kullback-Leibler divergence. In Proc. AISTATS, pages 669-6777 2014.
[43] Ocean Protocol Foundation. Ocean Protocol: decentralized substrate for Al data and services. Technical whitepaper, 2019.
12

---

[44] R. K. Pace and R. Barry. Sparse spatial auto-regressions. Statistics and Probability Letters, 33(3):291-297, 1997.
[45] F. Pérez-Cruz. Kulbback-Leibler divergence estimation of continuous distributions. In Proc. IEEE ISIT, pages 1676,1670, 2008.
[46] R. H. L. Sim, X. Xu, and B. K. H. Low. Data valuation in machine learning: "ingredients", strategies, and open challenges. In Proc. IJCAI, pages 5607-5614, 2022.
[47] R. H. L. Sim, Y. Zhang, M. C. Chan, and B. K. H. Low. Collaborative machine learning with incentive-aware model rewards. In Proc. ICML, pages 8927-8936, 2020.
[48] A. Singh and D. Koutra. Lecture 16 of 10-704: Information processing and learning course. Carnegie Mellon University, 19 March 2015.
[49] S. Singh and B. Póczos. Finite-sample analysis of fixed-k nearest neighbor density functional estimators. In Proc. NIPS, 2016.
[50] W. Smith, J. E. Everhart, W. C. Dickson, W. C. Knowler, and R. S. Johannes. Using the ADAP learning algorithm to forecast the onset of diabetes mellitus. In Proc. Annu. Symp. Comput. Appl. Med. Care, pages 261-265, 1988.
[51] S. S. Tay, X. Xu, C. S. Foo, and B. K. H. Low. Incentivizing collaboration in machine learning via synthetic data rewards. In Proc. AAAI, pages 9448-9453 2022.
[52] M. Titsias. Variational learning of inducing variables in sparse Gaussian processes. In Proc. AISTATS, pages 567-574, 2009.
[53] J. T. Wang and R. Jia. A note "Towards efficient data valuation based on the shapley value". arXiv:2302.1 1431, 2023.
[54] Q Wang, S. R. Kulkarni, and S. Verdú. Divergence estimation for multidimensional densities via k-ncarest-neighhor distances. IEEE Transactions on Information Theory, 55(5):2392-2405, 2009.
[55] T. Wang, J. Rausch, C. Zhang, R. Jia, and D. Song. A principled approach to data valuation for federated learning. In Q Yang, L. Fan, and H. Yu, editors, Federated Learning, volume 12500 of Lecture Notes in Computer Science, pages 153-167. Springer, Cham, 2020.
[56] Y. X. Wang, S. Fienberg, and A. Smola. Privacy for free: Posterior sampling and stochastic gradient Monte Carlo. In Proc. ICML, pages 2493-2502, 2015.
[57] L. Watson, R. Andreeva, H. Yang, and R. Sarkar. Differentially private Shapley values for data evaluation. urXiv:2206.0051.1 2022.
[58] X. Xu, L. Lyu, X. Ma, C. Miao, C. S. Foo, and B. K. H. Low, Gradient driven rewards to guarantee fairness in collaborative machine learning. In Proc. NeurIPS, pages 16104-16117, 2021.
[59] X. Xu, Z. Wu, C. Foo, and B. K. H. Low. Validation free and replication robust volume-based data valuation. In Proc. NeurIPS, pages 10837-10848, 2021.
[60] Y. Xu, M. Xiao, H. Tan, A. Liu, G. Gao, and Z. Yan. Incentive mechanism for differentially private federated learning in Industrial Internet of Things. IEEE Transactions On Industrial Informatics, 18(10):6977-633, 2022.
[61] M. Yang, L. Lyu, J. Zhao, T. Zhu, and K.-Y. Lam. Local differential privacy and its applications: comprehensive survey. arXiv:2008 03686, 2020.
[62] Q Yang, Y. Liu, T. Chen, and Y. Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology, 10(2):1-19, 2019.
[63] Yoon, S. O. Arik, and T. Pfister. Data valuation using reinforcement learning. In Proc. ICMI., pages 10842-10851, 2020.
13

---

[64] L. Zhang, T. Zhu, P. Xiong, W. Zhou, and P. S. Yu. More than privacy: Adopting differential privacy in game- theorrtic mechanism design. ACM Comput. Surv., 54(7), 2022.
[65] B. Z. H. Zhao, M. A. Kaafar, and N. Kourtellis. Not one but many tradeofts: Privacy vs. utility in differentially private machine learning. In Proc. ACM SIGSAC Conference Cloud Computing Security Workshop, pages 15-26, 2020.
[66] Zhao and Lai. Minimax optimal estimation of KL divergence for continuous distributions. IEEE Transactions Information Theory, 66(12):78777711 2020.
14

---

A Fundamental Concepts
In this section, we will elaborate on concepts from Sec. 2 in more detail.
A.1 Sufficient Statistics
Bayesian learning involves updating helief of the likely values of the model parameters captured in the prior p(0), to a posterior belief p(0 D2) & p(0) x p(D:(0). The posterior belief gets more concentrated (around the maximum likelihood estimate) after observing larger dataset D,
The statistic 8; is SS for D; 0 and D; are conditionally independent given 8;, i.e., p(0]D,) p(0|s; D:) p(0) 84)
44 [52. Knowing the dataset D; does not provide any extra information about 9 beyond the SS sy. SS exists for exponential family models [3] and Bayesian linear regression [39]. Approximate SS has been proposed by [21] for generalized linear models. For more complex data such as images, we can use pre-trained neural networks like VGG-16 as feature extractors and generate SS from the last hidden layer's outputs.
Bayesian Linear Regression. In linear regression, each datum consists of the input a R and the output variable y E Let D denote the dataset with e data points, and y and X be the corresponding concatenated output vector and design matrix in Rexw, Bayesian linear regression models the relationship as y X + (0,,0") where the model parameters consists of the weight parameters w E IR and the noise variance o². The likelihood
y Xw)
(y Xw)
ply|X, o2) (2 exp
20²
-1 20 y y
1 w X Xw
-2 -
& exp
w
X y
20
X). Concretely, when the prior p(0) of the weights and variance follow a normal gaaeerse-gamma distribution, NIG(O, Vo, dn, bo). the posterior p())D;) is the normal inverse-gamma distribution NIG(w, V,, ao + +c//2, b.) where e; the number of data points and
only depends on data via the sufficient statistics
w. VXX.y y:
Vi= (Vo x.)
+
b, = bo + (1/2) [y y: w V wi]
can be computed directly from The posterior belief p(. D2) given parties and j's dataset can be similarly computed using the SS of their pooled dataset, 8;j. As the SS sij works out to s; + 8,- we only need 8; and 8, from party and j instead of their private datasets.
Generalized Linear Model (GLM). generalized linear model (GLM) generalizes a linear model by introducing inverse link function T. The probability of observing the output y given input æ = (T(1))-... ((w)) and model weights depends on their dot product
plya, 0) = (( (m))))
Next, we define the GLM mapping function v to the log-likelihood of observing y given the GLM model. Formally,
v(y, x T0) & logp(y) 0))
As an example, logistic regression is GLM with Y defined the sigmoid function and ply = =ljsigmoid( 0)) follows a Bernoulli distribution. As the non-linearity of Y disrupts the exponential family structure, logistic regression and other GLMs do not have sufficient statistics.
Logistic regression's GLM mapping function Viog(U, x 0) = - log(1 + exp(-yæ: 0)).
21 propose to approximate the GLM mapping function with M-degree polynomial approximation Var- UM is an exponential family model with sufficient statisties g(d) = E; m, I M, Vi m, E 2 These SS are the polynomial approximate suf- ficient statisties for GLMs. For example, when M 2 and æ (2))) g(d)
[I ())()) (1=))) )m:]
1, 1, "/nn"" " " "
15

---

A.2 Differential Privacy
Remark Our work aims to ensure example-level DP for each collaborating party: A party updat- ing/adding//eleting single datum will only change the perturbed SS visible to the mediator and the corresponding belief the model parameters in a provably minimal way. We are not ensuring user-level DP: The belief of model parameters only changes minimally after removing collaborating party's (or a user/data owner's s) dataset, possibly with multiple data points [35].
Intuitively, DP algorithm R. D - o guarantees that each output o is almost equally likely regardless of the inclusion exclusion of a data point d in D. This will allay privacy concerns and incentivize data owner to contribute its data point d since even knowledgeable attacker cannot infer the presence or absence of
The works on noise-aware inference 4 27 assume that the input æ and output y of any data point have known bounded ranges. We will start by introducing our Nomain-dependen definitions:
Definition A.1 (Neighboring datasets). Two datasets and D' are neighboring if D' can be obtained from D by replacing a single data point. The total number of data points and all other data points are the same.
Definition A.2 (Sensitivity MT].
The sensitivity of a function g that takes in dataset D&: quantifies the maximum impact data point can have on the function output. The l fi-seniitivity (1 and fz-sensitivity (g(g) measure the impact using the & and Eg norm, respectively. Given that Dj must be a neighboring dataset of D;
D.D. A (g) A max (l) g(D))l1
(g max (l((D.) 9D()))l D.D
In our problem, y computes the exact SS 8, for D,- The sensitivity can be known/computed if the dataset is normalized and the feature ranges are bounded.
We start with the definition of e-differential privacy. The parameter bounds how much privacy is lost by releasing the algorithm's 's output.
Definition A.3 (Pure cDP [T]. A randomized algorithm R + o with range O c-DP if for all neighboring datasets D and D' and possible output subset O Range(R),
The Laplace mechanism is e-DP algorithm. Instead of releasing the exact SS 8;, the mechanism will output sample of the perturbed SS o, -applace(s, (g)(e) I).
A common relaxation of e-differential privacy is (c, -differrrnal privacy. It can be interpreted as eDD but with a failure of probability at most 8.
Definition A.4 ((e, dD-D). randomized algorithm R : D + o with range O (e, differrfrrenniillyy private if for all neighboring datasets D and D' and possible output subset O C Range(R),
P(R(D) E 0) S e P(R(D') e +8
The Gaussian mechanism is (e, 8)- algorithm. The variance of the Gaussian noise be added can be computed by the analytic Gaussian mechanism algorithm 2
In the main paper, have also discussed another relaxation of e-differential privacy that is reproduced below:
Definition A.5 (Rényi DP BS A randomized algorithm R : D + o is (A, Ré-nnii differen- tially private if for all neighboring datasets D and D', the Rényi divergence of order À 1 is (R(RDD) ((D")) < c where
P(R(D)= - P(R(D) o)
log E (D~R(D))
(x(R(D) |I R(D"))
A-1
16

---

When À = oc, Rényi DP becomes pure c-DP. Decreasing À emphasizes less on unlikely large values and emphasizes more on the average value of the privacy loss random variable log (P(R(D) / (RR())) = oj] with o ~ R(D').
The Gaussian mechanism is (A, -éRééy DP algorithm. Instead of releasing the exact SS 8,, the mechanism will output sample of the perturbed SS o; ~ ~ (s;, 0.5 (A/c) Aā(g) I).
Post-process post-processing. common and important property of all DP algorithms/meccanismms their robusiness to post-processing: Processing the output of a DP algorithm R. without access to the underlying dataset will retain the same privacy loss and guarantees [12].
Choosing Rényi-DP over (e, -DD. In our work, we consistently use the Gaussian mechanism in all the experiments, like in that of 277 We choose Rényi DP over (e, O-DP due the advantages stated
below:
Rényi-DP is stronger DP notion according to 38 While (c. 8)-DP allows for complete failure of privacy guarantee with probability of at most 6, Rényi-DP does not and the privacy bound is only loosened more for less likely outcomes. Additionally, (38 claims that it is harder analyze and optimize (c, S)DP due to the trade-off between and ó. More details can be found in (8).
collaborative ML framework, each party may need to release multiple outputs the same dataset D; such the SS and other information for preprocessing steps (e.g., principal component analysis). Composition rules bound the total privacy cost é of releasing multiple outputs of differentially private mechanisms. It is harder to keep track of the total privacy cost when using (c, 5)-DP due to advanced composition rules and the need to choose from wide selection of possible (e(o), 6) (38). In contrast, the composition rule (i.e., Proposition 1 in (38] is straightforward: When À is a constant, the of different mechanisms can simply be summed.
Rényi-DP supports easier composition:
Note that the contribution of our work will still hold for (e, 6)-P (using the Gaussian mechanism) and e-DP (using the Laplace mechanism) with some modifications of the inference process and proofs.
Remark 2. Our work is in the same spirit as local DP (and we also think that no mediator can be trusted to directly access any party's private dataset) but does not strictly satisfy the definition of local DP (see A.6). In the definition, the local DP algorithm takes in single input/datum and ensures the privacy of its output- - the perturbation mechanism applied to every input independently. In contrast, in our case, party may have multiple inputs and the perturbation mechanism is only applied to their aggregate statistics. Thus, a datum owner (c.g., a patient a collaborating hospital) enjoys weaker privacy in our setting than the local DP setting.
Definition A.6 Lc-Local DP [6]). randomized algorithm R. is e-oocal DP if for any pair of data points d, d' 'D and for any possible output O C Range(R),
P(R(d) E O) < ((R((')) EO).
A.3 DP Noise-Aware Inference
DP mechanisms introduce randomness and noise to protect the output of a function. Noise-naive techniques ignore the added noise in downstream analysis. In contrast, noise-aware techniques account for the noise added by the DP mechanism.
Consider a probabilistic model where the model parameters 0 generate the dataset D, which then generates the exact and perturbed suffiientt statistics of each party i, which are modeled as random variables S, and O,, respectively. The exact SS s; and perturbed SS o, computed by party i are realizations of S; and O,, respectively. As the mediator cannot observe i's exact SS, S, is a latent random variable. Instead, the mediator observes i's perturbed SS O; which also contains noise Z, added by the DP mechanism, i.e., O e S + Zz. The Gaussian mechanism to ensure (A, Réééni DP sets Z; Nf (0, 0.5 (A/e) A f). We depict the graphical model of our multi-party setting in Fig.
Differences between exact, noise-naive and noise-aware inference. When the mediator observes the exact SS 8; from party i, the exact posterior belief p())5, 8;) can be computed in closed form based on App. A.I However, when the mediator only observes the perturbed SS o, the mediator can
17

---

S
X
71
Figure 4: In the graphical model above, all parties share the same prior belief p(0) of model parameters 0 and prior belief p(w) of data parameters w. The mediator models its beliefs of the SS of each party separately and only observes the perturbed SS o, of every party i E N (thus, only O, is shaded). The sufficient statistic S, is generated from the model inputs X, and the model output yı (which depends on the model parameters 0). We illustrate the relationship between w. X;, and S; as dashed lines as they may be modeled differently in the various DP noise-aware inference methods. See 27 for their respective graphical models and details.
only compute the noise- naive and noise-aware posterior beliefs instead. The noise-naive posterior belief p(O|S; o,) will neither reflect the unobservability of the exact SS random variable S, accurately nor quantify the impact of the DP noise Z,. In contrast, for any party, the D) noise-aware posterior belief p(0|O; o;). conveniently abbreviated p pf)oo.) will quantify the impact of the noise added by the DP mechanism. (For a coalition C' of parties, the DP noise-aware posterior belief is p(0loc) - {O; = O: HiE)), as described in Footnote The works of [3 4 27 have shown that DP noise-aware inference leads a posterior belief that better calibrated (i.e., lower bias and better quantification of uncertainty without overconfidence) and of higher utility (i.e., closer to the non-private posterior belief), thus better predictive performance.
The main challenge of noise-aware inference lies in tractably approximating the integral p(O, = 0) p(s:(0)p(( (s. ds; and (0) [[ (x) p(X, y/0) d.X dy over all datasets.
3 4 27) exploit the observation that the SS sum individuals, the central limit theorem guarantees that the distribution p(s;()) (f) can be well-approximatte by the Gaussian distribution A (Ccu, cL, for large [4. Here, Mg and Σg are the mean and covariance an individual's SS. [ 27 26
prescribe how to compute Hg and Mg in closed form from the sampled 0 parameters and moments of x and set the noise of the DP mechanism based on sensitivity analysis. approximate the
posterior p)) Markov Chain Monte Carlo (MCMC) sampling steps are needed. [ propose to use Gibbs sampling, an algorithm that updates a group of parameters
time and exploits conditional
independence, for Bayesian linear regression models. 27 use the No-U-Turn [19] sampler and
utilizes Hamiltonian dynamics to explore the parameter space more efficiently for generalized linear models. We describe the BLR Gibbs sampler adapted for our multi-party setting in Algo T
18

---

Algorithm BLR Gibbs sampler from noise-aware posterior p(01ON oN) & IleN (p(o:]s;) p(s,10)] dai.... ds.. The algorithm (repeatedly) sample the latent variables Si, w and sequentially.
Require: Shared prior p(0) model parameters, prior p(w) of data parameters, data quantity C,, shared perturbed SS realization Os, the Gaussian noise distribution of Zi for every party É N, number b of burn-in samples, number m of samples, Boolean parameter (shared) controlling p(x:) is the same across parties.
1: Sample the initial model parameters ((0) from the prior p(0).
2: Sample the data prior parameters (0) from the prior p(w).
3: Compute the moments of X; based on w. do 5: for = ,,... do
4: for = 1, ,,..,,
6: Compute the normal approximation of p(S,10), denoted as px.(),0), using the moments of
X;
7: Sample (4) from the product of two multivariate Gaussians (s: p(o.(S)). which is also multivariate Gaussian.
8:
if not shared then
9:
Use information from 8 and G to perform conjugate update on p(ws) to obtain (1) and compute the moments of X,.
(s c.)). Sample wi end if
10:
11:
end for
12:
if shared then
Use information from (s. ci)eEN perform conjugate update on p(w) obtain (1) psw c.)veN) Sample (t))) and compute the moments of X4.
end if
Use (s N, to perform conjugate update on p(0) to obtain ps()(s)) (t) .c)iEN).
15:
Sample g(9) from p(0)(s)) (c)))))
b then 18: Append g(9) to e.
17: if >
19: end if
20: end for
21: return θ
19

---

B Key Differences with Existing Data Valuation, Collaborative ML, and DP/FL Works
Incentives for Data Sharing Higher reward for contributing more valuable data (fairness across parties, individual rationality, etc.)
Data Valuation
18
25
59
47
55 58
DP Mechanisms
20
27
56
26
36
Collaboratively Trained Model
Differentially Private Even to the mediator
Each party receives a model decentrally trained with everyone's 's data
Figure 5: Our work, *, uniquely satisfies all 3 desiderata. When parties share information computed from their data, we ensure that every party has at least its required DP w.r.t the mediator, receives collaboratively trained model, and receives higher reward for sharing higher-quality data than the others.
not trivial to (i) add DP to while simultaneously enforcing privacy-valuation trade-off, (ii) add data sharing incentives to v (i.e., design valuation functions and rewards), and (iii) achieve as access to party's 's dataset (or coalition's datasets) still needed for its valuation in (57]
Difference with existing data valuation and collaborative ML works considering incentives. Our work aims to additionally (A) offer parties assurance about privacy but (B) deter them from selecting excessive privacy guarantees. We achieve (A) by ensuring differential privacy (see definitions in App.L. A.2) through only collecting the noisier/perturbed version of each party's 's sufficient statistics (see App. A.T. To achieve (B), we must assign lower valuation (and reward)
noisier SS. Our insight to combine noise-aware inference (that computes the posterior belief of the model parameters given the perturbed SS) with the Bayesian surprise valuation function. Lastly, (C) we propose mechanism to generate model rewards (i.e., posterior samples of the model parameters) that attain the target reward value and are similar to the grand coalition's 's model.
Difference with with.federated learning and differential privacy works. Existing FL works have covered learning from decentralized data with DP guarantees. However, these works may not address the question: Would parties want to share their data? How do we get parties to share more to maximize the gain from the collaboration? Our work aims address these questions and incentivize (A) parties to share more, higher-que qualte- data and (B) select weaker DP guarantee. To achieve (A), it is standard data valuation methods [18 25 46 to use the Shapley value to value party relative to the data of others as it considers party's 's marginal contribution to all coalitions (subsets) of parties. This would require us to construct and value a trained model for each coalition C C N: To ease aggregation (and to avoid requesting more information incurring privacy costs per coalition), consider
20

---

sufficient statistics (see App.A.... A.Ib. To achieve (B), we want valuation function that provably ensures lower valuation for stronger DP guarantee. Our insight is to combine noise-aware inference (that computes the posterior belief of the model parameters given perturbed SS) with the Bayesian surprise valuation function. Lastly, like the works of 44 51], (C) we generate a model reward that attains target reward value (which parties can use for future predictions). Our model reward is in the form of posterior samples of the model parameters instead. We propose a new mechanism to control/generate model rewards that work using SS and preserve similarity to the grand coalition's 's model.
Fig. 5
shows how our work this paper fills the gap in the existing works.
C Characteristic/Vlluate
Function
C.1 Proofs of properties for valuation function
In this section, will use the random variable notations defined in App. A Moreover, abbreviate the set of perturbed SS random variables corresponding coalition C of parties Oc - {O.)eec.
Let (a) denote the entropy of the variable a.
Relationship between KL divergence and information gain.
I(0; Oc) = Bog~ DKLL (p(0 oc):
(T) E Do [0](0 = oc)]
Party monotonicity (V2). w.r.t random vector Oct,
Consider coalitions C C' S N. By taking an expectation
Eogr~O [vc] Eoc~Oe (PkL
1(0; -
and
Eog [UCr] = B [Dkr (Kkk((()0))) -100)
Then, Boo [FC'] > Bo [vc] as conditioning additionally on Oc should not increase the entropy (i.e., IHI (H)00, Ocnc) I (HOO)c)) due to the "information never hurts" bound for entropy [10).
Scy(a
Ocrt
0
S
O
O
7
Figure 6: Graphical model to illustrate privacy-valuation trade-off (V3) where O, 2 S, + Z and O A O, 23.
vrivaco-valuation trade-off (V3). Let ef < <;, and 2 and 2 be independent Gaussian distribu-
tions with mean 0 and, respectively, variance as/e, and (a./e))- function g computes the exact SS 8; from local dataset D;, and 22(g) denotes its fz-sensitivity. Adding Z! to S; will ensure (X, G)-DP while adding both Z and independent Z? to S; is equiva- lent to adding Gaussian noise of variance a:/e to ensure (>, ( From the graphical model
> O where a, 0.5 À (g)
Adding or subtracting independent noise will lead to random variable with higher variance. Thus, we cannot model the random variable O of lower variance a: /cs ensure (A, GD- as Of 22.
21

---

in Fig. 6 and the Markov chain 0 + O; - Og, the following conditional independence can be observed: TL Of O, By the data processing inequality, no further processing of O₁, such as the addition of noise, can increase the information of 0. Formally, I(0; O:) 2 T(0; Of). Simultaneously, J. O O Hence, [(;; O.) * [(;;; Of) = (T((;0,) > T(0; Of)).
To extend to any coalition C' containing i, by the chain rule of mutual information,
00, [[0 O., Ocy(a) + 07|0, Ocvo) T(0; Ocy()) + (0,0 Ocyt0)
As conditional independence 0 IL Of O Ocv(s) and dependence 0 O, Of, Ooya still hold, O1),0 Ocya)) = 0 and [00; (0,0, Ocyo)) > O, respectively. It follows from the above expression that I[(0; Oc) > (0; Of, Oct(s)). which implies Boc > or (v(8) For future work, the proof can be extended other DP mechanisms.
C.2 Proof of Remark in Sec.
Let the alternative valuation of a coalition C be o'c DKI,(p(0)ox) (p(0)ox):p(()oc))) Then, v/S and v'y (kc.))(0)ox):p(0)) can observed that
DRL. (p(0 o
Unlike ec, 1/c may be negative.
Unlike UN. ''y is guaranteed to have the highest valuation the minimum KL divergence only when (()) = p(0lox). This is desirable when we want the grand coalition to be more valuable than the other coalitions but odd when we consider the non-private posterior q()) = p(0]sx): Intuitively, the model computed using s should be more valuable using of than that computed using the perturbed SS oN.
DRt. (p(O)o))) (())
By taking an expectation w.r.t ON.
Ep(Ow))tt = O() Boc-p(Oo)
Bomcsp(Oxncloc) DRL (p(0loN (omccoc)))p((0on)))
E Eomospl0micle)) Eoup(0lonic.o)) log p(flonic.
Ol():O)) - Boc
p(0loc)
p(0 (0,oN))loo)
I(0;ON) - Eoc~p(Oe)
E Beonee-tee.0mclor log p(0 p(oNycloc)
Ol(0OO)) ) Bor~
DKL (p(0, (.0cOOOccooc::00000))) p(Onccloc))
(2) 1(0; ON) - 1(0; OxClOee
= [0:0cc) = (Ep(os)
In equality (i) above, we multiply both the numerator and denominator within the log term by p(oN(cloc) and consider the expectation of the joint distribution since by the chain rule of prob- ability, p(0, Oxicloc) p(Ox,cloc) ON,O oc). Equality (ii) is due the definition of conditional mutual information.
C.3 KL Estimation of Valuation Function
KL estimation only tool and not the focus of our work. Our valuation will become more accurate and computationally efficient as KI. estimation tools improve.
Recommended nearest-neighhors [45 54]. Given @pout and Oprior which consists of m samples of 0 (with dimension d) from, respectively, the posterior p(0)ac) and prior p(0), estimate the KL. divergence as
d
gpeioo (8)
m
log
log
gpost
771
m
where 58000( (0) is the distance of the sampled 0 to its k-th nearest neighbor in @ (excluding itself)
and (priin(() (0) is the distance of the sampled to the k-th nearest neighbor in Optio
22

---

The number & of neighbors is tumable and analyzed in the follow-up work of [49]. As the number m of samples increases, the bias and variance decrease. The convergence rate is analysed by [66]. Moreover, the estimate converges almost surely [45] and is consistent [54] for independent and
identically distributed (f..d.) samples. Furthermore, as the KI. divergence is invariant to metric
reparameterizations, the bias can be reduced by changing the distance metric 42 (4).
To generate i.i.d. samples, we suggest the usage of the NUTS sampler or thinning (keeping only every t-th sample). We observe that if the samples from 0 | oc are non-independent, i.e. correlated and close the previous sample, we may underestimate its distance to the k-thh distinct neighbor in 0 oc, % (0), and thus overestimate the KI. divergence. This is empirically verified in Table 2 We have also observed that the KI. divergence may be underestimated when the posterior is concentrated significantly different mean from the prior.
Recommended for large E approximate p(Oloc) using maximum likelihood distribution from the p(0)'s exponential family. When small noise is added to ensure weak DP, we can approximate p(0) oc) with a distribution from the same exponential family as p( sc). ). We can (i) determine q's parameters via maximmm likelihood estimation (MLE) from the Gibbs samples 19 and (ii) compute the KL divergence closed form.
However, the KI. estimate is inaccurate (i.e., large bias) when the distribution q is a poor fit for the posterior p(floc). Future work can consider using normalizing flows as to improve the fit, reduce the estimation bias, and work for larger range of DP guarantees c. However, this KL estimation method may be computationally slow and risks overfitting.
Probabilistic Classification. Let the binary classifier / θ + [0, (e.g.. a neural network) discriminate between samples from two densities qı (0) (here, the posterior p(0 oc)) and (0) (here, the prior p(0)) and output the probability that 0 comes from qı (0). Concretely, we label the m samples from qı (0) and (0) with y 1 and y = 0, respectively. By Bayes' rule, the density ratio
91 (0) p(0 1) pvy 1 ply 1
(O) p(0) y = 0) pvy 0
p(y=1
Optimizing a proper scoring rule such as minimizing the binary cross-entropy loss should return the Bayes optimal classifier (0) pyy 118). The KL estimate then computed as the mean log-density ratio over samples from & (0). As the log-density ratio is eigmoidd''pee (p(v 1())), when
f is a neural network with sigmoid d as the last activation layer, we can use the logits before activation directly.
However, with only limited finite samples m and large separation between the distributions @1 and qu, the density ratio and KL estimate may be highly inaccurate [8] Intuitively, the finite samples may be linearly separable and the loss is minimized by setting the logits of samples from şı (0) (hence KL) to infinity (i.c., classify it overconfidently with probability 1). As the separation between the distributions Q1 and go increases, exponentially more training samples may be needed to obtain samples between and go 8 Moreover, as training may not produce the Bayes optimal classifier, there is also an issue of larger variance across runs.
D Reward Scheme for Ensuring Incentives
D.1 Incentives based on Coalition Structure
Instead of assuming the grand coalition N form, we can consider the more general case where parties team up and partition themselves into a coalition structure CS. Formally, CS is a set of coalitions such that UCeds C N and C n C" 0 for any C, C' E CS and C # C". The following incentives are modified below:
P2 For any coalition C' E CS, there is a party i e C' whose model reward is the coalition C's posterior, i.c., 9, (0) = o())oc). It follows that r; = ve as in R2 of 47..
P5 Among multiple model rewards (0) whose value r; equates the target reward rū: we secondarily prefer one with a higher similarity rh.c- = - DDx (pkx (p) 9; (0)) to the coalition's posterior p(0 oc) where E C.
The distribution g from MLE minimizes the KL divergence (p() (()).
23

---

D.2 Fairness Axioms
The fairness axioms from the work of [47] are reproduced below:
Fl Uselessness. If including the data or sufficient statistic of party does not improve the quality of model trained the aggregated data of any coalition (e.g., when D; 0, e 0), then party i should receive a valueless model reward: For all i EN,
(VC C N ( {i) eCul)) = vc) - =0
F2 Symmetry. If including the data or sufficient statistic of party i yields the same improvement as that of party j in the quality of model trained the aggregated data of any coalition (e.g., when D. Dy), then they should receive equally valuable model rewards: For all i,j E N s.t. j.
(AC C N [6,) You( = (Cou)) = ri= ri
F3 Strict Desirability [33]. If the quality of a model trained on the aggregated data at least a coalition improves more by including the data sufficient statistic of party than that of party but the reverse is not true, then party should receive a more valuable model reward than party j: For all i
N s.t. i j.
(3B EBENY {i,}} AautA (BL())) A (AC' CNCNNN (N,5) ecu() 2 (Cub)) - m,,
F4 Strict Monotonicity. the quality of a model trained on the aggregated data of at least a coalition containing party improves (e.g., by including more data of party i), ceteris paribus, then party i should receive a more valuable model reward than before: Let [#c)ce2) and {ūc JCE2> denote any sets of values of data over all coalitions C C N, and r; and fg be the corresponding values of model rewards received by party i. For all E N,
(EB S N {i} DRu(y > eBu()) A (VCENT N (i) (Cu(1) 2 (Ou())
(VAÇN) (i) ε = =UA) (ŌN > r:) 30 -
D.3 Remark on Rationality
Let Us denote the Bayesian surprise party i's exact SS 8; elicits from the prior belief of model parameter. We define Stronger Individual Rationality (SIR, the strengthened version of P44 as: each party should receive a model reward that is more valuable than the model trained on its exact SS alone: Vi E Nr. 2 V'a.-
We consider two potential solutions to achieve stronger individual rationality and explain how they fall short.
Each party declares the value Vs and the mediator selects a smaller to guarantee SIR. SIR is infeasible when the grand coalition's posterior is less valuable than party i's model based on exact SS, i.e., UN < Usg. Fig. 2
we observe that when party selects a small 22. approximated by 22 under large E2, i.c., the right end point of
Uy is less than Uag which the blue line. Instead, SIR is only empirically achievable when party 2 and others select a weaker DP guarantec as in Fig. 10 in App. H.S) Note that our work only incentivizes weaker DP guarantees and does not restrict parties choice of DP guarantees.
The mediator should reward party i with perturbed SS E (for Sec. 5.1b KçOj, K4Gj, Ri (for Sec. 5.2) for every other party j + i. Party i can then combine these with its exact 8; to guarantee SIR.
This approach achieves SIR at the expense of truthfulness. As party i perturbed SS o; is not used to generate its model reward, party may be less deterred (hence more inclined) to submit less informative or fake SS.
SIR is not needed when each party prefers training a DP model even when alone. SIR may be desired in other scenarios. However, our approach does not use alternative solutions to satisfy SIR as we prioritize incentivizing parties to (i) truthfully submit informative perturbed SS that they would use for future predictions, while (ii) not compromising for weak DP guarantees.
24

---

E Details on Reward Control Mechanisms
In the subsequent proofs, any likelihood (-) should be interpreted as [p(-)] We only raise likelihoods (of data conditioned on model parameters) to the power of Riz-
E.1 Likelihood Tempering and Scaling SS Equivalence Proof
Let denote the function that maps any data point di or dataset DD. to its sufficient statistic. For any data point di, assume that the data likelihood p(d] (0) is from exponential family with natural parameters & and sufficient statistic g (d:). The data likelihood p(di(0) can be expressed in its natural form:
0) = h(di) exp [g(d)) -- A(0))
where a t b denotes the dot product between two vectors.
20 for p(Dx (0) with natural parameters 1/ and the [ AA()]] Then, for oą data points which are conditionally independent given the model parameters 6,
Next, we assume that p0) is the conjugate prio
sufficient statistic mapping function T
p(0 (di)(=)) & p(di (0) ... p(de, 10) p00)))
Ck
2k Σ g(di) 0 cAA(
1 h(dd))
exp
(h(0) exp (T(0) -n - B(n)l)
9(Dx)
exp (D() Cx A())(0) T(0) B())
x exp (Lo(Da)T, [.] +1) T()) C(n)
where C(n) is chosen such that the distribution is normalized.
Substituting the above SS formulae into (I. the normalized posterior distribution (after tempering the likelihood) is
(0) p"1(11 (di10) ... pp" p(0(v)
[ Ck
Ni
(II
exp exp (D()k) 0 c(O(]]]]
(h(0) exp (T(0) (n)]
x exp (D(g(D() k((AA(00))) TT()) B(r)
x exp (()))((D)) k[c]]] +n) T(0) c(n))
where (n) is chosen such that the distribution is normalized.
Thus, tempering the likelihood by H; is equivalent scaling the SS g(D)) and data quantity ck- We additionally proved that the normalized posterior can be obtained from the scaled SS and data quantity via the conjugate update.
Bayesian Linear Regression (BLR). The Bayesian linear regression model was introduced in App. I. To recap, BLR model parameters 0 consists of the weight parameters E R and the noise variance o². BLR models the relationship between the concatenated output vector y and the Xw o2), The tempered likelihood
design matrix X
(y X Xw) (wwT(u Xw) )
nd (y),, w. 0²)
(2Ta²) exp
20
= (2
exp
20 K.y
K.y
y
w K;X y 202 w TT X
only depends on the scaled sufficient statistics K; (y y, XT y. the conjugate normal inverse- inverse-gamma gamma distribution, the power posterior can be obtained from the scaled SS and data quantity via the conjugate update.
x X). When the prior p(0) follows
p(() and p(0)D:) belong the exponential family.
25

---

Generalized Linear Model (GLM), App. A.1 introduces GLMs and states that the polynomial approximation the GLM mapping function is an exponential family model. Tempering the GLM likelihood function by K; is equivalent to scaling the GLM mapping function by Ri and can achieved by scaling the polynomial approximate SS by the same factor.
E.2 Smaller Tempering Factor Decreases Reward Value Proof
The KL divergence between two members of the same exponential family with natural parameters y and v', and log partition function B(-) is given by (1 -1)) BB B(r) B(w') 41. To ease notational overload, we abuse some existing ones, which only apply in this subsection, by letting a - EEEN 8& and cv EKEN Ct. Let r/ and rj be the natural parameters of the prior and the normalized tempered posterior distribution (used generate model reward with value
rı), respectively. Then, = Tf' + (8 cN] For Ri E [0, 1]. the derivative of w.r.t K2 is non-negative:
dr;
dr: dn
dx,
On Ok;
((1) r/') T V2 B() + VB(m) VB(()) [s], eN]
[ mCNN] V B2) [ CN]
Ki [s eN] B [s ON]
0.
As B(T) is convex w.r.t
7. the second derivative
42 B2)()) is positive semi-definite, so
(T cNl Bn) [s CN
20.
Hence, for K; E (0, 1]. the KI. divergence is non-decreasing as K; increases to 1. other words, as K; shrinks towards O, the KI. divergence is decreasing: equality only holds when the variance of the SS is O.
E.3 Implementation Reward Control Mechanisms
This subsection introduces how to obtain the model reward (0) for each party i in Sec.
Update for noise addition (varying T;). We update the inputs Algorithm T for BLR or the No-U-Turn sampler for GLM. To generate party i's posterior samples, for every party & E N, the algorithm use the further perturbed SS E instead the perturbed SS Og. Moreover, the algorithm consider the total DP noise Z + N,, 0.5 (g(g)) T; I) instead of only the noise Zμ added by party k.
Update for likelihood tempering (varying K:). To generate party i's posterior samples, for every party & E N, Use KyCk, K,Ok, and Zx as the inputs to Algorithm I for BLR or the No-U-Tum 19 sampler for GLM instead. Scaling the perturbed SS would affect the sensitivity of party k's submitted information and the DP noise needed.
F
Time Complexity
Algorithm 2 An overview of our collaborative MI. problem setup.
The computational complexity given App.
Require: Rényi DP parameter, Noise-aware inference algorithm, Shared prior p(0) of model parameters and prior p(w) of data parameters, p-Shapley fairness scheme parameter.
// Party's actions (ensure DP)
1: for each party E N do
2: Compute exact SS s; from dataset D;,. 3: Choose DP guarantee (A, Réééé DP.
This second derivative is the variance of the sufficient statistic of 6. is non-negative and often positive.
26

---

4: Sample 2, from the Gaussian distribution p(2,) _V(0, 0.5 (A/e:) A3( r).
5: Compute perturbed SS o; _ 8; + Zi-
6: Submit (i) number e; |D,] of data points in its dataset D;, (ii) perturbed SS and (iii)
Gaussian distribution p( 2.) to the mediator.
7: end for
II Mediator's actions
Compute valuation of perturbed SS needed for Shapley value. The choice of e ensures a privacy-valuation trade-off.
8: Draw m samples from p0).
9: for each coalition C C N do Draw m samples from the posterior p(O)oc) by applying the noise-aware inference algorithm.
10:
The algorithm requires the perturbed SS oc {oi)icc data quantities {cz hiec and noise distributions {Ze) NEc-
11:
Compute VC by using the nearest-neighhors method 45 to estimate the KL divergence
DKL (p(0 ((O) from the samples.
12: end for
// 2. Decide the target reward values using p-Shapley value [47] which ensure efficiency P2
fairness (3)) rationality
(4] and control group welfare (P)).
13: for each party E N do
Compute Shapley value o; = //)n)occvv ((a))) (MCut) (veup)-oc)]
14:
end for
16: Identify the maximum Shapley value o. = maxKEN Ok.
for each party E do
18: Compute p-Shapley fair target reward rī for party i using the formula rf = UN x (d:/0.)
end for
// Generate model reward (0) with value T; r grand coalition's 's model and privacy for others P7
that preserves similarity
P5
with the
for each party E N do
21:
Initialize Kr = ().
22:
while True
23:
Select E [0 using root finding algorithm and Kr.
24:
Draw m samples from the normalized posterior (0) (Eq. by applying the noise-aware
inference algorithm. Use the scaled perturbed SS {K.O. data quantities (KeCH and noise distributions {N; Jee.
25:
Compute the reward value r; by using the nearest-neighhors method 45 estimate the KL. divergence DKL (q: p(f) from the samples.
26:
if attained reward value r then
27:
Reward party with the m posterior samples from (0).
28:
break end if
29:
30:
Update Kr Kr ((ss, ri),)
31:
end while
end for
The main steps of our scheme are detailed Algo. 2 and the time complexity of the steps are as follows:
Local SS 8; computation (Line 2 in Algo 2). Party will need sum the SS for its C; data points. Subsequent steps will not depend on the number c; of data points. The (approximate) SS is usually an (d2) vector where the number regression model features. Therefore, this step incurs O(e,d") time.
2. Perturbed SS O; computation (Lines in Algo 2). Each party will need the Gaussian mechanism to perturb s, Therefore, this step incurs (dd) time.
27

---

Valuation of Perturbed SS . The valuation of oN requires to draw posterior samples of model parameters using DP noise-aware inference (refer to App. A.3 and the cited references for the exact steps). As the methods of [27 and 4 incur (md") time for a single party, inference based on Fig. 4 will take n times longer to consider n parties. KL estimation using k-nearest neighbor will incur (m log(m)dim(0) time to value multiple (scaled) perturbed SS. Therefore, valuation incurs O Onnmd + m log(m) dim(O)) time.
A
3. Deciding target reward value r for every E N (Sec. Lines 1 in Algo 2). Computing the Shapley values exactly involves valuing oc for each subset C S N, hence, repeating Step A (2") time. When the number of parties is small (e.g., < 6), we can compute the Shapley values exactly. For larger n, we can approximate the Shapley values ( N with bounded E--norm error using ((n(logn)) samples [25] [3]. Moreover, the value of different coalitions can be computed in parallel. Therefore, this step incurs (2")
or ()) times the time in Step A
4. Solving for r6; to generate model reward (Sec. 5.2 Lines 31 Algo 2). During
root-finding, the mediator values different model rewards q (8) generated by scaling the perturbed SS Og, data quantity d and DP noise distribution Z₃ of each party A E N by different hence, repeats Step A As we are searching for the root in a fixed interval [0, 1 and to a fixed precision, Step A is repeated constant (usually < 10) number of times. Therefore, this step incurs O namd" + m log(m) dim( time per party.
The mediator can further reduce the number of valuation of model rewards (repetitions of Step A) by using the tuples of (K;, rz) obtained when solving for K; to narrow the root-finding range for other parties after i.
Therefore, the total incurred time depends the number of valuations performed in Step The time complexity may vary for other inference and KI. estimation methods.
28

---

G
Comparison of Reward Control Mechanisms via Noise Addition (Sec. 5.1 vs. Likelihood Tempering (Sec. 5.2)
See Fig
2
1
0
-1
p(w1, W2)
p we (
2
p W2)ON)
Pxg (WI, W2l
2
Figure 7: We contour plot the distribution of the regression model weights wy and W2 for the prior, the grand coalition N's posterior, and the model reward's posterior attain the target reward value r utilizing noise addition (Sec. 5 vs. likelihood tempering (Sec. (.2p as the reward control mechanism for the Syn dataset where p 55. The tempered posterior interpolates the prior and grand coalition N's posterior better as its mean/mode lies along the line connecting the prior's 's and grand coalition N's posterior mean and the variance is scaled by the same extent for both weights.
H Experiments
The experiments are performed machine with Ubuntu 20.04 LTS, 2x Intel Xeon Gold 6230 (2.1GHz) without GPU. The software environments used are Miniconda and Python. full list of packages used is given in the file environment.yre attached.
H.1 Experimental Details
Synthetic BLR (Syn). The BLR parameters 0 consist of the weights for each dimension of the 2D dataset, the bias, and the variance o². The normal rnverse-gammn distribution used (i) to generate the true regression model weights, variance, and 2D dataset and (ii) as our model prior as follows: o² ~ InvGamma(Au = 5. fu = 0.1) where and fo are, respectively, the inverse-gamnn shape and scale parameters, and w 0²2 ~ ~N o A. where Ao = 0.025 I.
We consider three parties 1, 2, and 3 with co 100, Cı 200, and c2 400 data points, respectively. We fix 61 = 63 = 0.2 and vary 62 from the default 0.1. As 62 increases (decreases), party 2 may become the most (least) valuable. We allow each party have different Gaussian distribution p(x:;) by maintaining a separate conjugate normal inverse- Wishart distribution p(w; = (Mw.i Ew.)) for each party. We set the prior En.; ~ ( = I, 1/2 = 50) where the and My are the scale matrix and degrees of freedom (i.e., how strongly believe the prior), respectively. Then, Muui ~ (O, Ex..). The lz- fz-sensitivity is estimated using (26)'s analysis based on the norms/bounds the dataset.
One posterior sampling generates 16 Gibbs sampling chains in parallel. For each chain, we discard the first 10000 burn-in samples and draw m 30000 samples. reduce the closeness/correlattoo between samples which will affect the neiueettneigghoo-bbee KL estimation, we thin and only keep
29

---

every 16-th sample and concatenate the thinned samples across all 16 chains. For the experiment on reward control mechanisms, we use 5 independent runs of posterior sampling and KL estimation.
Californian Housing dataset (CaliH). As the CaliH dataset may contain outliers, we preprocess the "public" dataset (60% of the CaliH data) by subtracting the median and scaling by the interquartile range for each feature. We train a neural network (NN) of 3 layers with [48, 24, 6] hidden units and the rectified linear unis (ReLU) the activation function to minimize the mean squared error, which we will then use as a "pre-trained NN". The outputs of the last hidden layer have features used as the inputs for BLR. We intentionally reduce the number of features in the BLR model by adding more layers to the pre-trained NN and reduce the magnitude of the BLR inputs by adding an activation regularizer on the pre- pre-trained NN hidden layers (i.e., l2 penalty weight of 0.005). These reduce the computational cost of Gibbs sampling/KL. estimation and the f2-sensitivity of the inputs to BLR (hence the added DP noise), respectively. We also add a weights/bias regularizer with an & penalty weight of 0.005 for the last layer connected to the outputs. Lastly, we standardize the outputs of the last hidden layer to have zero mean and unit variance.
We preprocess the private dataset for valuation and the held-out validation set (an 80-20 split) using the same pre-trained NN/trasforrmation process. To reduce the sensitivity and added DP noise, we filter and exclude any data point with a 2-score > for any feature. There are 6581 training data points left. We divide the dataset randomly among 3 parties such that parties 1, 2, and 3 have, respectively, 20%, 30% and 50% of the dataset and 6 = Eg = 0.2 while 62 is varied from the default 0.1.
The BLR parameters consist of the weights for each of the features, the bias, and the variance o². We assume 0 has normal inverse-gamen distribution and set the prior as follows. The prior depends on the MLE estimate based on the public dataset, and we assume it has the same significance as noo = 10 data points. Hence, we set o² InvGamma(ao = no/2, Bo no/2 x MLE estimate of o?) and w|o² ~ (O0 of x xTx) xxx=)))..
We assume that each party has the same underlying Gaussian distribution for p(æz) and maintain only one conjugate normal inverse- inverse-Wishart distribution p(w = (Na )w)) shared across parties. We initialize the prior p(w: to be weakly dependent the prior dataset [39] The fz-seesitivvtyy is
estimated using 26 's analysis based on the norms/bounds of the private transformed dataset.
One posterior sampling run generates 16 Gibbs sampling chains in parallel. For each chain, we discard the first 10000 burn-in samples and draw m = 30000 samples. To reduce the closeness/correlatio between samples which will affect the nearest-neighbor-base based KL estimation, we thin and only keep every 16-th sample and concatenate the thinned samples across all 16 chains. For the experiment on reward control mechanisms, use 5 independent runs of posterior sampling and KL estimation.
PIMA Indian Diabetes classification dataset (Diab). This dataset has raw features such age, BMI, number of pregnancies, and a binary output variable. Patients with and without diabetes are labeled y and y -1, respectively. We split the training and the validation set using 80-20 split. There are 614 training data points. There are 35.6% and 31.8% of patients with diabetes in the training and validation sets, respectively. Hence, random guessing would lead to a cross-entropy loss of 0.629.
We preprocess both sets by (i) subtracting the training set's median and scaling by the interquartile range for each feature, (ii) using principal component analysis (PCA) to select the 4 most important components of the feature space to be used new features, and lastly, (iii) centering and scaling the new features to zero mean and unit variance. To reduce the effect of outliers and the Ez-sensitivity. we clip each training data point's 's feature values +22.2.
We divide the 614 training data points such that parties 1, 2, and 3 have, respectively. 20%, 30%, and 50% of the dataset and é <3 0.2 while E2 is varied from the default 0.1. We compute the approximate SS 21 and perturb them for each party to achieve the selected E; 27 The Ez-seniitivtty is also estimated based on the dataset.
We consider a Bayesian logistic regression model, and its parameters @ consist of the bias and the weights for each of the 4 features. Like that of (27], we set an independent standard Gaussian prior for 0 but rescale it such that the squared norm ||0|] has a truncated Chi-square prior with d = 4 degrees
30

---

of freedom. Truncation prevents sampling & with a norm larger than 2.5 times the non non-private/true setting's 0r squared norm during inference.
We assume each party has the same distribution for p(æ). Our data prior p(x:) has mean O and covariance Σ (1 Q diag(s) where (11, D). E [0, 2], and Q follows Lewandowski- Kurowicka-Joe prior LKJ(2).
We use the No-U-Turn 19 sampler. We run 25 Markov chains with 400 burn-in samples and draw m 2000 samples with target Metropolis acceptance rate 0.86. We discard chains with a low Bayesian fraction of missing information (i.e., < .3) and split the concatenated samples across chains into 5 groups to estimate KL divergence. As sampling is slower and the generated samples tend to be less correlated,
fewer samples.
Remark. For the CaliH dataset, the preprocessing based on the "public" dataset, but for the Diab dataset, the preprocessing (i.e., standardization, PCA) is based on the private, valued dataset. We have assumed that the data is preprocessed. However, in practice, before using our mechanism, the parties may have to reserve/separately expend some privacy budget for these processing steps. The privacy cost is ignored our analysis of the privacy-valuation trade-off.
KL estimation. We estimate KL divergence using the k-nearest- sereeestteeighho--bre based KL estimator To reduce the bias due the skew of the distribution, we apply a whitening transformation where each parameter sample is centered and multiplied by the inverse of the sample covariance matrix based on all samples from 9 and o. As a default, we set and increase k until the distance to the k-th neighbor is non-zero.
45
H.2 Utility of Model Reward
The mean negative log probability (MNLP) test dataset D, given the perturbed SS o is defined as follows:
1
MNLP
Σ
-logp(y.læ.,00
D..
(x.:)-)ED.
We prefer MNLP over the model accuracy mean squared error metric. MNLP additionally measures if model is uncertain its accurate predictions or overconfident in inaccurate predictions. In contrast, the latter metrics penalize inaccurate predictions equally and ignore the model's confidence (which is affected by the DP noise).
Regression. Approximating the predictive distribution, o:), for test input æ, as Gaussian, the MNLP formula becomes
1 (10g(2m0(m..)) + (T((x.)) - y.)² (x.)
MNLP A
Σ
[D_|
(a..y.)ED,
where μlx and (xxx) denote the predictive mean and variance, respectively. The first term penalizes large predictive variance while the second term penalizes inaccurate predictions more strongly when the predictive variance small (i.e., overconfidence).
The predictive mean (xx..) ) is the averaged prediction of y. (i.e., w æ... where w is part of the model parameters 0) over all samples of the model parameters 0.
The predictive variance 6² (xx) is computed using the variance decomposition formula, i.e., the of the averaged d² (the unknown variance parameter within and the computed variance in predictions samples, i.e., m -1 Σラ= of + j (xx.) )2x.)
We estimate p(y= x.,, o.), for test input æ. using the Monte Carlo approximation and reusing the samples 0 from o.)). Concretely, p(u 1| o.) = m ΣØ=1 a0 T xx)). The MNLP is equivalent to the cross-entropy loss.
Classification.
39
H.3 Baselines
To plot the figures in Sec. 6 the bascline DP and collaborative ML works must
31

---

1. work for similar models, i.e. Bayesian linear and logistic regression;
2. not use additional information to value coalitions and generate model rewards (to preserve the DP post-processing property); and
3. decide feasible model reward values and suggest how model rewards can be generated.
Work of [59]. Valuation by volume is model-agnostic (satisfying criteria 1). Each party i E N can submit the noisy version of x; X; with DP guarantees to the mediator who can sum them value coalitions (satisfying criteria 2). The work does not propose model reward scheme to satisfy criteria
Work of 47 47 only considered Bayesian linear regression (with known variance) and is not straightforward to compute information gain model parameters for Bayesian linear regression (with unknown variance) and Bayesian logistic regression. Thus, the work does not satisfy criteria 1. For Bayesian linear regression (with known variance), each party i N can submit the noisy version of X X; with DP guarantees to the mediator who can sum them to value coalitions (satisfying criteria 2). The work proposed a model reward scheme which involves adding noise the outputs y ( ssatisfying criteria 3 but has to be adapted to ensure DP).
[36] to learn any model parameters (satisfying criteria 1) in conjunction with FedSV (55] to value coalitions without additional information (satisfying criteria 2). However, to our knowledge, these works will not satisfy criteria as they do not suggest how to generate model rewards of a target reward value.
DP-FL works. A promising approach is to use OP-FeeAvggDP-Feetee
As existing work satisfies all criteria, we compare against (1) using non-noise-awan inference instead of noise-aware inference, all else equal (in App. H.5); and (2) an adapted variant of the reward control via noise addition (in Sec. 5.1 Sec. and App.
H.4 Valuation Function
In Sec. 6 we only vary the privacy guarantee of one party i. In this subsection, we will analyze how other factors such as the coverage of the input space and the number of posterior samples on the valuation U;.
Coverage of input space. We vary the coverage of the input space by only keeping those data points whose first feature value is not greater than the 25, 50, 75, 100-percentile. Across all experiments in Table [ can be observed that as the percentile increases (hence, data quantity and coverage improve), the surprise elicited by the perturbed SS ON increases in tandem with the surprise elicited by the exact SS 8N.
Feature O's Percentile Range
[0, 25]
[0, 50,
[0, 75]
[0, 100
Syn Surprise of s
12.030
12.698
13.322
14.183
Surprise of ON CaliH
6.007
6.775
7.410
8.438
Surprise of s Surprise of ON Diab
21.261
22.401
26.578
28.422
9.282
10.212
12.121
17.959
Surprise of 8N Surprise of oN Table 1: We report the surprise elicited by s and On (with e 1) when using the subset of data with first feature value not exceeding the 25, 50, 75, 100 100-percentile for all datasets.
5,450
6.279
7.019
7.258
1.854
2.712
3.909
5.394
Number of posterior samples. For a consistent KI. estimator, the bias/variance of the KI. estimator should decrease with a larger number of posterior samples.
Gibbs sampling. We compare the estimated surprise using various degrees of thinning (i.e., keeping only every (-th sample) to generate 30000 samples for the CaliH dataset. In Table it can be observed that although the total number of samples is constant, the surprise differs significantly. Moreover,
32

---

as t increases, the surprise decreases at a decreasing rate and eventually converges. This may be because consecutive Gibbs samples are highly correlated and close, thus causing us underestimate the distance to the k-th nearest-neighhor within 0 ON (see discussion in App- C.3 Increasing / reduces the correlation and closeness and better meets the i.i.d. samples assumption of the nearest- neighbor- based KI, estimation method [55]
Thin every t-th sample
Surprise UN
14.849 + 0.036
2
12.839 + 0.033
11.626 = 0.018
8
11.038 = 0.022
10.834 = 0.033
20
10.790 = 0.032
10.793 + 0.011
Table 2: Thinning factor vs. surprise UN for CaliH dataset.
NUTS logistic regression. After drawing 10000 samples for the Diab dataset using the default setting, we analyze how using a subset of the samples will affect the estimated surprise. In particular, we consider using (i) the first m samples or (ii) thinned m samples where we only keep every 10000/m-th sample.
In Table 3] it can be observed that as the number m of samples increases, the standard deviation of the estimated surprise decreases. Moreover, there is significant difference between using the first m samples or the thinned m samples. This suggests that the samples are sufficiently independent and thinning is not needed.
No. m of Samples
Surprise UN
First 1000
2.227 + 0.051
Thinned 1000
2.211 0.034
First 2000
2.117 = 0.049
Thinned 2000
2.117 = 0.045
First 5000
2.145 + 0.037
Thinned 5000
2.119 + 0.038
All 10000
2.128 + 0.030
Table 3: Number m of samples vs. surprise un for Diab dataset.
H.5 Additional Experiments on Valuation, Privacy-valuatton Trade-off, and Privacy-reward Trade-off
6
2
2
2
-2
1
2
0
logio
Iogan F2
logia 62
(a) Syn
(b) CaliH
(c) Diab
Figure 8: Graphs of Shapley value oi of parties 1,2,3 party 2's privacy guarantee c2 for various datasets.
Shapley value. In Fig. 8 it can be observed that as party 2 weakens its privacy guarantee (i.e., 62 increases), its Shapley value increases while other parties' Shapley values (e.g., Φ3) decrease.
33

---

When party 2 adds less noise to generate its perturbed SS O2. others add less value (i.c., make lower marginal contributions (MC)) coalitions containing party 2. Party changes from being least valuable to being most valuable, even though it has more data than party 1 and less data than party 3.
30
20
40
3
-2
1og S2
10g
log
(a) Syn
(b) CaliH
(c)Diab
Figure 9: Graphs of party 2's valuation U2 Shapley value d2, and attained reward value 72 vs. privacy guarantee 62 for various datasets when performing non-noise-awe (i.e., noise-naive) inference, i.e., S( oN) and treating on though it is s..
Without DP noise-aware inference. In Fig. Dh. it can be observed that 62 increases, V and Φ for party i == do not strictly increase. In Figs, pp-c, can be observed that as e2 increases, 2 and d for party i 2 decrease instead. The consequence of non-noise-aware inference is undesirable for incentivization guarantee, i.e., greater privacy sacrifice. Moreover, when 62 is small (i.e., under strong privacy guarantee), party 2 is supposed to be least valuable. However, the significantly different O2 causes party 2 to have the highest valuation and be rewarded with the grand coalition N's model (i.e., r; close to ux) instead.
party 2 unfairly gets a lower valuation and reward for using weaker privacy
Lastly, also observe that without DP noise-aware inference, the utility of the model reward is small. For example, the naive posterior for the Syn dataset results in an MNLP larger than 100.
Conditions for larger improvement in MNLP. In Fig. it seems that the utility of party i = 2's model reward measured by MNLP, cannot improve significantly over over that of its individually trained model when 62 is large. However, party i's MNLP, can be improved by larger extent when (i) any other party j * i selects a weaker privacy guarantee (i.e., larger Cj), thus improving the utility of the collaboratively trained model or (ii) party i and others have lower data quantity (i.e., smaller c3: for all & E N) and are unable to individually train a model of high utility. Figs. T0p. TOp, and are examples of (i), (ii), and (i+ii), respectively. In Fig. 10h, the MNLP of grand coalition N's collaboratively trained model is lower than that Fig. 3h. In Fig. 10p, the MNLP, party i's model is higher due less data. In these examples, we observe that party can still gain significant improvement MNLP; MNLP, when E; >
Condition (i) for larger improvement in MNLP, is satisfied when the orf deters parties from selecting excessive DP guarantees, i.e., incentivizes parties to select weaker DP guarantees that still meet their legal and customers' requirements. Condition (ii) should be satisfied in most real-life scenarios where a party wants to participate collaborative MI and federated learning. The party (e.g., bank) is unable to achieve its desired utility with its individually trained model due to limited data and collaborates with others to unlock any improvement the utility of collaboratively trained model.
34

---

0.5
0.5
MNLP
MNLP L.
MNLP
0.0
0.6
NV
log 52
logie C2
logio
(c) Diab, larger EN halved {CK]KEN
(a) Syn, larger Cj
(b) Syn, halved {cKtReN
Figure 10: Graphs of utility of party = 2's model reward (0) measured by MNLP, vs. privacy guarantee eg for Syn dataset (a) when E E3 instead of 0.2, and (b) when only subset of cx/2 data points is available for every party k = 2, 3. (c) Graph of utility of party i = I's model reward (0)) measured by MNLP, vs. privacy guarantee ci for Diab dataset when c2 = <3 2 instead of 0.2 and only a subset of c data points is available for every party & = 2.
Higher À = 10. Fig. 11 the privacy-valuation, privacy-reward, and privacy-utility trade-offs are still observed when parties select higher 10 when enforcing the Rényi DP guarantee. Moreover, the utility of party 2's model reward is higher (i.e., lower MNLP) than that of its individually trained model.
12
1/
UN
UN
02
-2
-2
logio
logio
Ingau
(a) Syn
(b) CaliH
(c) Diab
0.8
0.70
MNLP
MNLP
0.65
0.0
0.60
Jog:0
log
log 5g
(d) Syn (MNLP vs. E2) (c) CaliH (MNLP vs. 62) (f) Diab (MNLP vs. E2)
Figure 11:
Graphs of party 2's (a-c) valuation U2, Shapley value Φ2, and attained reward value 72, and (d-f) utility of its model reward (,()) measured by MNLP, privacy guarantee 62 for various datasets when enforcing (A = 10, & Rényy DP guarantee.
H.6 Additional Experiments on Reward Control Mechanisms
For the CaliH dataset, there a monotonic relationship between r; vs. both K; and t, as shown in Fig. 12p. However, it can be observed from Figs. 12b-c that for the same attained reward value ri, adding scaled noise variance т; will lead a lower similarity rf to the grand coalition N's posterior p(0)on) and utility of model reward (higher MNLP,) than tempering the likelihood by Kg.
35

---

MNLP.
6
1.0
0,0
0.5
140
-10
10
Joga
(a) 72 VS. Kss Tj
(b) r/ vs. T3
(c) MNLP, vs. rs
Figure 12: (a) Graph of attained reward value r; vs. Ky (Sec. 5.2) and 7; (Sec. 5.1 (b) graph of similarity r to the grand coalition N's posterior p(0 vs. T/, and (c) graph of utility of party i 2's model reward q: measured by MNLP, vs. r; for CaliH dataset.
For Diab dataset, there is monotonic relationship between r; both K, and T., shown in Fig. 13 However, it can be observed from Fig. p3 that for the same attained reward value тú, tempering the likelihood by Ky leads higher similarity r the grand coalition N's posterior p(0lON) and utility of model reward (lower MNLP,) than adding scaled noise variance Tü.
2.0
N2
1.5
MNLK
10
2
logu
(a) F2 VS.
(b) rf vs.
(c) MNLP, vs.
Figure 13: (a) Graph of attained reward value r; vs. Ki (Sec. 5.2) and Ti (Sec. 5. (b) graph of similarity r to the grand coalition N's posterior p(Olon) vs. Fi, and (c) graph of utility party i = 2's model reward qı (0) measured by MNLP, vs. T; for Diab dataset.
Problematic noise realization. We will show here and in Fig. 14h that some (large) noise realization result in monoooooooicc relationship between the attained reward value r; vs. the scaled additional noise variance т;. As a result, it is hard to bracket the smallest root 7; that solves for = r3 (e.g.. 2 or 3). Moreover, it can be observed from Figs. 14b-c that the model reward's posterior q: (0) has low similarity rf to the grand coalition N posterior p( p(0) ox) and a much higher MNLP, , than the prior. This suggests that injecting noise does interpolate well between the prior and the posterior. In these cases, it is not suitable to add scaled noise variance т; and our reward control mechanism via likelihood tempering with Kg, preferred instead.
34
Prion
0.0
0.5
1.0
loga 7
T
(a) Fr VS. Kes, Ti
(b) r/ vs. T
(c) MNLP, VS. F3j
(Non Nonnmmontooii in 75)
Figure 14: (a) Graph of attained reward value r; vs. Ky (Sec. 5.2) and (Sec. 5.1 (b) graph of similarity r to the grand coalition N's posterior p(0loN) vs. ri. and (c) graph of utility of party i = 2's model reward q: (0) measured by MNLP, vs. for Syn dataset corresponding to (a).
36

---

I Other Questions
Question 1: Are there any ethical concerns we foresee with our proposed scheme?
Our privacy-valuation trade-off V3 should deter parties from unfetteredly selecting excessively strong DP guarantees. Parties inherently recognize the benefits of stronger DP guarantees and may prefer such benefits in collaboration out of overcaution, mistrust of others, and convenience. The trade-off counteracts (see Fig. [1) the above perceived benefits by explicitly introducing costs (i.e., lower valuation and quality of model reward). Consequently, parties will carefully select weaker yet satisfactory privacy guarantee they truly need.
Answer:
However, a potential concern is that parties may opt to sacrifice their data's privacy to obtain higher-quality model reward. The mediator can alleviate this concern by enforcing a minimum privacy guarantee (i.e., maximum <) each party must select. The model rewards will preserve this minimum privacy guarantee due to [P The mediator can also decrease the incentive by modifying vc.
Another potential concern that if parties have data with significantly different quan- tity/quality/privacyy guarantees, the weaker party & with fewer data or requiring stronger privacy guarantee will be denied the best model reward (i.e., trained on the grand coalition's SS) and instead rewarded with one that is of lower quality for fairness. The mediator and at least ensure individual rationality (P4) by using a smaller p so that a weaker party can obtain a higher-quality model reward with higher target reward value rz-
alleviate the concern
Question 2: Is it sufficient and reasonable to value parties based on the submitted information fc,, o, p( bEN instead of ensuring and incentivizing truthfulness? Would parties strategi- cally declare other values to gain a higher valuation and reward?
Answer: An ideal collaborative ML scheme should additionally incentivize parties to be truthful and verify the authenticity of the information provided. However, achieving the "truthfulness" incentive hard and has only been tackled by existing works a limited extent. Existing work cannot discern if the data and information declared are collected or artificially created (c.g.. duplicated) and thus, this non-trivial challenge is left future work. The work of (22 assigns and considers each client's 's reputation from earlier rounds, while the works of 29 31 measure the correlation in parties' predictions and model updates. The work of 7 proposes payment rule based on the log point- wise mutual information between a party's 's dataset and the pooled dataset of others. This payment rule guarantees that when all other parties are truthful (i.e., strong assumption), misreporting a dataset with an inaccurate posterior is worse (in expectation) than reporting dataset with accurate posterior
Thus, like the works of [88 25 40 47 51 and others, we value data as-is and leave achieving the "truthfulness" incentive future work. In practice, parties such hospitals and firms will truthfully share information as they are primarily interested in building and receiving a model reward of high quality and may additionally be bound by the collaboration's 's legal contracts and trusted data- sharing platforms like Ocean Protocol [43]. For example, with the use of X-road ecosystem 23 parties can maintain a private database which the mediator can query for the perturbed SS. This ensures the
authenticity of the data (also used by the owner) and truthful computation given the uploaded private database.
Lastly, a party i who submits fake SS will also reduce its utility from the collaboration. Party k's fake SS will affect the grand coalition's posterior of the model parameters given all perturbed SS and is also used to generate k's model reward. As party is only receives posterior samples, k cannot replace the fake SS with its exact SS locally. As party A have bear the consequences of the fake SS, it would be more likely to submit true information.
Question 3: Why do we only consider Bayesian models with SS?
The payment rule may be unfair as when two parties are present, they will always be paid equally. t//p/////oooo//////oo/o/////////
/nttps://joinpp. wwwp:p.ccee...oooooo k-road-das data- exchange- Layeaangg--ayra/bbaaaa
37

---

Answer: See Apple A.1 for a background on SS. Our approach would also work for Bayesian models with approximate SS, such as Bayesian logistic regression, and latent features extracted by a neural network.
1. The exact SS captures all the information (i.e., required by the mediator) within party i's dataset D, Thus, the mediator can do valuation and generate model rewards from the perturbed SS {or JeN without requesting more information from the parties. This limits the privacy cost and allows us to rely on the DP post-processing property.
2. In Sec. 3 the proof that Def. 3.1 satisfies privacy- valuation trade-off uses the properties of SS.
Our work introduces privacy as an incentive and simultaneously offers a new perspective that excessive DP can and should be deterred by introducing privacy-valuation and privacy-reward trade-offs and accounting for the DP noise. We use Bayesian models with SS as case study to show how the incentives and trade-offs can be achieved. is up to the future work to address the non-trivial challenge of ensuring privacy-valuation and privacy-reware trade-offs for other models.
Question 4: Can alternative fair reward schemes be used in place of p-Shapley fair reward scheme 4
Answer: Yes, if they satisfy P3 and P4 For example, if the exchange rate between the perturbed SS quality and monetary payment is known, then the scheme of [40] can be used to decide the reward instead. Our work will still ensure the privacy-valuation trade-off and provide the mechanism to generate the model reward (0) attain any larget reward value rf while preserving similarity to the grand coalition N's model (P5).
Question 5: What is the difference between our work here and that of [47]
Answer: We clearly outlined our contributions in bullet points at the end of the introduction section (Sec. D and in Fig.
At first glance, our work seems to only add a new privacy incentive. However, as discussed in the introduction section (Sec. [ privacy is barely considered by existing collaborative MI. works and raises significant challenges. The open questions/challenges in [64]'s survey on adopting DP in game- theoretic mechanism design (see Sec. 7.1 therein) inspire us ask the following questions:
How can DP and the aims cooperative game theory-inspired collaborative ML be compatible?
Will DP invalidate existing properties like fairness?
How should parties requiring a strong DP guarantee be prevented from unfairly and randomly obtaining high-quality model reward?
We propose to enforce a provable privacy-valuatee trade-off to answer the latter. The enforcement involves novelly selecting and combining the right valuation function and tools, such as DP noise- aware inference.
Additionally, propose new reward control mechanism that involves tempering the likelihood (practically, scaling the SS) to preserve similarity to the grand coalition' 's model (P5) and hence increase the utility of the model reward.
Question 6:
Will party with high-quality data (e.g., a large data quantity, less need for DP guarantee) be incentivized to participate in the collaboration?
Answer: From Fig. 3 it may seem that rich party i with ample data and weak privacy guarantee (i.e., large <,) has lower utility of model reward gain from the collaboration. However, may still be keen on a further marginal improvement in the utility of its model reward (e.g.. increasing the classification accuracy from 97% 99% and predicting better for some sub- sub-groups) and can reasonably expect a better improvement as other parties are incentivized by our scheme (through enforcing a privacy-valuation trade-off and fairness F44 to contribute more data at a weaker yet satisfactory DP guarantee (see App. H.5). Moreover, a rich party does not need to be concerned about others unfairly benefiting from its contribution as our scheme guarantees fairness through Shapley value. In Fig. 8 as party selects weaker DP guarantee (and all
38

---

else being held constant), the Shapley values of others, which determine their model rewards, decrease.
Question 7: What is the impact of varying other hyperparameters?
Answer: The work of [47] proposes p-Shapley fairness and theoretically and empirically show that any p > 0 guarantees fairness across parties and a smaller p will lead to a higher attained reward value r; for all other parties which do not have the largest Shapley value. These properties apply to our problem setup, and using larger p will worsen/reduce T; and the utility of party i's model reward q. (9) measured by MNLP,- The work of [47] has empirically shown that the number of parties does not impact the scheme's 's effectiveness. However, affects the time complexity to compute the exact and approximate SV.
More importantly, the extent to which party can benefit from its contribution depends on the quantity/qullity of its data relative to that of the grand coalition N (and the suitability of the model or informativeness of the prior).
Party i's DP guarantee e; is varied in Sec. 6 while the DP guarantee eg of the other party k and its number O2 of data points for k N are varied in App. H.S The privacy order is varied in App. H.5 Across all experiments, we observe that the privacy- valuayyvaluation trade-off holds. Moreover, when (i) party has cower-quality data in the form fewer data points or smaller c,, or (ii) another party has higher-quality data such as larger eg, the improvement in the utility of its model reward over that of its individually trained model larger.
Question 8: Can privacy be guaranteed by using secure multi-party computation and homo- morphic encryption in model training/data valuation??
Answer: These techniques are designed to prevent direct information leakage and prevent the computer from learning anything about the data. However, as the output of the computation is correct, any mediator and collaborating party with access to the final model can query the model for predictions and infer private information/membershhpp of a datum (indirect privacy leakage). In our work here, every party can access model reward. Hence, the setup should prevent each party from inferring information about a particular instance in the data beyond what can be learned from the underlying data distribution through strong DP guarantees.
Question 9: In Sec. 4 we mention that (i) it is possible to have negative marginal contributions (i.e., toui < UC) in rare cases and (ii) adding some noise realizations may counter-intuitivlly create more valuable model reward (e.g., T3 > uy). Why and what are the implications?
Answer: For our choice of valuation function via Bayesian surprise, the party monotonicity (V2 and privacy-valuatis trade-off (V3) properties involve taking expectations, i.c., on average/in most cases, adding a party will not decrease the valuation (i.e., the marginal contribution is non-negative), and strengthening DP by adding more noise should decrease the reward value. However, in rare cases, (i) and (ii) can occur. We have never observed (i) our experiments, but related example of (ii) is given in Fig. 14a: A larger T; surprisingly increased the valuation.
The implication of (i) is that the Shapley value Φ; may be negative, which results in an unusable
negative/undefined rī. However, this issue can be averted while preserving P3 by upweighting non negatiiee MCs, such to the empty set, as mentioned in Footnote I0 The implication of (ii) is that some (large) noise realization can result in more valuable model reward than the grand coalition's 's model, i.e., r3 > UN. However, collaborating parties still prefer p(0) (Nv) valued at en as the more surprising model reward is not due to observations and information. This motivates us to define more specific desiderata (PT and P2 for our reward scheme.
Lastly, one may question if we should change the valuation function. Should we use the information gain (0; oc) = Eog [Mc] on model parameters given perturbed SS oc instead to eliminate (i) and (ii)? No, the information gain is undesirable as it disregards the observed perturbed SS oc and will not capture party's preference for higher similarity of its model reward to the grand coalition N's posterior p.
39


Reviews:
[{"review_id": "QlYKtnEDT2", "reviewer": "Reviewer_zMuU", "summary": "From a mostly empirical angle, the paper studies a new valuation metric for incentivizing agents to share their data for collaborative ML while ensuring the data they share is Renyi-DP. Particularly, the KL-divergence between agents' prior and posterior, or the Bayesian surprise, is used as the value of the (possibly perturbed) observations received by the agents. Finally, the proposed method is validated on a synthetic dataset, a regression dataset, and a classification dataset.", "questions": "1.  Can the authors explain **P1** in more detail? From my understanding, it seems like **P1** means that agents&rsquo; reward cannot reveal too much information about other agents&rsquo; data. It would be great if the authors could confirm this. It might be me but currently the definition looks a bit confusing.\n\n", "limitations": "The authors have discussed in detail the potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "1. The experimental results are explained carefully, in detail, and the figures emphasize the key takeaways from the paper.\n2. Overall the paper is easy to follow and nicely presented.\n3. Ethical concerns and potential societal impact are discussed in depth, and in detail, in the appendix.\n4. The problem being studied is an interesting one and especially timely given current conversation on privacy and ethical concerns of large scale ML models.\n", "weaknesses": "1.  While the paper is mostly empirical and should be assessed accordingly, the proposed method still lacks mathematical justification. For instance, it is unclear for what choices of $\\rho$ (or if any) would IR be satisfied for all agents. Quantitative analysis of the desiderata for different values of $\\rho, \\lambda, \\epsilon$, especially quantifying the interplay between $\\rho$ and $(\\lambda, \\epsilon)$ Renyi-DP, would strengthen the results. At the current stage, it is unclear under what kind of problem settings or privacy constraints would the proposed mechanism be feasible.\n2.  In the same vein, desiderata **P5** and **P6** are only discussed intuitively. For ML practitioners with money at risk, additional discussions (and perhaps mathematical or game-theoretic justifications) would be more persuasive.\n3.  While Appendix I, Q5 has partially addressed the relationship between the work and [Sim et al., 2020], as discussed above, it is not clear how **P5** fit in the existing theoretical framework around Shapley values. Similarly, while the tempering technique has not been introduced in prior works, the mathematical or game-theoretic implications of $\\kappa$ are not addressed, and only an intuitive discussion is provided in the appendix. \n4.  The potential application of the method seem limited in domain. The method does not appear to be generalizable outside of Bayesian linear regression. Moreover, calculating the proposed values already entails a costly MCMC inference procedure in order to evaluate the Baeysian surprise. It is unclear if such procedures would remain practical even for smaller neural nets. (While the appendix has discussed various approximation schemes, it may be difficult to persuade practitioners to adopt the method without additional mathematical guarantees on how robust the proposed desiderata are to the estimation errors in both KL and posterior).\n5.  Desiderata **P2** is a strict relaxation of the weak efficiency constraint (R3) in [Sim et al., 2020]. Particularly it requires only one agent, as opposed to one agent in each group, to take full advantage of shared data, and may discourage agents from participating in the mechanism (especially with limited IR guarantees).\n\n- [Sim et al., 2020]. \"Collaborative machine learning with incentive-aware model rewards.\" International conference on machine learning. PMLR, 2020\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed review & questions! We will address your concerns below and include them in the revised paper. We hope our clarifications will improve your opinion of our work.\n\n> W1: Math justifications\n\nTo clarify, our work includes both mathematical and empirical justifications of the proposed method. We have theoretically shown that V1-V3 (Sec.3, App.C) and P1-P2 can be satisfied. \nP3-P4 can be satisfied by using the quantitative analysis of $𝜌$ in Theorem 1 of Sim et al. [2020] since we adopted their $𝜌$-Shapley reward scheme (line 209).\nIn our revision, we will \n- refer readers to Sim et al. [2020] for analysis of the impact of varying $𝜌$;\n- clarify that for **any** privacy constraint $(λ,ϵ_i)$ and problem setting (i.e., dataset), IR is satisfied for all agents if $0 < 𝜌 \\leq 𝜌_r$ ($𝜌_r$ is defined in Sim et al [2020]'s Theorem 1 and computed based on $v_i$ & $v_N$). Our results should hold for any privacy constraint;\n- elaborate V3: A higher $λ$ or smaller $ϵ_i$ should lead to lower valuation.\n\nThere is limited quantitative analysis of the interplay with $(λ,ϵ_i)$ as, like the properties of the dataset, they only affect the reward value and choice of $𝜌$ _indirectly_ by affecting $\\\\{v_C\\\\}_{C \\subseteq N}$. \nHowever, empirically, we have shown that IR holds for a range of $ϵ_i$'s (Figs.2,3) and additionally for a larger $λ$ in Fig.11.\n\n> W3: how P5 fit in the existing theoretical framework around Shapley values (SV)\n\nP5 complements the framework. The framework decides the target reward values $r^*_i$; then, collaborative ML works [46,50,ours] propose mechanisms to generate model rewards to realize the target values. Without P5, the ML practitioner may be indifferent to different model rewards $q_i(θ)$ that achieve the same target reward value. As P5 is a secondary criteria that is maximized after other desiderata have been achieved, it does not change existing SV results.\n\n> W3: Mathematical implication of $κ_i$\n\nIn App.E.2, we mathematically prove that a smaller $κ_i$ decreases the Bayesian surprise.\nIn our revision, we will cite existing works (on likelihood tempering, power posterior, e.g., https://andrewcharlesjones.github.io/journal/power-posteriors.html) that discuss the implication/interpretation of varying $κ_i$ (e.g., synthetically reducing the dataset size).\nIn App.'s Fig.7, we empirically show that likelihood tempering leads to better similarity to the grand coalition’s $p(θ|o_N)$.\n\n> W2: P5 & P6 justifications\n\n**P5** We introduce $r'$ to address parties' secondary preference of similarity to the posterior $p(θ|o_N)$ and a model reward that makes similar predictions. $r'$'s definition is inspired by lines 158-60 & 724 and should decrease with stronger privacy/less data.\n\nA preference for lower KL divergence between the posterior and $q_i(θ)$ \n- has precedent (e.g., it is minimised by expectation propagation in Bayesian ML);\n- is empirically justified as we observe that for the same $r_i$, higher similarity (purple line) with $p(θ|o_N)$ in Figs.2f,12b,13b leads to a lower MNLP$_r$ (higher model utility) in Figs.3d-f.\n\n**P6** Maximizing group welfare is a common concept in game theory & collaborative ML [46,50,D]. From party $i$'s perspective, a higher group welfare will either (i) increase $i$'s reward value or (ii) others' reward value. (i) is desired and (ii) is acceptable to party $i$ when fairness is still ensured.\n\nIf the above is insufficient, can you clarify what are the intended justifications?\n\n[D] Optimality and stability in federated learning: A game-theoretic approach. NeurIPS 2021.\n\n> W4: Applications\n\nWe described in lines 91-3 that our work applies to Bayesian models with SS, not just linear regression. We considered logistic regression in our experiments.\n\nWe acknowledge that our method cannot be directly applied to neural networks. However, it may be applicable when ML practitioners manage to generate SS. For example, ML practitioners tend to use existing large pre-trained models (e.g., VGG-16 for images) and only fine-tune the last layer(s), so the linear/logistic model would still be useful.\n\n> Additional mathematical guarantees on how robust the proposed desiderata are to the estimation errors in both KL and posterior\n\nP1&2 will always hold. P3 and P4 may be affected by the errors in KL and posterior estimation.\n\nWe will justify why the errors can be low: \n- In App.C.3, we extensively discuss how the error in KL estimation can be reduced by taking more samples.\n- Though the DP noise-aware inference works [Bernstein and Sheldon, 2019; Kulkarni et al, 2021] did not provide theoretical results about the estimation errors, they have empirically demonstrated the similarity to the non-private posterior. \n- Empirically, we checked MCMC diagnostics (e.g., R-hat) to ensure that convergence to the true posterior distribution has been achieved and that the variance of KL estimation across runs is low (Tables 2,3). \n\n> P2 vs. R3 in [Sim et al., 2020]\n\nR3 only allows an agent per group $C$ to take full advantage of the shared data of $C \\in CS$ when the coalition structure $CS$ consists of multiple disjoint groups.\nHowever, when the coalition structure is the grand coalition $CS=\\\\{N\\\\}$ (the desired case in Sec.4 Para.2 of [Sim et al, 2020]), only 1 agent can benefit from the shared data of $N$. This is the same as P2.\n\nIn our paper, we assume that $N$ will form for simplicity. However, we can consider other coalition structures or ensure the formation by selecting $𝜌 \\leq 𝜌_s$ according to Sim et al's Theorem 1.\n\n> Q1. Explain P1.\n\nYour understanding is generally correct.\nTo be specific, other agents have already revealed private information with $(λ,ϵ_k)$-DP guarantee to the mediator. Agent $i$’s reward cannot depend on more private information (e.g., ask for more data or samples of model parameters). Instead, it should only use the information already disclosed to the mediator."}, {"review_id": "pWYol9wiwx", "reviewer": "Reviewer_kKLU", "summary": "This paper proposes a mechanism to do single-round private collaborative model learning by several agents, each with access to a dataset. The agents do not want to share their data and instead exchange perturbed sufficient statistics of their data, which the central server must aggregate and learn from. Since the devices benefit from collaboration, they might be incentivized to add excessive noise to their sufficient statistics to get the maximum privacy possible while still getting some benefit from collaboration. While this might benefit specific agents, it might not be the ideal scenario from the perspective of the majority of agents. This paper's mechanism disincentivizes this behavior by providing different models to each client, based on their differential privacy requirements, with better models to agents with \"most useful\" sufficient statistics. The rewards provided by the server also satisfy other desirable properties such as fairness, individual rationality, group welfare, etc.        \n\nOverall I like the paper. It is a good step towards reconciling federated learning with agents' strategic behavior. Apart from complaints about presenting the overall scheme, and other minor writing issues, I do not have major concerns about the paper and recommend accepting it. I would recommend the authors incorporate the suggestions below to improve the exposition. I am open to increasing my score. \n ", "questions": "See comments above. Can actual individual rationality be satisfied by the mechanism? ", "limitations": "The paper should emphasize the scope of the work. Most federated learning happens over several interactions and involves local processing on the agent. There might be some applications where a single round of interaction between the server and the clients is enough, but that is an exception, not the norm. It is unclear if the mechanism provided in this paper can be applied repeatedly in some manner. I understand this extension might be complex, but not discussing it is incorrect. I urge the authors to list potential applications they have in mind in the motivation. As mentioned above, the authors should be more explicit about the exact computations and the complexity of running the mechanism. Finally, the individual rationality requirement in P4 seems wrong. If this can not be changed, it should be emphasized strongly that this is a limitation of the approach. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper addresses a significant problem: agents' strategic and self-serving behavior in federated learning. Federated learning hopes to enable large-scale privacy-preserving collaborations and encourage users to share the benefits of their data to develop an overall better model. Most incentive designs work with explicit monetary rewards, but without an actual server, that is not doable. This paper bypasses the issue and designs model rewards that satisfy several desirable properties. The paper is also quite exhaustive in its treatment of which desirable properties must be satisfied at each step.  ", "weaknesses": "1. The paper is written in a bottom-up approach, i.e., from sufficient statistics to the final model. It is OK to write it this way, but the overall scheme of things is unclear after reading the paper. I know figure one is an attempt to summarize everything, but an actual pseudocode would be helpful to show explicitly which quantities are being computed, how sampling occurs, etc. It would be helpful to also indicate in the pseudocode which sampling steps are approximated using MCMC procedures. For instance, currently, the way it's presented is unclear up to section four; why is the paper talking about coalitions? An informed reader might guess it is due to Shapley value computations, but otherwise, it seems a bit arbitrary. Writing the paper top-down or adding the above pseudocode might clarify these aspects. \n\n2. The individual rationality definition in P4 seems incorrect. Why would the agent perturb the sufficient statistic if they are alone? Collaboration with perturbed statistics should be better than unperturbed individual effort. \n\n3. Finally, the complexity of computation/sampling will also become explicit by being more precise about the exact computations. Shapley value computations are generally expensive, and discussing the effect of inexactness in the procedure would be good.   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your helpful comments and suggestions! We have responded to them below and hope it will improve your opinion of our work.\n\n>Weakness 1\n\nOur paper is written in a bottom-up approach and defers information to when it is needed or the appendix: App.A.3 contains the pseudocode for sampling, App.B (lines 684-94) contains information for readers less familiar with data valuation and collaborative ML, and App.F describes the main steps of our scheme and how various quantities should be computed. We agree that it is useful to give an overview (e.g., to clarify why coalitions are mentioned) in the main paper and will add one to Sec.2. \n\nWe have attached an overview of the quantities and steps involved in our private collaborative ML scheme in the global pdf.\n\n>Weakness 2\n\nAn agent will perturb the sufficient statistic (SS) when alone to protect the privacy of data owners from curious users of its ML model. For example, a hospital would not want its doctors to infer much about any patient’s data and a firm would not want employee users to infer about customers. This motivation applies to existing DP works like DP-SGD [Abadi, 2016] and DP noise-aware inference [Bernstein & Sheldon, 2018; Kulkarni et. al, 2021]. We will clarify the above in our paper.\n\nWe think that P4 is correct as (1) from the mediator's perspective, party $i$'s submitted perturbed SS is only worth $v_i$ and rationality is defined according to conventions of game theory, (2) each party may still want DP when alone, and (3) it seems natural for $i$'s reward value $r_i$ to be less than the value of its exact SS $s_i$ if $i$ selected an excessively strong DP guarantee (e.g., and collaborator $j$ only has one data point).\n\n> Can actual individual rationality (AIR) be satisfied by the mechanism? \n\nWe assume that AIR means that each party $i$'s reward value $r_i$ is at least the value of its unperturbed SS $s_i$. AIR may be satisfied when parties are incentivized enough to select a large ϵ (weak DP). However, AIR cannot be theoretically guaranteed by the mechanism as parties are still free to seek stronger DP (footnote 2) that reduces the benefit of the collaboration and the mediator cannot access the private $s_i$ to generate $i$'s model reward. \nThe mediator should use party $i$'s perturbed SS $o_i$ to generate its model reward to incentivize $i$ to be truthful and contribute more valuable information (Q2 in App.I). \n\nHowever, P4 can be theoretically guaranteed if the $𝜌$ used in the $𝜌$-Shapley fairness scheme is $\\leq 𝜌_r$ defined in Sim et al's Theorem 1. We will highlight that the stronger AIR has not been theoretically guaranteed as a limitation.\n\n>Weakness 3\n\nWe have been more precise about the exact computations and time complexity in App.F. In our revision, we will further reference the citations/pseudocode for computing the local SS, clarify that step 3 has to be repeated for each coalition $C \\subseteq N$, and step 5 uses the scaled perturbed SS $\\kappa_i o_j, \\kappa_i c_j, \\kappa_i Z_j$ for each party $j \\in N$ for noise-aware inference.\n\nWe would add that: when there are <6 parties (as in our experiments), it is feasible to compute the Shapley value (SV) exactly. When there are more parties, SV has to be approximated and the inexactness (absolute error in the SV estimate) can be controlled by sampling enough coalitions and in accordance to steps outlined by [25, M, Z].\n\n[M] Bounding the estimation error of sampling-based Shapley value approximation. arXiv:1306.4265, 2013.\n\n[Z] Probably Approximate Shapley Fairness with Applications in Machine Learning. AAAI 2023.\n\n\n> Limitations: The paper should emphasize the scope of the work. \n\nIn Sec. 2 & 8, we clearly stated that our work only covers the scope of Bayesian models with SS. \n\nOur method would still work if a party submitted perturbed SS in _multiple_ rounds of interaction instead. The value of party $i$ (coalition $C$) should be the Bayesian surprise of party $i$'s (coalition $C$'s) SS from all rounds and party $i$'s model reward involves scaling all perturbed SS across rounds by $\\kappa_i$. The mediator can reward each party only once at the end of the collaboration and make either of the following modifications to use our scheme:\n- Sum the perturbed SS across rounds for each party $i$ (due to Line 101) \n- Replace $o_N$ on Line 261 with the set of perturbed SS across rounds and modify noise-aware inference (Algo 1) by adding an extra for loop for different rounds\n\nWe will include this discussion in our revised paper.\n\n"}, {"review_id": "G4GIvjKENc", "reviewer": "Reviewer_Rv9L", "summary": "\nThis research paper investigates the intersection of data sharing incentives and privacy concerns within the realm of collaborative machine learning (ML). Collaborative ML aims to improve model quality by leveraging diversified data from multiple parties, yet the potential benefits of this practice are often hampered by concerns about privacy and the costs of sharing data.\nSeveral existing studies have acknowledged the need for incentives that encourage collaboration, such as guaranteed fair rewards for valuable data contributions. Yet, these incentive-based rewards expose the parties to privacy risks. Meanwhile, some solutions enforce differential privacy (DP) to mitigate privacy concerns but may inadvertently compromise the perceived fairness of collaboration and group welfare. This research fills the gap by proposing an incentive-aware, privacy-preserving reward scheme.\nThe authors address several questions in their investigation. They consider the impact on valuation and reward if a party demands stronger DP guarantee, suggesting that such a party's reward should generally decrease to avoid randomness due to DP noise. They propose a privacy-valuation trade-off and explore ways to value a party's data, focusing on the quality of inference of model parameters under DP. Finally, they detail a reward scheme designed to maintain privacy, individual rationality, and fairness.\n\nThe paper's significant contributions include the development of a new privacy-valuation trade-off criterion, the proposal of novel incentives, and the introduction of reward control mechanisms to adjust the distribution of posterior samples of model parameters among different parties. These solutions aim to preserve similarity to the grand coalition's model while deterring excessive DP.", "questions": "no questions ", "limitations": "yes ", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "A key strength of this paper is its addressing of a highly significant, real-world issue. Collaboration between diverse parties is a critical aspect of machine learning. However, progress in this field is often hindered by concerns surrounding privacy. Therefore, the paper's proposition of a framework that integrates privacy within the incentive scheme of a collaborative process is not just beneficial, but essential. It effectively merges theoretical constructs with pragmatic applications, fostering advancements in secure, collaborative machine learning practices. Moreover, the paper has good organization and clarity.\n", "weaknesses": "While the paper might appear to lack novelty as it adopts numerous techniques from previous work in collaborative machine learning, it does so within the context of differential privacy. This presents a unique perspective. The process of designing incentives that take into account privacy considerations necessitates an innovative approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging feedback! We appreciate your detailed and accurate summary of the contribution of our work and the strengths. We also appreciate that the reviewer has recognized the novelty of our work as the process of designing incentives that take into account privacy considerations. This necessitates an innovative approach combining numerous techniques, which is the main thrust of this paper."}, {"review_id": "6ggnTfsSII", "reviewer": "Reviewer_oNeh", "summary": "This paper studies the problem of learning a machine learning model collaboratively under differential privacy and the incentives for parties to participate in the effort. More specifically, in the papers setting, multiple parties are sharing private sufficient statistics to a central aggregator. DP induces noise to the sufficient statistics and parties with less strict privacy guarantees contribute more signal to the inference than the ones with strong privacy guarantees. Therefore, authors argue that there should be an incentive structure in participating in the scheme which rewards the parties with less strict privacy guarantees more. Besides accuracy, authors consider fairness as another desired property from the collaboration. Authors propose a method, that learns a posterior distribution for the parameter of interest using the shared private suff. stats., and releases tempered posterior samples to each client. The level of tempering will determine how close the samples are to the true posterior, and parties with stricter privacy guarantees get samples from more flattened (less tempered?) posterior. The level of tempering is selected by the central aggregator based on the Bayesian surprise which measure how much more information the parties data brings in (measure in terms of the KL divergence against the prior). Authors demonstrate empirically, that a party's reward from collaboration is a better model than simply using their own posterior learned from local data under DP. Furthermore the results show that the reward mechanism is able to give larger rewards for looser privacy guarantees. Finally, authors demonstrate that the proposed reward control mechanism outperforms an existing one (i.e. gets larger benefits from the collaboration), especially when the reward is low.", "questions": "- You say that you can optimize the $\\kappa_i$ to control $q_i(\\theta)$ using any root-finding algorithm. However, to solve the $q_i(\\theta)$ for a given $r_i^*$ you would need to optimize the KL-divergence between the tempered posterior and the prior right? As you say in Section 3, this KLD is intractable, and hence you need to deploy MCMC methods to evaluate it. How computationally expensive is this? Would you need to run the entire MCMC chain for each $\\kappa_i$ value from scratch? \n- Figures 2a and 2c: is the difference between $v_2$ and $v_N$ on the largest $\\epsilon$ due to some numerical issue in valuating the party? Or are they supposed to overlap if $r_2 = v_N$?\n- Minor comment: On line 238, you say that \"... party k will now enjoy $(1/\\tau)$-DP guarantee ...\". I guess you don't really mean this as pure DP guarantee, but as an RDP guarantee? If so, it would be good to add $\\lambda$ in the privacy notation (and call it RDP instead of DP).", "limitations": "The limitations of the method are discussed in the main paper and more thoroughly in the appendix.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I believe the setting where multiple data holders would like to collaboratively learn from sensitive data is very realistic, and proposing a reasonable incentive structure for participation is a valuable goal. The proposed structure, that promises more reward for less perturbed data, sounds reasonable to me. The theoretical properties (especially V2 and V3) of KL as a valuation function are novel as far as I know, and give a solid theoretical foundation for using it. Using tempering to control the reward is also novel and sounds like a reasonable choice.\n\nThe empirical evaluation over multiple models and data sets gives support for the incentive structure, showing that a party can gain from the collaboration and as the $\\epsilon$ grows they are rewarded more. ", "weaknesses": "The method relies on a rather strong trust model that the parties contribute honestly to the collaboration. As the surprise, which determines the valuation for a party, is computed as the KL-divergence between the parties posterior and the prior, it would be quite easy for a party to send bogus data to the mediator that would yield a large KLD (especially if the prior is know). Authors do address this limitation in Remark in line 172 (and extensively in Appendix I), but I would encourage authors to extend this discussion in the main paper as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed summary of our paper and comments. We will address some of the weaknesses and questions below and include them in the revision of our paper.\n\n> Weaknesses.\n\nThank you for referring to Appendix I for our discussion on the truthfulness assumption. We will find the space to transfer part of the discussion to the main paper.\n\n> Q1 on optimising $\\kappa_i$\n\nYes, we run the entire MC sampling for each $\\kappa_i$ value from scratch. The computational complexity is given in Appendix F. Importantly, the number of runs is only a constant factor of Step 3.\n\nWe think that our mechanism is computationally practical and can be scaled to more parties.\nWhen there are more parties, the mediator can sample coalitions according to [25, M, Z] to approximate the Shapley value (in step 3 of App F) within a desired absolute error.\n\nIn the reward phase (step 5 of App F), the  $(\\kappa_i, r_i)$  pairs evaluated for root-finding of party $i$ can be reused to identify a narrower range for root finding for the other parties, thus reducing the number of evaluations. \n\n[M] Maleki, S., Tran-Thanh, L., Hines, G., Rahwan, T., & Rogers, A. (2013). Bounding the estimation error of sampling-based Shapley value approximation. arXiv:1306.4265, 2013.\n\n[Z] Zijian Zhou, Xinyi Xu, Rachael Hwee Ling Sim, Chuan Sheng Foo, and Bryan Kian Hsiang Low.Probably Approximate Shapley Fairness with Applications in Machine Learning. AAAI, 2023.\n\n> Figures 2a and 2c:\n\nIn Fig. 2a and 2c, for the largest $\\epsilon$, we have (1) $r_2 = v_N$ and (2) party 2 model reward's value $r_2$ is slightly larger than the value of its perturbed SS $v_2$.\nRecall that the largest $\\epsilon$ corresponds to weaker privacy and thus more information in $o_2$.\n\n(1) As party 2 has the highest Shapley value, by fairness P3, party 2 should get a higher reward value than others. By P2, party 2 should get a model reward with value $r_2 = v_N$.\n\n(2) Party 2 model reward's value $r_2$ is larger than the value of its perturbed S $v_2$ as the model reward is additionally trained on the data from party 1 and 3. However, as party 1 and 3 selected moderate privacy guarantee $\\epsilon_1 = \\epsilon_3 = .2$, the increase is small.\n\n> Minor comment\nYes, it should be the RDP guarantee. We will make the correction in the paper!\n\n\n"}]

Author rebuttal:
We thank all reviewers for the encouraging feedback that recognizes the novelty of our work. We appreciate the high-quality reviews and valuable feedback which we will consider carefully in revising our paper.  In our rebuttal, we have
- Clarified the (mathematical) justifications of P1-6 (Reviewer zMuU);
- Clarified reviewers’ doubt about the problem setting by
    - Referring the reviewers to Secs. 2 & 8 which stated that our approach works for models with sufficient statistics; 
    - Explaining the need for DP and perturbed SS when alone (Reviewer kKLU);
    - Justifying our choice of rationality in P4 (Reviewer kKLU).
- Pointed the reviewers to App.F for a discussion of the computational complexity and main steps of our scheme. We also provided an alternative diagrammatic overview in the PDF attached.

Please let us know if you have any more questions, and we would be happy to address them within our allowed period.

We would like to correct a minor typo in P5: $r’_i$ should be the negated KL divergence instead. Our subsequent theory/experiment results are not impacted.


Meta-review: This paper studies the private collaborative machine learning and its incentive structures.

The reviewers are positive and agree that the problem studied in this paper is very interesting and practical, and the proposed scheme and mechanism are solid and useful. In addition, the reviewers' concerns have been well addressed.

In light of this, I recommend acceptance and encourage the authors to incorporate the suggested changes (of reviewers) into the revision.
Decision: Accept (poster)