Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 l2 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.

heading: 2 PROBLEM DEFINITION

heading: 2.1 CLASSIFICATION
text: Given a training dataset {(xi, yi) ∈ X × Y}ni=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 plearn(w). With a reasonable learning algorithm, plearn(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)

heading: 2.2 PERFORMANCE EVALUATION
text: 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 Eq(x)[NR(x;α)] and margin error Eq(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).

heading: 2.3 THE ATTACK-DEFENSE PROTOCOL
text: 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 {qt(x | o1:t−1)}Tt=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 Qattack(q | o1:T ). We call a specific choice of {qt(x | o1:t−1)}Tt=1 andQattack an attack strategy, and a specific choice of plearn(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,o1:T and q.
The protocol can be modified in the defender’s favor if defender only sends yt according to Eq.(1) instead of zt. However, using zt 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 yt).
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 Prq(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.

heading: 3 TOWARDS A CERTIFIED DEFENSE
text: 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.

heading: 3.1 DEFENSIBILITY
text: 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 xbad so that |f(w,xbad)− g(w∗,xbad)| is maximal, and set q(x) = δxbad (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 plearn(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 plearn(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 ∈ plearn(w). We formalize this intuition as the following condition. Condition 1. Given a classifier g(·, ·), margin α, and true parameter w∗, a distribution plearn(w) is t-defensible if ∀x ∈ X , we have Eplearn(w)[|g(w,x)− g(w∗,x)| ≥ α] ≤ e−t.
In other words, the above condition says that if plearn(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 ∼ plearn(w).

heading: 3.2 QUERY PRIVACY
text: As discussed before, the attacker cannot find an attack distribution q a-priori to fool f(w, ·) when plearn(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.

heading: 3.3 CERTIFYING THE DEFENSE STRATEGY
text: 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 plearn(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 plearn(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.

heading: 3.4 ASYMPTOTIC ANALYSIS OF (KERNEL) LOGISTIC REGRESSION
text: 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) = 11+exp(−y(w∗,x)) , we can prove that plearn(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 {(xi, yi)}ni=1 ∼ p∗(x)p∗(y | x), the estimator wn 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(wn −w∗) d→ N (0,Σ),
where Σ = (Ex[p(y = 1 | x)(1− p(y = 1 | x))xxᵀ])−1 .
The asymptotic Gaussianity of plearn(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) = 11+exp(−y〈w∗,φ(x)〉) . For kernel logistic regression, we can similarly prove that plearn(w) is asymptotically Gaussian (see Lemma 6 in the appendix), with asymptotic variance
ΣH = (Ex[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 plearn(w) is nα 2
2‖Σ‖2d -defensible
and our defense strategy is ‖Σ‖2d2nτ2 -query private. For kernel logistic regression, the asymptotic distribution of plearn(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.

heading: 3.5 NON-ASYMPTOTIC VERIFICATION OF ASSUMPTIONS
text: 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∗ = Ep(x)[x]. Let x1, · · · ,xn ∼ p(x) and w = 1n ∑ i xi, 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∗ = Ep(x|y=1)[x] − Ep(x|y=0)[x]. Let x1, · · · ,xn ∼ p(x|y = 0) and x′1, · · · ,x′n ∼ p(x|y = 1). If we choose w = 1n ∑ i xi − 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 plearn(w).
Proposition 3. If g(w,x) = (w,x) and plearn(w) has covariance Σ, it is d‖Σ‖2
2τ2 -query private.

heading: 4 RATE ANALYSIS AND MINIMAX OPTIMALITY
text: To demonstrate more concrete asymptotic rates, we will analyze a simple setup. We study a classifier with g(w,x) = (w,x) and plearn(w) = N (w∗, σ2I) 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 < α 4n2γ
2d2 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).

heading: 4.1 AN ATTACKER STRATEGY
text: 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 ∈ Rd to find out the sign of w−w∗. The attacker finds a x such that (x,w−w∗) is large but (x,w∗) < 0.
PROTOCOL 2. THE SIGN ATTACK PROTOCOL
1. Defender samples w ∼ plearn(w). 2. For round = t = 1, · · · , T
(a) Attacker chooses xt = t mod d, where i is the i-th basis vector for Rd. (b) Defender sends zt = (xt,w) +N (0, τ2) to attacker.
3. Attacker computes w̄i = avg{zt|xt = i}. Without loss of generality (by re-indexing the dimensions) |w∗1| > |w∗2| > · · · > |w∗d|. For i = 1, · · · , λd choose xi = −sign(w∗i ), and for i = λd, · · · , d choose xi = sign(w̄i −w∗i ). Attacker chooses the smallest λ such that (x,w∗) < 0. She outputs a delta distribution on this x as his attack distribution.
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α 4n2 d2 if n ≤ d2 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. ‖w −w∗‖1 ≤ α), then no example will be falsely classified.

heading: 4.2 RATE SUMMARY AND COMPARISON
text: Note that Corollary 2 is a lower bound on required number of queries: no attacker can have high success rate unless T > α
4n2γ 2d2 log 2/δ ; while Theorem 2 is an upper bound: with T = 20α4n2
d2 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 Prp∗(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).

heading: 5 EXPERIMENTS

heading: 5.1 LINEAR MODELS
text: 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, σ̃2I) and p(x|y = 0) = −w∗ +N (0, σ̃2I) 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%.

heading: 5.1.1 RESULTS
text: 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
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.

heading: 6 DISCUSSION
text: 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.

heading: A APPENDIX
text: A.1 PROOFS RELATED TO THE LOWER BOUND OF T
Proof of Theorem 1. If a strategy is (2α, γ, 2δ) winning then with probability γ
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.(3) is true one of the following must be true
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;o1:T ) ≥ γ(t+ log δ)− log 2.
Therefore, if I(w;o1: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 xt only depends on w through o<t, and yt only depends on xt and w, we have
I(w;o1:T ) = I(w;o<T ) + I(w;xT |o<T ) + I(w; yT |xT ,o<T ) ≤ I(w;o<T ) + I(w; yT |xT )
≤ · · · ≤ T∑ t=1 I(w; yt|xt) ≤ Ts
Therefore Eq. (5) is false with at least γ probability if
I(yt;w|xT ) ≤ sT < γ(t+ log δ)− log 2 which is equivalent to T < 1s (γ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
Eplearn(w)[q(X (w))] = Eplearn(w)Eq(x) [I(x ∈ X (w))] = Eq(x) [I(w ∈M(x))] = Eq(x)Eplearn(w) [I(w ∈M(x))] ≤ Eq(x)[e −t] = e−t
We abbreviate Eplearn(w) by Ew. Define s(q;w) = max(q(X (w)), e−t), then
Ew[s(q;w)] ≤ Ew[q(X (w))] + Ew[e−t] ≤ 2e−t = e−t+log 2
In addition we have Ew[EQ(q)[s(q;w))]] = EQ(q)[Ew[s(q;w))]] ≤ e−t+log 2. Finally by DonskerVaradhan inequality,
EwEQ(q|w)[log s(q;w)] ≤ EwKL(Q(q | w)‖Q(q)) + Ew logEQ(q)[elog s(q;w)] ≤ I(q;w) + logEwEQ(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 ∼ plearn(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 o1:T , we have by data processing
I(w;o1:T ) ≥ I(w; q) ≥ γ(t+ log δ)− log 2
Proof of Corollary 2. First by Lemma 4 we know that plearn(w) is α 2 2σ2d -defensible and σ2d 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
σ2d
( γ α2
2σ2d + γ log δ − log 2
) = α2n
d log 2/δ
( γ α2n
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, · · · , x̂d) = (sign(w̄1 −w∗1), · · · , sign(w̄d −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̂ir∗i ] = ∑ i E[x̂ir∗i | xi = b∗i ] Pr[x̂i = b∗i ] + E[x̂ir∗i |x̂i 6= b∗i ] Pr[x̂i 6= 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 x̂ir ∗ i , where {x̂ir∗i , i = 1, · · · , d} are independent mixtures of Gaussian. In addition x̂ir∗i has a sub-Gaussian tail
Pr[x̂ir ∗ i ≥ c] ≤ Pr[|r∗i | ≥ c] ≤ e
− c2 4σ2
so it is σ2/2-sub Gaussian. Combined we have (x̂, r∗) is σ2d/2-sub Gaussian. Therefore
Pr[(x̂, r∗) ≤ µ− cd] ≤ e− c2d2 dσ2 = e− c2d σ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 x̂i = b∗i with non-negligible probability. Because w̄i −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, a2), y ∼ N (0, b2) 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|] = Ey [Pr[x ≤ |y||y]] = Ey [ Φ ( |y| a )] Because Φ is concave in [0,+∞) we have
Ey [ Φ ( |y| a )] ≤ Ey [ |y| a Φ′(0) + 1 2 ] = 1 a 1√ 2π Ey[|y|] + 1 2 = 1√ 2πa b √ 2√ π + 1 2 = b πa + 1 2
For a lower bound we have for any u ≥ 0,
Ey [ Φ ( |y| a )] ≥ 1 2 + Ey [ I(|y| ≤ ub) ( |y|Φ (ub/a)− 1/2 ub )] + Ey [ I(|y| > ub) ( Φ ( ub a ) − 1 2 )] ≥ 1
2 + Φ(ub/a)− 1/2 ub Ey [I(|y| ≤ ub)|y|]
According to Wikipedia for truncated Gaussians, we know that Ey[y|0 < y < ub] = b φ(0)−φ(u)Φ(u)−Φ(0) , so
Ey [I(|y| ≤ ub)|y|] = Ey [|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 Ey [ Φ ( |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
−s2/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∗‖22 = (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 xi, 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∗‖22 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 (x1:λd,w∗1:λd) = −‖w∗1:λd‖1 < −λd, so with probability at least 1− e−s2/2
(x,w) = (x1:λd,w ∗ 1:λd) + (xλd:d,w ∗ λd:d) ≤ −λd+ s
√ bd
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−s2/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 xi, (x1:λd, r∗1:λd) is ∑λd i=1 x 2 iσ 2 ≤ λdσ2 sub-Gaussian, so for any s > 0 we have
Pr[(x1:λd, r ∗ 1:λd) ≥ s
√ λdσ] ≤ e−s 2/2 (8)
By Lemma 3 we have
Pr [ (xλd:d, r ∗ λd:d) ≥ √ 2√ π β(1− λ)dσ ] ≥ 1− e2β(1−λ)d/π
Combined we have
Pr [ (x, r∗) ≥
√ 2√ π β(1− λ)dσ − s √ λdσ
] ≥ 1− e2β(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πα 2n2τ2
d2 =
400πα4n2
64d2
In particular we can choose T = 20α 4n2
d2 . This is true if the condition if Lemma 4 is true. That is τ/ √ T ≥ 2σ, or T ≤ τ2/4σ2 = α
2n 8 log 2/δ . Such a T could exist if
α2n
8 log 2/δ ≥ 20α
4n2
d2 n ≤ d
2
160α2 log 2/δ
Conversely if τ = 0, we have E[‖r1: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 [ ‖r1:T ‖1 ≥
Tσ√ π
] →d→∞ 1
We can similarly show that Pr[ME(x) = 1] ≥ 12 (1 − γ) if Tσ/ √ π ≥ α, which becomes the
condition T ≥ √ πα √ n. We choose T = 2α √ n to satisfy it.
A.3 PROOFS RELATED TO THE CONDITIONS
Proposition 4 (Representer Theorem with Hard Constraints). The optimal solution
wn , arg min ‖wn‖≤2λ
1
n n∑ i=1 log(1 + e−yi〈w,φ(xi)〉)
can be represented as
wn = n∑ i=1 αiφ(xi),
where αi is a function of {(xi, yi)}ni=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.
max α min w
1
n n∑ i=1 log(1 + e−yi〈w,φ(xi)〉) + µ(‖w‖ − 2λ), µ ≥ 0.
Due to the traditional representer theorem, we know that w∗ = ∑n i=1 αi(µ
∗)φ(xi), 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 Σ = QTΛQ where Q is orthonomal and Λ is diagonal. Because Q is
orthonormal, ‖Qx‖2 ≤ √ d, then
xTΣx ≤ sup y:‖y‖22=d yTΛy = sup y:‖y‖22=d ∑ i Λiiy 2 i ≤ ( sup i Λii )(∑ i y2i ) = ‖Λ‖2 d = ‖Σ‖2 d
now we can bound defensibility by (x,w −w∗) ∼ N (0,xTΣx/n) and
Pr [ N ( 0, xTΣx
n
) ≥ α ] ≤ Pr [ N (
0, ‖Σ‖2 d n
) ≥ α ] ≤ e− nα2 2‖Σ‖2d
We can also bound mutual information by
I(z;w | x) = H(z|x)−H(z|w,x) = H(N (0,xTΣx/n+ τ2))−H(N (0, τ2))
= 1
2 log
( xTΣ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
Λ , Ep(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 x0 ∈ X
E[(x0, r)2] = E  1 n2 (∑ i (x0,xi) )2 = E  1 n2 ∑ i,j (x0,xi)(x0,xj)  = E [ 1
n2 ∑ i (x0,xi) 2
] + E  1 n2 ∑ i 6=j xT0 xix T j x0  = 1
n E[(x0,x)2] +
1
n2 ∑ i 6=j xT0 E[xi]E[xj ]Tx0 = 1 n E[xT0 xxTx0] = 1 n xT0 Σx0 ≤ d n ‖Σ‖2
Because E[(x0, r)] = 0, Var[(x0, r)] = E[(x0, r)2] ≤ dn ‖Σ‖2, by Bernstein inequality
Pr[(x0, 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] = xTΣx+ τ2 ≤ dρ(Σ) + τ2, so H(z|x) ≤ 12 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 Pnl(x, y;w), and denote wn , arg minPnl(x, y;w). We will first prove that wn
p→ w. As the first step, we prove the uniform law of large numbers of l(x, y;w). notice that
E[ sup ‖w‖≤2λ |Pnl(x, y;w)− Pl(x, y;w)|]
=E[ sup ‖w‖≤2λ
|E[Pnl(x, y;wn)− Pnl(x′, y′;w)]|]
≤E[ sup ‖w‖≤2λ |Pnl(x, y;w)− l(x′, y′;w)|]
=E
[ 1
n sup ‖w‖≤2λ ∣∣∣∣∣ n∑ i=1 i(l(xi, yi;w)− l(x′i, y′i;w∗)) ∣∣∣∣∣ ]
≤ 2 n E [ sup ‖w‖≤2λ ∣∣∣∣∣ n∑ i=1 il(xi, yi;w) ∣∣∣∣∣ ]
(i) ≤ 4 n E [ sup ‖w‖≤2λ ∣∣∣∣∣ n∑ i=1 i(w,xi) ∣∣∣∣∣ ] = 4 n E [ sup ‖w‖≤2λ ∣∣∣∣∣(w, n∑ i=1 ixi) ∣∣∣∣∣ ]
(ii)
≤ 8λ n E [∥∥∥∥∥ n∑ i=1 ixi ∥∥∥∥∥ ] (iii) ≤ 8λ n √√√√√E ∥∥∥∥∥ n∑ i=1 ixi ∥∥∥∥∥ 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λ |Pnl(x, y;w)− Pl(x, y;w)| ≤ 8λ√ nδ .
Therefore, with probability 1− δ, Pl(x, y;wn)− Pl(x, y;w∗) can be bounded as 0 ≤ Pl(x, y;wn)− Pl(x, y;w∗)
= Pl(x, y;wn)− Pnl(x, y;wn) + Pnl(x, y;wn)− Pnl(x, y;w∗) + Pnl(x, y;w∗)− Pl(x, y;w∗)
≤ 16λ√ nδ .
Furthermore, the smoothness of Pl(x, y;w) guarantees that when ‖wn −w∗‖ is small enough, Pl(x, y;wn)− Pl(x, y;w∗) = ∇Pl(x, y;w∗)ᵀ(wn −w∗)
+ 1
2 (wn −w∗)ᵀ∇2Pl(x, y;w∗)(wn −w∗) + o(‖wn −w∗‖)
≥ 1 4 λmin(∇2Pl(x, y;w∗)) ‖wn −w∗‖2
(i) ≥ 1 4 λmin(Cov[∇Pl(x, y;w∗)]) ‖wn −w∗‖2 ,
where (i) is due to Bartlett’s identity, and λmin denotes the smallest eigenvalue. Combining the fact that Pl(x, y;wn)
p→ Pl(x, y;w∗) and Pl(x, y;wn) − Pl(x, y;w∗) ≥ O(‖wn −w∗‖2), we can conclude that with probability 1− δ, there exists a large enough n such that ∀n ≥ n :
‖wn −w∗‖2 ≤ 64λ√
nδλmin(Cov[∇Pl(x, y;w∗)]) ,
and as a simple corollary,
wn p→ w∗.
Because wn minimizes Pnl(x, y;w), we have that whenever ‖wn −w∗‖ < λ,∇Pnl(x, y;wn) = 0. This is equivalent to saying that √ n∇Pnl(x, y;wn)
p→ 0. Using Taylor expansion, we obtain ∇Pnl(x, y;w∗) +∇2Pnl(x, y;w∗)(wn −w∗) + op(1)(wn −w∗) = ∇Pnl(x, y;wn) = op( 1√n ), which is equivalent to √ n(P∇2l(x, y;w∗) + (Pn − P )∇2l(x, y;w∗) + op(1))(wn −w∗) = − √ nPn∇l(x, y;w∗) + op(1).
Combining the central limit theorem and Slutsky’s theorem, we have √ n(wn −w∗) d→ N (0;E[∇2l(x, y;w∗)]−1 Cov[∇l(x, y;w∗)]E[∇2l(x, y;w∗)]−1).
Bartlett’s identity asserts that E[∇2l(x, y;w∗)] = Cov[∇l(x, y;w∗)]. Therefore, the asymptotic variance of √ n(wn −w∗) can be simplified to
Σ , Cov[∇l(x, y;w∗)]−1 = E [
xxᵀ
(1 + ey(w∗,x))2 ]−1 = ( Ex [ e(w ∗,x)
(1 + e(w∗,x))2 xxᵀ ])−1 = (Ex[pw∗(1− pw∗)xxᵀ])−1 ,
where pw∗ = 11+e−(w∗,x) .
Lemma 6. Assume that there exists w∗ ∈ H such that p∗(y | x) = 11+exp(−y〈w∗,φ(x)〉) . Assume further that ‖w∗‖ ≤ λ, and ∀x : k(x,x) ≤ 1. Suppose we are given a dataset {(xi, yi)}ni=1 i.i.d.∼ p∗(x)p∗(y | x). Let ŵn be the solution to the following objective
min ‖w‖≤2λ
1
n n∑ i=1 log(1 + e−yi〈w,φ(xi)〉).
Then we have wn p→ w∗, and
√ n(wn −w∗) d→ N (0,ΣH),
where
ΣH = (Ex[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)〉), Ln(w) = 1n ∑n i=1 l(xi, yi;w), and L(w) = E[l(x, y;w)]. Now, we prove the uniform convergence of Ln to L. Denote B , {w| ‖w‖H ≤ 2λ}, and consider the expected error
E [
sup w∈B |L̂n(w)− L(w)|
] = E [ sup w∈B |L̂n(w)− E[l(x, y;w)]| ] = E [ sup w∈B ∣∣∣∣∣ 1n n∑ i=1 l(xi, yi;w)− E [ 1 n n∑ i=1 l(x′i, y ′ i;w) ]∣∣∣∣∣ ]
≤ E [ sup w∈B 1 n ∣∣∣∣∣ n∑ i=1 i[l(xi, yi;w)− l(x′i, y′i;w)] ∣∣∣∣∣ ]
≤ 2E [ sup w∈B 1 n ∣∣∣∣∣ n∑ i=1 il(xi, yi;w) ∣∣∣∣∣ ]
= 2R[l(x, y;w)]
Now let X(w) , 1n ∑n i=1 il(xi, yi;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 ∣∣∣∣∣ 1n n∑ i=1 iyi〈w, φ(xi)〉 ∣∣∣∣∣ ]
= E [ sup w∈B ∣∣∣∣∣〈w, 1n n∑ i=1 iyiφ(xi)〉 ∣∣∣∣∣ ]
≤ E [ ‖w‖H ∥∥∥∥∥ 1n n∑ i=1 iyiφ(xi) ∥∥∥∥∥ H ]
≤ √√√√√λ2 n2 E  n∑ i=1 n∑ j=1 i jyiyjk(xi,xj)  = √ λ2
n √√√√E[ n∑ i=1 k(xi,xi) ]
≤ λ√ n ,
where we assume that k(x,x) ≤ 1, which is satisfied by many universal kernels, such as Gaussian RBF. Taken together, we have
E [
sup w∈B |L̂n(w)− L(w)|
] ≤ 4 √ λ
n .
With Markov inequality, we have ∀δ > 0,
Pr[sup w∈B |L̂n(w)− L(w)| > δ] ≤
4
δ
√ λ
n .
The uniform convergence concludes that L(wn) p→ L(w∗). Using the same arguments as in the proof of Lemma 1, we conclude that wn p→ w∗.
next, we prove the asymptotic normality of wn. 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
∇wl(x, y;w) = − y〈φ(x), ·〉
1 + ey〈w,φ(x)〉 .
Let g(w) , ∇wl(x, y;w) : H → H. We can further take the Gâteaux derivative of g(w) to get
dg(w0 + t(w −w0)) dt = ey〈w0+t(w−w0),φ(x)〉 (1 + ey〈w0+t(w−w0),φ(x)〉)2 〈w −w0, φ(x)〉〈φ(x), ·〉
and even compute higher-order Gâteaux derivatives
d2g(w0 + t(w −w0)) dt2 = − ey〈w0+t(w−w0),φ(x)〉
( ey〈w0+t(w−w0),φ(x)〉 − 1 )( ey〈w0+t(w−w0),φ(x)〉 + 1
)3 〈w −w0, φ(x)〉2〈φ(x), ·〉. Using fundamental theorem of calculus for Gâteaux derivatives, we obtain
g(w) = g(w0) + ∫ 1 0 dg(w0 + t(w −w0)) dt ∣∣∣∣dt = g(w0) + ∫ 1 0 dg(w0 + t(w −w0)) dt ∣∣∣∣ t=0 dt+ ∫ 1 0 ∫ v 0 d2g(w0 + t(w −w0)) dt2 ∣∣∣∣ t=u dudv.
note that∥∥∥∥∫ 1 0 ∫ v 0 d2g(w0 + t(w −w0)) dt2 ∣∣∣∣ t=u dudv ∥∥∥∥ ≤ 120 ∥∥〈w −w0, φ(x)〉2〈φ(x), ·〉∥∥ = o(‖w −w∗‖), we have
g(w) = g(w0) + ey〈w0,φ(x)〉
(1 + ey〈w0,φ(x)〉)2 φ(x)⊗ φ(x)(w −w0) + op(1)(w −w0).
Using the same arguments as in the proof of Lemma 1, we can assert that g(wn) = op( 1√n ). Now we can expand L̂(wn) in the neighborhood of w∗ to get√ nPn∇wl(x, y;wn) = op(1)
= √ nPn∇wl(x, y;w∗) + ( Pn
ey〈w ∗,φ(x)〉
(1 + ey〈w∗,φ(x)〉)2 φ(x)⊗ φ(x) + op(1)
) (w −w∗)
(i) = √ nPn∇wl(x, y;w∗)
+ √ n ( P
ey〈w ∗,φ(x)〉
(1 + ey〈w∗,φ(x)〉)2 φ(x)⊗ φ(x) + (Pn − P )
ey〈w ∗,φ(x)〉
(1 + ey〈w∗,φ(x)〉)2 φ(x)⊗ φ(x) + op(1)
) (w −w∗)
= √ nPn∇wl(x, y;w∗) + √ n ( P
ey〈w ∗,φ(x)〉
(1 + ey〈w∗,φ(x)〉)2 φ(x)⊗ φ(x) + op(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 inH. 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(wn −w∗) is again Gaussian, with mean 0 and variance Σ = (Ex[pw∗(1− pw∗)φ(x)⊗ φ(x)])−1 ,
where
pw∗ = 1
1 + e−〈w∗,φ(x)〉
A.3.1 ADDITIONAL EXAMPLES AND PROOFS FOR SECTION 4
An example where plearn(w) = N (w∗, σ2I) Let Berd(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) = Ber1(1/2) and p(x|y = 1) = Berd(3/4) and p(x| = 0) = Berd(1/4). We choose w∗ = ( 1 2 , 1 2 , · · · , 1 2 ) and the ground truth score function is gw∗(x) = (x,w∗).
We draw a dataset of size n from the distribution {x1, y1, · · · , xn, yn}, to learn w the algorithm simply takes the average ∑ i:yi=1
xi∑ i:yi=1 1 − ∑ i:yi=−1 xi∑ i:yi=−1 1 . Then by CLT we have plearn(w) = N (w ∗, σ2I),
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. Proof of no-response rate. When α = √ d and τ = 0 we have
Pr p∗(x)
[NR(x)] ≤ Pr [|(x,w)| ≤ α] ≤ Pr [ |(x, r∗)| ≤ d/2− √ d ]
= Pr [∣∣N (0, dσ2)∣∣ ≤ d/2−√d]→d→∞ 0
Similarly for α = √ d and τ = α 2
2 log 2/δ we have
Pr p∗(x)
[NR(x)] ≤ Pr [∣∣(x,w) +N (0, τ2)∣∣ ≤ α] ≤ Pr [∣∣(x, r∗) +N (0, τ2)∣∣ ≤ d/2−√d]
= Pr [∣∣∣∣N (0, dσ2 + d2 log(2/δ) )∣∣∣∣ ≤ d/2−√d]→d→∞ 0

Review summaries:
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: