Generative Adversarial User Privacy in Lossy Single-Server Information Retrieval
Authors: Chung-Wei Weng
Yauhen Yakimenka
Hsuan-Yin Lin
Eirik Rosnes
Joerg Kliewer
Venue:  (2021)
Keywords: Generative adversarial network
generative adversarial privacy
information-theoretic privacy
compression
private information retrieval
data-driven framework

Abstract: We consider the problem of information retrieval from a dataset of files stored on a single server under both a user distortion and a user privacy constraint. Specifically, a user requesting a file from the dataset should be able to reconstruct the requested file with a prescribed distortion, and in addition, the identity of the requested file should be kept private from the server with a prescribed privacy level. The proposed model can be seen as an extension of the well-known concept of private information retrieval by allowing for distortion in the retrieval process and relaxing the perfect privacy requirement. We initiate the study of the tradeoff between download rate, distortion, and user privacy leakage, and show that the optimal rate-distortion-leakage tradeoff is convex and that it allows for a concise information-theoretical formulation in terms of mutual information in the limit of large file sizes. Moreover, we propose a new data-driven framework by leveraging recent advancements in generative adversarial models which allows a user to learn efficient schemes in terms of download rate from the data itself. Learning the scheme is formulated as a constrained minimax game between a user which desires to keep the identity of the requested file private and an adversary that tries to infer which file the user is interested in under a distortion constraint. In general, guaranteeing a certain privacy level leads to a higher rate-distortion tradeoff curve, and hence a sacrifice in either download rate or distortion. We evaluate the performance of the scheme on a synthetic Gaussian dataset as well as on the MNIST dataset. For the MNIST dataset, the data-driven approach significantly outperforms a proposed general achievable scheme combining source coding with the download of multiple files.

Under review as a conference paper at ICLR 2021
GENERATIVE ADVERSARIAL USER PRIVACY IN LOSSY SINGLE-SERVES INFORMATION RETRIEVAL
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the problem of information retrieval from dataset of files stored on a single server under both a user distortion and a user privacy constraint. Specifically, user requesting a file from the dataset should be able to reconstruct the requested file with a prescribed distortion, and in addition, the identity of the requested file should kept private from the server with a prescribed privacy level. The proposed model can be seen an extension of the well-known concept of private information retrieval by allowing for distortion in the retricval process and relaxing the perfect privacy requirement. We initiate the study of the tradeoff between download rate, distortion, and user privacy leakage, and show that the optimal titeddisoortion-laaage tradeoff is convex and that in the limit of large file sizes this allows for a concise cnoematiinnthhooetiini information. Moreover, we propose new data-driven framework by leveraging recent advancements in generative adversarial models which allows a user to learn efficient schemes in terms of download rate from the data itself. Learning the scheme is formulated as constrained minimax game between a user which desires to keep the identity of the requested file private and an adversary that tries to infer which file the user is interested in under a distortion constraint. In general, guaranteeing certain privacy level leads to higher rate-distortion tradeoff curve, and hence sacrifice in either download rate distortion. We evaluate the performance of the scheme on a synthetic Gaussian dataset as well as on the MNIST and CIFAR-10 datasets. For the MNIST dataset, the data-driven approach significantly outperforms a proposed general achievable scheme combining source coding with the download of multiple files, while for CIFAR-10 the performances are comparable.
formulation in terms mutual
INTRODUCTION
Machine learning (ML) has been recognized as a game-changer in modern information technology, and various ML techniques increasingly being utilized for variety of applications from intrusion detection to image classification and to recommending new movies. Efficient information retrieval (IR) from single or several servers storing such datasets under a strict privacy constraint has been extensively studied within the framework of private information retrieval (PIR). In PIR, first introduced by Chor al. (Chor et al. 1995), user can retrieve an arbitrary file from a dataset without disclosing any information (in an information-theorriie sense) about which file she is interested in to the servers storing the dataset. Typically, the size of the queries is much smaller than the size of a file. Hence, the efficiency of PIR protocol is usually measured in terms of the download cost, or equivalently, the download (or PIR) rate, neglecting the upload cost of the queries. PIR has been studied extensively over the last decade, see, e.g., (Banawan & Ulukus) 2018 Freij-Hollanti et al. 2017 Kopparty et al. 2011 Sun & Jafar 2017 Tajeddine et al. 2018 Yekhanin 2010) and references therein.
Recently, there has been several works proposing to relax the perfect privacy condition of PIR in order to improve on the download cost, see, e.g., (Lin et al. 2020 Samy et al. 2019 Toledo et al. 2016). Inspired by this line research, we propose to simultaneously relax both the perfect privacy condition and the perfect recovery condition, by allowing for some level of distortion in the recovery process of the requested file, in order to achieve even lower download costs (or, equivalently, higher download rates). We concentrate the practical scenario in which the dataset is stored on single

---

