Differential Privacy in Adversarial Learning with Provable Robustness
Authors: NhatHai Phan
My T. Thai
Ruoming Jin
Han Hu
Dejing Dou
Venue:  (2020)
Keywords: differential privacy
adversarial learning
robustness bound
adversarial example

Abstract: In this paper, we aim to develop a novel mechanism to preserve differential privacy (DP) in adversarial learning for deep neural networks, with provable robustness to adversarial examples. We leverage the sequential composition theory in DP, to establish a new connection between DP preservation and provable robustness. To address the trade-off among model utility, privacy loss, and robustness, we design an original, differentially private, adversarial objective function, based on the post-processing property in DP, to tighten the sensitivity of our model. An end-to-end theoretical analysis and thorough evaluations show that our mechanism notably improves the robustness of DP deep neural networks.

Under review as a conference paper at ICLR 2020
DIFFERENTIAL PRIVACY IN ADVERSARIAL LEARNING WITH PROVABLE ROBUSTNESS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we aim to develop novel mechanism to preserve differential privacy (DP) in adversarial learning for deep neural networks, with provable robustness adversarial examples. We leverage the sequential composition theory in DP, establish a new connection between DP preservation and provable robustness. To address the trade-off among model utility. privacy loss, and robustness, we design an original, differentially private, ad adversarial objective function, based on the post- processing property DP, to tighten the sensitivity of our model. An end-to-end theoretical analysis and thorough evaluations show that our mechanism notably improves the robustness of DP deep neural networks.
INTRODUCTION
The pervasiveness of machine learning exposes new vulnerabilities in software systems, in which deployed machine learning models can be used (a) to reveal sensitive information in private training data (Fredrikson al. 2015), and/or (b) make the models misclassify, such as adversarial exam- ples (Carlini & Wagner (017). Efforts to prevent such attacks typically seek one of three solutions:
(1) Models which preserve differential privacy (DP) (Dwork et al.] (2006). rigorous formulation of privacy in probabilistic terms; (2) Adversarial training algorithms, which augment training data to consist of benign examples and adversarial examples crafted during the training process, thereby empirically increasing the classification accuracy given adversarial examples (Kardan & Stanley) 2017 Matyasko & Chau 2017); and (3) Provable robustness, in which the model classífication given adversarial examples is theoretically guaranteed to be consistent, i.e., small perturbation in the input does not change the predicted label (Cisse et al. 2017 Kolter & Wong 2017).
On the one hand, private models, trained with existing preeaccypr mechanisms (Abadi et al.) 2016 Shokri Shmatikov] 2015 Phan et al.) 2016 2017b/a Yu et al., 2019: Lee & Kifer 2018). unshielded under adversarial examples. On the other hand, robust models, trained with adversar- ial learning algorithms (with or without provable robustness to adversarial examples), do not offer privacy protections to the training data. That one-sided approach poses serious risks to machine learning-basse based systems; since adversaries can attack deployed model by using both privacy infer- ence attacks and adversarial examples. To be safe, model must be i) private protect the training data, and ii) robust to adversarial examples. Unfortunately, there has not yet been research on how to develop such a model, which thus remains a largely open challenge.
Simply combining existing DP- DP-preserving mechanisms and provable robustness conditions (Cisse) al. 2017: Kolter & Wong, 2017: Raghunathan al. 2018) cannot solve the problem, for many reasons.
(a) Existing sensitivity bounds (Phan et al. [216)] 2017b a) and designs (Yu et al. 2019
Lee Kifer 2018) have not been developed to protect the training data in adversarial training. It
is obvious that using adversarial examples crafted from the private training data to train our models introduces previously unknown privacy risk, disclosing the participation of the benign examples (Song et al.] 2019). (b) There is an unrevealed interplay among DP preservation, adversarial learn- ing, and robustness bounds. (c) Existing algorithms cannot be readily applied to address the trade-off among model utility, privacy loss, and robustness. Therefore, theoretically bounding the robustness of a model (which both protects the privacy and is robust against adversarial examples) is nontrivial.
Our Contributions. Motivated by this open problem, propose develop novel differentially private adversarial learning (DPAL) mechanism to: 1) preserve DP of the training data, 2) be prov- ably and practically robust adversarial examples, and 3) retain high model utility. In our mech-

---

