We propose the differentially private lottery ticket mechanism (DPLTM). An end-to-end differentially private training paradigm based on the lottery ticket hypothesis. Using "high-quality winners", selected via our custom score function, DPLTM significantly outperforms state-of-the-art. We show that DPLTM converges faster, allowing for early stopping with reduced privacy budget consumption. We further show that the tickets from DPLTM are transferable across datasets, domains, and architectures. Our extensive evaluation on several public datasets provides evidence to our claims.
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.