Title: TOWARDS CERTIFIED DEFENSE FOR UNRESTRICTED ADVERSARIAL ATTACKS

Abstract: Certified defenses against adversarial examples are very important in safety-critical applications of machine learning. However, existing certified defense strategies only safeguard against perturbation-based adversarial attacks, where the attacker is only allowed to modify normal data points by adding small perturbations. In this paper, we provide certified defenses under the more general threat model of unrestricted adversarial attacks. We allow the attacker to generate arbitrary inputs to fool the classifier, and assume the attacker knows everything except the classifiers' parameters and the training dataset used to learn it. Lack of knowledge about the classifiers parameters prevents an attacker from generating adversarial examples successfully. Our defense draws inspiration from differential privacy, and is based on intentionally adding noise to the classifier's outputs to limit the attacker's knowledge about the parameters. We prove concrete bounds on the minimum number of queries required for any attacker to generate a successful adversarial attack. For a simple linear classifiers we prove that the bound is asymptotically optimal up to a constant by exhibiting an attack algorithm that achieves this lower bound. We empirically show the success of our defense strategy against strong black box attack algorithms.

1. INTRODUCTION:

Classifiers trained using machine learning can often achieve high accuracy on test data coming from the same distribution as the training one. Unfortunately, for a class of inputs called adversarial examples (Szegedy et al., 2014) , many classifiers can be fooled to give wrong predictions with high confidence. This poses a significant security risk for real world deployment of machine learning models. To mitigate this threat, many methods have been proposed to defend against adversarial examples (see, e.g., Papernot et al. (2016) ; Song et al. (2018a) ; Ma et al. (2018) ; Buckman et al. (2018) ). However, empirically grounded methods are often found to be ineffective using newer attack methods that they had originally not considered (Carlini & Wagner, 2017; Athalye et al., 2018) . To end this arms race, defenses with certified theoretical guarantees against a threat model have recently gained more traction (see, e.g., Raghunathan et al. (2018) ; Wong & Kolter (2017) ; Dvijotham et al. (2018) ; Cohen et al. (2019) ).

Existing certified defense methods are all restricted to perturbation-based attacks (Song et al., 2018a) , a threat model where the attacker is only allowed to generate an adversarial example by perturbing existing data points using small adversarial noise. In addition, a certified defense for one type of perturbation (e.g., based on l 2 norm) can still be vulnerable to a different type of perturbation (e.g. spatial transform (Xiao et al., 2018) ). Following Song et al. (2018b) and Brown et al. (2018) , we consider the much more general threat model of unrestricted adversarial attacks, where the small perturbation restriction is removed: any input is considered a valid adversarial example as long as it induces the classifier to predict a different label than an oracle classifier. As shown in Song et al. (2018b) , existing certified defenses are not robust to unrestricted adversarial attacks.

In this paper, we provide a defense strategy with (asymptotically) certified guarantees against unrestricted adversarial attacks. The attacker can use any strategy to choose any input, and the attack is successful as long as the input is confidently classified into the wrong class by the target classifier. Note that in the white-box setup, where the attacker has access to all parameters of the classifier, defending against unrestricted adversarial examples is essentially impossible unless the classifier is perfect, because the attacker can simply enumerate all possible inputs to find adversarial ones (we do not assume any computational restriction of the attacker). As a result, we focus our discussion on black-box unrestricted attacks, where the attacker does not know the exact parameters of the model nor the exact training data (otherise, the attacker could recover the parameters by simulating the learning algorithm), but can query the model for a limited number of times before making unrestricted adversarial examples. For example, for online services, it is easy to limit the number of queries allowed per user.

Consider a classifier learned using empirical risk minimization. Because the training data are randomly drawn from the data-generating distribution, the parameters of the classifier will be random even if the training algorithm is deterministic. Since we assume a black-box setting where the attacker does not know the learned parameters or the training dataset, the attacker has to obtain extra information by querying the model, even though the exact training algorithm and even the data-generating distribution might be known to the attacker. As a result, we can adopt methods similar to those used in differential privacy (Dwork et al., 2014) to reduce the amount of information about the parameters leaked from each query issued by the attacker.

We give concrete lower bounds on the minimum number of queries an attacker needs in order to successfully generate adversarial examples. For most classifiers the guarantees are asymptotic, meaning that the guarantees are valid if the number of training examples is sufficiently large. For very simple classifiers we prove finite sample guarantees. Our bound is also asymptotically minimax optimal with respect to important parameters of the problem -the dimension of the input and the size of the training set. We prove this by exhibiting a class of classifiers and a concrete attacking algorithm that successfully generates adversarial examples while querying no more than the minimum necessary according to the lower bounds (up to a constant).

Experimentally, we show that the defense strategy is effective against strong black-box unrestricted attacks, even when we use complex classifiers for which no theoretical guarantee with finite sample size is available. Compared to models without any defense, the number of queries needed to identify vulnerabilities often increases by an order of magnitude using our defense strategy, with negligible effect on the accuracy on "clean" inputs. Providing finite sample guarantees for complex models such as deep neural networks is an open problem for future work.

2. PROBLEM DEFINITION:

2.1 CLASSIFICATION Given a training dataset {(x i , y i ) ∈ X × Y} n i=1 i.i.d.

∼ p * (x)p * (y | x), we consider the task of learning a classifier to predict the label y for an input x. To simplify our discussion, we assume that X = [-1, 1] d , and Y = {-1, 1}. Let {g(w, •) : X → R} be a class of score functions with parameter w, whose signs determine the class labels, i.e., y = sign(g(w, x)), where we define sign(x) = 1 when x ≥ 0, and sign(x) = -1 otherwise. The model family is assumed to be well-specified, i.e., there exists a ground-truth parameter w * such that the true labeling function is given by y = sign(g(w * , x)).

We can use any learning algorithm to obtain w based on a training dataset. Since the training data are randomly generated from the underlying distribution p * (x)p * (y | x), w is also a random vector and we denote its distribution as p learn (w). With a reasonable learning algorithm, p learn (w) should be increasingly concentrated around w * while the size of the training dataset n grows. When deploying the classifier to real world applications, we might want to use a (possibly stochastic) surrogate score function f (w, •) : X → R which depends on the learned parameter w of our model. Usually, it is just g(w, •), but to mitigate adversarial attacks we might choose f (w, •) to be some special classifier with a defense strategy. To avoid low confidence incorrect predictions, we give no response when the confidence is low. Specifically, we allow a threshold α ∈ R + such that given an input query x, the predicted label is

y =    1, if f (w, x) > α -1, if f (w, x) < -α No response,

otherwise.

(1) PROTOCOL 1. THE ATTACK-DEFENSE PROTOCOL Attacker knowledge: w * , p learn (w), T , g(•, •), f (•, •).

Interacting procedure:

1. The attacker chooses the distributions q t , t = 1, • • • , T and Q attack defined as below.

2. The defender samples w ∼ p learn (w).

3.. For:

t ← 1, • • • , T (a) The attacker observed o 1:t-1 = (x 1 , z 1 ), • • • , (x t-1 , z t-1

) and sample x t ∼ q t (x t |o 1:t-1 ) as the next query. (b) The defender sends z t = f (w, x t ) to the attacker. 4. The attacker samples q ∼ Q attack (q | o 1:T ), where q is a probability distribution on X . The attacker outputs q(x).

