1 2 33 4. 5 6 7 8 g 10 11 12 13 14 115 16 17 18 19 as
21
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
Wenxin Ding¹, Nihar B. Shah¹,², Weina Wang ¹ ¹ Computer Science Department, ² Machine Learning Department Carnegie Mellon University {wenxind@andrew, nihars@cs, weinaw@cs}.cmu.edu
Abstract
A major impediment to research on improving peer review is the unavailability of peer-review data, since any release of such data must grapple with the sensitivity of the peer review data in terms of protecting identities of reviewers from au- thors. We posit the need to develop techniques to release peer- review data in a privacy-preserving manner. Identifying this problem, in this paper we propose a framework for privacy- preserving release of certain conference peer-review data — distributions of ratings, miscalibration, and subjectivity – with an emphasis on the accuracy (or utility) of the released data. The crux of the framework lies in recognizing that a part of the data pertaining to the reviews is already avail- able in public, and we use this information to post-process the data released by any privacy mechanism in a manner that improves the accuracy (utility) of the data while retaining the privacy guarantees. Our framework works with any privacy- preserving mechanism that operates via releasing perturbed data. We present several positive and negative theoretical re- sults, including a polynomial-time algorithm for improving on the privacy-utility tradeoff.
11
Introduction
A fair and efficient peer-review process is of utmost impor- tance to the development of scientific research. There are, however, a large number of challenges in peer review, per- taining to its fairness and efficiency. Consequently there is an overwhelming desire to "fix" the "broken" peer review process (Rennie 2016; McCook 2006). And taking heed to this call, there is a growing amount of research on this topic. Research on improving peer review suffers from a con- siderable handicap – unavailability of data (Balietti, Gold- stone, and Helbing 2016; Tomkins, Zhang, and Heavlin 2017; Squazzoni et al. 2020; Schroter, Loder, and Godlee 2020). Concealing the identities of reviewers from authors of any paper is paramount in most peer review systems. Thus releasing any peer review data is fraught with the risk of compromising on this privacy. As noted by Balietti (2016): "The main reason behind the lack of empirical stud- 37 33 39 ies on peer-review is the difficulty in accessing data. In fact, peer-review data is considered very sensitive, and it is very seldom released for scrutiny, even in an anonymous form."" Although there is a large body of research on the topic of privacy in various domains, not much privacy research directly targets the application of peer review. In an influ- ential recent paper about peer review, Tomkins, Zhang, and Heavlin (2017) highlight the challenges they faced in this respect and their consequent inability to release data: “We would prefer to make available the raw data used in our study, but after some effort we have not been able to devise an anonymization scheme that will simultane- ously protect the identities of the parties involved and allow accurate aggregate statistical analysis. We are familiar with the literature around privacy preserving dissemination of data for statistical analysis and feel that releasing our data is not possible using current state-of-the-art techniques. "" We thus posit the need to develop techniques to help re- lease peer-review data while ensuring that identities of re- viewers of any paper are protected. With this motivation, we focus on the privacy-utility tradeoff in releasing certain con- ference peer-review data. The data to be released comprises distributions of the ratings or miscalibration or subjectivity in the peer-review process. The notion of privacy we con- sider is quite general – our techniques apply to any notion of privacy which operates by perturbing the data, including dif- ferential privacy. We design a framework to improve in this tradeoff by improving the utility (accuracy) while retaining privacy guarantees. Our work relies on the key observation that a non-trivial part of conference peer-review data is already available in the public domain. We design techniques which use this pub- licly available information to post-process the data released by any privacy mechanism. Our approach is guided by the following four desiderata for such a post processing: D1 Under no circumstances should the accuracy decrease after applying the algorithm. D2  Under no circumstances should the privacy guarantee be compromised after applying the algorithm. D3  The algorithm should have a computational complexity polynomial in the number of reviewers and papers. 1 42 43 44 45 46 47 48 49 so 51 52 53 54 55 56 57 58 59 20 61 ßß 
EL 64 65 96 67 S2 89 70 71 72 73 74 75 76 77 78 79 880 40 41 81 82 
 
 
 & 885 886 87 888 89 98 91 92 83 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 D4 In special cases where an exact answer can be easily ob- tained from public data, the algorithm should also return the same answer with no error. (This is defined formally in Section 4.3.) Our technical contributions (detailed in Section 4) to- wards this problem are as follows. We use the straightfor- ward observation that projecting the (noisy) output of the privacy mechanism on the convex hull of all possible true values is desirable from the perspective of the desiderata. We prove that, however, such a projection is NP-hard (via reduc- ing the ℓ -partition problem). We then design a polynomial- time computable algorithm which projects the noisy output of the privacy mechanism on a convex set containing all possible true values, and satisfies the four desiderata listed above. As a result of independent interest, we also prove that the more obvious approach of projecting on the set of all true values (instead of a convex set containing them) can, in fact, reduce the accuracy. Finally, in Appendix C, we conduct synthetic simula- tions, which reveal that our methods can yield considerable improvements in the privacy-utility tradeoff as compared to standard approaches. The associated code for our al- gorithm is available at https://github.com/wenxind/privacy- utility-tradeoff-in-peer-review-data.
