Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper proposes a differentially private version of the lottery ticket mechanism using the exponential mechanism, thus improving the utility of DPSGD by reducing the number of parameters. It provides the privacy guarantee of the proposed algorithm and shows experimentally that the proposed algorithm outperforms DPSGD across datasets and privacy parameters.

The proposed algorithm seems quite interesting. Though it is more of a simple combination of the non-private lottery ticket mechanism and the exponential mechanism, improving utility for DPSGD is a very important topic in differentially private machine learning. The experimental results seem pretty strong. 

My only concern is on the aspect of privacy, specially Lemma 1. I think if you’re only using the fact that A and C are in [0, 1], then A*(1-nu*C) can change by 1 if you go from (A=0, C=0) to (A=1, C=0). In the last step of equation (5), you replaced A-A’ by 1, which I think needs to be double-checked since there is the absolute value outside (and I guess the equality should  be <=). 
If the calculation is correct, I’m still a bit concerned that the sensitivity is a bit too high compared to the signal. A and C are in [0, 1], and it seems like the sensitivity may not be much smaller than 1, which means the exponential mechanism can be pretty random. To that end, I think you may consider experimentally comparing with DPSGD with a randomly selected ticket, or a ticket with a moderate number of parameters kept.


----- Post-rebuttal response -----
I still don't see why the sensitivity is |1-\nu|. (Doesn't that mean sensitivity is 0 when \nu=1?) If we have (A=1, C=0) and (A'=0, C'=0), we have S(A,C)-S(A',C')=1-0=1; if we have (A=1, C=0) and (A'=1, C'=1), we have S(A,C)-S(A',C')=1-(1-\nu)=\nu. Yet for \nu<1, |1-\nu|<1 and for \nu>1, |\nu-1|<\nu. I believe the sensitivity should be something like max(\nu, 1). You may want to further check that. And I still think this is because the last step in (5) is not correct. Since you have absolute sign, you can't do |A-A'-X| \leq ||A-A'|-X|.

I'm also confused by the range of \nu I should think of. 
If \nu <= 1, then in the example you give (A = 0.8, C=0.9,0.7,0.4,0.1, eps=0.1), I think the probability distribution used by exponential mechanism is not much higher for 0.9 than 0.1 (I think it's roughly 0.22 vs. 0.29?) with sensitivity |1-\nu|.
If \nu > 1, then I don't quite understand the score function S(A,C) = A*(1-\nu*C), since for C > 1/\nu, (1-\nu*C) is negative and S would thus penalize higher A. The higher \nu is, the wider the range of C that S will penalize. I can sort of understand this as setting a threshold such that any C above that threshold is just considered useless, but I still think it's a bit unreasonable to penalize higher accuracy, even for very complex model. You may want to explain more on that end.

Thanks for the experiments! They're very useful in supporting your proposed algorithm.

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: The existing differentially private training mechanism of deep neural networks includes a step that applies L2 normalization to gradient vectors. The authors argued that such norm clipping could lead to a small norm model parameter at the end, and the noise can thus overwhelm the accumulated gradient, leading to a substantial loss in terms of utility. To mitigate such utility loss, the authors proposed to use the lottery ticket mechanism to train a smaller network with similar utility and design an end-to-end differentially private mechanism for the whole process, including the selection of sub-network and the re-training of the selected sub-network. The general idea is quite interesting, but I have the following concerns.

-   From Algorithm 1 of Abadi et al. 2016, one could see that the norm of per instance gradient is at least C, and the added noise has standard deviation of \sigma C. Furthermore, since the final gradient step is an accumulation of all the per instance gradient in the mini-batch, this means that the scale of the final gradient is roughly $B\cdot C$, where $B$ is the batch size. Note that since the noise is added to the accumulation gradient, so the scale of the noise should be roughly 1/B of the accumulated gradient. It seems to me that in this case the injected noise shouldn't overwhelm the gradient vector. Could the authors have a comment on this? 

-   The overall algorithm can be understood as a simple composition of the Exponential Mechanism algorithm and the DPSGD algorithm. Both of them satisfy differential privacy, so by a simple composition theorem argument the whole process also satisfies DP. This all makes sense, but the novelty is quite limited. The authors claim that the proposed mechanism is 
"different from DPSGD's naive implementation". This is not true, since at the end the original DPSGD algorithm is still used, just on a subnetwork. 

-   If the goal is to train a model with fewer parameters and comparable utility, why not simply starting from a small model with DPSGD and then use the large model as a teaching model? This simple strategy naturally gives DP guarantee without worrying about the LTH, hence you can also get same privacy guarantee with less injected noise.

-   The experimental results basically confirm the expectation that with less injected noise, the model achieves better utility as compared with the DPSGD applied on the original large model.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper is a mash-up of recent work on differentially private stochastic gradient descent (DPSGD) and the lottery ticket hypothesis. Differential privacy is a paradigm for ensuring that statistical models learned from a large dataset do not disclose any particulars of individual elements of that dataset. DPSGD is a technique that applies differential privacy ideas to models trained with stochastic gradient descent, where privacy is guaranteed by clipping and adding noise to gradients. On the other hand, the lottery ticket hypothesis is a method for finding sparse sub-networks contained in larger dense neural network models that are at least as accurate as the underlying dense model. The authors propose and demonstrate that by combining DPSGD with the lottery ticket hypothesis that they can train end-to-end differentially private models that outperform the DPSGD technique.

I am up in the air about whether or not to accept this paper. I have trouble assessing the originality and significance of this work, the former since it seems to be a simple combination of two recent ideas, and the latter because I don't really have a context for how important the development of differentially-private optimization strategies are. I also didn't really find the experimental results to be that extensive, but I don't have a real sense of what state of the art is for differential privacy. Perhaps some of these issues could be mitigated by some additional exposition? I think one of my problems is that most of the paper is written to show that this new technique is superior to DPSGD, but I don't really have a good sense if either of them are sufficient as a practical solution of this problem.

Some additional questions I had are as follows:

1) One of the reasons given for combining the lottery ticket hypothesis with DPSGD is that DPSGD scales poorly as models get larger due to clipping by the norm of the gradient. Could you not compensate for this by scaling the norm by the number of parameters, or does that mess up the differential-privacy calculation?

2) I don't understand how the winning ticket selection portion is differentially privacy. I understand that they use the exponential mechanism, but I would have assumed that the dataset needs to be varied in addition to the model. Is there an intuitive explanation for how privacy is achieved essentially just by varying the initialization and not actually adding noise to the data?

3) Are there any datasets or methods where the effectiveness of the differential privacy technique could be directly assessed? For example, is there a way of testing whether the model is memorizing specific data elements, and then further showing that these differential privacy techniques mitigate this? This would be a nice check to have in addition to the plots of accuracy vs. privacy budget.
review_title: Official Blind Review #1

Meta-review: This paper provides an approach to improve the differentially private SGD method by leveraging a differentially private version of the lottery mechanism, which reduces the number of parameters in the gradient update (and the dimension of the noise vectors). While this combination appears to be interesting, there is a non-trivial technical issue raised by Reviewer 3 on the sensitivity analysis in the paper. (R3 brought up this issue even after the rebuttal.) This issue needs to be resolved or clarified for the paper to be published.
Decision: Reject