Figure 1 : The attack-defense protocol

2.2. PERFORMANCE EVALUATION:

We evaluate the expected performance of the classifier f (w, x) on a test distribution q(x)p * (y | x).

The traditional setting in statistical machine learning assumes that q(x) = p * (x). In adversarial settings, however, q(x) is the distribution of adversarial examples and is very different from p * (x).

Since we consider unrestricted attacks, we assume no relationship between q(x) and p * (x).

The classifier f (w, x) can make two kinds of errors for a given input x. First, f (w, x) might give no response. We call this the no-response error, which is denoted as

NR(x; α) I(|f (w, x)| ≤ α),

where I[P] is the indicator function whose value is 1 when the property P holds; other it produces 0.

Secondly, f (w, x) can produce a wrong prediction with high confidence. We call this the margin error, which is defined as

ME(x; α) = I(g(w * , x) < 0 ∩ f (w, x) > α) + I(g(w * , x) > 0 ∩ f (w, x) < -α).

An ideal classifier f (w, x) should minimize the expected no-response error E q(x) [NR(x; α)] and margin error E q(x) [ME(x; α)] simultaneously. When defending against an adversary, the margin errors are more important because a confident but wrong prediction is arguably more harmful than giving no prediction at all. Consequently, we only focus on bounding the margin errors achievable by attackers in the sequel. We will only consider no response error for clean data x ∼ p * (x).

2.3. THE ATTACK-DEFENSE PROTOCOL:

In Figure 1 , we provide a specific protocol of attack and defense to capture our assumptions of the threat model. Since we consider the threat model of unrestricted adversarial attacks, we assume the attacker to be fully general: The attacker is allowed to use any adaptive set of intermediate distributions {q t (x | o 1:t-1 )} T t=1 to issue queries based on all previous observations. For the final attack distribution q, the attacker is allowed to sample it from any distribution of distributions Q attack (q | o 1:T ). We call a specific choice of {q t (x | o 1:t-1 )} T t=1 and Q attack an attack strategy, and a specific choice of p learn (w) and f (•, •) a defense strategy. We additionally allow the attacker to know the exact defense strategy. Note that when the attack and defense strategies are fixed beforehand, the attack-defense protocol defines a joint probability over w, o 1:T and q.

The protocol can be modified in the defender's favor if defender only sends y t according to Eq.(1) instead of z t . However, using z t allows normal users (sampling from p * (x)) to get a confidence score, and any certified defense results are more general (they are still true if attacker only has access to y t ).

Intuitively, the attack strategy is successful under the attack-defense protocol, if with high probability the final attack distribution q incurs large expected margin errors for f (w, x). To formalize this intuition, we define a winning strategy of the attacker as follows.

Definition 1. For a given defense strategy, an attack strategy in the attack-defense protocol is an (α, γ, δ)-winning strategy if with probability at least γ, the attacker outputs a q such that Pr q(x) [ME(x; α)] ≥ δ.

In the following part, we will propose a concrete defense strategy and prove that no winning strategies can exist under some conditions.

3. TOWARDS A CERTIFIED DEFENSE:

In order for a certified defense strategy to exist we need some reasonable conditions on the problem. All the proofs are available in the appendix.

3.1. DEFENSIBILITY:

For an omniscient attacker who knows f (w, •) and g(w * , •) (this is beyond the capabilities granted by our attack-defense protocol), there will not be any effective defense strategies unless f (w, x) never produces wrong predictions. This is because the attacker can simply enumerate an input x bad so that |f (w, x bad ) -g(w * , x bad )| is maximal, and set q(x) = δ x bad (here δ x denotes a point mass distribution on x). This results in the maximal average margin error for f (w, x).

Under our attack-defense protocol, the attacker does not have access to w and hence do not know f (w, •). The randomness of p learn (w) makes it more difficult for the attacker to infer w through queries. To guarantee the existance of a certified defense for all attacks, we need to make sure the randomness of p learn (w) is sufficient such that no fixed distribution q(x) can incur large average margin error for f (w, •) with high probability for a random draw of w ∈ p learn (w). We formalize this intuition as the following condition. Condition 1. Given a classifier g(•, •), margin α, and true parameter w * , a distribution p learn (w

) is t-defensible if ∀x ∈ X , we have E p learn (w) [|g(w, x) -g(w * , x)| ≥ α] ≤ e -t .

In other words, the above condition says that if p learn (w) is t-defensible, there will not exist any x ∈ X such that g(w, x) significantly deviates from the ground-truth score g(w * , x) with large probability over w ∼ p learn (w).

3.2. QUERY PRIVACY:

As discussed before, the attacker cannot find an attack distribution q a-priori to fool f (w, •) when p learn (w) is t-defensible. To strive for successful attacks, the attacker must then obtain more information about the specific w used by the defender through queries. Therefore, a successful defense strategy should not leak too much information through each query from the attacker. We formalize this intuition as follows. Condition 2. A defense strategy in the attack-defense protocol is s-query private if for any x ∈ X we have I(z; w | x) ≤ s.

3.3. CERTIFYING THE DEFENSE STRATEGY:

To satisfy this condition and prevent leakage of information on w, we take inspiration from differential privacy and perturb the scores with Gaussian noise. By adding the right amount of noise, we hope to hit the sweet spot where the accuracy on clean input x ∼ p * (x) is mostly preserved, while at the same time the attacker obtains least information from queries. We use the following stochastic surrogate function f (•, •) as the key of our defense strategy.

f (w, x) = g(w, x) + N (0, τ 2 ) (2)

As the first main result of our paper, the following theorem asserts that under the above two conditions no attacker has a winning strategy using a limited number of queries. Theorem 1. Suppose p learn (w) is t-defensible, and the defense strategy is s-private. ∀α > 0, 0 < γ, δ < 1, and for τ 2 ≤ α 2 8 log 2/δ , there is no (2α, γ, 2δ) winning strategy if T ≤ 1 s (γt+γ log δ-log 2).

Note that in the definition above s implicitly depends on τ 2 . Adding more noise (larger τ 2 ) reduces the amount of leaked information on w.

In practice, it can be hard to verify the defensibility of p learn (w) or the query-privacy of the defense strategy for complicated models. In the following, we show examples of simple models where these two conditions are either strictly satisfied or asymptotically satisfied in the limit of infinite data. In the next section, we will first show that for logistic regression and kernel logistic regression models, the conditions hold asymptotically when the models are well-specified. After that, we show that the conditions can hold exactly for a simple naïve Bayes model. We leave the analysis of defensibility and query-privacy for more complicated models as an open problem for future research.

3.4. ASYMPTOTIC ANALYSIS OF (KERNEL) LOGISTIC REGRESSION:

We start by considering a linear model g(w, x) = (w, x), where (•, •) denotes the inner product in Euclidean space. One common approach to learning this model is logistic regression. When the model is well-specified, i.e., there exists w * such that p * (y

| x) = 1 1+exp(-y(w * ,x))

, we can prove that p learn (w) converges in distribution to a Gaussian distribution with mean w * as n → ∞. Specifically, we have the following lemma.

Lemma 1. Assume that w * ≤ λ. Given i.i.d. samples {(x i , y i )} n i=1 ∼ p * (x)p * (y | x)