2
Related Work
This work falls in the intersection of two lines of research: peer review and privacy. Peer review: Peer review is the backbone of scientific re- search. There is an overwhelming desire in many domains of science and engineering for improving peer review, and con- sequently, there are many past works on the topic of either evaluating the efficacy of peer review or improving the peer review process (Peters and Ceci 1982; Kliewer et al. 2004; Bennett, Jagsi, and Zietman 2018; Mavrogenis, Quaile, and Scarlat 2020; Bernard 2018; Snodgrass 2006; Scott 1974; Lindsey 1988; Douceur 2009; Reinhart 2009). These works, however, largely focus on the journal reviewing setup that is common in non-computer-science fields, whereas our focus is on the conference reviewing setting which is more com- mon in computer science. The number of submissions to many computer science conferences, particularly to machine learning or artificial in- telligence conferences, is growing near-exponentially and is presently in the several thousands. This rapid growth has spurred a considerable amount of recent research on peer review in computer science. These works include those on handling problems related to reviewer-assignment (Gold- smith and Sloan 2007; Charlin and Zemel 2013; Welch 2014; Stelmakh, Shah, and Singh 2018; Kobren, Saha, and McCallum 2019), miscalibration (Roos, Rothe, and Scheuermann 2011; Ge, Welling, and Ghahramani 2013; Wang and Shah 2019), subjectivity (Noothigattu, Shah, and Procaccia 2018), biases (Tomkins, Zhang, and Heavlin 2017; Stelmakh, Shah, and Singh 2019), strategic behav- ior (Balietti, Goldstone, and Helbing 2016; Xu et al. 2019; 2018). Stelmakh, Shah, and Singh 2020) and others (Cabanac and Preuss 2013; Fiez, Shah, and Ratliff 2019; Lawrence and Cortes 2014; Shah et al. 2018; Stelmakh et al. 2020). In par- ticular, as will be detailed later, our work is also useful to- wards releasing data pertaining to miscalibration and subjec- tivity, thereby helping in the understanding and mitigation of these problems. Privacy: Privacy-preserving data analytics has been re- ceiving rapidly increasing attention as the big-data regime emerges. There is a large body of research that investigates formal notion of privacy and quantifies the tradeoff between privacy and utility (see, ee.g., Dwork et al. 2006b; Dwork 2006; Blum, Ligett, and Roth 2008; Gaboardi et al. 2014; Wang, Ying, and Zhang 2016; Bun, Ullman, and Vadhan 2018). Among these studies, differential privacy (Dwork et al. 2006b; Dwork 2006) has become the de facto standard and has been applied to many areas. In this paper, we investigate the privacy-utility trade- off for publishing histograms of peer-review data. Privacy- preserving release of histograms has been a major focus of the literature (Chawla et al. 2005; Dwork et al. 2006a; Hay et al. 2010; Li et al. 2010; Bassily and Smith 2015; Balcer and Vadhan 2019; Abowd et al. 2019). To the best of our knowledge, existing techniques for improving the privacy- utility tradeoff are generally inadequate for the application of peer review since they do not take into account the spe- cial structures in peer-review data. In particular, one special feature of peer-review data is that some specific part of the data such as scores received by papers is already published in its original, non-privacy- preserving form. This provides us an opportunity to utilize the "consistency" with public knowledge. The concept of consistency, with different problem-specific meanings, has been investigated by existing work for privacy-preserving algorithms. Hay et al. 2010 improves accuracy by assuring consistency among answers to different queries. The clos- est work to ours is the privacy-preserving approach for US Census (Abowd et al. 2019), where consistency with public data is a requirement and it is in the form of a set of linear constraints. In contrast, we are not subject to a strict require- ment of consistency, but instead, we exploit consistency as a method to improve accuracy. Additionally, the consistency with public knowledge in our problem is of a more combina- torial nature. As we discuss in the sequel, the idiosyncratic nature of the peer-review setting implies that one can design methods tailored to this application which yield a (consid- erable) improvement in the privacy-utility tradeoff as com- pared to standard privacy mechanisms. Peer review and privacy: An exception is the concur- rent work (Jecmen et al. 2020) which considers releasing the reviewer-paper similarity matrix and source code for the reviewer assignment (whereas in contrast we consider re- leasing a function of the scores given by reviewers to pa- pers). Their approach involves modifying and randomizing the reviewer-paper assignment process and their guarantees pertain to plausible deniability (that is, any reviewer may be assigned to any paper with a probability at most a certain value). On the other hand, we do not modify the peer-review process in any way, and instead use any privacy-preserving 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 data-release mechanism coupled with post processing of the data from peer review. 197 198 199 200
201
Background and problem setting
3
In this section, we provide some background on the peer review setting and privacy, and describe our problem setting in more detail.
Peer review
3.1
We consider a conference peer review setting, where there are n reviewers and m papers. We index the papers as [ m ] = {1, 2, . . . , m} and the reviewers as [n] = {1, 2, . . . , n} . 2 For simplicity we assume that the number of papers re- viewed by each reviewer is the same for all reviewers – denoted as ℓ , and that the number of reviewers reviewing each paper is the same for all papers – denoted as k . 3 Conse- quently, we have the relation nl = mk . All four parameters ( n, m, ℓ, k ) are public knowledge. Each review comprises a real-valued score. We assume that all papers and all associated reviews (that is, the set of scores received by each paper) are public knowledge (e.g., in conferences such as ICLR and others on the OpenReview.net review platform). The list of all reviewers is also available publicly (such a list is released by many conferences). How- ever, importantly, the identity of which reviewer reviewed which paper is private. We now introduce notation to describe the score given in any review. If reviewer j ∈ [ n ] reviews paper i ∈ [ m ], then we use s ij E R to denote the score of this review. This score is private in the sense that the identity of the re- viewer who gives this score is not publicly available. How- ever, for each paper i ∈ [m] , the multiset { s ij | reviewer j ∈ [n] reviews paper i} is public. This setting can be described by a bipartite graph, as shown in Figure 1. The bipartite graph has two disjoint sets of vertices, [ m ] and [ n ] representing the sets of papers and reviewers, repectively. In private data (Figure 1a), an edge exists between any vertex (paper) i E [m] and any ver- tex (reviewer) j ∈ [n] if reviewer j ∈ [n] reviews paper i  ∈  [m]. We associate each edge (i,j) with the score sij. The edges (and their associated scores) are all private. The private data is accessible to the program chairs of the confer- ence. In public data (Figure 1b), for each vertex (paper) in [m] , the weights of the edges connected to it are known pub- licly. However, the edges of the graph are not known. Note that in both public and private data, identities of papers and reviewers are known. There are various quantities of interest for release that we consider in this work. An intermediate set of terms to- wards these quantities is the multiset { w ij | reviewer j ∈ [n] reviews paper i ∈ [m]} discussed below, which we refer to as the set of weights. This multiset can be computed from the scores { s i j | reviewer j ∈ [ n ] reviews paper i ∈ [ m ]}. Figure 1: An illustration of the data (a) available privately to the program chairs of the conference, and (b) available to the public under increasingly popular 'open review' paradigms in computer science. We now discuss three such choices of { w ij | reviewer j ∈ [n] reviews paper i ∈ [m]} , and subsequently describe the data we aim to release. • Reviewer ratings. In this case, the mapping from scores to weights is simply the identity mapping:
246 247 248 249 250
251 252 253 254 255 256 257 258 259 260 •  Miscalibration. Miscalibration pertains to the problem of strictness or leniency of different reviewers, which can govern the fate of papers (Roos, Rothe, and Scheuer- mann 2011; Ge, Welling, and Ghahramani 2013; Wang and Shah 2019). In order to understand the amount of miscalibration, it is instructive to see the difference be- tween the scores given by a reviewer and the scores given by other reviewers for the same papers. To this end, we let w ij denote the miscalibration in any individual review (for any paper i by any reviewer j ):
• Subjectivity. Subjectivity is the problem that different re- viewers place different emphasis on the various criteria when making an overall decision for a paper (Lee 2015). Techniques such as that proposed in Noothigattu, Shah, and Procaccia 2018 can be used to normalize each score in a manner that mitigates the subjectivity. Specifically, the technique in Noothigattu, Shah, and Procaccia 2018 uses the public data to transform the score s ij associated to each review into a normalized version, say, š ij . We can then set w ij =  š ij for every review, and the algorithm in this paper will help release statistics of these normal- ized scores. A second use case we consider is to better understand and investigate the issue of subjectivity, by releasing the amount of subjectivity present in the sys- tem, that is, the aggregate difference of reviewers' scores 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 and their normalized scores. Concretely in this case, af- 276 ter obtaining the normalized scores {͡s ij ] reviewer j  ∈ 277 [n] reviews paper i ∈ [m]}, we set wij =  sij −  šij for 278 every review. 279 Analogous to the scores s ij 's, the weights w ij 's are also 280 associated to public and private components. We can use the 281 same bipartite graphs as in Figure 1 to represent the set- 282 ting with weights. In particular, the private data continues 283 to include the edges pertaining to which reviewer reviewed 284 which paper. The private data also includes the weight w ij 285 on each edge ( i , j ) representing the weight that reviewer 286 i  ∈  [n] gives to paper j  ∈  [m] . The private data is de- 287 picted in Figure 1a where in this interpretation, the values 288 on the edges represent the weights. The public data, as in the 289 case of scores, only includes the multiset of weights received 290 by any paper, that is, the public data comprises the multi- 291 sets { w ij | reviewer j ∈ [ n ] reviews paper i } for every paper 292 i ∈ [m] . The public data is depicted in Figure 1b where the 293 values on the edges represent the weights. 294 It is very important to note the following two properties 295 in the transformation of scores s ij to weights w ij for each 296 of the aforementioned choices. First, clearly, given access 297 to all private scores, all weights can be computed. Second, 298 the public weights (that is, the multisets { w ij |reviewer j ∈ 299 [n] reviews paper i} for every paper i ∈ [m]) can be com- 300 puted using only the publicly available score data (that is, 301 the multisets { s ij | reviewer j ∈ [ n ] reviews paper i } for ev- 302 ery paper i ∈ [m] ). This relation between the public (or pri- 303 vate) weights and public (or private) scores allows us to in- 304 terchange them in the graphs in Figure 1. 305 For each reviewer j  ∈  [n], let Yj be the set of all 306 papers reviewed by reviewer j , that is, Yj = 307 | 2 [m] | reviewer j reviews paper i}. Let yj denote the mean 308 309 weight of reviewer j :
Note that since the identity of the reviewer in any review is private, the values of Y j and y j in general cannot be com- puted from the public data. Quantity to be released: The quantity of interest is the histogram of the mean weights per reviewer, represented by the sorted version of the mean-weight vector ( y 1 , y 2 , …, y n ), which we denote by θ* = (θ*,θ*,…,θ*,). Then θ* < ... < θ * and the multiset (θ * ,θ * , ...,θ * ) equals the multi- set ( y 1 , y 2 , …, y n ). We call θ * the true sorted mean-weight vector. According to the applications discussed above, the vector θ* can either represent the mean scores per reviewer or capture the amount of miscalibration, or subjectivity in the reviews. Our goal is to release θ* , while ensuring privacy of re- viewer identities. When the underlying weights are equal to the scores, the sorted mean-weight vector (that is, the his- togram of scores) is commonly released by various confer- ences (Shah et al. 2018). These are however usually released without any privacy considerations, and our work addresses privacy-preserving release with high accuracy. Addressing the issues of miscalibration and subjectivity is extremely im- portant for fair and high-quality peer review (Ge, Welling, and Ghahramani 2013; Wang and Shah 2019; Roos, Rothe, and Scheuermann 2011; Lee 2015; Noothigattu, Shah, and Procaccia 2018; Siegelman 1991; Kerr, Tolliver, and Petree 1977), and releasing the statistics pertaining to the amount of miscaliabraiton or subjectivity can considerably help both research and policy-design regarding these issues. Publishing histograms of datasets in a privacy-preserving manner has been a central objective in the literature of pri- vacy research (Chawla et al. 2005; Dwork et al. 2006a; Hay et al. 2010; Li et al. 2010; Bassily and Smith 2015; Balcer and Vadhan 2019). Histograms are typically the most fre- quently used statistics in official reports, and more impor- tantly, they form the basis for more complicated statistical analysis. To the best of our knowledge, existing techniques for improving the privacy-utility tradeoff (for histograms or otherwise) are generally inadequate for the application of peer review since they do not take into account the special structures in peer-review data. Our goal is to use the spe- cific type of publicly available data in peer review in order to improve the privacy-utility tradeoff. Finally we note that the high-level ideas behind our pro- posed algorithm are more general and may also be used to improve the utility of the released data for settings beyond the sorted mean-weight vector. We revisit this point later in the paper.
3.2  Privacy
To protect the privacy of reviewers, we consider privacy- preserving mechanisms that (randomly) perturb the quan- tities of interest. By virtue of the random perturbation, the privacy mechanism makes it hard to infer each individual re- viewer's scores given to papers from the noisy data. Specif- ically, we consider any privacy mechanism that releases a vector r = (r1,r2,...,rn) E Rn obtained by randomly per- turbing the sorted mean-weight vector (θ ῖ , θ ῖ , …, θ ῖ , θ ῖ , θ ῖ , ∈ R n . An example of a privacy mechanism is the Laplace mecha- nism, which satisfies the popular notion of differential pri- vacy (Dwork et al. 2016; Dwork and Roth 2014) in which ( r 1 , r 2 , …, r n )  =  (θ ∗ ,θ ∗ ,…,θ ∗ ) + (η 1 ,η 2 ,…,η π ). Here ཀｭ, ཀ₂, . . . , ཀ n are i.i.d. random variables drawn from a zero- mean Laplace distribution.
3.3
Utility (Accuracy)
Let t = (t 1 , · · · ,t n ) denote the final output (after post- processing) that is released. We measure the utility or ac- curacy of the output in terms of its mean squared error with respect to the true value of the vector θ *, that is, . We say that an (possibly random) out- .., t n ) is more accurate than another output put t = ( t ′ , …, t' n ) with respect to θ* if 3.4
Our goal is to design algorithms to process the data output by the privacy-preserving mechanism, r , before its actual re-
380 381 382 383 384 385 lease in a manner that improves the privacy-utility tradeoff. Specifically, we aim to satisfy the four desiderata D1–D4 listed in Section 1.
386
387
Main Results
4
4.1
Approach
388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 We first derive a representation of the set of all possible val- ues in the sorted mean-weight vector θ* based on the public data. For any paper i ∈ [m] , we use x i1 , x i2 , · · · , x ik to de- note the k weights on edges connected to that vertex (paper) in the public data, listed in an arbitrary order. Note that the second subscript of x ij does not correspond to a reviewer identity. The multiset { x 11 , · · · , x mk } is available publicly, and for each i ∈ [m] , the multiset { x i1 , · · · , x ik } is identi- cal to the multiset { w ij | reviewer j ∈ [ n ] reviews paper i } . Let G be a set of weighted bipartite graphs comprising all valid reviewer-paper weights based on the public data, that is, each member of G satisfies: • It is a bipartite graph, with the vertices in the two parts corresponding to papers [m] and reviewers [n] . • All vertices in [ m ] are k regular and all vertices in [ n ] are ℓ regular. • The k edges incident on any vertex i ∈ [ m ] have weights Xil, Xi2,..., Xik. Furthermore, for any graph g ∈ G , any paper i , and any reviewer j , we define wij(g) equal to the weight of edge between i and j if this edge exists, and w ij (g) = 0 other- wise. Then the set Θ, that comprises all possible values of the sorted mean-weight vector based on public data, is given by
412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 true sorted mean-weight vector θ*, the noisy mean-weight vector r obtained by adding Laplace noise with zero mean and a fixed, non-zero variance to θ* , and the output t of the projection (4.2) of r on the set C = Θ, are related as
430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452
453 454 where the expectation is taken with respect to the noise dis- tribution. The proposition implies that using the closest valid vector violates desideratum D1 of not reducing the accuracy. The proof of Proposition 4.1 is given in Appendix D.1. Consequently, in order to ensure desideratum D1 of not reducing the accuracy is met, we project the noisy data onto a convex set that contains Θ. The following proposition (proved in Appendix D.2) indicates that such projection can never harm the accuracy, and is a straightforward application of the fact that projection on to convex sets is non-expansive. Note that projection methods have been used in the litera- ture (Hay et al. 2010; Abowd et al. 2019) and it is known that projection does not decrease accuracy. For complete- ness, we include Proposition 4.2 here as the specific form of such results for our problem. Proposition 4.2. Consider any true sorted mean-weight vector θ*, and any arbitrary (noisy mean-weight) vector r. Let C be any closed convex set such that Θ ⊆ C. Let t = (t 1 , …, t n ) be the projection of r on to set C as in (4.2). Then it must be that Since proposition 4.2 holds for all r , it follows that if r is obtained by randomly perturbing θ *, then
Moreover, for two closed convex sets C 1 ⊆ C 2 both contain- ing Θ, if we have a projection on C 2 , then further projecting it on C 1 can never increase the error and can possibly de- crease the error. Our goal thus is to project the noisy data on to a (small) convex set that contains all possible true values. 455 456 457 458 459 460
NP-hardness of Projection onto Convex Hull
4.2
461 462 463 464 465 466 467 468 469 Consequently, in this section we consider the goal of pro- jecting the noisy data onto the convex hull of Θ . In this case, the final result we will output can be represented as choosing C = convex-hull(Θ) in Equation (4.2). Unfortunately, as we show below, projection onto convex-hull(Θ) is NP-hard. 470 471 472 473 474
When the privacy-preserving algorithm perturbs the true sorted mean-weight vector θ *, the resulting noisy mean- weight vector r may not lie in the set Θ. It is thus intuitive to instead replace the resulting vector with the vector in Θ closest to it, that is, to instead output the projection (4.2) of the vector r with the choice C = Θ. The following result shows that this intuitive approach can actually increase the error. We state and prove this result concretely in the case of additive Laplace noise, but as seen in the proof, the result is much more general. Proposition 4.1.  There exists a review setting such that the Note that the true paper-reviewer graph is also a member of G and the true sorted weight vector θ* ∈ Θ. Throughout this section, we consider algorithms based on projecting the noisy data on certain sets. To this end, for any set C ⊂ R n , we define the projection of vector r on the set C as The smallest convex set that contains Θ is the convex hull of Θ. Observe that if we could project on to the convex hull, then it can also be used to improve upon the projection on any other convex set. Specifically, if t is the projection of the perturbed data r on some convex set that contains Θ, and if t ′ is the projection of t on convex-hull(Θ), then with an argument identical to that in Proposition 4.2 we have that 475 476 477 478 479 480 481 482 483 484
4.3
485
486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 Theorem 4.3. When k = ℓ > 2, m = n and n is a multi- ple of ℓ, the problem of projecting noisy data onto convex- hull(Θ) is NP-hard. We prove this result via reducing the l -Partition prob- lem to the projection problem. Given any instance of an ℓ- Partition problem, which is a multiset of integers, we can construct a conference where each paper has a weight from the multiset. We can construct a vector such that the projec- tion result can directly answer the l -Partition problem. The complete proof of Theorem 4.3 is provided in Appendix D.3.
An Efficient Algorithm
In this section, we present an algorithm that meets the four desiderata D1–D4 listed in Section 1. Since we cannot effi- ciently project on to the convex hull of Θ, we must make do with a larger convex set that contains Θ. We use desidera- tum D4 for guidance on what constitutes a reasonably small set and associated projection. Axioms defining desideratum D4 Recall that desidera- tum D4 says that the algorithm should automatically recover the ground truth when the structure of the public data is sim- ple enough. More concretely, we benchmark any algorithm using the following axiomatic properties: A1 When all weights are identical, the projection should re- sult in a vector whose entries are all the same as the weight. Formally, if x ij  =  z ∀ i  ∈  [m], j  ∈  [k] for some z , then the output t of the algorithm must be t 1 = t 2 = ··· = t n = z. A2 When ℓ = 1 (that is, each reviewer reviews 1 pa- per), the projection of any noisy data should result in a sorted vector of all weights. Formally, if ℓ = 1 then the output t of the algorithm must be (t 1 ,t 2 , · · · ,t n ) = sorted( x 11 , x 21 , . . . , x n 1 ). A3 When all but one papers have all zero weights, the projection of any noisy data should result in a sorted vector with (n − k) zero entries and the remain- ing entries equal to  f of the weights for the pa- per that does not have all-zero weights. Formally, if x ij = 0 Vi E {2,...,m},j E [k], then the out- put t of the algorithm must be (t 1 ,t 2 , . . . ,t n ) = sorted( ˃˃˃, ˃˃, ˂̶High-level idea behind the algorithm The main idea be- 515 516 I. 517 518 II. 519 520 III. 521 522 523 524 525 526 527 528 529 530 hind our algorithm comprises the following three steps: From the public data, take all tuples of size ℓ contain- ing weights from different papers into consideration. Use them to construct lower and upper bounds on ev- ery entry of (the unknown vector) θ*. Project the noisy data r on the set specified by the aforementioned lower and upper bounds, along with any other problem-specific (convex) constraints. As one can intuitively see, these three steps imply a pro- jection of the noisy data on a convex set which includes all valid values of the true data, and hence from Proposition 4.2 it will not reduce the utility (desideratum D1). Moreover, the entire algorithm uses only the public data along with the vec- tor r released by the privacy mechanism, and hence does not compromise privacy (desideratum D2). The idea is general enough to be applied to many forms of the noisy data, and in what follows, we apply it to release the histogram of the true sorted mean-weight vector. Of course, the devil lies in the details of how these steps are executed, which will deter- mine whether the designed algorithm meets desiderata D3 and D4. 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 5G 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 Full algorithm description We now describe our algo- rithm in full detail. (We also provide an illustrative exam- ple in Appendix B.) Recall that we use x i1 , x i2 , . . . , x ik to represent the k weights on edges connected to any vertex (paper) i ∈ [ m ] in the public data. Note that since reviewer identities are not available publicly, the second subscript " j " in “ x ij ” has no particular meaning other than capturing the fact that each paper has k weights. We use matrix X to dis- play all the weights in the public data where row i column j of X has value x ij I. Valid weight tuples We define a weight tuple as a mul- tiset of ℓ real values. We say that a tuple is a valid weight tuple if it consists of ℓ weights from distinct papers. In other words, a valid weight tuple contains ℓ entries of matrix X where no two entries are from the same row in X . We com- pute Ω′ as the list of all valid weight tuples. In other words, Ω′ contains all the possible weight tuples given by a re- viewer. We sort the list Ω ′ based on the mean weight of the weight tuples (breaking ties arbitrarily), and henceforth use the notation Ω for this sorted list. II. Lower and upper bounds We now compute lower and upper bounds on each entry of θ * based only on the public data. We create a graph G which has all weight tuples in Ω as its vertices. Since each weight tuple in Ω corresponds to a vertex in graph G , we use the terms "weight tuples in Ω" and "vertices in G" interchangeably. There is an edge between two vertices if the two weight tuples do not contain weights corresponding to the same entry in X . Then for each vertex, we define its left chain and right chain as follows. Recall that Ω is a sorted list and all of its entries, which are weight tuples, are totally ordered. We use the indices of the tuples (vertices) in this ordering for the following definitions. Definition 4.4. For any vertex ν in G , a left chain (resp. right chain) of ν is a simple path in G from ν to another ver- tex such that the indices of the vertices in this path decrease (resp. increase) starting from ν . We also define the length of a chain to be the number of vertices in the chain. For each vertex, we compute the length of its longest left chain and the length of its longest right chain using dynamic programming. To compute the length of the longest left chain of a vertex ν in G , we check the length of the longest left chain of all its neighbors at lower indices. Then the length of the longest left chain of ν is the maximum of these neighbors' longest left chain lengths plus one. Similarly, to compute the length of the longest right chain of ν , we check the length of the longest right chain of all its neighbors at higher indices. The length of the longest right chain of ν is the maximum of its neighbors' longest right chain lengths plus one. We store the length of the longest left and right chain of each vertex for subsequent use in the algorithm. The algorithm to compute a lower bound on θ ∗ for each 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 653 665 666 667 668 669 670 671 672 673 674 675 676 Algorithm 1: Computation of lower bounds Input: matrix X of weights, sorted list of weight tuples Ω Initialize i = 1, set w ∈ R ℓ as the first tuple in Ω , and all entries of X are unmarked. while i ≤ n do for each weight in the tuple w , find its corresponding entry in matrix X and mark the entry if length of tuple w’s longest left chain > i and number of unmarked entries on each row of X ≤ n − i then lower bound on θ * = mean of all entries of tuple w i+ = 1 end if set w as the next tuple in Ω end while i ∈ [ n ] is presented in Algorithm 1. In more detail, the al- gorithm uses two criteria to determine if mean of a weight tuple is a lower bound on θ * . The criteria are C1 The longest left chain of the tuple has length at least i. C2  In X , after we mark the ℓ weights from each tuple con- sidered so far, each row has at most n — i unmarked entries. The intuition is as follows. We call the n weight tuples that compute θ* the true weight tuples. The true weight tu- ple with mean θ * must have i − 1 weight tuples with smaller or equal mean to θ * . No two reviewers give the same weight so no two true weight tuples contain weights from the same entry in X . Thus, criterion C1 is a necessary condition for a weight tuple to be the true weight tuple that computes θ ∗ . In addition, there are n − i entries in θ * whose values are no smaller than θ ∗ . Since no two true weight tuples contain weights from the same paper, each paper can have at most n − i unused weights. Therefore, each row of X cannot have more than n − i unmarked entries. Thus, criterion C2 is nec- essary for all weights to be assigned among the reviewers. For each entry i ∈ [ n ], we choose the valid weight tuple with the smallest mean that satisfies criteria C1 and C2 as the lower bound on θ . * . Hence, it is a valid lower bound. The computation of the upper bounds is analogous to that of lower bounds, and is presented in Appendix A in detail. III. Projection Let L i denote the lower bound we com- pute on θ ε and U ε denote the upper bound we compute on θ *  in part II above. The final output of our algorithm is the solution to the following optimization problem: 589 590 591 592 593 594 595 596 597 598 599 600 601 602 6CC 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621
This convex optimization problem with a quadratic objec- tive and 2 n linear constraints can be solved efficiently. Remark 4.5 (Extension to non-uniform paper and reviewer loads).  Our algorithm easily extends to the setting of non- uniform reviewer and paper loads. First, if the papers are reviewed by different number of reviewers, the algorithm above continues to work. Now if the reviewers review dif- ferent numbers of papers, then we make the following mod- ification to the algorithm. Let L ⊂ [m] denote the set of all paper loads on the reviewers, that is, ℓ ∈ L   ←⇒  there is a reviewer who reviews exactly ℓ papers. Then the set Ω′ computed in the first step of the algorithm includes all weight tuples of size ℓ for every ℓ ∈ the algorithm remains identical to that described above. The proof of correctness in these settings follows from the same arguments (given in Appendix D.5) as those for the setting of uniform reviewer and paper loads. The algorithm contin- ues to have a computational complexity that is polynomial in n and m (where we continue to assume that the maximum reviewer and paper loads are constants (Shah et al. 2018)). In this section, we evalu- Guarantees of Our Algorithm ate our algorithm with respect to the four desiderata listed in Section 1. We first prove the correctness of the algorithm in terms of projection on to an appropriate set. Theorem 4.6.  The algorithm projects noisy data onto a con- vex set that contains all true values. The proof of this theorem is given in Appendix D.5. This result, combined with Theorem 4.2, guarantees that our al- gorithm does not increase the error. Thus, our algorithm sat- isfies desideratum D1. In addition, since our algorithm uses only the public data for post processing, it satisfies desider- atum D2. We now discuss the computational complexity of our algorithm. Theorem 4.7.  The algorithm has polynomial time complex- ity in the number of reviewers and the number of papers. Our algorithm thus satisfies desideratum D3. The proof of this theorem is given in Appendix D.6. To be clear, while the algorithm is polynomial time in n and m , it is exponential in ℓ . In practice ℓ is usually a small constant (Shah et al. 2018). We finally visit desideratum D4 – of returning an exact answer when it can easily be deduced from public data. Theorem 4.8.  The algorithm satisfies the axiomatic proper- ties A1, A2 and A3 defined in Section 4.3. The proof of this theorem is given in Appendix D.7. We have thus shown that our proposed algorithm meets all four desiderata D1–D4.
Conclusion
5
We take the first steps towards designing methods for privacy-preserving release of peer-review data, and posit the need for much more research on this topic to address the important challenge of improving peer review. While we addressed a certain type of peer-review data, it is of the- oretical and practical interest to enable privacy-preserving release of more peer-review data such as properties of the reviewer graph, reviewer bids, and other functions of the scores. Moreover, it is of interest to design methods that can utilize data from multiple conferences, while preserving the privacy in each conference, for improving the peer-review process in any subsequent conference. 664 678 679 680 681 682 683 684 Abowd, J.; Kifer, D.; Moran, B.; Ashmead, R.; Leclerc, P.; Sexton, W.; Garfinkel, S.; and Machanavajjhala, A. 2019. Census TopDown: Differentially Private Data, Incremental Schemas, and Consistency with Public Knowledge. US Cen- sus Bureau. https://github.com/uscensusbureau/census2020- das-e2e/blob/master/doc/20190711_0945_Consistency_for_ Large Scale Differentially Private Histograms.pdf. 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 Chawla, S.; Dwork, C.; McSherry, F.; and Talwar, K. 2005. On Privacy-Preserving Histograms. In Conf. Uncertainty in Artificial Intelligence (UAI), 120–127. Douceur, J. R. 2009.  Paper rating vs. paper ranking.  ACM SIGOPS Operating Systems Review 43(2): 117–121. Dwork, C. 2006.  Differential privacy.  In Proc. Int. Conf. Automata, Languages and Programming (ICALP), 1–12. Venice, Italy. Dwork, C.; Kenthapadi, K.; McSherry, F.; Mironov, I.; and Naor, M. 2006a. Our data, ourselves: privacy via distributed noise generation.  In Proc. Annu. Int. Conf. Theory and Applications of Cryptographic Techniques (EUROCRYPT), 486–503. St. Petersburg, Russia. Dwork, C.; McSherry, F.; Nissim, K.; and Smith, A. 2006b. Calibrating noise to sensitivity in private data analysis.  In Proc. Conf. Theory of Cryptography (TCC), 265–284. New York, NY. Dwork, C.; McSherry, F.; Nissim, K.; and Smith, A. 2016. Calibrating noise to sensitivity in private data analysis. Jour- nal of Privacy and Confidentiality 7(3): 17–51. Dwork, C.; and Roth, A. 2014.  The Algorithmic Founda- tions of Differential Privacy.  Found. Trends Theor. Comput. Sci. 9(3–4): 211–407. Fiez, T.; Shah, N.; and Ratliff, L. 2019.  A SUPER* Algo- rithm to Optimize Paper Bidding in Peer Review.  In ICML workshop on Real-world Sequential Decision Making: Re- inforcement Learning And Beyond. Gaboardi, M.; Arias, E. J. G.; Hsu, J.; Roth, A.; and Wu, Z. S. 2014.  Dual Query: Practical Private Query Release for High Dimensional Data. In Int. Conf. Machine Learning (ICML). Beijing, China. Ge, H.; Welling, M.; and Ghahramani, Z. 2013. A Bayesian model for calibrating conference review scores. URL {http: //mlg.eng.cam.ac.uk/hong/nipsrevcal.pdf}. Goldsmith, J.; and Sloan, R. H. 2007. The AI conference pa- per assignment problem. In Proc. AAAI Workshop on Prefer- ence Handling for Artificial Intelligence, Vancouver , 53–57. Hay, M.; Rastogi, V.; Miklau, G.; and Suciu, D. 2010. Boost- ing the accuracy of differentially private histograms through consistency.  Proceedings of the VLDB Endowment 3(1-2): 1021–1032. Jecmen, S.; Zhang, H.; Liu, R.; Shah, N. B.; Conitzer, V.; and Fang, F. 2020. Mitigating Manipulation in Peer Review via Randomized Reviewer Assignments. arXiv . 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 Bassily, R.; and Smith, A. 2015.  Local, Private, Efficient Protocols for Succinct Histograms. In Proc. Ann. ACM Symp. Theory of Computing (STOC) , 127–135. Portland, OR. Bauschke, H. H.; Combettes, P. L.; et al. 2011. Convex anal- ysis and monotone operator theory in Hilbert spaces , vol- ume 408. Springer. Bennett, K. E.; Jagsi, R.; and Zietman, A. 2018.  Radiation oncology authors and reviewers prefer double-blind peer re- Proceedings of the National Academy of Sciences view. 115(9): E1940–E1940. Bernard, C. 2018. Gender Bias in Publishing: Double-Blind Reviewing as a Solution?  Eneuro 5(3). Blum, A.; Ligett, K.; and Roth, A. 2008.  A learning the- ory approach to non-interactive database privacy.  In Proc . Ann. ACM Symp. Theory of Computing (STOC) , 609–618. Victoria, Canada. Bun, M.; Ullman, J.; and Vadhan, S. 2018. Fingerprint- ing Codes and the Price of Approximate Differential Pri- SIAM Journal on Computing 47(5): 1888–1938. vacy. doi:10.1137/15M1033587. URL  https://doi.org/10.1137/ 15M1033587. Cabanac, G.; and Preuss, T. 2013.  Capitalizing on order effects in the bids of peer-reviewed conferences to secure reviews by expert referees.  Journal of the Association for Information Science and Technology 64(2): 405–415. Charlin, L.; and Zemel, R. S. 2013.  The Toronto Paper Matching System: An automated paper-reviewer assignment system. In ICML Workshop on Peer Reviewing and Publish- ing Models. Balietti, S. 2016.  Science is suffering because of peer re- view’s big problems. The Conversation . Babel, L.; Kellerer, H.; and Kotov, V. 1998. Thek- partitioning problem. Mathematical Methods of Operations Research 47(1): 59–82. Balcer, V.; and Vadhan, S. 2019.  Differential Privacy on Finite Computers.  Journal of Privacy and Confidentiality 9(2). doi:10.29012/jpc.679. 677 Balietti, S.; Goldstone, R. L.; and Helbing, D. 2016. Peer re- view and competition in the Art Exhibition Game. Proceed- ings of the National Academy of Sciences 113(30): 8414– 8419. Kerr, S.; Tolliver, J.; and Petree, D. 1977.  Manuscript char- acteristics which influence acceptance for management and social science journals.  Academy of Management Journal 20(1): 132–141. Kliewer, M. A.; DeLong, D. M.; Freed, K.; Jenkins, C. B.; Paulson, E. K.; and Provenzale, J. M. 2004.  Peer review at the American Journal of Roentgenology: How reviewer and manuscript characteristics affected editorial decisions on 196 major papers.  American Journal of Roentgenology 183(6): 1545–1550. Kobren, A.; Saha, B.; and McCallum, A. 2019. Pa- per Matching with Local Fairness Constraints.  In ACM SIGKDD International Conference on Knowledge Discov- ery & Data Mining. 785 786 787 Lawrence, N.; and Cortes, C. 2014. The NIPS Exper- http://inverseprobability.com/2014/12/16/the-nips- iment. experiment. [Online; accessed 11-June-2018]. 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 Stelmakh, I.; Shah, N.; and Singh, A. 2018. PeerRe- view4All: Fair and Accurate Reviewer Assignment in Peer Review. arXiv preprint arxiv:1806.06237 . Stelmakh, I.; Shah, N.; and Singh, A. 2019.  On Testing for Biases in Peer Review. In NeurIPS . 839 840 Stelmakh, I.; Shah, N.; and Singh, A. 2020.  Catch Me if I Can: Detecting Strategic Behaviour in Peer Assessment. arXiv . 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 Stelmakh, I.; Shah, N.; Singh, A.; and Daumé III, H. 2020. Prior and Prejudice: The Bias against Resubmissions in Conference Peer Review. arXiv . Tomkins, A.; Zhang, M.; and Heavlin, W. D. 2017. Reviewer bias in single-versus double-blind peer review.  Proceedings of the National Academy of Sciences 114(48): 12708–12713. Wang, J.; and Shah, N. B. 2019.  Your 2 is My 1, Your 3 is My 9: Handling Arbitrary Miscalibrations in Ratings.  In AAMAS. Wang, W.; Ying, L.; and Zhang, J. 2016. On the rela- tion between identifiability, differential privacy, and mutual- information privacy.  IEEE Trans. Inf. Theory 62(9): 5018– 5029. Welch, I. 2014.  Referee recommendations.  The Review of Financial Studies 27(9): 2773–2804. Xu, Y.; Zhao, H.; Shi, X.; and Shah, N. 2019.  On Strate- gyproof Conference Review. In IJCAI. Noothigattu, R.; Shah, N. B.; and Procaccia, A. D. 2018. Loss Functions, Axioms, and Peer Review.  arXiv preprint arXiv:1808.09057 . Peters, D. P.; and Ceci, S. J. 1982.  Peer-review practices of psychological journals: The fate of published articles.  Be- havioral and Brain Sciences 5(2): 187–255. Reinhart, M. 2009.  Peer review of grant applications in bi- ology and medicine. Reliability, fairness, and validity.  Sci- entometrics 81(3): 789–809. Rennie, D. 2016. Make peer review scientific. Nature 535(7610): 31–34. Roos, M.; Rothe, J.; and Scheuermann, B. 2011.  How to Calibrate the Scores of Biased Reviewers by Quadratic Pro- gramming.  In AAAI Conference on Artificial Intelligence. Schroter, S.; Loder, E.; and Godlee, F. 2020.  Research on peer review and biomedical publication. Scott, W. A. 1974. Interreferee agreement on some charac- teristics of manuscripts submitted to the Journal of Person- ality and Social Psychology.  American Psychologist 29(9): 698. Shah, N. B.; Tabibian, B.; Muandet, K.; Guyon, I.; and Von Luxburg, U. 2018.  Design and analysis of the NIPS 2016 review process. The Journal of Machine Learning Re- search 19(1): 1913–1946. Siegelman, S. S. 1991.  Assassins and zealots: variations in peer review. Radiology 178(3): 637–642. Snodgrass, R. 2006.  Single- Versus Double-Blind Review- ing: An Analysis of the Literature.  SIGMOD Record 35: 8–21. doi:10.1145/1168092.1168094. Squazzoni, F.; Ahrweiler, P.; Barros, T.; Bianchi, F.; Birukou, A.; Blom, H. J.; Bravo, G.; Cowley, S.; Dignum, V.; Dondio, P.; et al. 2020.  Unlock ways to share data on peer review. Lee, C. J. 2015. Commensuration bias in peer review.  Phi- losophy of Science 82(5): 1272–1283. Li, C.; Hay, M.; Rastogi, V.; Miklau, G.; and McGregor, A. 2010. Optimizing Linear Counting Queries Under Differen- tial Privacy. In Symp. Principles Database Systems (PODS) , 123–134. Indianapolis, IN. Lindsey, D. 1988.  Assessing precision in the manuscript review process: A little better than a dice roll. Scientometrics 14(1-2): 75–82. Mavrogenis, A. F.; Quaile, A.; and Scarlat, M. M. 2020. The good, the bad and the rude peer-review. McCook, A. 2006.  Is peer review broken? Submissions are up, reviewers are overtaxed, and authors are lodging com- plaint after complaint about the process at top-tier journals. What's wrong with peer review? The scientist 20(2): 26–35. 853 884 865 866 867 888 869 870 871 872 The computation of upper bounds is similar to the method- ology in Algorithm 1 from Section 4.3 and is presented in Algorithm 2. The two criteria we use to determine if mean of a tuple is an upper bound on θ ∗ are C3 The longest right chain of the tuple has length at least n − i + 1. C4  In X , after we mark the ℓ weights from each tuple con- sidered so far, each row has at most i — 1 unmarked entries. Algorithm 2: Computation of upper bounds Input: matrix X of weights, sorted list of weight tuples Ω Initialize i = 1, set w ∈ R ℓ as the first tuple in Ω , and all entries of X are unmarked. while i ≥ 1 do for each weight in the tuple w , find its corresponding entry in matrix X and mark the entry if length of tuple w ’s longest right chain ≥ n − i + 1 and number of unmarked entries on each row of X ≤ i − 1 then upper bound on θ * = mean of all entries of tuple w i − = 1 end if set w as the previous tuple in Ω end while 873 874 875 876 877 878 879 880 881 882 883 884 885
887 888 889 890 891 892 893 894 In this section, we illustrate our algorithm (described in Sec- tion 4.3) by means of an illustrative example. Consider a case where n = m = 4, ℓ = k = 3. Let 3 papers among the 4 have all 0 weights and the fourth paper has weights 1, 2 and 3. In this example, we can infer that (θ † , θ ∗ , …, θ ∗ ) = (0,  ∗ ,  ∗ , 1) regardless of assignment. This example reflects axiomatic property A3 presented in Sec- tion 4.3. We show that our algorithm for computing bounds indeed results in a convex set that contains only the vector (0, ξ, ξ, 1). And thus the projection of any noisy data onto this convex set results in (0, 1 , 2 , 1). First, we visualize the matrix X as 011 012 paper 2 : paper 3 : paper 4 : 031 022
033 242 343- 032 141 021 between the tuples (011,021,031) and (012,022,032) since all six weights in these two tuples correspond to different entries in X . On the other hand, there is no edge between the tuples (011,021,141) and (012,022,141) because they both contain weight 141. The first tuple in Ω meets both the criteria so lower bound on θ * is mean of the first tuple, which is a tuple with mean 0. Therefore, lower bound on θ * is 0. Without loss of gener- ality, the first tuple is (011,021,031) and we mark the corre- sponding entries in X . Now the matrix X can be visualized as follows (where we mark any entry when we need to):
To compute a lower bound on θ *, we start from the second tuple in Ω. Since there are 27 tuples that have mean zero, the second tuple still has mean zero. However, we do not choose any tuple that has mean zero due to criterion C2 from the algorithm. Choosing any (0,0,0) tuple leaves all 3 entries of row 4 in X unmarked, and thus will not leave row 4 with at most 2 unmarked entries. Therefore, we will only stop at the first tuple that has mean  3 . Without loss of generality, we choose tuple (011,021,141) and mark the corresponding entries in X . This will leave the matrix X as
For a similar reason, we do not choose any tuple that has mean ξ to be a lower bound on θ ξ as it would not leave row 4 of X  with at most 1 unmarked entry. So we choose the first tuple that has mean  3 and a lower bound on θ ∗ is  3 . Lastly, a lower bound on θ ∗ is computed using the first tuple that has mean 1. Now we can look at the computation of upper bounds us- ing the proposed algorithm. Upper bound on θ å is taken as mean of the last tuple, which is a tuple with mean 1. There- fore, an upper bound on θ * is 1. In addition, we mark two entries of weight 0 and one entry of weight 3. Without loss of generality, we mark entries 0 11 , 0 21 , 3 43 . Now the matrix X can be visualized as
To compute an upper bound on θ ∗ , we start from the second to last tuple in Ω. Since there are 27 tuples that have mean 1, the second to last tuple still has mean 1. However, we do not choose any tuple with mean 1 due to criterion C3 from the algorithm. Any (0, 0, 3) tuple does not have a right chain of length at most 2 because all tuples with value (0,0,3) are not connected due to the uniqueness of the weight 3. Therefore, we will only stop at the first tuple that has mean ミas it has a right chain of length 2. Since we have encountered all combinations of (0, 0, 3), the matrix X after we choose a tuple (0,0, 2) becomes 932 933 934 935 936 937 938 939 940 941 942 907 908 909 910 911 912 913 914 915 916
918 919 920 921 922 923 924 925 926 927 928 929 930
subscripts entries of The indicate the the  weights Some elements X. in C are:    (011,021,031), in ··· , (013, 023, 033), (011,012,141), ··· , (013, 023, 141), (011,012,242), . . . , (011,012,343). After we sort Ω ′ based on the mean of the weight tuples, we get Ω where the first 27 tuples have mean 0, followed by 27 tuples with mean ξ, 27 tuples with mean ξ, and 27 tuples with mean 1. We construct graph G in which for instance, there is an edge 895 896 897 898 899 900 901 902 903 904 905
943 944 945 946 947 948 949 950 951 952 953 954 955 956 paper 1 : Ors Iri Ir2 paper 2 : O Ozi Ors paper 3 : 0~2 losi paper 4 : 141 For a similar reason, we do not choose any tuple that has mean ङ to be an upper bound on θ ∗ as it would not have a right chain of length at least 3. So we choose the first tuple we encounter that has mean ξ and an upper bound on θ 2  is = . Lastly, an upper bound on θ ∗ is computed using the first tuple that has mean 0. Thus, the bounds on θ* = ( ³ ＜ θ² > ≤ θ² > θ² > ≥ and 1 ≤ θ² > 1. Along with the conditions that θ² + θ² + θ² + θ² + θ² + θ² + θ² + θ² > θ² > θ² > θ * , the only possible value of θ * is (0, ξ , ξ , 1). Thus the out- put of our algorithm is the singleton set {(0, f, f, f, 1)}. Pro- jection of any data to the convex set {(0, ξ, ξ, 1)} results in (0, ξ, ξ, 1), which is consistent with axiomatic property A3. 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 our algorithm described in Section 4. The simulations compute the mean squared error between the true sorted mean-weight vector θ* and the output from each of these three methods, that is, ∑ n = 1 ( t i − θ ∗ ) 2 where t is the output of any of these algorithms. Note that in the figures, the error bars (standard error of the mean) are plotted but not visible in most cases since they are too small. We now describe the method for generating the weights in each simulation, and refer the reader to the corresponding plots. Note that the y-axes (representing the mean squared error) on each of the plots is on a logarithmic scale. • In Figure 2a—2e, the number of reviewers ranges from 995 10 to 50. The weights are all i.i.d. and are generated from 996 the beta distribution specified in the corresponding sub- 997 caption. 998 • In Figure 2f, the number of reviewers is fixed at 10. On 999 the x-axis, we vary a parameter a ∈ {0.5,1, . . . ,10}. 1000 For each value of a , we draw all weights i.i.d. from the  1001 beta( a, a) distribution. 1002 • In Figure 2g, we again vary the number of reviewers n 1003 on the x-axis. For any paper i ∈ [n] , one weight is gen- 1004 erated from beta(1, i) and the other weight is generated 1005 from beta(2, i) independently. 1006 •  In Figure 2h, whenever any paper i ∈ [m] is reviewed by 1007 reviewer j ∈ [ n ], the weight of that review is generated 1008 from beta( i, j ). 1009 All in all, these simulations reveal that our algorithm can 1010 lead to a multi-fold improvement in the utility (accuracy) 1011 while not compromising the privacy. 1012 1013 1014 We present proofs of all the claimed results. 1015 We prove the proposition using a counter example. Assume   1016 the true value θ * = 0 and the set of all possible values Θ = 1017 {-4, -2, 0, 2, 4}. The noisy data r = θ* + η where η is 1018 a Laplace random variable with probability density function 1019 η( x ) = 0.5e-|π|. 1020 Without projection, the expected error incurred by the 1021 _ 0.5e-lxlx2dx = 2. But if we project the 1022 noise is noisy data on the set Θ and get result t , the expected er- 1023 ror after the projection is computed as 16 f_ 3  0.5e-l-ldx + 1024 _ 3 0.5e-lxldx + 4 f 3 0.5e-lxldx + 16 f 3 0.5e-lxldx = 1025 2.06896, which is greater than the expected error without 1026 projection. Thus, projecting on the set that contains all true  1027 values could decrease the accuracy of data. 1028 It is known that projection on a closed convex set is non- 1030 expansive (Bauschke, Combettes et al. 2011). Since θ * re- 1031 sults from a valid assignment, it is contained in Θ. Therefore 1032 it is contained in any closed convex set that contains Θ. Pro- 1033 jection of r onto any such convex set will not increase its 1034 squared error from θ*. Therefore, proposition 4.2 holds. 1035 We will prove the NP-hardness by reducing the ℓ -Partition problem, which is NP-hard (Babel, Kellerer, and Kotov 1998), to the problem of projecting noisy data onto convex hull of Θ. The ℓ -Partition problem where ℓ > 2 is defined as follows. 1037 1038 1039 1040 1041 Definition D.1. ℓ -Partition problem: Given a multi-set W ＝ 1042 { w 1 , w 2 , ..., w n } of n non-negative integers where n is a  1043 multiple of ℓ , decide if we can partition W into  γ subsets 1044 such that each subset has size ℓ and the sums of all subsets 1045 are the same. 1046 In this section, we conduct synthetic simulations to evaluate the performance of our algorithm. We synthetically gener- ate a conference review setting in one of several ways as described below. In each of the settings, the number of re- viewers equals the number of papers, and each reviewer re- views 2 papers and each paper is reviewed by two reviewers. The assignment of reviewers to papers is done uniformly at random subject to given load constraints. The weight given by any reviewer to any reviewed paper is drawn from a beta distribution. For preserving privacy, we consider the com- mon method of adding i.i.d. Laplace noise (with mean zero and variance 2) to each component of the true sorted mean- weight vector. We evaluate the following three methods of releasing the sorted mean-weight vector, which includes our proposed al- gorithm and two baselines: • Noisy where Laplace noise is added but no post- processing is performed; Baseline projection where the noisy data is post- processed via projecting onto a convex set which con- strains the sum of all entries, the value of each entry in terms of the range of weights (0 to 1), and imposes a monotonicity constraint; We project on the set { t ∈ Rn|0 ≤ ti ≤ 1Vi ∈ [n], Xij, t1ニt² < ・・・ < t n } . • Our algorithm where the noisy data is post-processed via 1036 1029 1047 1048 1049 1050 1051 1052 1053 1054 Consider any instance of the l -Partition problem with W = { w 1 , w 2 , …, w n }, where w i ≥ 0 and n is a multiple of ℓ . Now we construct a peer-review dataset where there are n reviewers and n papers, each reviewer reviews ℓ papers and each paper receives ℓ reviews. Note that the number of reviewers is the same as the number of elements in W . Let each paper i has weight wi and ℓ — 1 zero weights, and a denote the average of all elements in W , i.e., 1055 1056 1057 1058 1059 1060 1061
Let v = (0, ..., 0, α, ..., α) be a vector of n entries whose last 7 entries all have value a . Let V = W U {0, ..., 0} be the multiset containing all values of W and n · ( ℓ − 1) zeros. Then the projection problem is to project v onto the convex hull of Θ defined for this peer-review dataset. The reduction from the ℓ -Partition problem to the projec- tion problem constructed above is as follows. If the solution to the projection problem is v itself, we return True for the  1062 ℓ-Partition problem; otherwise we return False. 1063 We first prove the correctness of the reduction. Suppose 1064 W can be ℓ -partitioned into   subsets of equal sums. Then 1065 we can partition V into subsets of size ℓ where these subsets 1066 are the subsets that give the ℓ -partition of W and subsets 1067 that consist of ℓ zeros. By Lemma D.2 below, this partition 1068 of V gives a valid assignment for the peer-review problem, 1069 and thus v  =  (0, ..., 0, a, ..., a) corresponds to a valid as- 1070 signment. Therefore, the projection of v is itself. The proof 1071 of Lemma D.2 is presented in Section D.4. 1072 Lemma D.2.  In the setting described above, any ℓ-partition 1073 of the n · ℓ weights in V , i.e., any partition of V into subsets 1074 of size ℓ, can be interpreted as a valid assignment such that 1075 subset i corresponds to the weights from reviewer i given to 1076 ℓ distinct papers. 1077 Next, suppose that the projection of v is itself. We show 1078 that W can be ℓ -partitioned into subsets of equal sums. We 1079 first claim that v must correspond to a valid assignment it- 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 self. To see this, suppose v = (0, ..., 0, a, ..., a) is a con- vex combination of some sorted mean weight vectors. Then these vectors must all have value a for their last   entries since each of these mean weight vector is sorted. Due to the sum constraint, these mean weight vectors have to be (0, ..., 0, a, ..., a). Next we note that in the assignment given by v , each reviewer who has an average weight of a must give ℓ weights with values from W due to the pigeonhole principle. Therefore, the  s subsets each of which consists of weights given by one of the last  f reviewers form an l- partition of W with equal sums. Finally, we prove the efficiency of the reduction. Since the construction of v has O ( n ) time complexity and the con- struction of V has O (1) time complexity, the reduction has O(n) time complexity, which is polynomial in the size of the input. Thus, the reduction can be done efficiently, which completes the proof. 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 Fix ℓ , we will prove the lemma by induction on n , the num- ber of reviewers, which is the same as the number of papers. Base case: when n = ℓ , every reviewer reviews all papers, so any ℓ partition of the weights can be validly assigned to reviewers. Inductive hypothesis: suppose when there are fewer than n reviewers for an n > ℓ , every ℓ partition of the weights forms a valid assignment for reviewers. Consider when there are n reviewers and n papers. With- out loss of generality, assume all weights in W are non-zero. Consider an ℓ partition of the set V . We will argue in two cases based on whether there is a subset that contains ex- actly one non-zero weight. 1. Case 1: In the partition, if there is a subset with exactly one non-zero weight. Without loss of generality, assume that the subset with exactly one non-zero weight contains w 1 and the subset is { w 1 , 0, ..., 0}. We denote the subset S 1 . In S 1 , there are ℓ − 1 zero weights and a non-zero weight w 1 from W . Since paper 1 receives ℓ weights in total, we can remove S 1 , paper 1 and reviewer 1. Now we are left with n − 1 reviewers and papers. The re- moval does not affect the number of reviews received by the rest of the papers. We still have each paper getting ℓ weights. Among the weights, there is one non-zero weight from W and ℓ − 1 zero weights. By the inductive hypoth- esis, the rest of the subsets in the partition form a valid assignment of V \ S 1 . We can assign the weights to n − 1 reviewers. We then add S 1 back to the assignment. Since reviewer 1 l weights to paper 1, it is not valid. We can solve this by swapping the zero weights in S 1 with zeros in other sub- sets. We need to make ℓ − 1 swaps. We label the rest of the subsets S 2 , . . . , S n where S 2 is the subset that contains most non-zero weights and the labels go in decreasing or- der based on the number of non-zero weights contained in a subset. We look at the rest of the subsets in the order of their labels. Since none of the rest of the subsets contain any weight from paper 1, swapping a zero weight from paper 1 into any of these subsets will nor affect the validity of the sub- 1139 set. There are at least n − 1 − π ξ 1 subsets that con- 1140 tain at least a zero weight. Since n > ℓ and ℓ > 2, 1141 n − 1 − π구1 = (ℓ−1)(π−1) ≥ ℓ − 1. Thus, we have  1142 enough subsets to swap the zero weights from paper 1 in.   1143 Then we make sure the zero weights swapped into S 1 will   1144 not come from the same paper. We label the zeros in S 1 1145 with index 1, . . . , ℓ − 1. Suppose there are no subsets that 1146 do not contain any zero weights. Then when we need to  1147 swap out the zero weight at index i in S 1 , there are at most 1148 n − i non-zero weights in the untouched subsets due to the   1149 order we look at the subsets. There are n − i untouched  1150 subsets as well. Then there exists an untouched subset that 1151 contains i zero weights. Since at this stage S 1 has already 1152 completed i — 1 swaps, we can find a zero weight from  1153 the untouched subset to swap so that the zero weight does   1154 not come from the same paper as the zero weights from  1155 previous swaps. Note that if we have any subset that does   1156 not contain any zero weight or we skip some subsets due  1157 to conflict of papers, then the fraction of non-zero weights 1158 left and untouched subsets will be even smaller. So we are   1159 guaranteed to find a proper zero weight to swap. Thus, we   1160 can make ℓ − 1 swaps of the zero weights to S 1 and make  1161 all subsets valid assignments of weights. Such swaps do  1162 not affect the values in each subset. 1163 Therefore, such partition can result in a valid assignment 1164 of the n · ℓ scores among n reviewers. 1165 2. Case 2: In the partition, if there are no subsets with exactly 1166 one non-zero weight. 1167 Since W contains n elements and there are n subsets, by  1168 pigeon hole principle, there must be a subset S 1 that con- 1169 tains all zero weights. 1170 Without loss of generality, we find the subset that con-  1171 tains w 1 and then swap w 1 with a zero weight in S 1 . This 1172 results in $1 = { w1, 0, . . . , 0}. 1173 Now we have a subset that contains exactly 1 weight from 1174 W . Like in case 1, we remove the subset, reviewer 1 and  1175 paper 1. We can find a valid assignment of the rest of the  1176 weights to n − 1 reviewers. Then we will put S ′ back to  1177 the assignment. Currently all weights in S 1 are from paper 1178 1. We identify the subset where w 1 comes from, and swap  1179 w 1 back into the subset with a zero weight there. Since  1180 the subset can not contain any weights from paper 1, we  1181 can safely put w 1 back without having two weights from  1182 the same paper. 1183 After the swap, S j has ℓ − 1 zero weights from paper  1184 1 and a zero weight from a different paper, say paper 2.  1185 We need to make ℓ − 2 swaps for the zeros in S l . We 1186 label the rest of the subsets S 2 , . . , S n where S 2 is the 1187 subset that contains most non-zero weights and the labels 1188 go in decreasing order based on the number of non-zero  1189 weights contained in a subset. We look at the rest of the  1190 subsets in the order of their labels. 1191 Since none of the rest of the subsets contain any weight  1192 from paper 1, swapping a zero weight from paper 1 into  1193 any of these subsets will nor affect the validity of the sub-   1194 set. In the worst case, there exists a subset that contains  1195 w 1 and there are at most n=2 subsets that only contains a  1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 zero weight from paper 2 because such tuples cannot con- tain w 2 . Then there are at least n − 1 − γ − 2 − 1 subsets that we can swap the zero weights in S 1 . Since n > ℓ and ℓ > 2, n − 1 − ⇌ − 1 − (ℓ−2)(n−2) ≥ ℓ− 2. Thus, we ℓ−1 have enough subsets to swap the zero weights from paper 1 in. We keep a zero weight from paper 1 in S 1 and label the rest of the zero weights in S 1 with index 1, . . . , l — 2. Suppose there are no subsets that do not contain any zero weights. Then when we need to swap the zero weight at index i in S 1 , there are at most n − i non-zero weights in the untouched subsets due to the order we look at the subsets. There are n − i untouched subsets as well. Then there exists a subset that contains i + 1 zero weights. Since at this stage S 1 has already completed i − 1 swaps, we can find a zero weight to swap that does not conflict with the weights from previous swaps and not from paper 2 ei- ther. Note that if we have any subset that does not contain any zero weight or we skip some subsets due to conflict of papers, then the fraction of non-zero weights left and untouched subsets will be even smaller. So we are guar- anteed to find a proper zero weight to swap. Thus, we can make ℓ − 2 swaps of the zero weights to S ′ and makes all subsets valid assignments of weights. Such swaps do not affect the value in each subset. Therefore, such partition can result in a valid assignment of the n · ℓ weights among n reviewers. In conclusion, any ℓ -partition of V can be interpreted as a valid assignments of weights to n reviewers. We would like to show that the convex set contains Θ. We will show that the bounds are indeed lower and upper bounds on each entry. We will first show that the lower bounds computed by the algorithm are correct. Assume for the sake of contradiction, there exists an as- signment such that θ * is less than the lower bound on θ * we computed, denoted as θ i . We use ν to denote the tuple that results in θ * and use ν ′ to denote the tuple that we choose in the algorithm that has mean θ i . Since ν is a valid assign- ment, it is the sum of ℓ weights from ℓ distinct papers. Since Ω contains all such tuples, it contains ν . And since θ ∗ < θ i , we encountered ν before we encounter ν in Ω . We did not choose ν as the tuple for lower bound due to its violation of either criterion C1 or criterion C2. If ν violates criterion C1, it does not have a left chain of size at least i . There cannot be i — 1 weight tuples each containing ℓ weights from different papers such that they all have mean no larger than θ ∗ . Otherwise they form a left chain of length i . So ν cannot have its mean appear at entry i in θ*. If ν violates criterion C2, there exists a row that has more than n − i unmarked entries in X . The weights of the un- marked entries have not been encountered so far, which in- dicates that any tuple that contains the weights from un- marked entries has mean no less than θ ∗ . Otherwise, we would have encountered the weight before ν and mark its entry. We know that there are n − i reviewers who has mean  1254 weight no less than θ ∗ . In addition, there are more than n − i   1255 weights left for at least one paper. By Pigeon Hole Principle,   1256 there exists a reviewer gives a weight tuple that contains two 1257 weights from the same paper. However, no two weights from 1258 the same paper can be in the same tuple since one reviewer 1259 cannot give 2 weights to the same paper. So ν cannot have  1260 its mean appear at entry i in θ *. 1261 Thus, θ * cannot be a value for entry i in θ * . The value θ i 1262 we computed is indeed a lower bound on that entry. 1263 Following a similar argument, we can prove the correct- 1264 ness of the upper bounds from the algorithm. 1265 1266 We will show that the proposed algorithm has polynomial  1267 time complexity in the number of reviewers. There are 1268 n · ℓ weights, so the size of Ω ′ , denoted |Ω ′ |, has size at  1269 most ( η ℓ ), which is of complexity O ( n ℓ ). Sorting Ω ′ has  1270 O(|Ω′| log(|Ω′|)) time complexity, which is still polynomial 1271 in n . There are ( | ঙ ′ | ) pairs of vertices to examine for edges. 1272 Therefore, constructing G is of polynomial time in n . To 1273 compute the length longest left chain and right chain of a  1274 vertex, we can make use of a dynamic programming algo- 1275 rithm that only requires us to loop through Ω once to com-  1276 pute length of longest left chain of all vertices and loop one  1277 more time to compute the length of longest right chain. For  1278 each vertex, we examine at most all its neighbors, which is  1279 of size polynomial in n . Lastly, after all preparation work,  1280 for each vertex, we take O (1) time to check criteria C1 and  1281 and C3 at most O(m) time to check criteria C2 and C4. 1282 Since m < n · ℓ , both operations are polynomial in n . Thus, 1283 the proposed algorithm computes the bounds in time poly- 1284 nomial in n . 1285 We will use quadratic programming to project noisy data 1286 onto the convex set and there are 2 n linear constraints. This 1287 operation is also polynomial in n . 1288 Thus, the proposed algorithm has time complexity that is   1289 polynomial in n . 1290 1291 Axiomatic property A1: When all weights are the same, all 1292 weight tuples have the same mean, which equals the weight. 1293 Thus, all lower and upper bounds have the same value as the   1294 weight. The convex set contains a single vector and projec-  1295 tion of any noisy data on such convex set will result in the  1296 vector, whose entries are all the same as the weight. 1297 Axiomatic property A2: When ℓ = 1, there are exactly n  1298 weight tuples, each containing one weight. We will choose  1299 the same weight tuple for lower bound and upper bound on  1300 θ*. The mean of the chosen weight tuple is the weight of 1301 rank i among all n weights. Therefore, the convex set con- 1302 tains exactly one vector, which is the sorted vector of all 1303 weights. Projection of any noisy data onto this convex set  1304 will result in the vector of sorted weights. 1305 Axiomatic property A3: When all except for one paper re- 1306 ceives all zero weights, computation of lower bound on θ ∗ 1307 when i < n − k will choose a tuple whose weights are all 1308 zeros. When i > n − k , computation of lower bound will  1309 1310 1311 1312 1313 1314 1315 1316 1317 choose a tuple that contains a nonzero weights due to crite- rion C2. Similarly, to compute an upper bound on θ i * when i ≥ n − k , we will choose a tuple with a nonzero weight due to the criterion C3. But when i < n − k , the algorithm will choose a tuple with all zero weights. The example we present in Section B illustrates this process. Therefore, the convex set again contains only a vector who has n − k zero entries. Projection of any noisy data will result in this vector.