Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Topic: 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.

Technical comments: Several statements in the technical formulation needs to be revised for correctness and readability. For example,
1. 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.   

2. 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). 

Presentation: 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.


Post Rebuttal:

I'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.

From 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.

I 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.  

The 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.

For 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. 

I'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. 

Besides, the author has adequately addressed the issues of the missing conditions in the Theorems. 

Conclusively, my recommendation remains the same for the above reasons. 

review_title: Some technical statements needs to be formalized 

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
The 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. 

pros:
+The method offers a nice trade-off between the three dimensions of cost, utility and privacy. 
+The proposed method is evaluated both theoretically and experimentally which helps verify its veracity. 

cons:
- 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? 

- 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? 


[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].
review_title: feasible and sound approach for private information retreival

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: 
This 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.

Pros: 1. The trade-off between distortion, privacy, the download rate is indeed an interesting problem.


Cons: 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.

Questions: 1. Since the authors apply the data-driven approach, I am wondering how does the overfitting problem/mode-collapse affect the trade-off.

Reasons 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. 
review_title: this paper extend PIR with data distortion and provide a GAN based scheme

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