, the estimator w n obtained by solving the following objective function

max w ≤2λ 1 n n i=1 log(1 + e -yi(w,xi) ) is consistent. Moreover, √ n(w n -w * ) d → N (0, Σ), where Σ = (E x [p(y = 1 | x)(1 -p(y = 1 | x))xx ]) -1 .

The asymptotic Gaussianity of p learn (w) greatly facilitates the investigation in its defensibility. However, the assumption that a linear model g(w, x) being well-specified is rather restrictive. We therefore additionally consider a generalization called kernel logistic regression, where g(w, x) = w, φ(x) . Here φ(x) is the natural basis vector of the Reproducing Kernel Hilbert Space H corresponding to a kernel k(•, •), and we use •, • to denote the inner product in H. When the kernel is universal (Micchelli et al., 2006) , e.g., the Gaussian RBF kernel, functions in RKHS can approximate any bounded continuous function arbitrarily well w.r.t. the uniform norm. Therefore, it is a much milder assumption that there exists w * ∈ H such that p * (y | x) = 1 1+exp(-y w * ,φ(x) ) . For kernel logistic regression, we can similarly prove that p learn (w) is asymptotically Gaussian (see Lemma 6 in the appendix), with asymptotic variance

Σ H = (E x [p(y = 1 | x)(1 -p(y = 1 | x))φ(x) ⊗ φ(x)]) -1 ,

where ⊗ denotes the tensor product.

For both logistic regression and kernel logistic regression, under the assumptions of well-specification and in the asymptotic regime, we can prove both defensibility and query privacy. Formally, Proposition 1. For logistic regression, the asymptotic distribution of p learn (w) is nα 2 2 Σ 2 d -defensible and our defense strategy is

Σ 2 d 2nτ 2 -query private. For kernel logistic regression, the asymptotic distribution of p learn (w) is nα 2 2 Σ H op

-defensible, and our defense is

Σ H op 2nτ 2 -query private.

Therefore, our defense strategy is asymptotically certified for logistic regression and kernel logistic regression models.

3.5. NON-ASYMPTOTIC VERIFICATION OF ASSUMPTIONS:

Asymptotic conditions hold for sufficiently large training set size n, but to be fully verifiable we need results that hold for finite n. These bounds are very difficult to obtain, and we show some bounds for very simple classifiers (naive Bayes).

Before showing the results for naive Bayes classifiers, we first show defensibility of computing averages.

Proposition 2. Let p(x) be any distribution with covariance Σ and w

* = E p(x) [x]. Let x 1 , • • • , x n ∼ p(x) and w = 1 n i x i , then the distribution of w is nα 2 2d Σ 2 +2/3dα -defensible.

Note that the results of this theorem is almost as good as if we knew the distribution p(x) is Gaussian N (0, Σ). In that case, we can apply Proposition 1 and conclude that it is nα 2 2d Σ 2 -defensible.

The following Corollary shows a similar bound for a naive Bayes classifier. This is a direct outcome of the above proposition.

Corollary 1. Let p(x|y = 0) and p(x|y = 1) be distributions with covariance Σ, and

w * = E p(x|y=1) [x] -E p(x|y=0) [x]. Let x 1 , • • • , x n ∼ p(x|y = 0) and x 1 , • • • , x n ∼ p(x|y = 1). If we choose w = 1 n i x i -1 n i x i , then it is nα 2 4d Σ 2 +4/3dα -defensible.

Therefore, we can use the training data to upper bound Σ 2 (El Karoui et al., 2008) and obtain a non-asymptotic certificate of defensibly.

For query privacy non-asymptotic guarantees are easier to get. All we need is to upper bounding the covariance spectral radius of p learn (w).

Proposition 3. If g(w, x) = (w, x) and p learn (w) has covariance Σ, it is d Σ 2 2τ 2 -query private.

4. RATE ANALYSIS AND MINIMAX OPTIMALITY:

To demonstrate more concrete asymptotic rates, we will analyze a simple setup. We study a classifier with g(w, x) = (w, x) and p learn (w) = N (w * , σ 2 I) where σ 2 = 1/n. We also assume that w * ∞ < b for some b > 0 (we need b to be fixed as we analyze the asymptotic rate when d → ∞). We give an example of a classifier where this distribution could arise in the appendix. Based on this setup, we have the following specialization of Theorem 1.

Corollary 2. There is no (2α, γ, 2δ) winning strategy if

T < α 4 n 2 γ 2d 2 log 2/δ + o(n) if we choose τ 2 = α 2 2 log 2/δ .

This bound is desirable if α 1 (there is a large margin) and n d (more data than input dimensions).

4.1. AN ATTACKER STRATEGY:

Corollary 2 is the minimum number of queries any attacker strategy needs to win. Now we show a concrete attacker strategy that (almost) achieves this lower bound.

The concrete attacker strategy is shown below. Intuitively, the attacker queries each of the d dimensions of the input x ∈ R d to find out the sign of ww * . The attacker finds a x such that (x, ww * ) is large but (x, w * ) < 0. PROTOCOL 2. THE SIGN ATTACK PROTOCOL 1. Defender samples w ∼ p learn (w).

2.. For round:

= t = 1, • • • , T (a) Attacker chooses x t = t mod d , where i is the i-th basis vector for R d . (b) Defender sends z t = (x t , w) + N (0, τ 2 ) to attacker. Theorem 2. For any 0 < γ < 1, α > 0, if d is sufficiently large, the attacker in Protocol 2 is a α, 1, 1-γ 2 winning strategy if T = 20α 4 n 2 d 2 if n ≤ d 2

160α 2 log 2/δ and we choose τ 2 = α 2 2 log 2/δ ; it is a α, 1, 1-γ 2 winning strategy when T = 2α

√ n if we choose τ 2 = 0.

The extra condition n ≤

d 2

160α 2 log 2/δ ensures that adversarial examples actually exist; if the classifier is sufficiently accurate (i.e. ww * 1 ≤ α), then no example will be falsely classified.

4.2. RATE SUMMARY AND COMPARISON:

Note that Corollary 2 is a lower bound on required number of queries: no attacker can have high success rate unless T > α 4 n 2 γ 2d 2 log 2/δ ; while Theorem 2 is an upper bound: with

T = 20α 4 n 2 d 2

there is at least one attacker that can achieve high success rate. The two bounds have the same asymptotic with respect to α, n and d, which shows that the bound is asymptotically optimal with respect to these parameters.

To better study the asymptotic behavior for large d and large n, we will choose α = √ d. For both methods Pr p * (x) [NR(x)] can be arbitrarily small for sufficiently large d. This is proved in the Appendix. We have the following rates for the smallest T such that an attacker can have a (α, 1, 1-γ 2 ) winning strategy for any γ > 0 and α = √ d. With this choice of α, T no longer depend on d for both upper and lower bounds, and we can get:

• For defended classifier with τ 2 = α 2 2 log 2/δ we have T = Θ(n 2 ) queries. • For undefended classifier with τ 2 = 0 we have T = O(n).

5. EXPERIMENTS:



5.1. LINEAR MODELS:

We will first verify our method empirically on linear classification tasks. We will use two classification datasets.

