Training Differentially Private Neural Networks with Lottery Tickets

Abstract

We propose the differentially private lottery ticket hypothesis (DPLTH). An end-to-end differentially private training paradigm based on the lottery ticket hypothesis, designed specifically to improve the privacy-utility trade-off in differentially private neural networks. DPLTH, using high-quality winners privately selected via our custom score function outperforms current methods by a margin greater than 20%. We further show that DPLTH converges faster, allowing for early stopping with reduced privacy budget consumption and that a single publicly available dataset for ticket generation is enough for enhancing the utility on multiple datasets of varying properties and from varying domains. Our extensive evaluation on six public datasets provides evidence to our claims.

Appendix

Theorem 1

Phase 2 (Selecting a winning ticket) is ($\epsilon _1$) - differentially private.

Proof

We consider the scenario where the EM outputs some element $r \in \mathcal {R}$ on two neighbouring datasets, $X,X'$.

$$\begin{aligned} \dfrac{Pr[\mathcal {M}(X,u,\mathcal {R}) = r]}{Pr[\mathcal {M}(X',u,\mathcal {R}) = r]} = \dfrac{\bigg ( \dfrac{\exp (\dfrac{\epsilon _1 u (X,r)}{2 \varDelta u})}{\sum _{r' \in \mathcal {R}} \exp (\dfrac{\epsilon _1 u (X,r')}{2 \varDelta u})} \bigg )}{\bigg ( \dfrac{\exp (\dfrac{\epsilon _1 u (X',r)}{2 \varDelta u})}{\sum _{r' \in \mathcal {R}} \exp (\dfrac{\epsilon _1 u (X',r')}{2 \varDelta u})} \bigg )} \end{aligned}$$

(6)

$$\begin{aligned} = \bigg ( \dfrac{\exp (\dfrac{\epsilon _1 u (X,r)}{2 \varDelta u})}{\exp (\dfrac{\epsilon _1 u (X',r)}{2 \varDelta u})} \bigg ) . \bigg ( \dfrac{\sum _{r' \in \mathcal {R}} \exp (\dfrac{\epsilon _1 u (X,r')}{2 \varDelta u})}{\sum _{r' \in \mathcal {R}} \exp (\dfrac{\epsilon _1 u (X',r')}{2 \varDelta u})} \bigg ) \end{aligned}$$

(7)

$$\begin{aligned} = \exp \bigg ( \dfrac{\epsilon _1 (u(X,r') - u(X',r'))}{2 \varDelta u} \bigg ) . \bigg ( \dfrac{\sum _{r' \in \mathcal {R}} \exp (\dfrac{\epsilon _1 u (X,r')}{2 \varDelta u})}{\sum _{r' \in \mathcal {R}} \exp (\dfrac{\epsilon _1 u (X',r')}{2 \varDelta u})} \bigg ) \end{aligned}$$

(8)

$$\begin{aligned} \le \exp (\dfrac{\epsilon _1}{2}) . \exp (\dfrac{\epsilon _1}{2}) . \bigg ( \dfrac{\sum _{r' \in \mathcal {R}} \exp (\dfrac{\epsilon _1 u (X,r')}{2 \varDelta u})}{\sum _{r' \in \mathcal {R}} \exp (\dfrac{\epsilon _1 u (X',r')}{2 \varDelta u})} \bigg ) \end{aligned}$$

(9)

$$\begin{aligned} \le \exp (\epsilon _1) \end{aligned}$$

(10)

   $\square$