Under review as a conference paper at ICLR 2020
anism, privacy- preeeevii noise is injected into inputs and hidden layers achieve DP in learning private model parameters (Theorem I. Then, we incorporate ensemble adversarial learning into our mechanism to improve the decision boundary under DP protections. To do this, introduce a concept of DP adversarial examples crafted using benign examples in the private training data under DP guarantees (Eq. 19). To address the trade-off between model utility and privacy loss, we propose a new DP adversarial objective function to tighten the model's global sensitivity (Theorem 3) thus, we significantly reduce the amount of noise injected into our function, compared with ex- isting works (Phan et al., 2016 2017b In addition, ensemble DP adversarial examples with a dynamic perturbation size Ma are introduced into the training process further improve the robust- ness of our mechanism under different attack algorithms. An end-to-end privacy analysis shows that, by slitting the private training data into disjoint and fixed batches across epochs, the privacy budget in our DPAL is not accumulated across training steps (Theorem 4
After preserving DP in learning model parameters, we establish a solid connection among privacy preservation, adversarial learning, and provable robustness. Noise injected into different layers is considered as a sequence of randomizing mechanisms, providing different levels of robustness. By leveraging the sequential composition theory in DP (Dwork& & Roth 2014), we derive novel gener- alized robustness bound, which essentially is a composition of these levels of robustness (Theorem[5) and Proposition I. To our knowledge, our mechanism establishes the first connection between DP preservation and provable robustness against adversarial examples in adversarial learning. Rigor- ous experiments conducted on MNIST and CIFAR-10 datasets (Lecun et al. 1998, Krizhevsky & Hinton 2009) show that our mechanism notably enhances the robustness of DP deep neural net- works, compared with existing mechanisms.
2 BACKGROUND
In this section, we revisit adversarial learning, DP, and our problem definition. Let D be a database that contains N tuples, each of which contains data x E [-1, 1] and a ground-truth label y E Zk, with K possible categorical outcomes. Each y is one-hot vector of K categories y (vi..... WK A single true class label ya: E y given x E D is assigned to only one of the K categories. On input x and parameters 0, model outputs class scores Rd + R that maps d-dimensional inputs x to a vector of scores f(x)- = (f(
s.t. Vk E [1, fa(x) E [0, 1] and Ek (z) = 1. The class with the highest score value is selected as the predicted label for the data tuple, denoted as y(x) = m (x). A loss function L(f(x), y) presents the penalty for mismatching between the predicted values f(x) and original values y. For the sake of clarity, the notations and terminologies frequently used in this paper are summarized in Table [ (Appendix A). Let us briefly revisit DP orrresseginng techniques in deep learning, starting with the definition of DP.
Definition (e, (DD (Dwork el al. 2006 A randomized algorithm A fulfills (e. 8)-DP, for any two databases D and D' differing most tuple, and for all O C (A)ge(A), we have:
Pr(A(D) O s e Pr(A(D') + +
A smaller enforces a stronger privacy guarantee.
Here, controls the amount by which the distributions induced by D and D' may differ, 8 is a broken probability. DP also applies to general metrics p(D, D') S 1, where p can be 1p-norms (Chatzikooolkiis et al. 2013). -P-preserving algorithms in deep learning can be categorized into two lines: 1) introducing noise into gradients of parameters (Abadi et al. 2016 Shokri & Shmatikov]
2015 Abadi et al. 2017 Yu et al. a [2019] Lee & Kifer 2018 Phan et al. 2019), 2) injecting noise into objective functions (Phan et al. 2016; 2017b a), and 3) injecting noise into labels (Papernot et al.) will show that mechanism achieves better sensitivity bounds
2018). In Lemmas 2 and
compared with existing works (Phan et al. 2016 a).
Adversarial Learning. For some target model and inputs (r, Uz), the adversary's goal is to find an adversarial example ad = x + a, where a is the perturbation introduced by the attacker, such that: (1) gd and are close, and (2) the model misclassifies 2. i.e., yf(2="v) ) + y(x). In this paper, we consider well-known (1, -norm -norm bounded attacks (Goodfellow et al. 2014b). Let (,(
{ar E Idd ||ж| S n²) be the norm ball of radius μ.. One of the goals in adversarial learning is to minimize the risk over adversarial examples: H* = arg ming -( max]]o]]ss L(f(x +
o, 0), )z)] where an attack is used approximate solutions to the inner maximization problem,
2

---

Under review as a conference paper at ICLR 2020
and the outer minimization problem corresponds to training the model f with parameters 0 over these adversarial examples znd = I + a. There are two basic adversarial example attacks. The first one is single-step algorithm, in which only single gradient computation is required. For instance, FGSM algorithm (Goodfellow et al., 2014b) finds adversarial examples by solving the inner maximization max Ial, [_ which multiple gradients are computed and updated. For instance, in (Kurakin et al., 2016a). FGSM applied multiple times with Tp small steps, each of which has size of p/TT.
az f0), Mar) The second one is an iterative algorithm, in
To improve the robustness of models, prior work focused on two directions: 1) Producing cor- rect predictions on adversarial examples, while not compromising the accuracy on legitimate inputs Papernot et al. 2016b a Gu
(Kardan & Stanley [0177] Matyasko & Chau, [2017] Waan et al. [2016]
& Rigazio 2014| Papernot Grosse et al. |017] Xu et al.
[ Hosseini et al.
2017:
and 2) Detecting adversarial
examples (Metzen et al. [
2017 Abbasi & Gagné, 2017; Gao
2017). Among existing solutions, adversarial training appears to hold the greatest promise for learning robust models (Tramèr et al. 2017). One of the well-known algorithms was proposed in
al.
(Kurakin et al. 2016b). At every training step, new adversarial examples are generated and injected
into batches containing both benign and adversarial examples. The typical adversarial learning in (Kurakin et al. 2016b) is presented in Alg. 2 (Appendix B).
DP and Provable Robustness. Recently some algorithms (Cisse et al. 2017 Kolter & Wong 2017 Raghunathan et al. 2018 Cohen et al., 2019: Li et al. 2018) have been proposed to derive provable robustness, in which each prediction guaranteed to be consistent under the perturbation o, if a robustness condition is held. Given benign example x, we focus on achieving a robustness condition to attacks of 1p (u) -norm, follows:
Va E 1p(n): fx(x + a > max [a + a)
where k = v(x),, indicating that small perturbation a in the input does not change the predicted label v(z). To achieve the robustness condition in Eq. 2 Lecuyer et al. (Lecuyer et al. 2018 introduce an algorithm, called PixeIDP. By considering
input x (e.g.. images) as databases in DP parlance, and individual features (e.g., pixels) as tuples, PixeIDP shows that randomizing the scoring function f(x to enforce DP small number of pixels in image guarantees robustness of predictions against adversarial examples. To randomize fzz). random noise o, is injected into either input x or arbitrary hidden layer, resulting in the following (er, PixeelDD condition:
Lemma (e,, Pixe-PX (Lecuyer et al. 2018). Given a randomized scoring function f(x) sat- isfying (Er, dii--ix w.r.t. a L. lp-norm metric, have:
Vk, Vo E (1(1) Bff(x) S "'BBaa( + ai) ö, where (x) the expected value of f& (z), G, is a predefined budget, 8, a broken probability.
At the prediction time, certified robustness check is implemented for each prediction. A general- ized robustness condition is proposed as follows:
Eoff(()) e2tr max m.. (z) + + 6 (ast
where En and E.d are the lower and upper bounds of the expected value E.. derived from the Monte Carlo estimation with an cy-oofiidence, given n is the number of invocations of fzz with independent draws in the noise σ,.. Passing the check for given input guarantees that no perturbation up to (1) (1)-norm can change the model's 's prediction. PixeIDP does not preserve DP in learning private parameters 0 to protect the training data. That is different from goal.
DPAL WITH PROVABLE ROBUSTNESS
Our new DPAL mechanism is presented in Alg. [ Our network (Figure D can be represented as: f(x) = g(a(x, 0,),, where a(I, 01) is feature representation learning model with x as an input, and g will take the output of a(x:, 01) and return the class scores fxx) At a high level, DPAL has three key components: (1) DP a(z,, 01), which is to preserve DP in learning the feature representation model a(x, 0)); (2) DP Adversarial Learning, which focuses on preserving DP in adversarial learning, given DP axx 0:); and (3) Provable Robustness and Verified Inferring, which are to compute robustness bounds given an input at the inference time. In particular, given a deep neural network f with model parameters 0 (Lines 2-3), the network is trained over T training steps. In each step, a batch of m perturbed training examples and a batch of m DP adversarial examples derived from D are used to train our network (Lines 4-1)).
3

---

Under review as a conference paper at ICLR 2020
Algorithm DPAL Mechanism
Input: Database D. loss function L. parameters batch size m. learning et. privacy budgets: and <2, robustness parameters: cy, A,, and A", adversarial attack size Mes the number of invocations n, ensemble attacks A, parameters V and &, and size [h/] of h
1: Draw Noise X1 + Lapp( d ]]d + [Lap( dR )1 x3 + LLap( Ac2)] )bzl
2: Randomly Initialize = {01, 02). B (Bi..... BN/m] s.t. VB E B is a batch with the size mt,
Pin... B.y.,/.BB//.... = 0, and B1 U... BNy. = D. B (BI,.... Bu where [1, N/ml B,
{ir 4 x 21 xEB,
3: Construct a deep network f with hidden layers {hr + 2x2 h. }. where h, is the last hidden layer m
4: for É [2]]] do
Take a batch B. where (N(N)m), Assign B. <- B,
6: Ensemble DP Adversarial Examples:
7: Draw Random Perturbation Value E [0,
8: Take batch Bi+1 B, Assign Be +-
for do 10: Take the next batch B. C Bi+1 with the size m/[A|
11: VI, E B.: Craft 1nth by using attack algorithm A(] with Lx (ur), ; Bith + Bith Uzj
12: Descent: 01 4- 01 2t Vo, RTLI,"" (01): 02 +- 02 2e Vo I B.u (02) with the noise Xa
Output: (e1 ( f1/ + 61/7 + 62 22) parameters 0 = {01, 02), robust model with an budget
13: Verified Inferring: (an input attack size pta))
14: Compute robustness size (I (p) mam in Eq. of
15: + m)ms Ho then
16: Return is Robust(x)) = True, label k (I6 + pp)a
17: else
18: Return is (obust((x) False, label k. (n + p)mux
3.1 DP FEATURE REPRESENTATION LEARNING
Our idea is to use auto-encoder to simultaneously learn DP parameters 0 and ensure that the output of a(x,0) is DP. The reasons we choose an auto-encoder are: (1) It is easier to train, given its small size; and (2) It be reused for different predictive models. A typical data reconstruction function (cross-entropyy, given batch B, at the training step t of the input I;, as follows:
nh estimation
Input
averaag scores
Noise
Layer 1
Layer
Output DP loss
B1
Noise
E
6.2
By/m
Mr
Badv
0.5
Ma
Bf(x)
a(.)
DP DNN
g())
Figure 1: An instance of DPAL.
RB. (01)
Σ Σ Dis log(1 + -1gh1 + (1 - log(1 + + els)
(5)
2;CB,
where the transformation of x; is h4 of xt, the hidden layer h of a(x, 01) given the batch B, is denoted as h1s, {8T x; Ia,E,,, and T. = 02 h; is the reconstruction of r;.
To preserve -D in learning 81 where 61 polynomial approximation of RB, (01) by applying Taylor Expansion (Arfken 1985). denoted as (01). Then, Functional Mechanism (Zhang et al. 2012) is employed to inject noise into
privacy budget, we first derive the 1st-order
efficients of the approximated function Rr (01) = Em.e,, Ei where F1)(2) = zij log(1 + + (2)(2) = (1- log(1 + e*), we have that: RB. (01) = ErEEB, Ei log 2 01, I.1)) In RR, (0,), parameters 01, derived from the function op-
F/r (0) (O1ghis""
timization need to be -DP. To achieve that, Laplace noise 1 Lapp AR is injected into coefficients
(1 - kii)),, his where AR is the sensitivity of R, (0)), as follows:
(0) = Σ
Σ 8
0is
kis)he 4 + Lap AR )
1 m
Σ F.EB.
T.J.J
(6)

---

Under review as a conference paper at ICLR 2020
To ensure that the computation of Hn does not access the original data, we further inject Laplace noise Lap( As into z;. This can be done as preprocessing step for all the benign examples to construct a set of disjoint batches B of perturbed benign examples (Lines and 5). The
perturbed function now becomes:
RB, (81)
Σ
Σ 2 01yha) Z
where 2, =x m Lap( AR AR), = h, + Lap( AR ). and x; = 01
e1
Let us denote 3 as the number of neurons in h,, and hy is bounded in [-1, 1], the global sensitivity
Ag is follows:
Lemma The global sensitivity of R over any two neighboring batches, B, and Bi, as follows: AR S d(3 + 2).
All the proofs are in our Appendix. By setting DR = d(3 + 2), we show that the output of a(-), which is the perturbed affine transformation 1 = (0) पe + 2 Lap( Ar )),E is (e1/?)- DP, given 7 m mi0,1li, and |00 |1,1 is the maximum 1-norm of 0, columns (Operator norm 2dx
2018). This is important to tighten the privacy budget consumption in computing the remaining hidden layers ((( 01). fact, without using additional information from the original data, the computation of (( 01), 02) is also (c1 (P (the post pess-processing property of DP). Similarly, we observe that the perturbation of a batch B: = {x; + + J..EB. achieves (c1 h//))))))))) -DP, with 7x Note that do not use the post-processing property of DP to estimate the DP guarantee of h T., based upon the DP guarantee of B,, since c < c1/%x in practice. As a result, the (c1/7)- DP h B, provides more rigorous DP protection to the computation of g(-) and to the output layer.
Lemma The computation of the affine transformation h1s, is (e1/7)-DP and the computation of the batch B, as the input layer is (e1/7x)-DR
The following Theorem shows that optimizing RB, (01) is (E1/1x + D1D in learning 0, given an (E1/ (PP B, batch.
Theorem The optimization of RB, (01) preserves (E1/1x + DD in learning 01.
3.2 DP ADVERSARIAL LEARNING
To integrate adversarial learning, we first draft DP adversarial examples zith using perturbed benign examples Fj, with an ensemble of attack algorithms A and a random perturbation budget μ4 E (0, 1], each step t (Lines 6-11). This will significantly enhances the robustness of our models under different types of adversarial examples with an unknown adversarial attack size μ..
F. μ sign (f (),
with y(ī,) is the class prediction result of f(T,) to avoid label leaking of the benign examples 4; during the adversarial example crafting. Given a set DP adversarial examples Brdd training the auto-eneoder with B,St preserves (E1/7x+ DD.
Theorem The optimization of (0)) preserves (EI/7x DDD DP in learning O,.
The proof of Theorem 2 is in Appendix H, Result 4. It can be extended to iterative attacks as adv Zj 25
adv 4..
P Tp
sign (egn (( 0). ((())))))))
where U(T)dV) is the prediction result of f( 0). E [0,T, -
Second, we propose a novel DP adversarial objective function Ls, (02). in which the loss function L. for benign examples is combined with additional loss function T for DP adversarial examples,
5

---

Under review as a conference paper at ICLR 2020
to optimize the parameters 82. The objective function LB, (82) is defined as follows:
B.u (02) m(1 + E)
1 Σ 2,EB,
C(I(T,; Mb) + EB,
Σ T(((z,), (0te,,,,)),000 02).
(10)
where & is a labels yz, and Vu, of examples 2; and Tj. Note that 2ith and x share the same label yz,,
For the sake of clarity, in Eq. TO, we denote ys and yj as the true class
Now are ready to preserve DP in objective functions [(f 02), y:) and T (f (2))),.,8))330)0)) ys) in order to achieve DP in learning 02. Since the objective functions use the true class labels yi and yj. need to protect the labels the output layer. Let us first present our approach to preserve DP in the objective function L for benign examples. Given h computed from the I, through the network with Wx the parameter at the last hidden layer h, Cross-entropy function is approximated as
CB, (02) 2
ΣΣ
1 h -h W Wii) h W (h W Wnn)2p 2 LIB. (02) - (02)
1
1=1
where f f (02) E Whn 2 W "
and LR (02) =
Ek= En (hmilikk W Based on the post-processing property of DP (work & Roth 2014
LBB, - _(has),,n, is (e1/7)-DP, since the computation of b1s, is (e1/7)-DP (Lemma 30. As result, the optimization of the functtin CIB, (02) does not disclose any information from the training data, and Pr(C,E, (02)) Pr(h,z,)
Pe (02] Pr(h, S < given neighboring batches B, and B, Thus, we only need to preserve Dp the function CRD, (02), which accesses the ground-trus truth label yok- Given coefficients hnilik the sensitivity Ac2 of L (02) computed as:
Lemma 4 Let B, and B¹ be neighboring batches of benign examples, we have the following in- equality: Ac2 S 2/ where [ba] is the number of hidden neurons in ha-
The sensitivity of our objective function is notably smaller than the state-of-the-art bound (Phan al. 2017a), which crucial to improve our model utility. The perturbed functions are as follows:
LB (02) (IB((02) LyB, (02), where LyB, (02)
ΣEO (hriglik + - Lapp
1
Ac2 )) Wa*
m
E2
Theorem Algorithm preserves (e1/1 + c2) in the optimization of (02)..
We apply the same technique preserve (61/7 + E2)-DP in the optimization of the function T [s( 02). over the DP adversarial examples zyddy E Beet As the perturbed functions L and T are always optimized given two disjoint batches B, and B. the privacy budget used to preserve DP in the adversarial objective function Ln, (02) is (e1/7 + e2), following the parallel
composition property of DP (Dwork & Roth 2014). The total budget learn private parameters Ø 00 02) arg min
(R
B.UB (01)
T. (02)) is (E1 +//7 62) (Line 12).
We have shown that our mechanism achieves DP at the batch level B, B,U., given specific training step l. By constructing disjoint and fixed batches from the training data D, we leverage both parallel composition and post-processing properties of DP (Dwork& & Roth 2014) to extend the result to
(a1 +G1/x + (1/7 DDP DPPi in learning 0 = (01. P2) on D across T training steps. There are three key properties in our approach: (1) It only reads perturbed inputs B, and perturbed coefficients hj, which are DP across T training steps; (2) Given N/m disjoint batches each epoch, for any example E. F is included in one and only one batch, denoted B3 E B. As a result, the DP guarantee in Ba; since the optimization using any other batches
to in D equivalent to the DP guarantee does not affect the DP guarantee of T; and (3) All the batches are fixed across T training steps to prevent additional privacy leakage caused by generating new and overlapping batches (which are considered overlapping datasets in the parlance of DP) in the typical training approach.
Theorem Algorithm 1 achieves (E1 + t1/%% + f1/7 + DDP parameters ø = =0,,80 F2} on the private training data D across T training steps.

---

Under review as a conference paper at ICLR 2020
3.3
PROVABLE ROBUSTNESS
Now, we establish the correlation between our mechanism and provable robustness. In the inference time, to derive the provable robustness condition against adversarial examples ar, i.e. Va E (,(1), PixelDP mechanism randomizes the scoring function [(x) by injecting robustness noise into
A or h = h + Lap( - where A and A +,
either input x or a hidden layer, i.e., x' = x + Lap( are the sensitivities of x and h, measuring how much I and h can be changed given the perturbation E (p(1 in the input x. Monte Carlo estimation of the expected values [x()), Eu and (z) are used to derive the robustness condition in Eq.
On the other hand, in our mechanism, the privacy noise op includes Laplace noise injected into both imput x, i.c., 1 Lap( AR), and its affine transformation h, i.e., 2 Lapí AR). Note that the perturbation of 2B, (0z) is equivalent to 2E, (02) = Ex= Ex, (hrrths + Lap( Lap( A ( This helps us to avoid injecting the noise directly into the coefficients hri The correlation between our DP preservation and provable robustness lies in the correlation between the privacy noise op and the robustness noise o,.
e
ez
We can derive a robustness bound by projecting the privucy noise op on the scale of the ro- bustness noise Gr. Given the input x, let K. = / / in our mechanism we have that: T T Lap(kA//er)) By applying a group privacy size x (Dwork & Roth, 2014 Lecuyer al. 2018), the scoring function f(x) satisfies -ixeeDD given a E (p(k), or equivalently RE, PPxeeDD given a E (p(1), 8, = O. By applying Lemma]] [ we have
Ak,Va Va E (1())) (T)(()) S e c'"Bft(r+aa)
or Vk, Va E (,(1) : (x)()) S (nc, Ef((++a)
(11)
With that, we can achieve a robustness condition against (1(x:) attacks, as follows: (xff(x) > 2cr max (()))(())) stigh
(12)
with the probability 2 7/.-Confiddnce, derived from the Monte Carlo estimation of Bf(x).
Our mechanism also perturbs / (Eq. 7 Given 9 me1 / we further have h = l1 + Lap( P Therefore, the scoring function f(x) also satisfies r,-PixeIDP given the perturbation E (g)). In addition to the robustness to the (n:) attacks, we achieve an additional robustness bound in Eq. 12 against ()())) attacks. Similar to PixeIDP, these robustness conditions can be achieved as randomization processes in the inference time. They can be considered as two independent and provable defensive mechanisms applied against two lp nn-norm attacks, i.e., (x)) and Lp(p).
One challenging question here is: "What the general robustness bound, given K and 4?" Intu- itively, model is robust to attacks with E 1p(K + ip). We leverage the theory of sequential composition in DP (Dwork & Roth 2014) to theoretically answer this question. Given S indepen- dent mechanisms MM,... Ms. whose privacy guarantees are c1,..., Cs-DP with (1). Each mechanism M,. which takes the input æ and outputs the value of f(x) with the Laplace noise only injected to randomize the layer (i.e., no randomization at any other layers), denoted f(xx,, is defined as: Vs E S), of any composition scoring function f(M M,lz)) bounded in [0, 1), defined as follows:
Rd + (x) E RR We aim to derive generalized robustness
$ II M.f(x) + M.M....,MMpp. Rd II (x) E
(13)
Our setting follows the sequential composition in DP Dwork & Roth 2014). Thus, we can prove
that the expected value Ef(M,,..., Ms|zz) is insensitive to small perturbations a E ((1) in
Lemma 5 and we derive our composition of robustness in Theorem 5 as follows:
Lemma Given independent mechanisms Mi...., Ms. which are Ei....,Es' Es- wart a by n--rorm metric, then the expected output value of any sequential function of them, i.e, (JMr...,MMsla. E [0, 1), meets the following property:
Yo (1)) E.M.M,........... Ms|ax) <e WB
7

---

Under review as a conference paper at ICLR 2020
Theorem 5 (Composition of Robusiness) Given S independent mechanisms MI....,Ms, Given any sequential function f(M Ms|z), and let Esg and Eub lower and up- per bounds with an n-confidence, for the Monte Carlo estimation of EJ(M,,..., Msla) 1 En (MMI...,MMsI)),, En f*(x))) For any input x, E (a Ms(x) > 2 (a) max Maa.i(M siighh
(14)
then the predicted label k = arg maxg [. ..... Msl.)) robust to adversarial exam- ples x + a, da E 12(1), with probability 2 T, by satisfying: Ejs(M + aa) > max
+ ar), which is the targeted robusiness condition in Eq. 2
It is worth noting that there is no 17, 77-cooffidence for each mechanism s, since we do not estimate the expected value Eff independently. To apply the composition of robustness our mechanism, the noise injections into the input and its affine transformation / can be considered as two mechanisms M2 and M,, sequentially applied as ( (x:). When Mr (x) is applied by invoking ((x) with independent draws in the noise X2. the noise X1 injected into æ is fixed; and vice-versa. By applying group privacy (Dwork & Roth 2014) with sizes & and p. the scoring functions f"(x)) and
(()),, given Mr and Mr, are DP and DDP given a (1). With Theorem 5 generalized bound as follows:
we have
Proposition 1 (DPAL Robustness). For any input I, if 3k E K Ea,.e(M,,
e2cr max Bno Mglz) (i.e., Eq. 14). then the predicted label &. of our function (p K + 5) with the probability n. by satisfying
f(Mn; Mglax is robust to perturbations
Ya lp(x+ + () (f, Mela + a) maxBf Mala+ aa)
3.4 TRAINING AND VERIFIED INFERRING
Our model is trained similarly to training typical deep neural networks. Parameters 01 and 02 are independently updated by applying gradient descent (Line 12). Regarding the inference time, we implement verified inference procedure as a post-processing step (Lines 13-18). Our verified inference returns a robustness size guarantee for each example x, which is the maximal value of + ş.. for which the robustness condition in Proposition holds. Maximizing k + & is equivalent to maximizing the robustness epsilon ey, which is the only parameter controlling the size of + yi; since, all the other peper-parameters. i.e., AR. m, 61, 62, 01, 02, A,, and A are fixed given well-trained model fz))
(IS + p)max = max
A
A s.t. Batsk(0) > 2er max Eunhs())))) (i.e., Eq. 14 tiikt
(15)
mc1
The prediction on an example x is robust to attacks up to (K + p)maa- The failure probability 1-n be made arbitrarily small by increasing the number of invocations of f(x). with independent draws the noise. Similar to (Lecuyer et al. 2018), Hoeffding's inequality is applied to bound the approximation error in E (z) and to search for the robustness bound (K + +) We use the following sensitivity bounds A
B|1@21loo where ||0ı|lo is the maximum 1 -nnom of 01 rows, and A = jdd for 1x attacks. We also propose new way draw independent noise following the AR
distribution of X1 + m Lap((, e. /v/) for the input and 2x2 + 2 Lap(O, Ax /v6) for the transfor- mation h, where X1 and X2 are the fixed noise used to train the network, and vo is parameter to control the distribution shifts between training and inferring. This new Monte Carlo Estimation of Éx(x) works better without affecting the DP bounds and the robustness (Appendix L).
4 EXPERIMENTAL RESULTS
We have conducted an extensive experiment on the MNIST and CIFAR- 10 datasets. We consider the class of bounded adversaries to whether mechanism could retain high model utility, while providing strong DP guarantees and protections against adversarial examples.
Baseline Approaches. Our DPAL mechanism is evaluated in comparison with state-of of-the-art mechanisms in: (1) DP Dr-preseringg algorithms in deep learning, i..., DP-SGD (Abadi et al. 2016). AdLM (Phan et al.) 2017ab; in (2) Provable robustness, i.e., PixeIDP (Lecuyer al. 2018); and in
8

---

Under review as a conference paper at ICLR 2020
(3) DP prerserrii algorithms with provable robustness, i.c., SeD given heterogeneous noise (Phan et al. 2019). 9. and SecureSGD-AGM (Phan et al. 2019) given the Analytic Gaussian Mecha- nism (AGM) (Balle & Wang 2018). To preserve DP, DP- injects random noise into gradients of parameters, while A is a Functional Mechanism- approach. PixelDP is one of the state-of- the-art mechanisms providing provable robustness using DP bounds. SecureSGD is combination of PixelDP and DP-SGD with an advanced heterogeneous noise distribution; i.e. "more noise" is in- jected into "more vulnerable" latent features, improve the robustness. The baseline models share the same design in our experiment. Four white-bog attacks were used, including FGSM, I-FGSM, Momentum Iterative Method (MIM) (Dong et al., 2017), and MadryEtAr (aadr et al. 2018).
Model Configuration. It is important to note that x E [-1, in our setting, which is different from common setting, x E [0, 1j Thus, a given attack size tAi 0.3 in the setting of [0, 1] is equivalent to an attack size 2/4r = 0.6 in our setting. The reason for using I E [-1, 1] is to achieve better model utility, while retaining the same global sensitivities to preserve DP. compared with x E [0, 1] Our model configurations are in Appendix M and our approximation error bound analysis is presented in Appendix N. As in (Lecuyer et al. 2018), we apply two accuracy metries:
Σ Itestl
(sCorrect(
Σ 2i=1 isCorrect(ss) & is Riooust((r;) [tedd]
conventional acc
Li=l
&erttifee acc
Itest]
|tstt|
where [test] is the number of test cases, isCorrect(-) returns 1 if the model makes a correct predic- tion (else, returns 0), and is Robust(.)) returns 1 if the robustness size is larger than a given attack size Pa (else, returns 0). Our task of validation focuses shedding light into the interplay among model utility, privacy loss, and robustness bounds, by learning 1) the impact of the privacy budget er (Ei + f + E1/T + e2), and 2) the impact of attack sizes Pa. All statistical tests are 2-tail 1-tests. All experimental Figures are in Appendix O.
Results on the MNIST Dataset. Figure 2 iillssrates the conventional accuracy of each model as function of the privacy budget & on the MNIST dataset under Lo ((a))nnnn -norm attacks, with μa, = 0.2 (a pretty strong attack). It is clear that our DPAL outperforms AdI M,, DP-SGD, SecureSGD, and SecureSGI-AGMM in all cases, with < 1.32 - 4. On average, we register a 22.36% improvement over SeD (p- < 1.32e- - 4), a 46.84% improvement over SecureSGD-AGM (p < 1.83e - 6), a 56.21% % improvement over AdLM (p < 2.05e - 10), and a 77.26% improvement over DP-SGD (p < 5.20c- 14), given our DPAL mechanism. AdLM and DP-SGD achieve the worst conventional accuracies. There is no guarantee provided in AdLM and DP-SGD. Thus, the accuracy of the AdLM and DPSGD algorithms seem to show no effect against adversarial examples, when the privacy budget is varied. This is in contrast to our DPAL model, the SecureSGD model, and the SecureSGD- AGM model, whose accuracies are proportional to the privacy budget.
When the privacy budget 6, = 0.2 (a tight DP protection), there are significant drops, in terms of conventional accuracy, given the baseline approaches. By contrast, our DPAL mechanism only shows a small degradation in the conventional accuracy (6.89%, from 89.59% to 82.7%), compared with a 37% drop in SecureSGD (from 78.64% to 41.64%), and a 32.89% drop in SecureSGD- AGM (from 44.1% to 11.2%) on average, when the privacy budget 6 goes from 2.0 to 0.2. At e = 0.2, our DPAL mechanism achieves 82.7%, compared with 11.2% and 41.64% correspondingly for SecureSGD-AGM and SeCureSGD. This is important result, showing the ability offer tight DP protections under adversarial example attacks in our model, compared with existing algorithms.
Figure 4 presents the conventional accuracy of each model as function of the attack size μaa on the MNIST dataset, under a strong DP guarantee, = 0.2. It is clear that our DPAL mechanism outperforms the baseline approaches in all cases. On average, our DPAL model improves 44.91 % over SecureSGD (p < 7.43c- 31), a 61.13% over SecureSGD-AGM (p < 2.56e - 22), a 52.21 % over AdLM (p < 2.81e 23), and a 62.20% over SGD (p 2.57e 22). More importantly, our DPAL model is resistant to different adversarial example algorithms with different attack sizes. When Ha 2 0.2, AdIM, DP-SGD, SecureSGID, and SecureSGD-AGiN become defenseless. We further register significantly drops in terms of accuracy, when Pa is increased from 0.05 (a weak attack) to 0.6 (a strong attack), i.c., 19.87% on average given our DPAL, across all attacks, compared with 27.76% (AdLM), 29.79% (DP-SGD), 34.14% (SecrreGDD-AMM) and 17.07% (SecureSGD).
Figure 6 demonstrates the certified accuracy as a function of (4a- The privacy budget is set to 1.0, offering reasonable privacy protection. In PixeIDP, the construction attack bound e, is set to 0.1, which is a pretty reasonable defense. With (small perturbation) na < 0.2, PixelDP achieves better certified accuracies under all attacks; since PixelDP does not preserve DP to protect the training

---

Under review as a conference paper at ICLR 2020
data, compared with other models. Meanwhile, our DPAL model outperforms all the other models when Ma 2 0.3, indicating a stronger defense to more aggressive attacks. More importantly, our DPAL has consistent certified accuracy to different attacks given different attack sizes, compared with baseline approaches. In fact, when Paa is increased from 0.05 to 0.6, our DPAL. shows a small drop (11.8%% on average, from 84. 84.29%((za = 0.05) to 72.41 12.11%(z (14a 0.6)), compared with huge drop of the PixelDP, i.e., from 94.19%
= 0.05) to 9. 08%(ms MIM, and MadryEtAl attacks, and to 77.47% register significant drops in terms of certified accuracy for SecureSGD (78.74%, from 86. 74.% to 7. 7.99%) and SeMMreSGD-AGM (81.97% from 87.23% to 5.26%) on average. This is promising.
0.6) on average under I-FGSM, 0.6) under FGSM attack. Similarly, we also
Our key observations are as follows. (1) Incorporating ensemble adversarial learning into DP preser- vation, with tightened sensitivity bounds and a random perturbation size 14 E [0, 1] at each training step, does enhance the consistency, robustness, and accuracy of our model against different attack algorithms with different levels of perturbations. (2) Our DPAL model outperforms baseline algo- rithms, including both DP- -rrresserinng and non-private approaches, in terms of conventional accuracy and certified accuracy in most of the cases. It clear that existing DP-preserving approaches have not been designed to withstand against adversarial examples.
Results on the CIFAR-10 Dataset further strengthen our observations. In Figure 3 our DPAL clearly outperforms baseline models in all cases (p < 6.17e- 9), especially when the privacy budget is small (ce < 4). yielding strong privacy protections. On average conventional accuracy, our DPAL mechanism has improvement of 10.42% over SecureSGID (p 2.59e 7), an improvement of 14.08% over SecureSGD-AGM (p < 5.03e - 9), an improvement of 29.22% over AdLM (p < 5.28e - 26), and a 14.62% improvement over DP-SGD (p < 4.31e 9). When the privacy budget is increased from 2 to 10, the conventional accuracy of our DPAL model increases from 42.02% to 46.76%, showing a 4.74% improvement on average. However, the conventional accuracy of our model under adversarial example attacks is still low, i.e., 44.22% on average given the privacy budget at 2.0. This opens a long-term research avenue to achieve better robustness under strong privacy guarantees in adversarial learning.
The accuracy of our model is consistent given different attacks with different adversarial perturba- tions Ma under a rigorous DP protection (e, 2.0), compared with baseline approaches (Figure [5) In fact, when the attack size Pa increases from 0.05 to 0.5, the conventional accuracies of the base- line approaches
remarkably reduced, i.e., a drop of 25. 25.26% average given the most effective baseline approach, Secure SecureSGD.Mcaawwhlee there is a much smaller degradation (4.79% on average) in terms of the conventional accuracy observed in our DPAL model. Our model also achieves better accuracies compared with baseline approaches in all cases (p < 8.2e - 10). Figure 7 further shows that our DPAL. model is more accurate than baseline approaches (i.e., c,. is set to 0. in PixeIDP) in terms of certified accuracy in all cases, with a tight privacy budget set to 2.0 (p < 2.04e - 18). We register an improvement 21.01% % in our DPAL model given the certified accuracy over SecureSGD model, which is the most effective baseline approach (p < 2.04c 18).
5 CONCLUSION
In this paper, we established a connection among DP preservation protect the training data, adver- sarial learning, and provable robustness. A sequential composition robustness theory was introduced to generalize robustness given any sequential and bounded function of independent defensive mech- anisms. An original DP-preserving mechanism was designed to address the trade-off among model utility, privacy loss, and robustness by tightening the global sensitivity bounds. A new Monte Carlo Estimation was proposed to improve and stabilize the estimation of the robustness bounds; thus improving the certified accuracy under adversarial example attacks.
However, there are several limitations. First, the accuracy of our model under adversarial example attacks still very low. Second, the mechanism scalability dependent on the model structures. Third, further study is needed to address the threats from adversarial examples crafted by unseen attack algorithms. Fourth, in this study, our goal is to illustrate the difficulties in providing DP protections to the training data in adversarial learning with robustness bounds. The problem is more challenging when working with complex and large networks, such as ResNet (He et al., (015). VGG16 (Zhang al. 2015), LSTM (Hochreiter & Schmidhuber 1997), and GAN (Goodfellow (et al., 2014 Fifth, there can be alternative approaches to draft and to use DP adversarial examples. Addressing these limitations needs significant efforts from both research and practice communities.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. arXiv: 00133, 2016.
Martín Abadi, Ulfar Frlingsson, Ian Goodfellow, H Brendan McMahan, lyya Mironov, Nicolas Pa- pernot, Kunal Talwar, and Li Zhang. On the protection of private information in machine learning systems: Two recent approches. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 1-6. IEEE, 2017.
Mahdich Abbasi and Christian Gagné. Robustness to adversarial examples through an ensemble of specialists. CoRR, abs/ 702.06686, 2017. http:ppp/aaxx...orr///////20200
T. Apostol. Calculus. John Wiley & Sons, 1967.
GEORGE Arfken. In Mathematical Methods for Physicists (Third Edition). Academic Press, 1985.
Borja Balle and Yu-Xiang Wang. Improving the Gaussian mechanism for differential privacy: Ana- lytical calibration and optimal denoising. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Ma- chine Learning Research, pp. 394 403, Stockholmsmässsan Stockholm Sweden, 10-15 Jul 2018. PMLR. htt.:htp:p/// http://proceeeingg mlr prwss/ http://///aaaall.....a htmm
N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57, May 2017. doi: 10.1109/SP.2017.66
Konstantinos Chatzikokolakis, Miguel E. Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metrics. In Emiliano De Cristo- faro and Matthew Wright (eds.), Privacy Enhancing Technologies, pp. 82-102, 2013.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parse- val networks: Improving robustness adversarial examples. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 854-863, International Convention Centre, Sydney, Australia, 06-11 11 Aug 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320, Long Beach, California, USA, 09-15 Jun 2019.
Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Xiaolin Hu, and Jun Zhu. Discovering adversarial examples with momentum. CoRR, abs/1710.06081 2017.
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. Theory of Cryptography, pp. 265-284, 2006.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., (188:88211:422211 0400000042. URL httt::/ /wt. http://ww.....o/........6////0/0
August 2014. ISSN 1551-305X. doi: 10.1561/
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit con- fidence information and basic countermeasures. In Proceedings of the 22Nd ACM SIGSAC Conference on Computer and Communications Security, CCS '15 pp. 1322-1333, 2015. doi: 10.1145/281010: 2010033..81677777 13677.
Gao, Beilun Wang, and Yanjun Qi. Deepmask: Masking DNN models for robustness against adversarial samples. CoRR, abs/1772.00663,, 2017. URL http:::/aaxxv..oo/t/////o wttps///.r.aaa///b0//....
06763
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems 27, pp. 2672-2680. 2014a.

---

Under review as a conference paper at ICLR 2020
Ian J. Goodfellow. Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. CoRR, abs/1412.6572, 2014b.
Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick D. McDaniel. On the (statisticall) detectioon of adversarial examples. CoRR, abs/1702.06280, 2017. URLhttp:
Shixiang Gu and Luca Rigazio. Towards deep neural network architectures robust to adversarial
examples. CoRR, abs/1442.5068, 2014. URL httt:://aaxx.i... .tg/ abs/ / 1412. 5068
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CoRR, abs/ 10W/11312.3385... 2015.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8): 1735-17800 1997. doi: (t.1162/neco.1999 1997.9.8.1735.
Hossein Hosseini, Yize Chen, Sreeram Kannan, Baosen Zhang, and Radha Poovendran. Block- ing transferability of adversarial examples in black-box learning systems. arXiv preprint 1703.40700. 2017.
N. Kardan and K. O. Stanley. Mitigating fooling with competitive overcomplete output layer neural networks. In 2017 International Joint Conference on Neural Networks (IJCNN) pp. 518-525, 2017.
J. Zico Kolter and Eric Wong. Provable defenses against adversarial examples via the convex outer adversarial polytope. CoRR, abs/1711.0085// 2017. URL 008.1
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial examples in the physical world. CoRR, abs/1607.02553 2016a.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning at scale. CoRR, abss/611.00 101.11136.. 2016b.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recog- nition. Proceedings of the IEEE, 86(1 1):27782222, 1998. doi: 10.1 109/5.726799
Mathias Lecuyer Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustmess to adversarial examples with differential privacy. In arXiv:1802.03471, 2018. URL
htttp::/arxiv.oot wttp://wwww..gg//////////// 03471
Jaewoo Lee and Daniel Kifer. Concentrated differentially private gradient descent with adaptive per-iteration privacy budget. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1656-1665, 2018.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. CoRR, abs/1809.03115 2018. URL httl:/:/aax..../////aa/
18C9.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant adversarial attacks. In International Conference Learn- ing Representations, 2018. URL httpl/ttt///oeeeeiiiiieae
net/ forum did=r
A. Matyasko and L. P. Chau, Margin maximization for robust classification using deep learning. In 2017 International Joint Conference on Neural Networks (IJCNV), pp. 300-307, 2017.
Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff. On detecting adversar- ial perturbations. In Proceedings of Sth International Conference on Learning Representations (ICLR), 2017. URL htw.:htts://// /ttp://///xxv.vooo.eeo abs 07017.00000 04267
N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami. The limitations of deep learning in adversarial settings. In 2016 IEEE European Symposium on Security and Privacy, pp. 372-387, March 2016a 6a. doi: 10. 109/FuroSP.2016.366
12

---

Under review as a conference paper at ICLR 2020
N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami. Distillation as defense to adversarial perturbations against deep neural networks. 2016 IEEE Symposium on Security and Privacy (SP), pp. 582-597, May 2016b. doi: 10.1109/SP2016.44..
Nicolas Papernot and Patrick McDaniel. Extending defensive distillation. arXiv preprint 7r55v:1705.05264, 2017.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Er- lingsson. Scalable private learning with pate. arXiv preprint arXiv:/802.08906 2018.
N. Phan, X. Wu, H. Hu, and D. Dou. Adaptive laplace mechanism: Differential privacy preservation in deep learning. In IEEE ICDM' 17, 2017a.
NhatHai Phan, Yue Wang, Xintao Wu, and Dejing Dou. Differential privacy preservation for deep auto-encoders: an application of human behavior prediction. In AAA/'6,, pp. 1309-1316, 2016.
NhatHai Phan, Xintao Wu, and Dejing Dou. Preserving differential privacy in convolutional deep belief networks. Machine Learning, 2017b. doi: 10. 1099007776109944-----666-6--.
NhatHai Phan, Minh N. Vu, Yang Liu, Ruoming Jin, Dejing Dou, Xintao Wu, and My T. Thai. Het- erogeneous gaussian mechanism: Preserving differential privacy in deep learning with provable robustness. In Proceedings of the 28th International Joins Conference on Artificial Intelligence (IJCAI'19, pp. 4753 4759, 10-16 August 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. CoRR, abs/1801 0188011.944,, 2018. URL
09344
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In CCS'S5 pp. 1310-1321, 2015.
Liwei Song, Reza Shokri, and Prateck Mittal. Privacy Risks of Securing Machine Learning Models against Adversarial Examples. arXiv e-prints, art, 1905.v1995..02990 May 2019.
Operator norm.
Operator norm, 2018.
URL https://en.wike
Operator norm
Florian Tramèr, Alexey Kurakin, Nicolas Paperoo, Dan Boneh, and Patrick McDaniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint urXiv:/705.07220 2017.
Qinglong Wang, Wenbo Guo, Kaixuan Zhang, Alexander G. Ororbia II, Xinyu Xing, C. Lee Giles, and Xue Liu. Learning adversary-resisten deep neural networks. CoRR, abs/1612.01401, 2016.
Weilin Xu, David Evans, and Yanjun Qi. Feature squeezing: Deteeting examless in deep neural networks. CoRR, abs/1704.011555, 2017. URL http://axx...oorr/ab///0000 01155
L. Yu, L. Liu, Pu, M. Gursoy, and Truex. Differentially private model publishing for deep learning. In 20/9 IEEE Symposium on Security and Privacy (SP), pp. 326-343, 2019.
Jun Zhang, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, and Marianne Winslett. Functional mechanism: regression analysis under differential privacy. PVLDB, 5(11):1364-1355 2012.
Xiangyu Zhang, Jianhua Zou, Kaiming He, and Jian Sun. Accelerating very deep convolutional networks for classification and detection. CoRR, abs/1 505.06798. 2015.
13

---

Under review as a conference paper at ICLR 2020
A NOTATIONS AND TERMINOLOGIES
Table 1: Notations and Terminologies.
D and x
Training data with benign examples E 11
y (1) ....
One-hot label vector of K categories
f: F: + R
Function/model f that maps inputs
to vector of scores fz) = (f1(2)...... (x))
Ys E y
A single true class label of example x
( = maXKER K Sa(Ø)
Predicted label for the example æ given the function f
2 + a
Adversarial example where a is the perturbation
(p(10) 1a E R²=
lolp S b
The 1 n--rr ball of attack radius f
(cr, dr)
Robustness budget 6, and broken probability 6,
(x)
The expected value of fx)
Bis and Ens
Lower and upper bounds of
the expected value [x) = 1> f(x),
a(x,0) 01)
Feature representation learning model with and parameters 0,
B,
A batch of benign examples z;
RB, (01)
Data reconstruction function given B, in a(z, 01)
The values of all hidden neurons in the hidden layer h1 a(z, 0:) given the batch B,
his, = [0f x.
RB, (0z) and RT, (02)
Approximated and perturbed functions of Ra, (81)
2, and 24,
Perturbed and reconstructed inputs
AR = d(B + 2)
Sensitivity of the approximated function R. (01)
h1B,
Perturbed affine transformation h1s,
nullv 5
Lap( AR
DP adversarial examples crafting from benign example z;
Be and B,a
Sets of perturbed inputs T; and DP adversarial examples addl
11, (02)
Loss function of perturbed benign examples in Be, given 0g
(ff (x, 82).
Loss function of DP adversarial examples 2; given 0g
CT, (02)
DP loss function for perturbed benign examples B, A part of the loss function Lz, (82) that needs to he DP
L2 (82)
Composition scoring function given
S(M....,, M,(xr)
independent randomizing mechanisms Mi...., M.
A and A.
Sensitivities of 2 and h. given the perturbation
(1(1)
(e1 + El / + + E2)
Privacy budget to protect the training data D)
(re + p)mss
Robustness size guarantee given an input x at the inference time
B PSEUDO-CODE OF ADVERSARIAL TRAINING (KURAKIN ET AL., 201
Given a loss function:
T.(0) mi Em² Z.EB.
Σ C(((2.0))vv) + Σ T( 0))
(16)
where mi and m2 correspondingly are the numbers of examples in B, and Body at each training step.
Algorithm Adversarial Training (Kurakin et al.) 2016b)
Input: Database D, loss function L, parameters 0, batch sizes my and m2, learning rate et, param-
eter E
1: Initialize 0 randomly
2: for t E [T] do
3: Take a random batch B, with the size my, and a random batch B, with the size mg
4: Craft adversarial examples Budv (2.gd)) [e][mm from corresponding benign examples zy E
B.
5: Descent: 0 0 VoL
14

---

Under review as a conference paper at ICLR 2020
C
PROOF OF LEMMA 2
Proof Assume that Bt and Bi differ in the last tuple, am (x Then,
d
A = Σ
Σ
2 h4 Σ
Mill
+1
Σ
Tij Σ
xbsll]]
j=1
2
B
3y RBEB
x E
S 2 max
hel
1 + | 111) s d(3 +
2
D PROOF OF LEMMA 3
that h = 0g T. is a linear function of z. The sensitivity of a function h is defined as the maximum change in output, that can be generated by change in the input (Lecuyer al. 2018). Therefore, the global sensitivity of h can be computed as follows:
Proof 2 Regarding the computation of 1
10, T. B,
Dh: 1EZIET 01 (T,,-E,eh
0 1144
10 Jell1 S 110 ll.,1
S max
15 Ij -ETEEB 2/111 Z.EB.
|
following matrix norms (Operator norm 2018): 100 11,,1 is the maximum I-norm of 01 's columns. By injecting Laplace noise Lap( into hIs, iee. h = 10 z. Lap( ei )r we can and drawn as Laplace noise [Lapl ) in our mechanism, the perturbed affine transformation h,n, is presented as:
Auy
preserve C1-P in the computation of h Let us set Ån, 10, 11,1,
2 mAb
2X2 B.EB. [0 n.
- m
AR 11ah -Lapp
11B. =00 T4
ZIEB.
m
61
= 10 T
A 11 JR,EB. 10 v. + Lapp( c1/7
An 11 JR,EB.
T +
Lapp(
E1
This results in an (eI/))-DP affine transformation hin, 10, + |Lapl Ani 11
JMER.
A 1 Ja, Similarly, the perturbed inputs B, = = = (x; + XL J2,en, = fx: + [Lap( catta where Ax is the sensitivity measuring the maximum change in the input layer that can be generated by a change in the batch B, and 7x
Ax. Following Lecuyer et al. 2018), Ax can be computed mA.
|E. z. E Z/ll
as follows: Ax
IE TE b. 2 Tll = 1. As a result, the computation of Be is (e1/Tx)-DP.
Consequently, Lemma 3 does hold.
E PROOF OF THEOREM
Proof Given X1 drawn as a Laplace noise [Lop( Ae )Jd and X2 drawn as Laplace noise ( v.), denoted as o, can be rewritten
[Lap[ A )x) the perturbation of the coefficient follows:
for ò (x Σ
(bx,
+
Xi
AR nd Σ dn, +x= Σ dr, + [aap
m
E1
I
Z
for Q 1
1
Σ
(14
+
2X2
= Σ (0x, + X2
m
m
FEBB
AR 1
Σ
Qz, + X2 = Σ
Dz. + [aap(
B.EB
8.EB
15

---

Under review as a conference paper at ICLR 2020
have
61 c11E2,,BB 6z. -
Pr TT,R, (01))
II II exp (-
DR
j=1 6E#
R is set d(B + 2), we have that:
Pr Pr (8))
1 IOEE exp (
e1 1 E Un; 011
AR
Pr Pr(BB. (01))
E EB; Pz!
1 j=1 IL exp
AR
expl
Oz
Σ
AR
j=1dE#
BEB
1 max exp(
|| (11) S expl
Cdd(3 + 2), - exp(e1)
(17)
AR
mEB
DR
j=
Consequently, the computation of RB, (01) preserves E1-DP in Alg. In addition, the parameter optimization of R B, (01) only uses the perturbed data B,, which is (E1/7xx-DP (Lemma 3 in the computations of h4, h4, H. parameter gradients, and gradient descents at each step. These opera- tions do not access the original dataset Bú; therefore, they do not incur any additional information from the original data (the post-proo proccssccsigg property in DP Dwork & Roth (2014)). a result, the total privacy budgel learn the perturbed optimal parameters O1 in Alg. is (E1/7x + e1)-DP.
F PROOF OF LEMMA 4
Proof 4 Assume that Be and B3 differ in the last tuple, and Fm (Im) be the last tuple in B (B'), have that
K
C2
Σ
Σ
(bx.vu)) - (hasth ||
hambmnk h Smakll
k=1
TEE
Since You and y'nk are one-hot encoding, we have that Aca S 2 maxz, [hail|i- Given h E
[-1,1], we have
Ac2 s 2
(18)
Lemma does hold.
G PROOF OF THEOREM
Proof Let B, and B, be neighboring batches of benign examples, and Xs drawn as Laplace noise [Lap( Aca }] [h>,,, the perturbations of the coefficients h,slik can be rewritten as:
hmD Σ (hartiik +
X3 m
(hnilii))
[Lap(
Ac2 [b_]
z.
F,
Since all the coefficients are perturbed, and given Ac2 = 2/ we have that
Pr(Cz, (62) Pr(L (82)) x Pr(C (02)
Pr(Czz, (62))
Pr (8z) Pr(c (H2))
K exp(
EE. he Furiuell A
< 9//7
Ex hetlit BasMalll
k= exp(
Aez
K
6//4
exp(
62
Σ
hrifit
k=
9/7 exp(
E2
max z
bxilli)
Ara
16

---

Under review as a conference paper at ICLR 2020
The computation of L2B, (82) preserves (41/n + e2)-differential privacy. The optimization of Lnn, (02) does not access additional information from the original input x, E Br. Consequently, the optimal perturbed parameters 02 derived from L2B, (02) are (E1/7 (0//+++22// c2)-
H PROOF OF THEOREM
Proof 6 First, we optimize for a single draw noise during training (Line 3) and all the batches of perturbed benign examples are disjoint and fixed across epochs. a result, the computation of a; is equivalent to data preprocessing step with DP, which does not incur any additional privacy budget consumption over T training steps (the post-processing property of DP) (Result 1). That is different from repeatedly applying DP mechanism either the same overlapping datasets causing the accumulation of the privacy budget.
Now, show that algorithm achieves DP at the dataset level D. Let consider the compu- tation of the first hidden layer, given any two neighboring datasets D and D' differing at most one
tuple Ie E D and Ty E D'. For any O = I N/m
0,
E
N/m h
i=1
B (E R@x"), we have that
P PhID = 0) P(h 01)
P(h 1T ON/m)
(19)
Phhi 0) P(h, 01)
P(h
1T ON/m)
By having disjoint and fixed batches, we have that:
BBeBas s.t. de B and 3. B s.t. x' B'
(20)
From Eqs.
19
20
and Lemma
we have that
P P = 0) =1
VB
E
B
B ー
(21)
P(h IB' =0)
P = 0) P(h = 8)
Eqs.
20 and
27
P P(hin 0) P(h =)) S c/1/
(22)
As a result, the computation of hip is DDP given the data D, since the Eg. 22 does hold for any tuple D. That is consistent with the parallel composition property of DP, in which batches can be considered disjoint datasets given h 1B as a DP mechanism (Dwork & Roth 2014
This does hold across epochs, since batches B are disjoint and fixed among epochs. At each training step & E [1, the computation of h1B, does not access the original data. It only reads the per- turbed batch of inputs B., which is (E1/%x))-D -D (Lemma By. Following the post-pron post-processing property in DP Dwork & Roth 2014), the computation of h does not incur any additional information from the original data across T training steps. (Result 2)
Similarly, we show that the optimization of the function RB, (01) is (e1/Tx + DDD across T training steps. As in Theorem and Proof we have that Pr Pr(R (()) I1; IL exp e: E,E,, d=, -0,0) where B E B. Given any two perturbed neighboring datasets D and D' differ- ing at most one tuple Te E D and x's E
aR
Pr ((1)
Pr Pr (01) Pr P (81))
(23)
Pr (R (01)) Pr (r (01) Pr (R (01))
From Eqs.
and Theorem 7 we have that
((R
YB v BBBBB
B=
(24)
P(R B. (01))
((1)
P P(R
Eqs. and 24
S e P(Rg.(0))
(25)
PRR (01)
17

---

Under review as a conference paper at ICLR 2020
As resuls, the optimization of (D111) is (c1/Tx + cDDDP given the data D (which is c1/ c1/"ixDi (I (Lemma 3)), since the E.q. 25 does hold for any tuple 3e D. This is consistent with the parallel composition property in DP (Dwork & Roth 2014), in which batches can be considered disjoint datasets and the optimization of the function on one batch does not affect the privacy guarantee in any other batch. In addition, Vt E [1, the optimization of RB, (81) does not use any additional information from the original data D. Consequently, the privacy budget is (61/7x + +1) across T training steps, following the post-preen prot-psocssiing property in DP (Dwork Roth 2014) (Result 3).
Similarly, we can also prove that optimizing the data reconstruction function Rep (81) given the DP adversarial examples crafted in Eqs. Bandg i.e., xaa is also (C1/"ix + DD given t E [1, on the training data D. First, DP adversarial examples Jagly are crafted from perturbed benign examples Z-z- As a result, the computation of the batch B, Bude of DP adversarial examples 1) (<1/7x)-DPP (the post-processing property of DP (Dwork & Roth 2014)), and 2) does not access the original data Vt E [1.T]. In addition, the computation of h Li and the optimization of RT,.0(811) correspondingly are c1/"-DP and CD. In fact, the data reconstruction function R Rydd is presented as follows:
R Bi (0i) = Σ
ady 2 Oialty 15-2 zeg
znght E
1=1
Σ
ady 0lili
-I Tgzggh u sign
0). moddy)
2nth E
i=1
Σ
1atky -I, 3
adv
Σ 25 BB
a. sign ((t, aghh (26)
2
zaah E Budd
where hight = = T R. = high + 2. Lap( Az. ). and T = 0 adv The right summation compo- e1
adv
nent in Eq. does not disclose any additional information, since the sign(-)) ffnccto is computed from perturbed benign examples (the post-procsssing property in DP (work & Roth 2014)). Mean- while, the left summation component has the same form with RE, (01) in Eq. 7 Therefore, we can employ the Proof in Theorem I by replacing the coefficients Tb 122 hi 2.) with t to prove that the optimization of R Ba (01) is (61/1xx + (1) As a result, Theorem does hold. (Result 4)
2 high 2z3)
In addition to the Result 4, by applying the same analysis in Result 3, we can further show that the optimization of Ru (0:) is (61/7x (1) )-DP given the DP adversarial examples Dadv crafted using the data D across T training steps, since batches used to created DP adversarial examples are disjoint and fixed across epochs. It is also straightforward to conduct the same analysis in Result in order to prove that the computation of the first affine transformation h 10" zith +
EBt" given the batch of DP adversarial examples B, add is (e1/7)-DP with [1,7] training steps. This is also true given the data level D (Result 5)
2. Lap( AR )
m
Regarding the output layer, the Algorithm preserves (e1/7 DDP in optimizing the adversarial objective function L,g,U,"" (02) (Theorem 3.. We apply the same technique to preserve (e1/7 + e2)- DP across T training steps given disjoint and fixed batches derived from the private training data D. In addition, as our objective functions R and L are always optimized given two disjoint batches B, and B,th. the privacy budget used to preserve DP in these functions is (E1 ( following folloovinn the parallel composition property in DP (work & Roth 2014). (Result 6)
With the Results 1-6, all the computations and optimizations in the Algorithm Mare DP following the post-processing property in DP (Dwork & Roth 2014), by working on perturbed inputs and perturbed coefficients. The crafting and utilizing processes of DP adversarial examples based on the perturbed benign examples do not disclose any additional information. The optimization of
18

---

Under review as a conference paper at ICLR 2020
DP adversarial objective function at the output layer is DP protect the ground-trutt labels. More importantly the DP guarantee in learning given the whole dataset level D is equivalent to the DP guarantee in learning
disjoint and fixed batches across epochs. Consequently, Algorithm 1 preserves (E1 + E1/1xx + E1/y + -DP in learning private parameters 0 {01, 02) given the training data across T training steps. Note that the E 7/x is counted for the perturbation on the benign examples. Theorem does hold.
I PROOF OF LEMMA
Proof 7 Thanks to the sequential composition theory in DP Dwork & Roth 2014),
is (x) since for any O II Og II (z) R²). have
that
P(Mif(z)= P)) = os) P(J(MI,.... M.(MM....,MM...... Ms|a 0) P(Mif(++a) 01) ... ... P(Mssf(( + a) os)
exp(Es) (oo(es)=(<iiiiii c(
s=1
As a result, we have
P(f(M Ms|xx) S SeL.)) M(sl +a))
The sequential composition of the expected output is as:
Ef(M Msl.))
t)dt
S selE,ca aa) J
> t)dt
= =elE, WBf(M Msla
Lemma does hold.
PROOF OF THEOREM 5
Proof Va E from Lemma with probability 2 17 we have that
(27)
e(E5-10.)
e(Ziz1
In addition, we also have
Vi * ls @ Msla + a) S <ol2 en B Brise Ms|z))
+ W k: B/A Mslr a) S Ei (a)
max Bass (M (M, Mslo)
(28)
tiik
Using the hypothesis (Eq.
14
27 have that and the first inequality (Eq.
2 5)) max (a Ms(a)
+ +a)>
e
max f. Mslaz) kegk
Now, we apply the third inequality (Eq.
28
we have that
Vi ls
(M
Ms(x+aa
Ms|r +a) MM....l +a)
max
2
The Theorem ddoes hold.
19

---

Under review as a conference paper at ICLR 2020
K
PROOF OF PROPOSITION 1
Proof 9 Ya E (1)), by applying Theorem we have
Mn.le(M,, tier) max Bub (M Mglæ) Rzfk
2(++ max
Eas Is Saass/MMMan (M,r Mz
Furthermore, by applying group privacy, we have that Vo E (n :p) En Sn (M M2 >
2er max (MMn birk
By applying Proof it straight have
Va E (p + 9): MalMMM,MMMaae + max (asleo 1zz2
Maless
with probability 2 n. Proposition dooes hold.
L EFFECTIVE MONTE CARLO ESTIMATION OF Ef(x)
Recall that the Monte Carlo estimation is applied to estimate the expected value Rf(x) 1 En (x)). where n the number of invocations of f(x) with independent draws in the noise, i.e., m. Lap(O, Az) and 2 Lap(O, AR) ) in our case. When is small (indicating a strong privacy protec- tion), it causes a notably large distribution shift between training and inference, given independent draws of the Laplace noise.
In fact, let us denote a single draw in the noise as X1 = 1 Lap(0, Az) used to train the function (z), the model converges to the point that the noise X1 and 2X2 need to be correspondingly added into x and i in order make correct predictions. X1 can be approximated as Lap(xx X1, 2), where + O. the fixed noise X1 Lap(X1, 2). These distribution shifts can also be large, when noise is large. We have experienced that these distribution shifts in having independent draws of noise estimate (x) can notably degrade the inference accuracy of the scoring function, when privacy budget cj is small resulting in a large amount of noise injected to provide strong privacy guarantees.
clear that independent draws of the noise m Lap(O, Ax have distribution shifts with e1
To address this, one solution is increase the number of invocations of f(x). i.e., n, to huge number per prediction. However, this is impractical in real-world scenarios. We propose a novel m way to draw independent noise following the distribution of X1 + 1 Lap((0 Ar /v/) for the input
and 2x2 2 Lap(O, Åx /v/) for the affine transformation h, where is hyper-parameter to control the distribution shifts. This approach works well and does not affect the DP bounds and the provable robustness condition, since: (1) Our mechanism achieves both DP and provable robustness in the training process; and (2) It is clear that (x(x) = 3. Σ, f()) = En g(a(r + X1 + e1 ///), 82), where Lap,, (0, AR /v) is the n-th draw e1 of the noise. When - cc, Êf(x) will converge to + E. s(a(1 + 01 + 2x2. 0z), which aligns well with the convergence point of the scoring function f(z). Injecting X1 and 2x2 to and h during the estimation of [xx yields better performance, without affecting the DP and the robustness bounds.
xn
1 Lapa(0, AR //)), 01) + 2x2 + m Lap,, (0, AR m
e1
M MODEL CONFIGURATIONS
The MNIST database consists of handwritten digits (Lecun et al. 1998). Each example is a 28 x 28 size gray-level image. The CIFAR-10 dataset consists of color images belonging to 10 classes, ie.. airplanes, dogs, etc. The dataset split into 50,000 training samples and 10,000 test samples Krizhevsky & Hinton| 2009). The experiments were conducted
a single GPU, i.e. NVIDIA GTX TITAN X, 12 GB with 3,072 CUDA cores. All the models share the same structure, consisting of 2 and 3 convolutional layers, respectively for MNIST and CIFAR- 10 datasets.
20

---

Under review as a conference paper at ICLR 2020
Both fully-connected and convolution layers can be applied in the representation learning model a(x,01) Given convolution layer, the computation of each feature map needs to be DP; since each of them independently reads a local region of imput neurons. Therefore, the sensitivity Ar can be considered the maximal sensitivity given any single feature map in the first affine transformation layer. In addition, each hidden neuron can only be used to reconstruct unit patch of input units. That results in d (Lemma 2 being the size of the unit patch connected to each hidden neuron, c.g., d 9 given 3 3 unit patch, and 3 is the number of hidden neurons in a feature map.
MNIST: We used two convolutional layers (32 and 64 features). Each hidden neuron connects with a 5x5 unit patch. fully-comnected layer has 256 units. The batch size m was set to 2,499, 5 = 1, a = 2. I-FGSM, MIM, and MadryEtAl were used to draft lo (4) adversarial examples in training, with T, = 10. Learning rate @ was set to le 4. Given a predefined total privacy budget <t, 62 is
set to be 0.1, and 6 is computed as: 61 = (1+1/+11/72) This will guarantee that (c1 + G/7%x +
66-62
//7 + (2) = 6.- A (142 + 2) x 25 and Ac2 = 2 x 256.
CIFAR-1O: We used three convolutional layers (128, 128, and 256 features). Each hidden neuron connects with 4x4 unit patch in the first layer, and 5x5 unit patch in other layers. One fully- connected layer has 256 neurons. The batch size m was set to 1,851, < 1.5, 1i = 10, and T, = 3. The ensemble of attacks A includes I-FGSM, MIM, and MadryEtAl. We use data augmentation, including random crop, random flip, and random contrast. Learning rate O was set to 5e - 2. In the CIFAR- 10 dataset, 62 is set to (1 + r/3.0) and 61 (1 + 2r/3.0) + 1/7 + 1/7x), where is a ratio to control the total privacy budget 6, in our experiment. For instance, given r = O, we have (142 + 2) x 16 and Ac2 2 x 256.
0
that 6, (c1 / 9/7 + 62) 2. AR
Computational Efficiency and Scalability. In terms of computation efficiency, our mechanism does not consume any extra computational resources to train the model, compared with existing DP-preserving algorithms in deep learning (Phan et al., 2016 2017b The model invocations to approximate the robustness bounds can further be efficienlly performed in a parallel process. Regarding the scalability, with remarkably tightened global sensitivities, the impact of the size of deep neural networks in terms of the number of hidden layers and hidden neurons significantly remedied, since 1) Ag and A are small, 2) we do not need to inject any noise into the computation of the network g-)), and 3) we do not redraw the noise in each training step t. In addition, our mechanism is not restricted to the type of activation functions. That is similar to (Lecuyer et al.) 2018 Phan et al., 2019). As a result, our mechanism has a great potential to be applied in larger deep neural networks using larger datasets. Extensively investigating this property requires further study from both research and practice communities.
N APPROXIMATION ERROR BOUNDS
To compute how much error our polynomial approximation approaches (i.e., truncated Taylor ex- pansions). RB, (01) (Eq. 6 and Lzz (02), incur, we directly apply Lemma 4 in (Phan et al. 2016 Lemma 3 in (Zhang et al. al: 2012), and the well-known error bound results in (Apostol 1967] Note that R. (02) is the ost-rrder Taylor series and Lg. (0, is the 2nd-order Taylor series. Let us closely follow (Phan et al. 2016 Zhang et al. 2012 as follows:
Apostol 1967) to adapt their results into our scenario,
FI (0ight)" ", the original
Given the truncated function RB, (01) = - Ej 2i=1 =
Taylor polynomial function Rr. (6)) = Ex,EB, Ej= 2t=1 EL
FP(0) (0)
- (Bi,hh)² the average
error of the approximation is bounded as
4e X d (1 + e)²
RB, (0)) RB, (01) 5
(29)
B.
c² 2e -
Lg, (82) Ls, 5 e(1 + e)²
K
(30)
B&
where 0 = arg mino, RB, (01), 01 = argmino, RB (01), Σz, (02) is the original Taylor polyno- mial function of En,e,, 02), 02 arg ming, LB, (02), 02 arg orgmino, LB, (0z).
21

---

Under review as a conference paper at ICLR 2020
Proof 10 Ler U max6, (0) -RB, (01) and S = ming, (R (01) -R (0))).
We have that U 2 RR, - RB. (01) and F8% : S $ RB, (01) - (87). Therefore, we have Rs. (0:) RB, (01) - (0') Rs. (8)) S - 5
(31)
+ Rn (01) RR, (01) s U - U (Rs, (01) - RB, (01))
(32)
In addition, RB. (01) RB, S 0. it is straightforward to have:
RB, RB, -
(33)
U 2 0 and S S 0 then we have:
RRB, (01) - (f)) S S
(34)
Eq. 34 holds for every 01. including 01. Eq. 34 shows that the error incurred by truncating the Taylor series approximate function depends on the maximun and minimum values of Ræ, RR. (01).
This is consistent with (Phan et al. 2016 [hang et al. 2012). To quantify the magnitude of the
error, we rewrite RB, (01) - R. (01) as:
d
R& (01) - (0,) Σ RRB, (01,) - (B (015))
(35)
sc F (21z) Σ ΣΣ
Be
r! (01(10; 01z) -21)))) 215)")
(36)
where 915 (15(2;,013) = 01ghu and (12(11; 01g) 01ghi.
By looking into the remainder of Taylor expansion for each j (ie., following (Phan al. 2016
Apostol 1967), ) with 2j [ag 1, + 1]. [B.] (RB, (01)) (01)) must be the
interval Σ min., 15
(=;)) =z)²²
Σ max., 1 (=;)( 2,y)
If E. max., p/ (=))(z)-2))
21
0 and Σ, mine, F (z)) 21)
I 0. then we have that [ (RB( (0,) RB. (01)) 2
Ej= Ei max., Fl, (25)(() =1y) P F( (z))(e)-a)) This can be applied the case of our auto-
21
encoder, as follows:
For the functions
F1Ş(2;) = Fij log(1 + a)) and F2)(z,) = (1 - xzi)) log(1 e²),, we o²g (146557
have F13 (2,)
Zye zye
It can be verified that < O, arg max,, F() (zz) = (oaz > O, arg min,, F2 = 0,
and F (zz) = (1 - túz)
(1+e zy
arg ming, F19 (2)) = (146)
> 0. Therefore, the average emror of the approximation is at and arg max:, F5((2) [[+e]=
2c
most:
1 B₂l
4e d (1 + e)²
RB. (1) RB. 01)1 S (1+cp (1+ e)+
x d
(37)
Consequently, Eq. 29 does hold. Similarly, by looking into the remainder of Taylor expansion for each label ki Eq. 30 can be proved straightforwardly; In fact, by using the 2nd-order Taylor series with K categories, we have that: B. LCn (02) Ln, (0,) < 2420-1
e(1te] x K.
O COMPLETE EXPERIMENTAL RESULTS
22

---

Under review as a conference paper at ICLR 2020
0.9
0.9
conventions eccurscy
0.8
0.8
0.7
0.6
DPAL
0.8
0.5
AdLM DP SGD
0.5
0.4
DP-80D
0.3
0.3
0.2
0.2
0.1
0
0.2
0.4
0.6
0.8
1.2 1.4 1.6 1.8
2
1.8 +//+t//// (2)
privacy budget (e, + +///, +
privacy budget (c 5/3x +
(a) I-FGSM attacks
(b) FGSM attacks
0.9
0.9
conventional sccuracy
0.8
conventional accuracy
0.8
0.7
0.6
0.6
DPAL DP-530
SecureSSD AGM
SecureB0D
0.5
0.5
0.3
0.3
0.2
OPAL
BacUNSRD-AGY
0.2
0P-900
0.2
1.4
2
1.2 1.8 privacy budget (c, 9/5x + +/// + (2)
privacy budget (, 9/1x" + +//++ (2)
(c) MIM attacks
(d) MadryEtAl attacks
Figure 2: Conventional accuracy on the MNIST dataset given the privacy budget, under Loe (Ho = 0.2).
0.5
0.5
conventional accurscy
conventional accuracy
0.4
0.4
AdLM
0.3
SecureSCD-AGM
DP-SGD
DPAL
SecureSGD-AGM SecureSED
SecureSGD
AdLM
0.2
DP-SOD
0.1
0.1
8
10
privacy budget (, 4//x + /// (g)
privacy budget (, + +, x/x /
(a) I-FGSM attacks
(b) FGSM attacks
0.5
conventional accuracy
conventional accuracy
0.4
0.4
0.3
0.3
DPAL
SecureSOD-AGM SecureSGD
SecureSD--AGM
Adi
AAdM
SecureSGD
0.2
DP-SGD
0.2
DP-SGD
0.1
2
2
6
8
10
privacy budget (, c/%% + e
privacy budget (c, c/2, + cg)
(c) MIM attacks
(d) MadryEtAl attacks
Figure 3: Conventional accuracy the CIFAR-10 dataset given the privacy budget, under (o0 0.2).
23

---

Under review as a conference paper at ICLR 2020
0.9
0.8
0.7
DPAL
Secure00D-AGM
0.7
DPAL
SecureSGD-AGM
0.8
AdLM
Secura8GD
0.8
AdLM
SecureSGD
DP-SGD
DP-SGD
conventiona
0.5
0.5
0.3
0.3
0.2
0.2
0.1
0.05
0.3
0.050.1
Va
Paa
(a) I-FGSM attacks
(b) FGSM attacks
conventional accuracy
0.8
0.7
DPAL
SecuraSGD-AGM
0.7
DPAL DP-SGD
SecureSGD-AGM
0.6
AdLM
SecureSGD
Secure8G0
DP-SGD
0.4
0.4
0.3
0.3
0.2
0.1
0
0.060.1
0,2
0.3
0.5
0.8
0.050.1
0.2
0.3
0.4
0.5
0.8
Pa
Pa
(c) MIM attacks
(d) MadryEtAl attacks
Figure 4: Conventional accuracy on the MNIST dataset given the attack size Pax under (c1 f < 62) 0.2 (tight DP protection).
0.5
0.5
conventional accuracy
0.4
conventional accuracy
0.4
DPAL
SecureSGI SecureSGD
AALM
0.3
SGD
0.3
0.1
AdLM
SecuraBCD
De-SCD
0.1
0.05
0.3
0.4
0.5
P.
(a) I-FGSM attacks
(b) FGSM attacks
0.5
conventional accuracy
0.4
DPAL
BeaureGGD-AGM
conventionall accuracy
0.4
AdLM
SecureSGD
0.3
DP-SGD
0.3
0.2
0.2
0.1
SeeuneSGD-AGM
-ALM
SecureSGD
DP-SGD
0
0.05
0.1
0.2
0.3
0.4
0.5
0.05 0.1
0.2
0.3
0.4
0.5
P4
(c) MIM attacks
(d) MadryEtAl attacks
Figure 5: Conventional accuracy on the CIFAR-10 datasct given the attack size pas under (e) +
4 + 6/7 + (2) 2 (tight DP protection).
24

---

Under review as a conference paper at ICLR 2020
0.9
0.8
Certified accuracy
0.8
cartified accuraoy
0.7
0.7
0.5
0.4
0.4
0.3
PbxlDP
0.1
SocureSGD
SecureGD-AGM
0.1
SecureGGD-AGM
SecureSGD
0
0.050.1
0.2
0.3
0.4
0.5
0.8
0.050.1
0.2
0.3
0.4
0.5
0.8
Pa
(a) I-FGSM attacks
(b) FGSM attacks
0.9
0.9
0.8
Certifed accuracy
0.7
accurage
0.6
0.6
0.5
0.5
0.4
0.3
0.2
0.2
PhelDP
0.1
SecureSGD
0.1
SecimSSGD-ACH
0.050.1
0.2
0.3
0.5
0.6
0.060.1
0.2
0.3
0.4
0.5
0.8
Pa
(c) MIM attacks
(d) MadryEtAl attacks
Figure 6: Certified accuracy on the MNIST dataset. protection).
The privacy budget is set to 1.0 (tight DP
0.5
0.5
0.45
0.45
cartifidd accuracy
0.4
certifed accuracy
0.35
DPAL PbxelDP
0.35
DP AL Pi
0.3
SecureSGD-AGM
0.3
SecureSGDD
0.25
SecureSGD
0.25
0.2
0.15
0.15
0.1
0.05
0.1
0.2
0.3
0.4
0.5
0.05
0.1
0.2
0.3
0.4
0.5
(a) I-FGSM attacks
(b) FGSM attacks
0.5
0.45
0.45
certified accuracy
0.4
certiffed accuracy
0.35
0.35
0.3
PixelDP SecureSGD-AGH
PixelDP
SecureSGC AGM
0.25
SecureSGD
0.25
SecureSGD
0.2
0.2
0.15
0.16
0.1
0.3
0.05
0.1
0.2
0a
Pa
(c) MIM attacks
(d) MadryEtAl attacks
Figure 7: Certified accuracy the CIFAR-10 dataset. protection).
The privacy budget is set to 2 (tight DP
25


Reviews:
[{"review_id": "HklhXFj5FS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 propose an algorithm with DP preservation to train adversarially robust neural networks. To preserve DP, a single-layer linear autoencoder with shared weights is learned to extract features from training data, whose encoder is used to extract private features for the training and inference of a deeper network. To enhance robustness against various attacks, adversarial examples crafted with such attacks are injected into the training set in this algorithm. Guarantees of privacy preservation for training on both clean data and adversarial examples for the autoencoder and the inference network are given. Certified robustness of the smoothed classifier is also given, which depends on the privacy budget of each compositing mechanism. Experimental evaluations of two small (2 and 3 conv layers) networks are given on the MNIST and CIFAR10 dataset, showing improved conventional accuracy on clean samples and adversarial attacks, and certified accuracy than 4 baseline privacy-preserving algorithms.\n\nTo my knowledge, this paper provides the most comprehensive analysis so far about privacy preservation in the process of enhancing empirical adversarial robustness, as well as the impact of privacy preservation on the certified robustness of the smoothed classifier. However, the current version is quite difficult to follow for people without DP background, with some settings even conflict with other papers on adversarial robustness, and I do have some doubts about the experimental results. Specifically,\n\n1. What is the role of adversarial examples in the proposed algorithm? Perhaps I missed something, but the authors have not shown how it is related to certified robustness in the paper. The adversarial examples seem to be used only for improving the empirical accuracy against various adversarial attacks. Empirical adversarial robustness is usually down weighted to me when certified robustness is given, therefore an algorithm enhancing only the empirical one does not seem so interesting. \n\n2. What is even more against my intuition at first glance is that the empirical adversarial accuracy in Figure 4 is lower than the certified accuracy in Figure 6 in some situations. After a while I realized that the conventional accuracy against attacks in Figure 4,5 and the certified accuracy in Figure 6,7 are actually talking about different models, where the first one is the deterministic (or one-random-sample) inference network but the second one is for the smoothed classifier (as referred to in by Cohen et al. 2019, or the expectation of the inference network). This distinction should be addressed, since only one model can be chosen at deployment.\n\n3. The attacks used for evaluating the empirical adversarial robustness are too weak. Only 10 steps are used. More iterative steps, e.g., 1000 or 10000 step PGD I-FGSM, should be provided to reveal the actual robustness of the networks in Figure 4,5.\n\n4. The results of the proposed algorithm in Figure 7 is much better than the state-of-the-art, but I cannot see clearly from this paper how such improvement is achieved. With a ResNet110, [1] and [2] can only achieve around 30% certified accuracy when the maximum l_infty norm is 8/255. However, in Figure 7, the proposed algorithm is able to keep the certified accuracy above 40% at much larger perturbations, with only a 3-conv-layer network. If I am understanding the numbers correctly, could the authors explain clearly where such improvements come from?\n\nTherefore, I tend to reject the paper before my concerns are addressed.\n\n[1] \"Filling the Soap Bubbles: Efficient Black-Box Adversarial Certification with Non-Gaussian Smoothing\", https://openreview.net/forum?id=Skg8gJBFvr\n[2] Salman, Hadi, et al. \"Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers.\" NeurIPS (2019).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgntIT-qH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "In this submission, the authors address a challenging task, in which the goals are three-fold: 1) preserve the privacy of training data in terms of DP; 2) both provably and practically robust to adversarial examples; and 3) maintain high model utility. The authors demonstrate the advantage of the proposed method both theoretically and experimentally. \n\nOverall, this is a solid work. However, I have the following concerns. If the authors can clarify them during the rebuttal, I am willing to increase my review score.\n\n1) On page 9, the authors mentioned several existing DP-preserving algorithms with provable robustness. Could the authors clearly state the novelty of the proposed method given these existing methods? Thus it would be clear to access the technique contribution of this submission.\n\n2) How about the scalability of the proposed method when applying to real-world scenarios? In the experiment part, the authors show the results on MNIST and CIFAR-10; however, the scale of these two datasets are kind of small compared to real-world applications. Can the authors experimentally show the scalability of the proposed method by increasing the number of samples?\n\n3) This question will not be counted towards the review: Do the authors try other datasets? MNIST and CIFAR-10 are relatively simple image datasets, how about real images? How about non-image datasets? \n\n4) This submission is longer than 8 pages, it is OK. But the main results are actually in appendix, and the reviewers are forced to read more than 10 pages. It would be better to adjust the contents and have a balanced organization.\n\nA good thing to mention is: It is great to see that the authors conduct experiment comparison and analysis with a relatively small value of epsilon (i.e., epsilon = 0.2).", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1geoEjdYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 focus on providing both differential privacy and adversarial robustness to machine learning models. The authors propose an algorithm called differentially private adversarial learning (DPAL) to achieve such goal. DPAL consists two sub-models: (1) An auto-encoder to extract feature representation; and (2) A classifier takes the embedding of encoder and return the predict logits. The auto encoder uses the reconstruction loss and the classifier uses the similar loss as in adversarial learning. \n\nThe auto-encoder takes both real and adversarial examples as input. In order to guarantee  differential privacy to both sub-models, the authors use Functional Mechanism (Zhang et al., 2012), which perturbs the objective function to guarantee the objective is differentially private. To apply functional mechanism, the authors use the 1st-order polynomial approximation of both objective functions (by Taylor Expansion). Laplace noise is injected to both network input and the output of encoder to ensure the objective functions are differentially private (i.e. for any given weight, the influence of individual record on loss value is DP preserved). The authors further show the noise to guarantee privacy can be convert to PixelDP (Lecuyer et al., 2018) and therefore leads to provable robustness against adversarial examples. \n\nOverall, this paper studies an interesting setting when privacy guarantee and adversarial robustness are both needed in machine learning model and proposes an algorithm to achieve such goal. The paper is well-organized. However, the paper suffers from several critical questions. I do not support the acceptance unless the following questions are well addressed.\n\n1.\tThe approximation is necessary to derive the privacy guarantee for the objective function. But the paper does not provide either theoretical analysis on the approximation error or empirical result of the distance between the approximate and real function values.  Another way is to use the approximate loss as the objective function to train the models and see how the model performance changes. \n2. The differentially private objective does not lead to differentially private parameters.  In the proof of your Theorem 1, it is clear that the reconstruction loss in Algorithm 1 is differentially private. However, this does not lead to differentially private parameters. In Zhang et al., 2012, the resulting parameters are differentially private only if finding the minimizer of the perturbed objective does not involve any additional information from the original database (see the proof of their Theorem 1). One way is using data-independent grid search to find parameters with low loss. However, Algorithm 1 uses gradient descent to update the parameters, which needs to access the original database at each update. Though the paper uses a perturbed database, the perturbation is not sufficient to provide the privacy level as claimed in Theorem 1. \n\nMinor comments:\n1.\tWhen is \\chi_2 in Algorithm 1 being used? In Algorithm1, I do not see its appearance apart from its definition.\n2.\tAt the end of Introduction, you claim DPAL establishes the first connection between DP preservation and provable robustness. However, in the experiments section, SecureSGD and SecureSGD-AGM are given as baseline algorithms which are DP-preserving algorithms with provable robustness. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a framework for relating adversarial robustness, privacy and utility and show how one can train models to simultaneously attain these properties. The paper also makes interesting connections between the DP literature and the robustness literature thereby porting over composition theorems to this new setting.

The paper makes very interesting contributions, but a few key points require some improvement:
1) The initial version of the paper relied on an approximation of the objective function in order to obtain DP guarantees. While the authors clarified how the approximation impacts model performance in the rebuttal and revision, the reviewers still had concerns about the utility-privacy-robustness tradeoff achieved by the algorithm.

2) The presentation of the paper seems tailored to audiences familiar with DP and is not easy for a broader audience to follow.

Despite this limitations, the paper does make significant novel contributions on an improtant problem (simultaneously achieveing privacy, robustness and utility) and could be of interest. 

Overall, I consider this paper borderline and vote for rejection, but strongly encourage the authors to improve the paper wrt the above concerns and resubmit to a future venue.
Decision: Reject