Synthetic Gaussian. For this dataset we randomly sample w * from a standard Gaussian, sample p(x|y = 1) = w * + N (0, σ2 I) and p(x|y = 0) = -w * + N (0, σ2 I) and finally clip x to between [-1, 1]. We choose σ such that w * is the optimal logistic regression weight for p(y|x) = 1 1+e -(w * ,x) . Mnist. Because linear models cannot classify MNIST with high accuracy, we use deep network features (last layer of a pretrained AlexNet) as the input X instead of the pixel space. We train with the entire dataset and use the resulting vector as w * (for the attacker).

Attack Methods. We will use two attacking method: the first one is the attack strategy of Protocol 2 (which we will denote the sign attack); the second one is Simba (Guo et al., 2019) , a recently proposed black-box attacking algorithm with very good empirical performance.

Classifiers. We will use two classifiers, the naive Bayes classifier defined in Corollary 1 and logistic regression. For both classifiers we choose α such that the no-response rate on p * (x) (estimated using the validation dataset) is no more than 10%. We either choose τ 2 = 0 (undefended) or τ 2 = α 2 2 log 2/δ as in Theorem 1 (defended) where δ is chosen to be 5%.

5.1.1. RESULTS:

The results are shown in Figure 2 . For defended classifier, the number of queries required for successful attack typically increases by an order of magnitude. In addition, the effect on the clean data p * (x) is almost negligible. Another interesting observation is that, the naive Bayes classifier actually performs much better in terms of adversarial robustness than logistic regression. We conjecture that this is because logistic regression has high parameter estimation variance tr(Cov(w)) compared to naive Bayes. This indicates that adversarial robustness has very different requirements compared to classification accuracy. Even though logistic regression usually performs better in classification unless the training data size is tiny (Ng & Jordan, 2002) , its adversarial robustness is poor. 

5.2. DEEP MODELS:

Figure 3 : Success rate vs. number of queries for Simba attacker on Inception network. We adjust the threshold such that both methods have similar no response rate (NR) on the clean data. The undefended network is significantly more vulnerable to attack.

Our theoretical guarantees are far from effective for deep models. It is unlikely the analysis will be effective for current network architectures, so special architectures and analysis will be necessary for certified defense under out framework. Nevertheless we perform simple experiments on deep networks to empirically verify that our defense strategy can effectively protect our model against black box attack methods. The setup is identical to (Guo et al., 2019) on ImageNet, except we add a threshold α to the output sigmoid probabilities: if no class has a predicted probability greater than the threshold α, the model answers "I don't know". Here we choose α = 0.7.

The results are shown in Figure 3 . Similar to linear models, defended models require orders of magnitude more queries to attack. We hope these promising experimental performance will motivate further theoretical analysis and empirical investigation.

6. DISCUSSION:

In this paper we propose a new type of adversarial defense guarantee, one based on the concept of defensibility and query privacy. We show theoretical guarantees for simple classifiers and good empirical performance for complex classifiers.

Several open questions remain to be answered. The first one to verify defensibility and query privacy for more complex classifiers. The second one is to design classifiers with better defensibility and query privacy properties. The third one is large scale empirical investigation of the defense strategy or similar defense strategies, i.e. studying the performance of adding noise to different layers of a deep neural network against a larger suite of black box attack algorithms. We hope our work can serve as a first step in this exciting direction of research.

A APPENDIX:

A.1 PROOFS RELATED TO THE LOWER BOUND OF T Proof of Theorem 1. If a strategy is (2α, γ, 2δ) winning then with probability γ 3) is true one of the following must be true

Pr q(x) [|g(w, x) -g(w * , x) + N (0, τ 2 )| ≥ 2α] ≥ 2δ (3) Because |g(w, x) -g(w * , x) + N (0, τ 2 )| ≤ |g(w, x) -g(w * , x)| + |N (0, τ 2 )|. If Eq.(

Pr[|N (0, τ 2 )| ≥ α] ≥ δ (4) Pr q(x) [|g(w, x) -g(w * , x)| ≥ α] ≥ δ (5)

For Eq.( 4) we can bound by

Pr[|N (0, τ 2 )| ≥ α] ≤ 2e -α 2 2τ 2

Therefore, Eq.( 4) is false if the RHS is less than δ, which is when τ 2 ≤ α 2 2 log 2/δ . now we show the condition for Eq.( 5) to be true. We first define the following notation.

• X (w) = {x : |g(w, x) -g(w * , x)| ≥ α} • M (x) = {w : |g(w, x) -g(w * , x)| ≥ α}

• Let q be any distribution on X , let q(X (w)) denote the probability mass q assigns to X (w).

The following lemma is needed.

Lemma 2. In out attack-defense protocol, if with probability at least γ, we have

Pr[|g(w, x) - g(w * , x)| ≥ α] ≥ δ, then I(w; o 1:T ) ≥ γ(t + log δ) -log 2.

Therefore, if I(w; o 1:T ) < γ(t + log δ) -log 2, Eq. ( 5) is false with at least γ probability. If we additionally have the condition that the attack-defense protocol is s-private, by a sequence of data processing inequalities, and by the fact that x t only depends on w through o <t , and y t only depends on x t and w, we have

I(w; o 1:T ) = I(w; o <T ) + I(w; x T |o <T ) + I(w; y T |x T , o <T ) ≤ I(w; o <T ) + I(w; y T |x T ) ≤ • • • ≤ T t=1 I(w; y t |x t ) ≤ T s

Therefore Eq. ( 5) is false with at least γ probability if

I(y t ; w|x T ) ≤ sT < γ(t + log δ) -log 2 which is equivalent to T < 1 s (γt + γ log δ -log 2).

What remains is to prove Lemma 2, which we do below.

Proof of Lemma 2. By the condition of t defensibility we have

E p learn (w) [q(X (w))] = E p learn (w) E q(x) [I(x ∈ X (w))] = E q(x) [I(w ∈ M (x))] = E q(x) E p learn (w) [I(w ∈ M (x))] ≤ E q(x) [e -t ] = e -t

We abbreviate E p learn (w) by E w . Define s(q; w) = max(q(X (w)), e -t ), then

E w [s(q; w)] ≤ E w [q(X (w))] + E w [e -t ] ≤ 2e -t = e -t+log 2

In addition we have

E w [E Q(q) [s(q; w))]] = E Q(q) [E w [s(q; w))]

] ≤ e -t+log 2 . Finally by Donsker-Varadhan inequality,

E w E Q(q|w) [log s(q; w)] ≤ E w KL(Q(q | w) Q(q)) + E w log E Q(q) [e log s(q;w) ] ≤ I(q; w) + log E w E Q(q) [s(q; w)] ≤ I(q; w) -t + log 2

Suppose δ > e -t , log q(X (w)) ≥ log δ if and only if log s(q; w) ≥ log δ. In addition, because for all q and w, log s(q; w) ≥ -t, so log s(q; w) + t is a non-negative random variable, and we can apply Markov inequality to get (where the probability and expectation are taken with respect to w ∼ p learn (w) and q ∼ Q(q | w))

γ = Pr[q(X (w)) ≥ δ] = Pr [log q(X (w)) ≥ log δ] = Pr[log s(q; w) ≥ log δ] = Pr[log s(q; w) + t ≥ log δ + t] ≤ E[log s(q; w) + t] log δ + t ≤ I(q; w) + log 2 log δ + t