Under review as a conference paper at ICLR 2021
server. A problem formulation with arbitrary distortion and leakage functions is presented, which establishes a tri-fold tradeoff between download rate, privacy leakage to the server storing the dataset, and distortion in the recovery process for the user. We show that the optimal
diistortion-laaaaae ceammaaioo-theoretiin formulation in terms of mutual information in the limit of large file sizes (see Theorem []. In the special case dieeortttotiionn curve. The typical behavior of the rate-distortion-laaaae tradeoff is illustrated in Fig. T showing that an increased level of privacy leads to a higher rate distoriioo tradeoff curve, and hence sacrifice in either download rate or distortion. A general achievable scheme combining source coding with the download of multiple files is proposed for datasets with a known distribution. Moreover, to overcome the practical limitation of unknown statistical properties of real-world datasets, we consider a data-driven approach leveraging recent advancements in generative adversarial networks (GANs) (Goodfellow (ct al., 2014), which allows a user to learn efficient schemes (in terms of download rate) from the data itself. In our proposed GAN-based framework, learning the scheme can be phrased as a constrained minimax game between a user which desires to keep the identity of the requested file private and server that tries to infer which file the user is interested in, under both user distortion and download rate constraint. Similar to (Springenberg. 2016). where a cross-entropy loss function is used discriminative classifier for unlabeled or partially labeled data, the server is modeled as discriminator in the generalized GAN framework, and also trained with cross-entrope for labeled data. We evaluate the performance of the proposed scheme on a synthetic Gaussian dataset as well as on the MNIST (Lecun et al., 1998) and CIFAR- 10 (Krizhevsky) 2009) datasets. For the MNIST dataset, the data-driven approach significantly outperforms the proposed achievable scheme, while for the Gaussian dataset, where the source statistics is known, it performs close to the proposed achievable scheme using a variant of the generalized Lloyd algorithm (Lloyd 1982. Linde et al.) 1980) for the source code. For CIFAR-10, the performance of the data-driven approach is comparable to that of the proposed achievable scheme. Moreover, when the download rate is sufficiently low, it even slightly outperforms the achievable scheme.
tradeoff is convex (see Lemma D and that it allows for a concise
of full leakage to the server, the proposed formulation yields the well-known
Related Work
As outlined above, in this work con- sider "information retrieval" in the sense of PIR, while "information retrieval" in the traditional sense used by the information re- trieval community has a different meaning. In particular, in the traditional sense "infor- mation retrieval"' refers to the problem of providing list of documents given a query and has wide range of applications [Baeza- Yates et al. 1999p. In Wang et al. [2017 7) the authors proposed to iteratively optimize two well-established models of traditional infor- mation retrieval; namely generative retrieval focusing on predicting relevant documents given a query and discriminative retrieval focusing on predicting document relevance given a query and document pair. The resulting optimization problem is formulated minimax game. Due to differences in system model there is no clear connection to our proposed framework, besides the formulation as a minimax game.
Full leukage (no privacy)
Medium leakage (weak privacy)
No leakage (perfect privacy)
Rate
Distortion
Figure 1: The rate-distortion tradeoff under different privacy levels.
Similar data-driven approaches, under the names of generative adversarial privacy (Huang et al. 2017 2018), preseervig adverisal networks (Tripathy et al., 2019), and compressive privacy GAN (Tseng & Wu (020)). have recently been proposed for learning privatization mechanism directly from the dataset in order to release it to the public and for generating compressed represen- tations that retain utility while being able to withstand reconstruction attacks. A similar approach was also taken in (Blau& & Michaeli 2019) where tri-fold tradeoff between rate, distortion, and perception in lossy image compression was established. Relaxing the perfect information-thhcrrticall privacy condition by considering
information retrieval where the privacy requirement relies an intractability assumption (e.g., the hardness of deciding quadratic residuosity) has been investigated in several previous works, see, e.g.. (Kushilevitz & Ostrovsky/ [997] 2000 Lipmaa 2005). Hence, given infinite computational power, the requested file index can be determined precisely. Moreover, in (Kadhe et al. 2020), it was shown that allowing for side information can also
2

---

Under review as a conference paper at ICLR 2021
decrease the download cost in single-server PIR. In contrast to these previous works, here we propose to relax the perfect reconstruction constraint in order to decrease the download cost. Moreover, to the best of our knowledge, addressing PIR or the extension nonperfect privacy and recovery in the context of generative adversarial models has not been considered in the open literature so far.
2
PRELIMINARIES AND SYSTEM MODEL
2.1 NOTATION
We denote [a] a (1. aa. An arbitrary field is denoted F, while the set of nonnegative real numbers denoted by Rzo. Vectors are denoted by bold letters and sets by calligraphic uppercase letters, e.g., and X, respectively. We use uppercase letters for random variables (RVs) (either scalar or vector), e.g., X or X. For given index set [M], we write XIM] to represent { {X(m); E [M]]- Ex [ and Epx [:] denote expectation with respect to the RV X and the probability mass function Px respectively. H (X) or H (Px) represents the entropy of X, while I(X; denotes the mutual information (MI) between X and Y. The multivariate Gaussian distribution with mean l and covariance matrix is denoted as (,,,,)),
In particular, if the entries of this distribution are mutually independent, we have D = L²1, for marginal standard deviation Ryo and / denoting the identity matrix. The transpose of a vector is denoted as (-)T.
2.2 SNGLE--ERVER INFORMATION RETRIEVAL
Consider a dataset containing M files (1), (M) stored single server, where each file
((m) = (x(m)) (m) ............... ) m E [M]. can be seen as a x random vector (according to some
probability distribution px(m)) over F29 where IF is any field (finite or infinite). Assume that the user wishes to retrieve the M-th file, M E [M], where, for simplicity, M is assumed to uniformly distributed over [M][The The formal definition of a general hinle-server IR scheme is as follows.
Definition 1. An IR scheme ' for a single-server storing M files consists of: (i) random strategy S. (ii) A deterministic query function So that generates a query Q = fo S), where query Q is sent the server. (ii) A deterministic answer function S that returns the answer A SA X X back the user. (iv) deterministic reconstruction function X a fA, M, , Q) giving an estimate of the desired file using the answer from the server together with the requested file index M and the query Q.
Note that the server does not use S directly to produce A and thus using Q is sufficient in the reconstruction.
We are interested in designing IR scheme such that both the user's utility and privacy preserved. On the one hand, this scheme should satisfy the condition of retrievability with a distortion measure d(;; )), i...
EM.Q
x) D.
where is a given distortion constraint. On the other hand, the user would like to preserve her privacy with the query function, in the sense that the server should not be able to fully determine the identity M of the requested file. The server receives the query Q, and the leakage measured in terms of leakage metric p( p(PQ)M). The query function should be designed such that
p(Pq M) < L,
(2)
where I. is the maximum allowed leakage.
Moreover, it is worth mentioning that unlike the setting of classical PIR, where perfect retrievability is
ensured for every file, i.e., Eq d( X (m)) X)] = 0 for all E [M], the distortions for different files
need not be the same. In other words, it is possible to have Eq [d( X (m) x)] * Eq [d(x(m)) (m²) x)]
for m # m', and [ can be expressed as
EM.Q (M) (M) x) = -EM EE
[(x (M), x) M = ml D.
'The assumption that M is uniformly distributed can he lifted.
3

---

Under review as a conference paper at ICLR 2021
Given query function fo and an answer function fA of an IR scheme, measure its efficiency in terms of the download rate (in bits per symbol) defined as
( 3 Pa(9) (A(l)) (A),
R(fo: fA)
(3)
where (a) is the length of the answer for query q. Further the paper, the length lg (a) () is constant (i.e., independent of and ②) that is chosen according to the desired rate.
2.3 PROBLEM FORMULATION
We consider a model that pro- tects the privacy of the user against a honest-but-curion server. The IR model above guarantees that a user can re- trieve an arbitrary file stored on a single server (with some distortion), while the server can only partially infer the identity of the requested file. In this work, we will study the tri-fold tradeoff between download rate, expected dis- tortion, and privacy leakage the server for IR scheme. In particular, for given constraint D on the expected distortion EM.Q ( (,, for the retrieval of the requested file indexed by M and for given constraint L the leakage to the server p( (Q))) the goal is to minimize the download rate R(fo, fa). This can be formulated as the constrained optimization problem
fo
Q
fx
MY
gen
8 M
X(1
X(M)
: (X(M)
M
x
fx
Figure IR scheme for an arbitrary dataset stored on single server.
(M),
min min fo
R(fo, fA)
(4a)
subject to
( x) DD, p(PQ)M) LL
(4b)
x - M. Q), Q = fo(M fAQ,
(4c)
To further capture the information leakage for training, we define M A fx(() to be the server's inference of the user's requested file index M from the query Q using decision decoder fxr The proposed model is illustrated in Fig. The leakage on the identity of the requested file can also be quantified by a loss function denoted as oo (M, M). Hence, the expected loss with respect to M and Q is
J(fo f&a = EAS.Q fLoss (M, Mn] = Em. [LLon (ML, (M.
Here, the leakage metric P(Pa)a)) ms) ) in (2) is connected the expected loss J( f&) as p(PQ maxfy J(fo, faa). Note that the main objective is to minimize the user's leakage to the server, which equivalent to minimizing fx). while the goal of the server the opposite, i.c., of making the user's loss as large possible equivalently, of maximizing J( fu).
Lemma 1.
The set of achievable (feasible) rute-distortion-llaaage triples (R, D. from is convex set, for any leakage metric p that is convex in PQIM-
We remark that Lemma [ also holds for any loss function fLom, since any p( p(PQja)) that can be expressed via J(fo- f'x is always convex in PQjM-
Note that if fm, MM ) is the 0-1 loss function (Nguyen & Sanner 2013) it can be easily shown, following a similar argument as in Huang et al. (2017 Sec. 2.2), that the optimal inference strategy for the server is the MAP decoder, and that the privacy metric p M) in this case equals the server's inference accuracy Pr(M = M). This case is referred to as hard decision decoding. However, foos (mossm, M) ) is the los-loss function defined as
fLoss (m, Ai) H(M) + log FAir (m|));
(5)
4

---

Under review as a conference paper at ICLR 2021
then the leakage to the server is measured in terms of MI, i.e. p(PQIM) QM: This case is referred to as soft decision decoding. Moreover, the detailed derivation, which can be found in Appendix [ gives explicit reason (see (C.12)) to use empirical categorical cross-entropy as loss function for the data-driven approach in Section It can be seen that the leakage metrics p we considered here are all convex in PQIM- Thus, in the rest of paper, we will always assume that the metric p(-) is convex in its argument.
Theorem 1. The download rate given in 4 is equal to the following information rate-distortion- leakage function defined as
R(D,L)
min PaIM e
1(x [M] ; MM I
(6)
eF(D.L)
as B + 00, where
F(D,L) e (PIM PXIM x. EM [ x s DD p(P =
$1.
The proof that the rate R is bounded from below by R(D,L) for any 83 is given in Appendix B While the achievability proof is not provided, we do give the following intuition and relative technique from information theory. Note that our single-server IR scheme can be seen as a source coding problem with side information, where the server and the user act an encoder and a decoder, respectively, and where the query can be seen as a controllable side information known to both the encoder and decoder in order to enforce the privacy condition. This is similar to the well-known Wyner-Ziv problem (Wyner & Ziv] 1976). Hence, a random-coding based scheme can be used to achieve R(D, L) as 3 + cc. Further, it can be shown that the alphabet size of the designed queries can be restricted to M + 4, which follows from applying the Carathéodory's theorem (Cover & Thomas 2006, Thm. 15.3.5). Note, however, that finding an analytical closed-form expression for R(D, L) in our case is intractable even for independent and identically distributed (i.idd) files. Hence, we provide numerical results for Gaussian data in Section 5 which indicate that, by combining the achievable scheme proposed below in Section 3 with convexifying approach, (6) is achievable.
2.4 GENERATIVE ADVERSARIAL APPROACH
The inference of the server can also be modeled in a generative adversarial fashion (Huang et al. 2017 2018; Tripathy et al. 2019; Tseng & Wu, 2020). In particular, the leakage-distortion tradeoff for any fixed download rate constraint R is formally described as follows. Consider family of IR schemes with query generators fo. answer functions SA. and with download rate R(So, JA) at most R. The goal of the server is to maximize the expected loss J(fo. fa) of the user by designing the decision function fa- In contrast, the user would like to design a scheme with fo- f', and fx such that the download rate R(fo, fA) R and such that the expected loss J(fo- fka is minimized, while preserving the utility of the scheme, i.e., in the sense that the user can still retrieve the requested file with an expected distortion smaller than a prescribed D. This leads the constrained minimax optimization problem
min max fo fx
J(fo. fra)
(7a)
EM.Q [d (M) x)] < DD R(fo fA) SR
subject to
(7b)
x - M,Q))
Q S), A A=
(7c)
Note that the minimax formulation in (7a) can be written in a GAN form (Goodfellow al. 2014 in which far plays the role of the discriminator and fo plays the role of the generator. Thus, the machinery of GANs can be used to determine the leakage-distortion tradeoff. In doing so, first reformulated as the unconstrained optimization problem
[[fo- fai) m EM.q (M), ff Q.)) + +2 fa)
min max fo fu
(8)
where 7/, and 772 tuning parameters, and Q and A are according to Definition I The minimax game in (8) with soft decision decoding, i.c. with the log-loss function in (C.II), will be the basis for training, as described below in Section 4
5

---

Under review as a conference paper at ICLR 2021
3 ACHIEVABLE SCHEMES
In this section, we present a general achievable scheme for an arbitrary number of files M and hard decision leakage (or accuracy) L E {1, 1/2,
1/MJ.
The construction is based on the following fact. If = 1, then the problem becomes essentially the problem of lossy compression: the user explicitly tells the server what she needs to download, and the server sends the requested data compressed with some pre-agreed method. One well-known example of such compression is quantization. This scheme is designed against maxiiuu-llikelhoon decoder that provides the best inference for the server. Assume that the user wishes to retrieve the M-th file and to ensure leakage of I/N, N < M. We describe the steps of the scheme follows.
The user first selects lossy source coding scheme C' to encode together N files of size B each. Assume that the source coding scheme achieves an average compression size (in bits) of log2 |C] and expected normalized distortion D (normalized by N29), respectively.
The user's query is designed to exactly request N files with indices M,,-.., MN such that M E [M,,.... MN J. where the N 1 nondesired indices are chosen uniformly at random. These N 1 file indices are added in order "trick" the server and hide the real file index
M of interest.
After receiving the queries sent by the user, the server compresses all N files by using the source coding scheme C, and transmits the answer back to the user.
The user decompresses the answer using the selected source coding scheme. The N - 1 nondesired reconstructed files are discarded by the user, while the desired reconstructed file is kept.
The rate of the corresponding IR scheme is log, [CI/ while the expected distortion is and the leakage is L. The performance of this scheme is strongly dependent on the used source coding scheme C. Using Lemmal] a scheme for any leakage 1/M- S I. < (not only reciprocal of an integer) can be constructed.
From the general scheme above, two specific schemes can constructed based on the source coding scheme used. The first scheme is constructed by selecting a source coding scheme based on quantization. In particular, we use a variant of the generalized Lloyd algorithm (Lloyd 1982 Linde et al.) 1980). In the sequel, we will refer to this scheme as the compression-baat -basd scheme. The second scheme, referred to in the sequel as Shannon's 's scheme, assumes B + oc and uses the well-known aate-istortiinn function from information theory for the source coding scheme (Gray 1973). In Fig. a) below, together with convexifying approach described in Appendix [D2] we plot the performance of both schemes for an i.i.d. Gaussian dataset. It is worth mentioning here that by numerically solve (6) for Gaussian data, the lower bound and the approximation values of Shannon's s scheme are actually quite close, which shows that the converse bound is achievable for the i..d. Gaussian case.
4 DATA-DRIVEN APPROACH
In this section, we describe in detail our proposed data-driven framework for constructing an efficient IR scheme for downloading an arbitrary file from arbitrary dataset stored on single server. The four functions in Fig. 2 are represented as deep neural networks and we assume, for now, that they have already been trained.
The user wishes to retrieve the M-th file (M) and encodes M as one-hot Y Y2.......... YM) (0. 1M. where Y, = 1 if j M, and Y, = O otherwise. Next, the user generates a "noise" vector S = (Si, S2 ........ Sm). where S1, S2 .2...... SM are i.i.d. according the standard Gaussian distribution ( 1). The concatenation (S), S2...., SM, Y1, Y2,... Ym) is the input to deep neural network, representing the function fo. for query generation. This network produces the query Q that is sent to the server. The intuition behind this neural network is to hide the value of M. The server's s answer is produced by concatenating the stored data X [M] and the received query Q and then feed the result into a deep neural network, representing the function fx. for answer construction. The deep neural network produces the answer vector that sent back the user. The user then concatenates A and (S), ii.... SM, Yi.... Ym) and feeds the result into deep neural network for decoding, representing the function fx. to produce the estimate X of the requested file X (M).

---

Under review as a conference paper at ICLR 2021
On the server side, deep neural network, representing the function fM+ is used to guess the identity of the requested file. The imput to the network is the query vector Q and the output (using softmax) is a distribution-like vector F = (F), ....., FMM), where Σ F3 = 1, < P3 S 1, and where F} can be interpreted as "with probabilit/likkihhood F3, the user's requested file index M is equal to j." The server's estimate of the user requested file index is then M arg max Fj.
4.1 LEARNING ALGORITHM
,..., Let (MM) = (x.,,..... x. [n]. denote the /-th requested file during training and X, the corresponding user reconstructed estimate, where n is the number of training samples. Training the deep neural networks representing the functions fo- fA, fx. and f is done following (C.12) and (8)
by first fixing the download rate and then solving the minimax optimization problem
Σ - fXB-LOos (1, Fi) + 17 (x x:
min max (foJa.s) fo TE
(9)
where [xT-Loss (Y, Fi) - E Yú, log Fl, = log Fi,M, measures the categorical cross-entropy between the vectors Y, = (Yi......, Yi.M) and F, = (Fr.1..... -F........FI.M
Here, Y and F; is the
--vector and F-vector for the 1-th sample. The parameter 7) is tradeoff coefficient that increased in every epoch. The solution to the minimax optimization problem in (9) is found using an iterative algorithm employing stochastic gradient decent similar to Algorithm in Huang et al. (0117). The solution is found by first maximizing by the objective function of (9) to determine the optimal fM for a fixed initial triple (fo. fA.fx). Next, the optimal triple (fo. fA. fx) is found for the given fM from the previous step by minimizing the same objective function. This iterative process is continued until convergence or the maximum number of iterations is exceeded. Note that, although training is done based log-loss function (see (C.11). ), we evaluate the performance more intuitively using accuracy, i.e., Pr(M- M). in Section below.
NUMERICAL RESULTS
We demonstrate the application of our proposed data-driven approach to synthetic Gaussian dataset and also for the MNIST and CIFAR-10 datasets, showing that guaranteeing a certain privacy level leads to higher diettorttoiionnn tradeoff curve, and hence sacrifice in either download rate distortion. We also compare the data-driven approach with both the compression based scheme (for all datasets) and Shannon's 's scheme of Section (for the Gaussian dataset). The Gaussian dataset consists of M = 4 files, each of dimension B = and drawn independently according to ([((m)) _o²
where 44 = (-3.0, -3.0, T, 4 (2) = (3.0.3. 3.0, 3.0)T, 4 = (3.0, -3.0,- -3.0)T, (x( = (-3.0, 3.0, T, and
3. For MNIST (CIFAR-10), the training set is comprised of 6000
(5000) and size 28 x 28 (32 x 32) images for each digit (class), and testing is performed on randomly chosen images from 10000 test images. The distortion between a requested file (m) and its estimate
X is measured as the per-symbol squared error.
In Fig. 3 we plot the accuracy, or Pr(M M = M) as function of per-symbol squared error distortion for different download rates R for the data-driven approach (solid curves) and the compression-base scheme (dashed curves). For MNIST symbol is a grey-scale pixel, for CIFAR-10 a pixel of each color, while for the Gaussian dataset it is a one-dimensional Gaussian RV. As comparison, for the Gaussian dataset, we also plot the performance of Shannon's 's scheme (dotted curves), assuming 3-+ 20, as outlined in Section
3 For Shamnon's 's scheme, we use the information rate, denoted by Q) /. It is well-known that the information rate is a true lower bound on
Rinf and defined as H( A
the operational rate from 3 (ef. Cover & Thomas (2006)). Although Rinf is lower bound on R, their
numerical values are close, e.g., for the Gaussian dataset and D 4.35, R = 2 while Rinf ~ 1.97.
As expected, one can have a higher privacy level (i.e., smaller leakage) for given distortion at the expense of a higher download rate. For the MNIST dataset, the data-driven approach significantly outperforms the compression-bast based scheme, while for the Gaussian dataset performs close to the compression-bee based scheme using variant of the generalized Lloyd algorithm (Lloyd) 1982 Linde cet al. 1980) for the source code. This should not come as a surprise, as for the Gaussian dataset, the probabilistic model is simple and known precisely. In particular, we believe that the generalized
7

---

Under review as a conference paper at ICLR 2021
0.8
0.8
Accuncy
Ascuncy
Axcuncy
0.0
Persymbul squred errer distcetion
Pervyybbol squared ernor distection
Persymbol squared eroor distertion
(a)
(b)
Figure 3: Accuracy versus per-symbol squared error distortion for both the data-driven approach and the schemes from Section
(a) Synthetic Gaussian dataset. (b) MNIST. (c) CIFAR-10.
0.5
original
= 0.6, D = 0.04
2
/ d 3
/ 4 5 6
d 3
Requested file index, M
3 5
4 5 6
7
9
7 8 9
0.2
7
L = 0.5, D = 0.05
L = 0.2, D = 0.09
/
0 3
/ 2 3
9
4
5 6
4 5 6
7 9
7 8 9
Answer retrieve index
Figure 5: Heat map with CIFAR-10 for leakage L
Figure MNIST, R = 1/2 bits per pixel.
0.30, distortion D 0.064, and rate R 1/4.
Lloyd algorithm provides to-timmll compression (cf. [abiin & Gray 1986) For MNIST we combined JPEG-like compression (including discrete-cosine transform). run-length encoding, and other entropy coding techniques for the compression-baxe However, due to very small size of images, the constant overhead (e.g.. for storing the Huffman codebook) turned out to unacceptably high. It is a well-known phenomenon that sophisticated compression methods work well only files of medium and large size. We thus opted for scalar quantization (see Appendix D33 for details). Fig. depicts an example of the reconstructed digits for three levels of distortion and accuracy for download rate of R 1/2 for the MNIST dataset.
scheme (cf.. [Bocharova] (2010) Sec. 8.2)).
For CIFAR-10 we have considered two different download rates, = 1/4 and l/s. The compression- based scheme for CIFAR-10 is rather similar to the scheme for MNIST (see Appendix D.44). Compared to MNIST, the performance of the data-driven approach for CIFAR-10 is very close to that of the compression-
scheme for R 1/4, while for R 1/s outperforms the compression-basee scheme slightly. Reasons for this might be the fact that the number of training images for CIFAR-10 lower and that the dimension of the images is around times larger than for MNIST. Hence, training is more difficult (due to the curse of dimensionality). Moreover, the images of CIFAR-10 are more structured (and with separate color channels) which may make the training harder.
So far only the download cost of the proposed schemes has been considered, neglecting both the query upload cost and the cost of distributing the trained neural networks. First, the cost of distributing the trained networks can be neglected since training is usually done beforehand server and can hence be seen as a one-time cost. This cost vanishes as the protocol can in principle run for very long time serving a large number of users while the dataset grows continuously. Second, the query upload cost is in most cases much smaller than the download cost of the answers. As will show below, this is also the case here for MNIST and CIFAR-10. For completeness, the one-time cost (in bits) of distributing the networks to the user is 465479 32, 1239135 x 32, and 744882 x 32 bits for the Gaussian, MNIST, and CIFAR-10 (R 1/8) datasets, respectively,
dedicated training
8

---

Under review as a conference paper at ICLR 2021
while the corresponding one-time cost of distributing the answer generation network to the server is 532230 x 32, 7336888 x 32, and 55871908 x 32 (R = 1/s) bits, respectively.
The number of neurons of the output layer of the query network is proportional to the number of files
M. The upload cost is at most 32 M (assuming 32-bits floats). For MNIST, this yields 32 10 = 320 bits, while the download cost is 28 28 1/2 392 bits (assuming R 1/2), which is higher. Downloading the entire dataset requires an overall communication cost of 28 28 8 10 = 62720
bits uncompressed, which is significantly higher. Moreover, the average losslessly compressed (with the LZMA algorithm (Salomon, 2007 Sec. 3.24)) sizes for different digits range from 1358 (digit 1) to 2151 (digit 8) and leads to total average size of 19021 bits, which is again significantly higher than the download cost. Analogously, one instance of the CIFAR-10 dataset (10 files) has the size of 32- -3-33-3-- 3- 8- 10 245760 bits, but can be on average compressed into 197208 bits. In general, the upload cost scales linearly with the number of files and is independent of the file size, while the download cost increases with the file size. In most cases, the file size is much larger than the number of files which is the standard argument for not considering the upload cost. In the embedded table we summarize the different costs (in bits) for the Gaussian, MNIST, and CIFAR- 1- datasets and compare with the cost (in bits) of downloading the entire dataset using lossless source coding.
In order to gain insight about the learned the output of the first network of the answer generation function (in Table 3 through heat map that reflects the contribution of each stored image in the answer, for a given requested image (further details on the construction of the heat map are given in Appendix E. The heat map is shown in Fig. 5
schemes, we consider CIFAR-10 10 and analyze
for (L, D, R) = (0.30, 0.064, 3/4) and in Appendix E.. (see Fig. 7 for (L, D, R) (0.40, 0.056, 1/1), where each row corresponds
requested image. The answer retrieve index (the label of the x-axis) refers to the index of the softmax output values from the first network of the answer function, while the color reflects the actual softmax value the sense that a warmer color indicates higher value. As an example, consider rows 1, 6, and 10 (corresponding to M = 1, 6, and 10). According to the heat map, the corresponding answers are functions of the files x ) X (6), and X (10), mcaning that the server can infer that the user is requesting one of these files, but not exactly which one, giving an accuracy of 1/3. By looking at the remaining rows, the overall (average) accuracy becomes I 3/10- 1/3 + 5/10 1/s + 2/10 1/2 3/10. Note that the scheme in this case is similar to the compression- based scheme from Section and resembles time- time-sharing of three different schemes with L = 1/a, 1/5, and 1/2, respectively. Also, averaging the expected distortion values of the schemes for given requested index gives exactly D 0.064 (see Lemma]
6 CONCLUSION
In this work, we have studied the tradeoff between down- load rate, privacy leakage to the server, and reconstruc- tion distortion at the user for single-server IR schemes. An IR scheme can be seen as an extension of the well-known concept of PIR by allowing for distortion in the retrieval process and relaxing the perfect privacy formulation for the tradeoff in terms of mutual information has
Download cost (R)
Upload cost
Download dataset
Gaussian MNIST
6 (2), 12 (4)
128
384
392 (1/2)
320
17825
1I
768 1/4
160
197208
CI
384 (1/6)
160
197208
requirement, An information-theored been provided in the limit of large file size. We have shown that generative adversarial models can be successfully applied to design efficient single-server IR schemes. This is in particular beneficial if the data statistics is unknown. The main ingredient is a new optimization approach which combines GANs with additional constraints for the download rate and the desired reconstruction distortion at the user. We have shown that our proposed GAN-based data-driven approach for a fixed download rate is able to provide a tradeoff between distortion for the user and privacy leakage to the server, which is close to that of proposed compression-base tradeoff as for the Gaussian case can be observed if the proposed data-driver approach is applied to real-world dataset like MNIST, for which it significantly outperforms the compression-bas -ased scheme. For CIFAR-10, -1, the performance of the data-driven approach is comparable to that of the compression-bast bbased scheme.
scheme where the source statistics is known. A similar

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ricardo Bacza- Yates, Berthier Ribeiro-Neto, et al. Modern Information Retrieval, volume 463. ACM press New York, 1999.
Karim Banawan and Sennur Ulukus. The capacity of private information retrieval from coded databases. IEEE Transactions on Information Theory, 643)):145-1156, March 2018. ISSN 0018-9448. doi: 10.1109911T22018227999
Yochai Blau and Tomer Michacli. Rethinking lossy compression: The rate-distortion perreettoonn tradeoff. Proceedings International Conference on Machine Learning (ICML), Long Beach, CA, USA, June 9-15, 2019. PMLR.
Irina Bocharova. Compression for multimedia. Cambridge University Press, Cambridge, UK, 2010.
Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In Proceedings 36th Annual IEFE Symposium on Foundations of Computer Science (FOCS), pp. 41-50, Milwaukee, WI, USA, October 23-25, 1995. doi: 10.1 S0.110//FFCS..195544222
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, New York, NY, USA, second edition, 2006.
Ragnar Freij- Freij-Hollant,, Oliver W. Gnilke, Camilla Hollanti, and David A. Karpuk. Private information retrieval from coded databases with colluding servers. SIAM Journal on Applied Algebra and Geometry, 1(1):647-664, November 2017. doi: 10.1137/16M1 102562.
Goodfellow. Nips 2016 tutorial: Generative adversarial networks, January 2017. URL https
7/arxiv. wttp:////aabaa/.1l.a///// 00160 arXiv:1701.001600 [cs.LG].
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. ISBN 0262035618.
Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Proceedings 28th Interna- tional Conference on Neural Information Processing Systems (NeurIPS), pp. 2680- Montreal, Canada, December 8-13, 2014.
Robert M. Gray. A new class of lower bounds information rates of stationary sources via conditional rate-distortion functions. IEEE Transactions on Information Theory, 1944)4800449, July 1973.
ISSN 1557-9654. doi: 10. 10.1109/TT..1773.1555555
Chong Huang, Peter Kairouz, Xiao Chen, Lalitha Sankar, and Ram Rajagopal. Context-aware generative adversarial privacy. Entropy, 19(12), December 2017. ISSN 1099-4300. doi: 10.3390/ e19120656.
Chong Huang, Peter Kairouz, Xiao Chen, Lalitha Sankar, and Ram Rajagopal. Generative adver- sarial privacy. In Proceedings ICML' 18 Workshop: Privacy in Machine Learning and Artificial Intelligence, Stockholm, Sweden, July 15, 2018.
Swanand Kadhe, Brenden Garcia, Anoosheh Heidarzadeh, Salim Rouayheb, and Alex Sprintson. Private information retrieval with side information. IEEE Transactions on Information Theory, 66 (4):2032-20433 April 2020. ISSN 1557-9654. doi: 10.1109//1..201992944888
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In Proceedings International Conference on Learning Representations (ICLR), Banff, AB, Canada, April 14-16, 2014.
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. In Proceedings 31th International Conference Neural Information Processing Systems (NeurIPS), pp. 972-981, Long Beach, CA, USA, December 4-9, 2017.
Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. High-rate codes with sublinear-time time decoding. In Proceedings 43rd Annual ACM Symposium on Theory of Computing, pp. 167-176, San Jose, CA, USA, June 06-08, 2011. ISBN 978- 777-1-4503-0661-11 doi: 10.1145/1993636.11999
10

---

Under review as a conference paper at ICLR 2021
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Eyal Kushilevitz and Rafail Ostrovsky. Replication is not needed: single database, computationally- private information retrieval. In Proceedings 38th Annual IEEE Symposium on Foundations of
Computer Science (FOCS), pp. 364-373, October 1997. doi: 10.1 109//OF/ 1997.646125.
Eyal Kushilevitz and Rafail Ostrovsky. One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval. In Proceedings 19th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pp. 104-121, Bruges, Belgium, May 14-18, 2000. ISBN 978- 458--4540--5539-4
Yann Lecun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2 2324,, November 1998.
Clément Levrard. Quantizaiion/clustrrnng when and why does k-means work? arXiv:1801.0081 180.03744.2 03742
[math.ST], January 2018. URL
Hsuan- Yin Lin, Siddhartha Kumar, Eirik Rosnes, Alexandre Graell Amat, and Eitan Yaakobi. The capacity of single-server weakly-private information retrieval. arXiv:2001.08727v2 [cs.IT], July 2020. BRLL:attee///xxx..orr///////////
08727
Yoseph Linde, Andrés Buzo, and Robert M. Gray. An algorithm for vector quantizer design. IEEE Transactions on Communications, 28(1):84-95, January 1980.
Helger Lipmaa. An oblivious transfer protocol with log-squared communication. In Proceedings 8th International Conference on Information Security (ISC), pp. 314-328, Singapore, September 20-23, 2005. ISBN 978-3-540-31930-6.
Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions Information Theory, 28 (2):129-137, March 1982.
Fabian Mentzer, Eirikur Agustsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. Condi- tional probability models for deep image compression. In Proceedings IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 43394 4402, Salt Lake City, UT, USA, June 18-23, 2018. doi: 10. 10.1109/ 201.200180004 8.00662.
Tan T. Nguyen and Scott Sanner. Algorithms for direct 0-1 loss optimization in binary classification. In Proceedings International Conference Machine Learning (ICML), pp. IIl-1085-III-100 Atlanta, GA, USA, June 16-21, 2013.
Michael John Sabin and Robert M. Gray. Global convergence and empirical consistency of the generalized Lloyd algorithm. IEEE Transactions on Information Theory, 32(2):148-153 March 1986. ISSN 1557-9654. doi:
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung. Alec Radford, and Xi Chen. Improved techniques for training GANs. In Proceedings 30th International Conference on Neural Information Processing Systems (NeurIPS), pp. 2234 2242, Barcelona, Spain, December 5-10, 2016.
David Salomon. Data compression: the complete reference. Springer- Verlag, fourth edition, 2007.
Islam Samy, Ravi Tandon, and Loukas Lazos. In Proceedings IEEE International Symposium on Information Theory (ISIT), pp. 1262-1266, Paris, France, July 07-12, 2019.
On the capacity leaky private information retrieval.
Jost Tobias Springenberg. Unsupervised and semi-supervised learning with categorical generative adversarial networks. In Proceedings International Conference on Learning Representations (ICLR), San Juan, Puerto Rico, May 2-4, 2016.
Hua Sun and Syed Ali Jafar. The capacity of private information retrieval. IEEE Transactions Information Theory, 63(7):4075-4083 July 2017. ISSN 0018-9448. doi: 10.110./TIT.201 2689028.
11

---

Under review as a conference paper at ICLR 2021
Razane Tajeddine, Oliver W. Gnilke, and Salim El Rouayheb. Private information retrieval from MDS coded data in distributed storage systems. IEEE Transactions on Information Theory, 64 (11):7081-7093, November 2018. ISSN 0018-9448. doi: 11111990TT22118885666000
Raphael Toledo, George Danezis, and Ian Goldberg. Lower-cost e-private information retrieval. In Proceedings Privacy Enhancing Technologies Symposium (PETS), pp. 184-201, Darmstadt, Germany, July 19-22, 2016.
Ardhendu Tripathy, Ye Wang, and Prakash Ishwar. Privacy-preseriing adversarial networks. In Proceedings 57th Allerton Conference on Communication, Control, and Computing, pp. 495-505, Monticello, IL, USA, September 24-27, 2019, doi: 10. 109/ALLERTOO.2219...9009 89119798
Bo-Wei Tseng and Yuan Wu. Compressive privacy generative adversarial network. IEEE Transactions Information Forensics and Security, 15:2499-2553 2020.
Jun Wang, Lantao Yu, Weinan Zhang, Yu Gong, Yinghui Xu, Benyou Wang, Peng Zhang, and Dell Zhang. IRGAN: A minimax game for unifying generative and discriminative information retrieval models. In Proceedings 40th International ACM Conference on Research and Development in Information Retrieval (SIGIR), pp. 514,524, Shinjuku, Tokyo, Japan, August 7 7-11, 2017, 2017. ISBN 9781450350228. doi: 131144455777733307777777
Aaron D. Wyner and Jacob Ziv. The rate-distortion function for source coding with side information at the decoder. IEEE Transactions Information Theory, 22(1):1-10, January 1976.
Sergey Yekhanin. Private information retrieval. Commun. ACM, 53(4):68-73, April 2010. ISSN 0001-0782. doi: 10.1144//721694.77711177
12

---

Under review as a conference paper at ICLR 2021
Appendix
A PROOF OF LEMMA
Assume the schemes that achieve the triples (R1. D1, L1) and (R2, D2, L2) are C1 and C2. respectively.
We denote the queries of C1 and C2 as Q1 and Q2. respectively. From C₁ and C2 we construct a new scheme C) that achieves the triple (AR1 (1 22 XD + (1 - 22 AL1 (1 2)L2), for any
E (0, 1). This is exactly the definition of a convex set. The scheme C. is as follows:
The user generates time-sharing RV K according to the distribution
{1-x
{A =
(k(k) = 11 1-
Then, the user forms the query Q = (K, Qk) and sends to the server, thus explicitly notifying which of the schemes, Ci C2, is used.
Finally, the server replies according to Cx using the query QK.
The leakage of C2 becomes
p(PQ)M) = p(APQ + (1- I Xp(Pa. + - XL1 22
where equality in (a) can be achieved by artificially "worsening" the scheme Cx. c.g., by explicitly sending M to the server some cases (with some probability). The proof for the distortion and the rate of C follows in similar manner (they are not just convex but also linear), Hence, the set of achievable rate- rate-distortion-ler distortioon-eaakae triples constitutes a convex set.
B PROOF OF THEOREM 1
Convexity. We prove the convexity for R(D.L) L) based on the assumption that p(PQ)M) is convex in PaIM, i.e. have
LA a p(APQ.l + (1-11)))) (o)))r
S Ap( + (1 A)p( S AL1 + (1 -1 (1-)) OSAS1.
Note that since the queries should be generated without knowing any realizations of the retrieved files, it is quite natural to have 1(x [M] Q) 0. Thus, the objective function in the minimization of (6) can be expressed as
(x [M]
[M]
Q) = 11(x [M], X [M] (Q) + +1(x [M] 1(x M
[M] Q)
Now, let the distributions P P [xIM] and P PX|M] Q21 achieve R(D L1) and R(D2, L2). respectively. Given Px(M)) 1.. XIM] = XP
x [(M]
Q Q +on++00 (1- (MM) [2[[xiM for any < X < 1,
using the convexity of mutual information
( we obtain
M( [M] Qx) S AI(X IM)
X MM
1 +1- X [M] Q2).
(B.10)
and P (MIII = XP x [ + (1 (1- A | X From the convexity of p(-) and the linearity of the distortion function d(,, -),
Further, one can also see that PQLIM = +1
straightforward to see that AL; + (1 A)L2 2 Lx and AD, (1 (1-)) 2 D,. Hence, from the definition of R(D,L, L) we get
R(AD, + (1 A)D2, XL1 + (1 (1-A)L2)
R(DA,L))
((x M) X
[M] Qx)
AR(D, Ln) A)R(D2, L2).
13

---

Under review as a conference paper at ICLR 2021
where (a) holds since the minimization is taken over smaller constrained set, and (b) follows from (B.0)). This then completes the proof of convexity of L)D
In the following, we show that for the case of memoryless vector sources | i... each element of (mm is chosen independently and uniformly random from E. the converse bound for the achievable rate R is indeed R(D.L). L).
Consider i..d. (x."), x/ ,..,,,,M)), ),M)), E [s], and each component (m) is distributed according to Px(m). The answer encoder f% takes the input sequence {X [M] 9 and the generated query Q to construct
sequence of length-M vectors (
Ji=1" where X!M
the codewords that are indexed by A = (1,2,..., 29R
J The reconstruction decoder f outputs an
estimate {X] [X for X!M] (X!"). x(2)
X X using the answer A requested index
11=1
M, and the generated query Q at the user side. A feasible scheme should satisfy
8
Σ
EM.Q ddx!M)) (((X))))(())) = D and p(PQ)M) S L.
B i=1
Hence, using the fact that the average code length over source code is bounded from below by the entropy of the source, e.g., see Cover Thomas 2006 Thm. 5.4. I), we have
GR N H(AlQ)
@ H(AQQ) - X
8
I= Q)
A
1[ M Je {X
[M]
Ji-1 Q)
Σ
H(X! (M |Q) Σ H(X! MJ
Σ
(x! ;
x Q)
(d(x ((( {( ((PQ)s))
1=1
8
Σ EM.Q [d(x!"m) xx(M)) ,p (PQq)))
B R
DR(DLL)
where (a) holds since the answer A is a function of {x! M
and Q: (6) follows by the data processing incquality: (c) can be verified by using the chain rule of entropy and conditioning reduces entropy; (d) and (e) hold because R(D, L) is nonincreasing and convex.
(
| و
C SOFT DECISION DECODING
In contrast to hard decision decoding where the server deterministically guesses exactly M m from the query, we can also consider a soft decision decoding rule for the server. In this case, (Q) can be seen distribution over [M], i.e., fx (Q) (m Q) for [M], where Σm (m) Q) = 1. Let fLoss (m, MM) ) be the log-loss function defined as
f (m, M) H(M) + log F Fyr (m|Q). i.c. the loss is zero when the server's guess equally likely. Then, the expected loss function is equal to
(C.11)
J(So H(M) - >n'-oooloe Po(a) (- Σ (m) log (s)(m))))
'Here, without loss of generality, we assume that the reconstruction X [M] has same dimensions as X [M] However, the user can choose the desired file (M) retrieve.
14

---

Under review as a conference paper at ICLR 2021
H(M)-
E (o(1))(PMMQ=4(()
|| (x)(+
(C.12)
S H(M)-
Σ PQl())(PMMQQ=44 H(M) PMM q), (C.13)
where H(Px ||
Py) denotes the cross-entropy between the distributions Px and Py, and C.13
follows since for any two distributions (x(() and P-()), we have ((Px()) Pr)-)) 2 (P) Moreover, observe that
max(J(Jo: S (M) - H(M Q) = (M,Q),
and from (C.13). it follows that equality holds if PM (+) = (-))))))- Therefore, under the log-loss function, the leakage to the server is measured in terms of MI, i.e., p (PQaM) = (M;)), and the user wishes minimize the MI leakage.
D ACHIEVABLE SCHEMES FROM SECTION
D.1 COMPRESSION- SCHEME FOR GAUSSIAN DATA
As reference for synthetic Gaussian data (see Fig. 3 ()), we used the compression-based scheme outlined Section vectors drawn from a Gaussian multinomial distribution. We used the generalized Lloyd algorithm, also known as the Seale-Buzo-Grng (or LBG) algorithm (Linde al. 1980p. Note that this algorithm is closely related to k-means clustering in unsupervised learning eLevradd] 2018). The authors argue Linde et al. (980)) that although their approach is not guaranteed to provide the best quantizer, its results are nearly optimal for wide class of distributions.
explained in Section 3 the scheme reduces to quantization of random
We briefly explain the steps of finding the quantization vectors (or levels) below and refer the interested reader to Linde et al. (1980) for further details. When quantizing Gaussian vector into bits, the number quantization vectors is k = 2
1. First, generate a large sample of n vectors { from the desired multinomial Gaussian distribution.
2. Then, select an initial set of quantization vectors {q:
3. Next, continue iterating as follows:
(a) Each sample vector æ; is quantized to (approximated by) its closest quantization vector (its "nearest neighbor") 93; where
o = arg min di 4;).
This gives a mean quantization error (or distortion) among all the sample vectors of
Σ d( 9;
D
TL
(b) Each quantization vector is updated to the mean the sample vectors as follows:
9
x
SJ
MES,
where the set of sample vectors that are quantized to qj is denoted by S, ("neighbor- hood" of q,).
4. The algorithm stops when the mean quantization error between two consecutive iterations changes less than a predefined threshold.
Since the mean quantization error (or distortion) D is nonnegative and nonincreasing between iterations, the algorithm is guaranteed to converge. Since it is randomized algorithm,
15

---

Under review as a conference paper at ICLR 2021
multiple times and chose the quantizer that produced the smallest mean quantization error. As final remark, we remind the reader that our goal here is not to find the best quantization possible, but only to have good enough upproximation.
Additionally, after the avhievable points are calculated, we make sure they all satisfy the convexity property (cf. Lemma D.. More precisely, if the triples (R1, D1, L1), (R2, D2, L2), and (AR1 + (1 2),2, D3, AL1 + (1 22) are achievable for some 0 < < 1, we update
D3 + min(Ds, AD, + (1 - -))
D.2 SHANNON'S SCHEME FOR GAUSSIAN DATA
This section briefly outlines the Shannon's scheme for Gaussian data (plotted in Fig. B(a), Following its description in Section 3 the server compresses N. N [M], independent files, each consisting of / independent Gaussian RVs, together. It is known from the rate-distortion theory for multi- dimensional sources Gray 1973). the file size / - 0o. that a download rate R (D) is achievable with distortion D. Here, RR(D) = max 2 log (e'/D).0) 00 for a Gaussian RV distributed according to N ((4,, d²) (Cover & Thomas 2006 Ch. 10). Similar to Section D.1 we further use a convexifying approach to obtain an achievable scheme for any hard decision leakage (or accuracy)
1/M S L < 1. In the following we brief describe the scheme. First, we select two accuracy values, say L1 and L2, L2 E {1, 1/2,/...... 1/M]. Applying the Gaussian rate-distortion function of (D) 1/2 log (D)) D E (0, o0, to the previously outlined scheme, one can obtain two achievable distortions Da (R L1) = g2. 2- and Da (R1, = a² 2 2-2R, Next, the desired accuracy I E [L1, L2] is selected to be I = XL1 (1- A)L2, and the goal is to determine the minimum possible linear combination of (R L,) and (R,, L2) subject R AR1 + (1 2 i.e.
min E(MM)
min
[RI, + (R L2)]
(D.14)
R (I- -
This then gives the performance of the synthetic Gaussian dataset in Fig.3(a also numerically evaluate the values of R(D, L) for the Gaussian dataset. For instance, for D = 1.875 and L = 0.6, we obtain R(D, L) x 2.0345, while (D.14) gives 1.875 for (R, = (2.0,06)) confirming that the performance of our proposed Shannon's scheme is optimal.
Ba). As a final remark, we
D.3 CMMPRESSION-AASED SCHEME FOR THE MNIST DATASET
The scheme is based on the ideas of Section D and reduces to choosing a lossy compression method for one image. First, we applied a grayscale compression similar to the instruments used by the JPEG standard. We refer the interested reader to (Bocharova 2010 Sec. 8.2) for more details and other techniques for image compression. The main ingredient of the JPEG standard is a two-dimensional discrete cosine transform. In the standard, an image is split into 8 8 blocks and the transform is applied to each block independently. Since the images from the MNIST dataset are of size 28 x 28, we applied the transform resulting values were quantized by uniform scalar quantizer. For each block, the top-left coefficients play the most important role as they grasp the low-frequency contents of the block. Thus, they are assigned more bits from the available pool of bits (defined by the desired rate). Finally, these quantized coefficients were encoded with a combination of run-length encoding and a two-dimensional Huffman code.
7 blocks. In this way, an image is split into 16 blocks. Next, the
Since the MNIST images have a small size, the entropy coding techniques do not provide any compression benefits. For example, the usually ignored overhead of storing the Huffman coding table requires too many bits in our case. Also, the run-length encoder performs poorly as there are not many repetitive values. In fact, it even increases the size of an MNIST image on many occasions. Therefore, we turned to a much simpler scalar quantization of the original grayscale images where each image is split into blocks. For each block, the average of values of its pixels was quantized and stored. This method also allows for easier control of the desired rate.
16

---

Under review as a conference paper at ICLR 2021
D.4 COMPRESSION-BANE SCHEME FOR THE CIFAR-10 10 DATASET
The compression-basee based scheme for CIFAR-10 is rather similar to the scheme for MNIST. The only difference being a standard image preprocessing stage that very common when compressing color images. First, the image is transformed from red, green, and blue channel representation to luminance-chrominancc representation. consisting of brightness, huc, and saturation channels. Next, the hue and saturation channels are decimated by factor of 2. In other words, four neighboring pixels that form a x 2 block are described by four values of brightness, one value of hue, and one value of saturation. These channels further quantized in similar manner as for MNIST.
E LEARNING ALGORITHM FOR THE DATA-DRIVEN APPROACH
Algorithm 1:
Training algorithm for generative adversarial user privacy
:Number of training samples n, training samples (X) [M]
M ..... X n ). number of
Input
training iterations T, size of minibatch for stochastic gradient decent b, and initial tuning parameter 7/nitial
Output: fo: far fx. and fM
1 +-1
1) f- Viiitiall
Initialize the neural networks representing JQ. SA. fx. and Saa
while t < do
for E [M] do
Generate minibatch Bm S [n] of indices corresponding to the m-th file, |Bm. Generate b noise samples $8.. from the distribution (0,
for b E Bm do
Am,b + fq(m, 8h))
10
end end
11
Update fúi by descending its stochastic gradient:
EM EBEB,,, 6xM log Fm (gm.b)
13
14
for m E [M] do
15
Generate minibatch B,n S [n] of indices corresponding to the mitt file, |Bm
Generate b noise samples 8,,,, from the distribution (0,
Generate minibatch of b training samples {X, (m) 6 Bm for b B, do
17
9m.b + fo(m, sb)
20
end end
21
22
for m E MM] do
23
for b B,n do
am + fa(am.b x (M))
24
25
end
end
27
Update fQ. SA. and fx by descending its stochastic gradient:
IM EleB.. bxM log Fm (qm,)) + d(xx'(x (m) f& (am, m, pm.)))
(x(m)
28
29
Update the tuning parameter i- ++1
end
32 return for fx. fx. and fM
As elaborated in Section 4.1 learning is done by first fixing the download rate R and then solving
the minimax optimization problem in (9). Here, the rate is computed based on the dimension of the answer network's output and the corresponding quantizer levels like Blau & Michaeli (2019); Mentzer et al. (2018). In Algorithm we outline the detailed training algorithm, which is similar
Algorithm in Huang et al. (2017). The learning rate is selected empirically for each accuracy
17

---

Under review as a conference paper at ICLR 2021
and distortion level with the RMSprop optimizer, and the number of iterations is T 100000. The number of training samples, denoted by nI, for the Gaussian case is set to a sufficienlly large number (samples easily be generated from Gaussian RV) and to 60000 (6000 for each digit) and 50000 (5000 for each class) for the MNIST and CIFAR-10 10 datasets, respectively.
The architectures of the deep neural networks representing the functions fo- SA. fx. and fxr used for training for the synthetic Gaussian dataset are detailed in Table [ the special case of accuracy - 1, i.c. full leakage, the problem reduces the classical rate-distortion problem, and to improve performance, we only considered an encoder (for compression of the requested file), corresponding to fa. and decoder (for decompression at the user side), corresponding to fx. Both the encoder and the decoder are represented as deep neural networks and trained in the classical way (Kingma & Welling 2014).
Table 1: Neural network architectures used for training for the synthetic Gaussian dataset. FC stands for fully connected layer. Size the number of neurons or input size. As activation function we used the scaled exponential linear unit (SeLU) KKlambauer et al. 2017).
Query generator, fo
Answer generation, fA
Size
Layer
Size
Layer
Input
4
3 x 4 X 1
Input
8
FC, SeLU
16
Flatten
8
FC, SeLU
256
FC, SeLU
8
FC, SeLU
256
FC, SeLU
8
FC, SeLU
256
FC, SeLU
4
FC, SeL.U
256
SeLU
256
FC, SeLU
256
FC, SeLU
256
FC, SeLU
256
FC, SeLU
256
FC, SeLU
Answer dim
FC, tanh
Decoder, fx
Adversary, fMr
Size
Layer
Size
Layer
Answer dim +8
Input
4
Input
256
FC, SeLU
64
FC, SeLU
256
SeLU
64
FC, SeLU
256
SeLU
64
FC, SeLU
256
FC, SeLU
64
FC, SeLU
256
FC. SeLU
64
FC, SeLU
256
FC, ScLU
64
FC, SeLU
256
FC, SeLU
4
FC, softmax
256
FC, SeLU
3
FC
For the MNIST dataset there are M 10 files (there are 10 digits) and each file of size
28 x 28 = 784 symbols, or 784 8 6272 bits (each picture is of size 28 x 28 pixels and each pixel is of size 8 bits). The architectures of the deep neural networks representing the functions fo- fA. fx. and fa in this case given in Table 2
For CIFAR-10 dataset there are also M = 10 files (there are 10 classes of files) and each file is of size 3 32 x 32 1024 symbols, or 1024 8 x 3 24576 bits (each picture is of size 32 x 32 pixels and each pixel is of size 8 bits for each of the 3 color channels). The architectures neural networks representing the functions fo, fA. fx. and fxr in this case given in Table 3 Note that contrast to the Gaussian dataset and MNIST, in Table 3 we list descriptions of three neural networks for the answer function fx, labeled as part 3. To produce the final answer, the output of
the deep
18

---

Under review as a conference paper at ICLR 2021
the first network is fed to the third network together with the output from the second network and the queries (which are fed into the fourth layer of the network). The imput to the first network the queries, while the imput to the second network is the database. The second network takes the database as input and extracts its features. As for the Gaussian case, training for both MNIST and CIFAR-10 can be simplified for I.
described above.
Table 2: Neural network architectures used for training for the MNIST dataset. The input pixel value rescaled between 1.0 and 1.0. FC stands for a fully connected layer. Conv and ConvT stand for convolutional and a transposed convolutional layer, respectively, where "st" is shorthand for stride. Size is the number of neurons or input size. As activation function we used SeLU and hyperbolic langent (tanh).
Query generator, So
Size
Layer
20
Input
20
FC, SeLU
20
FC, SeLU
20
FC, SeLU
10
FC, SeLU
Answer generation, FA
Size
Layer
10 + 10 x 28
28
Input
26 x 26 x
Conv, SeLU
12 x 12 x
Conv (st = 2), SeLU
10 x 10 x 16
Conv, SeLU
4 x 16
Conv (st = 2), SeLU
256
Flatten
2560
Concatenate 10 parallel outputs of previous layers
1024
FC, SeLU
1024
FC, SeLU
1024
FC, SeLU
1024
FC, SeLU
512
FC, SeLU
512
FC, SeLU
512
FC, SeLU
512
FC, SeLU
392
FC, tanh
Decoder, fx
Adversary, fmr
Size
Layer
Size
Layer
412
Input
Input
512
FC, SeLU
64
FC, SeLU
512
FC, SeLU
64
FC, SeLU
512
FC, ScLU
64
FC, SeLU
512
FC, SeLU
64
FC, SeLU
4 x 4 x 32
Unflatten
64
FC, SeLU
11 x 11 x 64
ConvT (st = 2). SeLU
64
FC. SeLU
25 x 25 128
ConvT (st 2). SeLU
FC, sofumax
28 x 28 x 1
Conv'T (st = 1), tanh
In order to assess the quality of the learning, tabulate below estimate of the inference accuracy of a MAP adversary for M, denoted by LMAP, operating directly on the queries from the query network and also estimate of the entropy of the answer A from the answer network for the
19

---

Under review as a conference paper at ICLR 2021
Table Neural network architectures used for training for the Cifar-10 dataset. The input pixel value is rescaled between -1.0 and 1.0. FC stands for fully connected layer. Conv and Conv'T stand for a convolutional and transposed convolutional layer, respectively, where "st" is shorthand for stride. Size is the number of neurons input size. As activation function we used SeLU, sigmoid, and hyperbolic tangent (tanh).
Query generator, fo
Answer generation part 1, fA
Size
Layer
Size
Layer
20
Input
5
Input
20
FC, SeLU
FC, SeLU
20
FC, SeLU
7
FC, SeLU
FC, SeLU
9
FC, SeLU
FC, SeLU
10
FC, softmax
FC, SeLU
Answer generation part 2, /A
Size
Layer
10
x
32
x 32
X 3
Input
10 x
30
30
Conv, SeLU
10 x 14
x
14
x
Conv (st = 2), SeLU
10
12
12
16
Conv, SeLU
2304
X
10
Concatenate 10 parallel outputs of previous layers
Answer generation part 3, /A
Size
Layer
10 + 2304 x 10
Input
2304 x 10
Broadcast and elementwise multiply Flatten
23040
Input
2304
FC. SeLU
1024
FC, SeLU
Answer dim
FC, sigmoid
Decoder, fx
Adversary, fir
Size
Layer
Size
Layer
Answer dim + 20
Input
5
Input
512
FC, SeLU
64
FC, SeLU
512
FC, SeLU
64
FC, SeLU
512
FC, SeLU
64
FC, SeLU
4 X
4 x 32
Unflatten
64
FC, SeLU
8 x X 16
ConvT (st = 2), ScLU
64
FC, SeLU
16
16 8
ConvT (st 2), ScLU
64
FC, SeLU
32 x
32 3
ConvT (st 2), tanh
10
FC, softmax
Gaussian dataset for different levels of per-symbol squared error distortion D. The estimates have been found by Monte-Carlo simulation of the networks, i.e., by repeatedly generating queries and answers and estimating the probability density functions of the random variables QIM and A. For comparison we also show the inference accuracy L of the adversary network in the third line. As can be seen by comparing the second and third lines. the inference accuracy of the adversary network is close to the inference accuracy of a MAP adversary. Likewise, the entropy H(A) is close of R 3, which gives an indication that the performance neural networks adversary is close to an optimal bound. For CIFAR-10 with accuracy I. = 0.40 and distortion D = 0.056, the MAP accuracy is MAP 0.41, which shows that also for CIFAR-10 10 the adversary trained quite well.
20

---

Under review as a conference paper at ICLR 2021
0.5
0.4
Accuracy
0.3
Training accuracy
Testing accuracy
0.2
0.1
Distortion
0.2
Training distortion (MSE)
Testing distortion (MSE)
0.1
0.2
0.4
0.6
0.8
1.2
1.4
1.6
1.8
Epochs
-105
Figure 6: Learning curves with CIFAR-10 for leakage = 0.40, distortion
0.056, and rate
1/1.
Gaussian data set and R = 2
Gaussian data set and R 4
D
6.60
5.46
4.35
1.16
D
3.93
1.15
0.72
0.21
LMAP
0.26
0.38
0.50
1.0
LMAP
0.27
0.53
0.76
1.0
L
0.25
0.37
0.50
1.0
0.26
0.51
0.76
1.0
H(A)
5.83
5.85
5.90
5.89
H(A)
11.82
11.56
11.45
10.86
To investigate the well-known overfitting problem in ML Goodfellow et al. 2016 we show some learning curves with the CIFAR-10 dataset (for leakage 0.40, distortion D
0.056, and rate R = 1/1) 1/1) in Fig. 6 The training distortion and training adversary accuracy curves are averaged over sliding window
length 100 and then sampled every 100 epoch. The testing distortion and testing adversary accuracy curves are sampled every 5000 epoch. If overfitting happened, then the testing distortion would increase while the training distortion would decrease with the number of epochs. This does not happen in our case. In fact, the testing distortion curve is decreasing and close to the training distortion curve. Hence, the level of overfitting is negligible. Moreover, training and testing accuracy values close.
The mode collapse issue in GANs is well-known (Salimans et al. 2016 Goodfellow 2017 Mode collapse means that the generator finds some weak point of the discriminator and keeps producing this mode of output to trick the discriminator. This may happen when the generator tries to fool the discriminator trained on real dataset and causes problems because GAN model is typically required to have diversity in its output. Techniques such as minibatch discrimination (Salimans et al. 2016 can be applied prevent mode collapse. However, note that in our step-up mode collapse is less relevant (and may even be beneficial in some cases) as we in general do not need to have diversity the query generation. In fact, a scheme for the MNIST (or CIFAR- 10) dataset producing a deterministic query is a valid scheme with MAP adversary accuracy LMAP = 1/10, while scheme giving a one-to-one correspondence between M and Q M is also valid and gives MAP adversary accuracy LMAP = 1. In order to investigate mode collapse in more detail for intermediate values of the accuracy, we have estimated the variance Var [Q M] for CIFAR-10 for leakage L L= 0.40, distortion D 0.056, and rate R 1/4. The estimated values are from 10t samples and are tabulated below. As can be seen from the table, the query network generates queries with some diversity. Moreover, from the MAP accuracy values LMAP above (for CIFAR-10 with (L, D, R) (0.40, 0.056, 1/4) it is 0.41), follows that the discriminator is trained quite well and do not appear to suffer from degeneration in the query generation training due mode collapse.
21

---

Under review as a conference paper at ICLR 2021
Query variances for given requested file index for CIFAR-10 with DL, R) = (0.40, 0.056, 1/4).
Requested file index M = m
Var [ = ml
1
(0.000, 0.000, 0.036,
2
(0.049, 0.007, 0.18,,
3
(0.041,00045)) 0.000000...00
(0.000, 0.000, 0,000,0000000000,3,,0000000)
5
(0.027, 0.041, 0.000,0.03300
6
0.041, 0.000, 0.,,7.0..0,..00000000233.00000
7
(0.027,0.04) 0.023,0000
8
(0.000, 0.00000.000...000,,035.000000001
9
(0.041, 0.0.0,00..91..000000000000
10
(0.040, 0.039, 0.0000,0..0.000000..000000
E. HEAT MAP REPRESENTATION OF THE ANSWER
In this subsection, provide additional details the heat map representation of the output of the first network the answer generation function for the learned data-driven schemes for CIFAR-10. As mentioned in Section 5] the heat map reflects the contribution of each stored image in the answer, for given requested image (corresponding to given row of the heat map). Denote by 8(2),..., 5(M) the outputs from the M neurons following the softmax activation functions of the first network of the answer generation function. The second network of the answer generation function extracts the features of the database, denoted by (1)) ..... ((M), which are fed as input to the third network of the answer generation function together with 8(1) ..... 8(M) and the queries (which are fed into the fourth layer). In the first layer (of the third network), the vector (5(1),... ,.., 5(M)) is multiplied elementwise with the feature vector (Z) ..... Z(M)), producing the vector (8 ( ..... , 5(M) z (M)), which subsequently combined with the queries in the fifth layer in order to produce the final answer. Now,
8 8(m), for some m [M], is close to zero, then the answer will not depend much on the file indexed
by m, and it follows that the heat map indeed reflects which files contribute the most to the generated answer.
In Fig. 7 the heat map for (L, R) = (0.40, 0.056, 1/4) is shown. As an example, consider rows 1, 4, and 8 (corresponding to .M 1, 4, and 8). According to the heat map, the corresponding answers are functions of the files ( ( and (8), meaning that the server can infer that the user is requesting one of these files, but not exactly which one, giving an accuracy of 1/a. For M = 2 (corresponding to the second row), however, the answer depends only on the second file, meaning that the server infer that the user is requesting the second file, giving accuracy of 1. By looking at the remaining rows, the overall (average) accuracy becomes 3/10- 1/3++3110 1/3+3/333/33 3/10- 1/3 + 1/10-1- 4/10.
22

---

Under review as a conference paper at ICLR 2021
1
2
0.8
Requested file index, M
3
4
0.6
5
6
0.4
7
8
0.2
9
10
10
Answer retrieve index
Figure 7: Heat map with CIFAR-10 for leakage L 0.40, distortion D 0.056, and rate R 1/4.
23


Reviews:
[{"review_id": "RcK-eyPSgMu", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe paper aims at taking a new approach towards the problem of private information retrieval. The proposed method relies on the interplay of the three parameters: distortion (utility), leakage (privacy) and the download rate/cost. They try to decrease the download cost, by sacrificing some utility (lossy compression through GANs), which is an interesting and seemingly novel take on the problem. Their method needs to solve two optimization problems: the first one assumes a fixed utility and privacy, and minimizes the download rate, the second one is a minimax loss that assumes a fixed rate and trades off privacy for utility. They then propose three practical methods based on this, the first two are not applicable on all cases, the last one, however, is data driven and can be applied to a wider range of problems. \n\npros:\n+The method offers a nice trade-off between the three dimensions of cost, utility and privacy. \n+The proposed method is evaluated both theoretically and experimentally which helps verify its veracity. \n\ncons:\n- This is more of a question: why are there only two datasets, the synthesized one and MNIST? why not bigger datasets? would the proposed methods also work on larger images? I assume one reason would be because information theoretic bounds are much harder to enforce in high dimension cases. Is that the case? If so, how can it be addressed? \n\n- Also, in Section 5, paragraph third paragraph, there was a sentence which is a bit ambiguous to me: \"However, due to a very small size of images, the overhead (e.g., for storing the Huffman codebook) turned out to be unacceptably high.\"I did not completely understand what the problem is. Is it the case that because the images are small, the codebook becomes really large? Would this get worse with larger images? \n\n\n[I am not at all familiar with information retrieval and the work surrounding it, so I am not entirely confident in my review and I might update it based on the review of expert reviewers later on].", "extra_scores": {}, "extra_text": {}}, {"review_id": "MwmlqJp1LSG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers and formulates a generalized version of the private information retrieval (PIR) problem, where a user aims to retrieve one of $M$ files from a dataset, but wants to keep the index $M$ private. Unlike the basic version studied in prior works, the problem formulated in the paper allows non-zero privacy leakage and distortion and aims to trade these two quantities as well as the download communication rate.  A data-driven approach is proposed to find PIR schemes, and a more conventional approach is presented as a benchmark.\n\nTopic: Overall the main focus of this work is on optimization and information theory and is less relevant to DL, so conferences like ICML or ISIT might be a slightly better match.\n\nTechnical comments: Several statements in the technical formulation needs to be revised for correctness and readability. For example,\n1. Lemma1 is proved by allowing the user to share some additional information to the server, which should be prohibited, otherwise, the user can simply deliver $M$ to the server and making the privacy requirement trivial. One possible fix is to send that information as part of the query and to fix related statements such as how the convexity of matrix $\\rho$ should be defined.   \n\n2. There are some missing conditions in the formulations of optimization problems such as (4b), where additional constraints such as Markov chain requirements are needed for the result to be non-zero (or non-trivial). \n\nPresentation: Regarding the plots in Figure (3), it might be good to add comments and provide intuition on why the data-driven approach is better in one setting and worse in the other.\n\n\nPost Rebuttal:\n\nI'm totally fine with the topic, which is a very minor issue as mentioned earlier. My main concern was regarding the overselling of some presented results.\n\nFrom the technical side, Lemma 1 is a common approach in information theory/channel coding/privacy that one can linearly combine several designs by randomly sampling them, which was presented in the abstract as one of the main results. I expected something beyond a simple application, such as determining an interesting condition where this approach can be used, but the provided statement does not seem to hold after revision. As long as one can append additional messages to the query, the domain of Q could change completely, and the convexity of P_{Q|M}, interpreted exactly as stated, will not provide any guarantee. The condition actually needed by the authors is essentially random sampling does not hurt privacy, making the statement \"random sampling can be applied when it can be applied\", which is a bit trivial.\n\nI carefully double-checked the provided proof steps and found that an additional assumption was needed in the very last step, which further requires something like the metric \\rho is invariant under permutation of Q, for which I didn't find in the paper, maybe I missed it. Adding this assumption totally makes sense to me, but requiring convexity+invariant under permutation is a bit over-complication, instead of just directly requiring random sampling does not hurt privacy. The theory part of the paper should be presented in the simplest possible way, without unnecessary complication.  \n\nThe authors do have a novel contribution in terms of experiments. But the contribution and novelty in the formulation are rather limited given that the considered components have been studied either separately or jointly in cited works.\n\nFor the experiments: I have a similar concern as mentioned by Reviewer 1, which is about the generalizability issue. A natural explanation of the presented results could be that the hyperparameters in the implemented solution are tweaked for datasets like MNIST or something similar. It is not clear if it would fail for more general datasets similar to synthetic Gaussian. \n\nI've read the authors' responses to review 1 and the revised paper. Overall, there is no more direct evidence of generalizability. But this issue itself is fine as it could happen in many other works, so I won't consider it as my main concern. \n\nBesides, the author has adequately addressed the issues of the missing conditions in the Theorems. \n\nConclusively, my recommendation remains the same for the above reasons. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7VPpHlVvVN", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThis paper studies single-server private information retrieval with user data distortion constraint. In particular, the authors formulate the problem as a minimization of download rate under distortion and privacy constraints. They show the achievable set is convex. They also provide a information-theoretic formulation of the trade-off. Based on this framework, the authors propose to parameterize query function and file estimation function by neural networks and formulate it as a two-player game. Empirically, the authors demonstrate the effectiveness on the Gaussian dataset and MNIST dataset.\n\nPros: 1. The trade-off between distortion, privacy, the download rate is indeed an interesting problem.\n\n\nCons: 1. The idea of using GAN for information retrieval is not new. It would be better if the authors could discuss the contributions compared to previous works like IRGAN 2017, other than adding privacy and distortion constraint.\n\nQuestions: 1. Since the authors apply the data-driven approach, I am wondering how does the overfitting problem/mode-collapse affect the trade-off.\n\nReasons for score: I am not an expert in information retrieval, so I could not tell the signification of the contributions. Overall the paper is well written. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper got mixed ratings. However, keeping in mind the low confidence of some of the reviewers, the paper needed an additional look. The AC himself went over the paper. The paper presents an interesting formalism for private information retrieval. As reviewers have pointed out the formalism is based on several existing ideas on utility privacy tradeoff. 
The use of GANs for enforcing privacy is also not new. The rebuttal did not convince some of the reviewers about novelty which seems reasonable given the area and literature in it. 

Overall, the paper needs to consolidate all ideas of Adversarial training for privacy and compare and contrast with the proposed approach to make it compelling for publication. 
Decision: Reject