Rearranging we get I(q; w) ≥ γ(t + log δ) -log 2

Finally because q is a function of o 1:T , we have by data processing

I(w; o 1:T ) ≥ I(w; q) ≥ γ(t + log δ) -log 2

Proof of Corollary 2. First by Lemma 4 we know that p learn (w) is α 2 2σ 2 d -defensible and σ 2 d 2τ 2 -query private. We apply Theorem 1 and choose τ 2 = α 2 2 log 2/δ to conclude that there is no (2α, γ, 2δ) winning strategy if

T ≤ 2τ 2 σ 2 d γ α 2 2σ 2 d + γ log δ -log 2 = α 2 n d log 2/δ γ α 2 n 2d + γ log δ -log 2 A.2 PROOFS RELATED TO THE SIGN ATTACK

Proof of Theorem 2. Under the distribution in Protocol 2, denote

x = (x 1 , • • • , xd ) = (sign( w1 -w * 1 ), • • • , sign( wd -w * d ))

Also denote the probability of attacker producing x given forecaster choose w as q(x | w). By observing the protocol we know that this distribution is factorized, i.e. q(x | w) = q(x 1 | w) • • • q(x d | w). Also denote b * = sign(w -w * ) as the true sign of the error.

Step 1: We show that if q(x i = b * i | w) ≥ 1/2 + β, (x, r * ) is likely large Lemma 3. Under the distribution defined in Protocol 2, suppose for all i we have q(

x i = b * i | w) ≥ 1/2 + β, then Pr (x, r * ) ≥ √ 2 √ π βdσ ≥ 1 -e -2βd/π

Proof of Lemma 3. The proof idea is to first lower bound the expectation, then lower bound the deviation from the expectation.

µ := E[(x, r * )] = i E[x i r * i ] = i E[x i r * i | x i = b * i ] Pr[x i = b * i ] + E[x i r * i |x i = b * i ] Pr[x i = b * i ] ≥ i E[|r * i |](1/2 + β) -E[|r * i |](1/2 -β) = 2βE[ r * 1 ] = 2 √ 2 √ π βdσ Then because (x, r * ) = i xi r * i , where {x i r * i , i = 1, • • • , d} are independent mixtures of Gaussian. In addition xi r * i has a sub-Gaussian tail Pr[x i r * i ≥ c] ≤ Pr[|r * i | ≥ c] ≤ e -c 2 4σ 2 so it is σ 2 /2-sub Gaussian. Combined we have (x, r * ) is σ 2 d/2-sub Gaussian. Therefore Pr[(x, r * ) ≤ µ -cd] ≤ e -c 2 d 2 dσ 2 = e -c 2 d σ 2 If we plug in c = √ 2 √ π βσ we have Pr (x, r * ) ≤ √ 2 √ π βdσ ≤ e -2βd π

Step 2: Lower bound on q(

x i = b * i | w). The first step is to show that xi = b * i with non-negligible probability. Because wi -w * i ∼ N (r * i , τ 2 /T ) and if τ 2 /T ≥ 2σ 2 Pr[x i = b * i ] = Pr[N (0, τ 2 /T ) ≤ |N (0, σ 2 )|] ≥ 1 2 + σ √ T 10τ (6)

The proof of the above statement relies on the following Lemma Lemma 4. Let x ∼ N (0, a 2 ), y ∼ N (0, b 2 ) be independent random variables, then if a ≥ 2b, then

1 2 + b 10a ≤ Pr[x ≤ |y|] ≤ 1 2 + b πa .

Proof of Lemma 4.

Pr[x ≤ |y|] = E y [Pr[x ≤ |y||y]] = E y Φ |y| a Because Φ is concave in [0, +∞) we have E y Φ |y| a ≤ E y |y| a Φ (0) + 1 2 = 1 a 1 √ 2π E y [|y|] + 1 2 = 1 √ 2πa b √ 2 √ π + 1 2 = b πa + 1 2

For a lower bound we have for any u ≥ 0,

E y Φ |y| a ≥ 1 2 + E y I(|y| ≤ ub) |y| Φ (ub/a) -1/2 ub + E y I(|y| > ub) Φ ub a - 1 2 ≥ 1 2 + Φ(ub/a) -1/2 ub E y [I(|y| ≤ ub)|y|]

According to Wikipedia for truncated Gaussians, we know that

E y [y|0 < y < ub] = b φ(0)-φ(u) Φ(u)-Φ(0) , so E y [I(|y| ≤ ub)|y|] = E y [|y|||y| < ub] Pr[|y| < ub] = b φ(0) -φ(u) Φ(u) -Φ(0) 2(Φ(u) -Φ(0)) = 2b(φ(0) -φ(u)) = 2b √ 2π (1 -e -u 2 /2 ) ≡ g(u)b

In addition by the concavity of Φ on [0, +∞) we have

Φ ub a ≥ 1 2 + Φ ub a ub a ≥ 1 2 + φ ub a ub a

Combining the above results we have

E y Φ |y| a ≥ 1 2 + Φ(ub/a) -1/2 ub g(u)b ≥ 1 2 + g(u)φ ub a b a

Now we can plug in numerical results. Let u = 1, and if b/a ≤ 1/2 we get the results in the Lemma.

Step 3: Bound the agreement between x and x. note that x can have high value of (x, r * ), but this is not useful unless in the final x outputted, a large proportion of the dimensions is equal to x. In other words, we need to show that λ cannot be too large.

Lemma 5. In Protocol 2, ∀s > 0, λ < s

√ bd+b d

with probability 1 -e -s 2 /2 , where b is an upper bound on w * ∞ .

To simplify our analysis, we will assume that d is large enough such that λ ≤ 1/2 with probability 1 -γ/2.

Proof of Lemma 5. We know that w * ∞ < b and w 1 = d, then by Hölder inequality have w * 2 2 = (w * , w * ) ≤ w * 1 w * ∞ ≤ bd. For any choice of s > 0 because the distribution of x λd:d do not depend on w * λd:d , and by symmetry arguments x i , i = λd, • • • , d are i.i.d. Bernoulli distributions with zero mean, so they are 1/2 sub-Gaussian. We know that (x λd:d , w * λd:d ) is

d i=λd (wi) 2 2 ≤ w * 2 2 2

≤ bd 2 sub-Gaussian. We can conclude for any s > 0

Pr[(x λd:d , w * λd:d ) ≥ s √ bd] ≤ e -s 2 /2 (7)

Because the assumption (without loss of generality

) that |w * 1 | ≥ |w * 2 | ≥ • • • ≥ |w * d | we know that w * 1:λd 1 ≥ λ w * 1 ≥ λd, so (x 1:λd , w * 1:λd ) = -w * 1:λd 1 < -λd, so with probability at least 1 -e -s 2 /2 (x, w) = (x 1:λd , w * 1:λd ) + (x λd:d , w * λd:d ) ≤ -λd + s

√ note that the algorithm will choose the smallest λ such that (x, w) < 0. In particular, it will not choose a λ such that (x, w) < -b, so we have with probability at least 1-e -s 2 /2 , -λd+s

√ bd ≥ -b, or λ ≤ s √ bd+b d

.

Step 4: Combining the Results. Finally we are in a position to bound ME(x) and prove Theorem 2.

We know that ∀i = 1,

• • • , λd, the distribution of r * i is independent of the choice of x i , (x 1:λd , r * 1:λd ) is λd i=1 x 2

i σ 2 ≤ λdσ 2 sub-Gaussian, so for any s > 0 we have

EQUATION

By Lemma 3 we have

Pr (x λd:d , r * λd:d ) ≥ √ 2 √ π β(1 -λ)dσ ≥ 1 -e 2β(1-λ)d/π

Combined we have

Pr (x, r * ) ≥ √ 2 √ π β(1 -λ)dσ -s √ λdσ ≥ 1 -e 2β(1-λ)d/π -e -s 2 /2

And if we plug in the above condition that λ < 1/2 (which is true with probability 1 -γ/2) we have

Pr (x, r * ) ≥ √ 2 2 √ π βdσ -s √ 2dσ ≥ 1 -e βd/π -e -s 2 /2

By previous analysis we know β ≥ σ √ T 10τ , so we can choose a sufficiently large s and given the choice of s we can choose a sufficiently large d such that

Pr (x, r * ) ≥ 1 2 √ π σ √ T 10τ dσ ≥ 1 -γ/2 So if 1 2 √ π σ √ T 10τ dσ ≥ α we have Pr [(x, r * ) ≥ α] ≥ 1 -γ note that ME(x) = 1 whenever (x, r * ) + N (0, τ 2 ) ≥ α.

Because of the symmetry of the Gaussian distribution, this happens with 1/2 probability if (x, r * ) ≥ α. Therefore we have

Pr[ME(x) = 1] ≥ 1 2 (1 -γ)

We can rewrite the condition as

T ≥ 400πα 2 n 2 τ 2 d 2 = 400πα 4 n 2 64d 2

In particular we can choose

T = 20α 4 n 2 d 2 . This is true if the condition if Lemma 4 is true. That is τ / √ T ≥ 2σ, or T ≤ τ 2 /4σ 2 = α 2 n 8 log 2/δ . Such a T could exist if α 2 n 8 log 2/δ ≥ 20α 4 n 2 d 2 n ≤ d 2 160α 2 log 2/δ Conversely if τ = 0, we have E[ r 1:T 1 ] = √ 2T σ √ π .

In addition by Lemma 5 for large d, λ → 0, so when T < d we have (when d is sufficiently large)

Pr (x, r * ) ≥ T σ √ π = Pr r 1:T 1 ≥ T σ √ π → d→∞ 1

We can similarly show that Pr can be represented as

[ME(x) = 1] ≥ 1 2 (1 -γ) if T σ/ √ π ≥ α,

w n = n i=1 α i φ(x i ),

where α i is a function of {(x i , y i )} n i=1 .

Proof of Proposition 4. We first make a critical observation that l(x, y; w) = log(1 + e -y w,φ(x) ) is convex w.r.t. w. We can then use the convex duality theory to obtain the following equivalent optimization problem. Due to the traditional representer theorem, we know that w * = n i=1 α i (µ * )φ(x i ), where (w * , µ * ) is a saddle point of the max-min problem. This completes our proof.

Proof of Proposition 1. For logistic regression, first we observe that because x ∞ ≤ 1, it must be that

x 2 ≤ √ d. Let Σ = Q T ΛQ where Q is orthonomal and Λ is diagonal. Because Q is orthonormal, Qx 2 ≤ √ d, then x T Σx ≤ sup y: y 2 2 =d y T Λy = sup y: y 2 2 =d i Λ ii y 2 i ≤ sup i Λ ii i y 2 i = Λ 2 d = Σ 2 d

now we can bound defensibility by (x, ww * ) ∼ N (0, x T Σx/n) and

Pr N 0, x T Σx n ≥ α ≤ Pr N 0, Σ 2 d n ≥ α ≤ e -nα 2 2 Σ 2 d

We can also bound mutual information by

I(z; w | x) = H(z|x) -H(z|w, x) = H(N (0, x T Σx/n + τ 2 )) -H(N (0, τ 2 )) = 1 2 log x T Σx/n + τ 2 τ 2 ≤ 1 2 log 1 + Σ 2 d nτ 2 ≤ Σ 2 d 2nτ 2

We can prove similar results for kernel logistic regression. note that Σ = Λ -1 , where

Λ E p(x) [p(y = 1 | x)p(y = -1 | x)φ(x) ⊗ φ(x)] ∈ H ⊗ H.

We will first show that Λ is a bounded operator. This is because for all f ∈ H, we have

Λf = E[p(y = 1 | x)p(y = -1 | x)φ(x) f, φ(x) ] ≤ E[ p(y = 1 | x)p(y = -1 | x)φ(x) f, φ(x) ] ≤ E[p(y = 1 | x)p(y = -1 | x) φ(x) 2 f ] ≤ E[p(y = 1 | x)p(y = -1 | x)] f ≤ f 4 .

Equivalently, Λ op ≤ 1 4 . Due to the Bounded Inverse Theorem, Σ = Λ -1 is also a bounded operator and therefore Σ op < ∞. Therefore, for any x ∈ X ,

φ(x), Σφ(x) ≤ φ(x) Σφ(x) ≤ Σ op .

As a result,

Pr[N (0, φ(x), Σφ(x) ) ≥ αn] ≤ Pr N 0, Σ op n ≥ α ≤ e -nα 2 2 Σ op .

The mutual information can be bounded by

I(z; w | x) = H(z|x) -H(z|w, x) = H(N (0, φ(x), Σφ(x) /n + τ 2 )) -H(N (0, τ 2 )) = 1 2 log φ(x), Σφ(x) /n + τ 2 τ 2 ≤ 1 2 log 1 + Σ op nτ 2 ≤ Σ op 2nτ 2

Proof of Proposition 2. We know that for any

x 0 ∈ X E[(x 0 , r) 2 ] = E   1 n 2 i (x 0 , x i ) 2   = E   1 n 2 i,j (x 0 , x i )(x 0 , x j )   = E 1 n 2 i (x 0 , x i ) 2 + E   1 n 2 i =j x T 0 x i x T j x 0   = 1 n E[(x 0 , x) 2 ] + 1 n 2 i =j x T 0 E[x i ]E[x j ] T x 0 = 1 n E[x T 0 xx T x 0 ] = 1 n x T 0 Σx 0 ≤ d n Σ 2 Because E[(x 0 , r)] = 0, Var[(x 0 , r)] = E[(x 0 , r) 2 ] ≤ d n Σ 2 , by Bernstein inequality Pr[(x 0 , r) ≥ α] ≤ e - nα 2 2d Σ 2 +2/3dα

Proof of Proposition 3. Proof of this proposition utilizes the fact that Gaussian distributions have highest entropy among distributions with the same covariance. Let z = (w, x) + N (0, τ 2 ), because

Var[z|x] = x T Σx + τ 2 ≤ dρ(Σ) + τ 2 , so H(z|x) ≤ 1 2 log dρ(Σ) + τ 2 . I(z; w|x) = H(z|x) -H(z|x, w) ≤ 1 2 log dρ(Σ) + τ 2 τ 2 ≤ dρ(Σ) 2τ 2

Proof of Lemma 1. Let us denote l(x, y; w) = log(1 + e -y(w,x) ). In order to learn w, we minimize the negative likelihood function P n l(x, y; w), and denote w n arg min P n l(x, y; w). We will first prove that w n p → w. As the first step, we prove the uniform law of large numbers of l(x, y; w). notice that |P n l(x, y; w) -l(x , y ; w

E[ sup:

)|] =E 1 n sup w ≤2λ n i=1 i (l(x i , y i ; w) -l(x i , y i ; w * )) ≤ 2 n E sup w ≤2λ n i=1 i l(x i , y i ; w) (i) ≤ 4 n E sup w ≤2λ n i=1 i (w, x i ) = 4 n E sup w ≤2λ (w, n i=1 i x i ) (ii) ≤ 8λ n E n i=1 i x i (iii) ≤ 8λ n E   n i=1 i x i 2   = 8λ √ n ,

where (i) is due to the Ledoux-Talagrand contraction theorem, (ii) is due to Cauchy-Schwarz, and (iii) is due to Jensen's inequality. Using Markov's inequality, we can conclude that with probability 1 -δ, sup w ≤2λ

|P n l(x, y; w) -P l(x, y; w)| ≤ 8λ √ nδ .

Therefore, with probability 1 -δ, P l(x, y; w n ) -P l(x, y; w * ) can be bounded as 0 ≤ P l(x, y; w n ) -P l(x, y; w * ) = P l(x, y; w n ) -P n l(x, y; w n ) + P n l(x, y; w n ) -P n l(x, y; w * ) + P n l(x, y; w * ) -P l(x, y; w * )

≤ 16λ √ nδ .

Furthermore, the smoothness of P l(x, y; w) guarantees that when w n -w * is small enough,

P l(x, y; w n ) -P l(x, y; w * ) = ∇P l(x, y; w * ) (w n -w * ) + 1 2 (w n -w * ) ∇ 2 P l(x, y; w * )(w n -w * ) + o( w n -w * ) ≥ 1 4 λ min (∇ 2 P l(x, y; w * )) w n -w * 2 (i) ≥ 1 4 λ min (Cov[∇P l(x, y; w * )]) w n -w * 2 ,

where (i) is due to Bartlett's identity, and λ min denotes the smallest eigenvalue. Combining the fact that P l(x, y; w n ) p → P l(x, y; w * ) and P l(x, y; w n ) -P l(x, y; w * ) ≥ O( w n -w * 2 ), we can conclude that with probability 1 -δ, there exists a large enough n such that ∀n ≥ n :

w n -w * 2 ≤ 64λ √ nδλ min (Cov[∇P l(x, y; w * )]) ,

and as a simple corollary,

w n p → w * .

Because w n minimizes P n l(x, y; w), we have that whenever w n -w * < λ, ∇P n l(x, y; w n ) = 0. This is equivalent to saying that √ n∇P n l(x, y; w n ) p → 0. Using Taylor expansion, we obtain ∇P n l(x, y; w * ) + ∇ 2 P n l(x, y; w

* )(w n -w * ) + o p (1)(w n -w * ) = ∇P n l(x, y; w n ) = o p ( 1 √ n ), which is equivalent to √ n(P ∇ 2 l(x, y; w * ) + (P n -P )∇ 2 l(x, y; w * ) + o p (1))(w n -w * ) = - √ nP n ∇l(x, y; w * ) + o p (1).

Combining the central limit theorem and Slutsky's theorem, we have

√ n(w n -w * ) d → N (0; E[∇ 2 l(x, y; w * )] -1 Cov[∇l(x, y; w * )]E[∇ 2 l(x, y; w * )] -1 ).

Bartlett's identity asserts that E[∇ 2 l(x, y; w * )] = Cov[∇l(x, y; w * )]. Therefore, the asymptotic variance of √ n(w n -w * ) can be simplified to

Σ Cov[∇l(x, y; w * )] -1 = E xx (1 + e y(w * ,x) ) 2 -1 = E x e (w * ,x) (1 + e (w * ,x) ) 2 xx -1 = (E x [p w * (1 -p w * )xx ]) -1 , where p w * = 1 1+e -(w * ,x) .

Lemma 6. Assume that there exists w * ∈ H such that p * (y | x) = 1 1+exp(-y w * ,φ(x) ) . Assume further that w * ≤ λ, and ∀x : k(x, x) ≤ 1. Suppose we are given a dataset {(x i , y i )} n where

Σ H = (E x [p(y = 1 | x)(1 -p(y = 1 | x))φ(x) ⊗ φ(x)]) -1 .

Proof of Lemma 6. Let us denote l(x, y; w) = log(1+e -y w,φ(x) ), L n (w) = 1 n n i=1 l(x i , y i ; w), and L(w) = E[l(x, y; w)]. Now, we prove the uniform convergence of L n to L. Denote B {w| w H ≤ 2λ}, and consider the expected error

E sup w∈B | Ln (w) -L(w)| = E sup w∈B | Ln (w) -E[l(x, y; w)]| = E sup w∈B 1 n n i=1 l(x i , y i ; w) -E 1 n n i=1 l(x i , y i ; w) ≤ E sup w∈B 1 n n i=1 i [l(x i , y i ; w) -l(x i , y i ; w)] ≤ 2E sup w∈B 1 n n i=1 i l(x i , y i ; w) = 2R[l(x, y; w)]

Now let X(w)

1 n n i=1 i l(x i , y i ; w). note that l(x, y; w) is a 1-Lipschitz function w.r.t. y w, φ(x) . Using the Ledoux-Talagrand contraction theorem, we conclude that R(l(x, y; w)) ≤ 2R(y w, φ(x) ), which can be bounded by noticing that

R(y w, φ(x) ) = E sup w∈B 1 n n i=1 i y i w, φ(x i ) = E sup w∈B w, 1 n n i=1 i y i φ(x i ) ≤ E w H 1 n n i=1 i y i φ(x i ) H ≤ λ 2 n 2 E   n i=1 n j=1 i j y i y j k(x i , x j )   = √ λ 2 n E n i=1 k(x i , x i ) ≤ λ √ n ,

where we assume that k(x, x) ≤ 1, which is satisfied by many universal kernels, such as Gaussian RBF. Taken together, we have next, we prove the asymptotic normality of w n . First, we note that l(x, y; w) is Fréchet differentiable w.r.t. w. This can be verified by the chain rule of Fréchet derivatives, because l(x, y; w) is Fréchet differentiable w.r.t. w, φ(x) , and w, φ(x) is Fréchet differentiable w.r.t. w. Then, we need to focus on the differentiability of ∇ w l(x, y; w) = -y φ(x), • 1 + e y w,φ(x) .

Let g(w) ∇ w l(x, y; w) : H → H. We can further take the Gâteaux derivative of g(w) to get dg(w 0 + t(w -w 0 )) dt = e y w0+t(w-w0),φ(x) (1 + e y w0+t(w-w0),φ(x) ) 2 ww 0 , φ(x) φ(x), • and even compute higher-order Gâteaux derivatives d 2 g(w 0 + t(w -w 0 )) dt 2 = -e y w0+t(w-w0),φ(x) e y w0+t(w-w0),φ(x) -1 e y w0+t(w-w0),φ(x) + 1 3 ww 0 , φ(x) 2 φ(x), • .

Using fundamental theorem of calculus for Gâteaux derivatives, we obtain g(w) = g(w 0 ) + n P e y w * ,φ(x) (1 + e y w * ,φ(x) ) 2 φ(x) ⊗ φ(x) + (P n -P ) e y w * ,φ(x) (1 + e y w * ,φ(x) ) 2 φ(x) ⊗ φ(x) + o p (1) (w -w * ) = √ nP n ∇ w l(x, y; w * ) + √ n P e y w * ,φ(x) (1 + e y w * ,φ(x) ) 2 φ(x) ⊗ φ(x) + o p (1) (w -w * ), where (i) is due to the law of large numbers. Because of ∀x : k(x, x) ≤ 1, the (weak) law of large numbers and the central limit theorem still holds for random variables in H. For the former, we can prove using McDiarmid's inequality, symmetrization, and Jensen's inequality. For the latter, the proof is the same as the traditional proof of CLT using characteristic functions. Similarly, Slutsky's theorem still holds. As a result, the asymptotic distribution of √ n(w n -w * ) is again Gaussian, with mean 0 and variance Σ = (E x [p w * (1 -p w * )φ(x) ⊗ φ(x)]) -1 , where p w * = 1 1 + e -w * ,φ(x)

A.3.1 ADDITIONAL EXAMPLES AND PROOFS FOR SECTION 4:

An example where p learn (w) = N (w * , σ 2 I) Let Ber d (p) be the d dimensional Bernoulli distribution where each dimension independently takes 1 with probability p and -1 with probability 1 -p.

Let p * (x, y) be defined by p(y) = Ber 1 (1/2) and p(x|y = 1) = Ber d (3/4) and p(x| = 0) = Ber d (1/4). We choose w * = 1 2 , 1 2 , • • • , 1 2 and the ground truth score function is g w * (x) = (x, w * ). We draw a dataset of size n from the distribution {x 1 , y 1 , • • • , x n , y n }, to learn w the algorithm simply takes the average i:y i =1 xi i:y i =1 1 -i:y i =-1 xi i:y i =-1 1 . Then by CLT we have p learn (w) = N (w * , σ 2 I), where σ 2 = 3/4n. note that it is possible to obtain non-asymptotic results because w is actually distributed as a multinomial, but we will use the convenience of a Gaussian distribution. 

:

Attacker computes wi = avg{z t |x t = i }. Without loss of generality (by re-indexing the dimensions)|w * 1 | > |w * 2 | > • • • > |w * d |. For i = 1, • • • , λd choose x i = -sign(w * i ), and for i = λd, • • • , d choose x i = sign( wiw * i ).Attacker chooses the smallest λ such that (x, w * ) < 0. She outputs a delta distribution on this x as his attack distribution.

Figures and Tables:

Figure 2: Success rate of attacker vs. number of queries on synthetic dataset and MNIST. Left to right: Left and Middle: the number of attacker queries vs. attack success rate for different training set sizes. Right: the no-answer (NR) and margin error (ME) on clean data x ∼ p * (x). Top to bottom: Top: naive Bayes classifier trained on synthetic Gaussian; Middle: naive Bayes classifier trained on MNIST; Bottom: logistic regression trained on synthetic Gaussian. Logistic regression trained on MNIST fails to achieve robustness for the training set sizes we experimented (up to 10k). For both cases, defended classifiers require orders of magnitude more queries for successful adversarial attack, while the adverse effect on clean data x ∼ p * (x) is negligible.

We choose T = 2α √ n to satisfy it.A.3 PROOFS RELATED TO THE CONDITIONSProposition 4 (Representer Theorem with Hard Constraints). The optimal solution w n arg min e -yi w,φ(xi) )

e -yi w,φ(xi) ) + µ( w -2λ), µ ≥ 0.

w ≤2λ |P n l(x, y; w) -P l(x, y; w)|] =E[ sup w ≤2λ |E[P n l(x, y; w n ) -P n l(x , y ; w)]|] ≤E[ sup w ≤2λ

i=1 i.i.d. ∼ p * (x)p * (y | x). Let ŵn be the solution to the following objective min e -yi w,φ(xi) ). Then we have w n p → w * , and √ n(w n -w * ) d → N (0, Σ H ),

The uniform convergence concludes that L(w n ) p → L(w * ). Using the same arguments as in the proof of Lemma 1, we conclude that w n p → w * .

0 + t(w -w 0 )) dt dt = g(w 0 ) + 1 0 dg(w 0 + t(w -w 0 )) dt (w 0 + t(w -w 0 )) 0 , φ(x) 2 φ(x), • = o( ww * ),we haveg(w) = g(w 0 ) + e y w0,φ(x) (1 + e y w0,φ(x) ) 2 φ(x) ⊗ φ(x)(w -w 0 ) + o p (1)(w -w 0 ).Using the same arguments as in the proof of Lemma 1, we can assert that g(wn ) = o p ( 1 √ n ). Now we can expand L(w n ) in the neighborhood of w * to get √ nP n ∇ w l(x, y; w n ) = o p (1) = √ nP n ∇ w l(x, y; w * ) + P n e y w * ,φ(x) (1 + e y w * ,φ(x) ) 2 φ(x) ⊗ φ(x) + o p (1) (w -w * ) (i) = √ nP n ∇ w l(x, y; w * ) + √

Proof of no-response rate. When α = √ d and τ = 0 we havePr p * (x) [NR(x)] ≤ Pr [|(x, w)| ≤ α] ≤ Pr |(x, r * )| ≤ d/2 -√ d = Pr N 0, dσ 2 ≤ d/2 -√ d → d→∞ 0Similarly for α = √ d and τ = α 2 2 log 2/δ we have Prp * (x) [NR(x)] ≤ Pr (x, w) + N (0, τ 2 ) ≤ α ≤ Pr (x, r * ) + N (0, τ 2 ) ≤ d/2 -√ d = Pr N 0, dσ 2 + d 2 log(2/δ) ≤ d/2 -√ d → d→∞ 0

Peer review (iclr2020):
The authors propose a new certified defense strategy that considers unrestricted black box attacks. The paper provides bounds for the minimum number of queries needed for the attacker to attack the classifier successfully and then the authors prove that they can devise a defender to be robust against that attack. Here are a few points to consider: 1. The paper is a bit difficult to understand (also not well-structured). The specific contributions are not quite clear with respect to the existing literature (which is reviewed in a sparse manner in the paper). Especially, the novelty of the theory and analysis presented here is a bit difficult to assess. 2. The results are not really validating the points they make in the analysis (for example in part 4.2 they talk about upper and lower bounds for number of queries as a function of ?, ?, etc. but they never provide some plots or tables regarding that in the results section). 4. Also, in Fig 2, it is hard to grasp the performance of the defended vs undefended classifiers with respect to the lower and upper bound that they have computed theoretically in the previous section. 5. They emphasize on the “defensibility” and “query privacy” in the analysis but they do not provide anything in the results section considering them. 6. As this is primarily a theoretical paper, focusing on simple classifiers is probably okay, but some sort of empirical comparison with other certified defense strategies is necessary. Just claiming that none of the existing methods would work for unrestricted attacks will not work is not sufficient. Some empirical results to show the specific advantages (e.g., at what budget the existing methods start to fail and the proposed method continues to perform well).