Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks

1 Introduction

Adversarial machine learning has been extensively studied in recent years, first with spam filtering in [Dalvi et al., 2004; Lowd and Meek, 2005a; Lowd and Meek, 2005b], and then when the notion of adversarial examples was introduced by [Szegedy et al., 2013], and independently noticed by [Biggio et al., 2013]. Various settings to study adversarial machine learning guarantees (and impossibility results) have emerged in the literature since. The most common distinction, presented in [Biggio and Roli, 2017], differentiates between attacks at training time, known as poisoning attacks, and attacks at test time, called evasion attacks.

∗ Full paper: http://www.fun2model.org/papers/gkkw22.pdf.

In the context of evasion attacks, a misclassification by a model has been defined in various ways, and sometimes regrettably referred to by the same terminology. [Dreossi et al., 2019; Diochnos et al., 2018; Gourdeau et al., 2021] offer thorough discussions on the subject. We will focus on the exact-in-the-ball notion of robustness (also known as error region risk in [Diochnos et al., 2018]), which necessitates a ground truth function. Briefly, the exact-in-the-ball notion of robustness requires a hypothesis to be correct with respect to the ground truth in a perturbation region around each test point. Note that, in this case, the ground truth must be specified on all input points in the perturbation region. By contrast, the constant-in-the-ball notion of robustness (which is also known as corrupted input robustness) is concerned with the stability of the hypothesis to perturbations in the input, and requires that the label produced by the hypothesis remain constant in the perturbation region, meaning that we only need access to the test point labels.

The hardness of robust classification has been explored from both a computational complexity and a statistical viewpoint, see for e.g., [Bubeck et al., 2019; Montasser et al., 2019]. In this paper, we focus on the Boolean hypercube {0, 1}n as our input space and study the information-theoretic complexity of robust learning by exhibiting sample complexity upper and lower bounds that depend on an adversarial budget, i.e., the number of bits an adversary is allowed to flip at test time, thus illustrating that the adversarial budget is a fundamental quantity in determining the sample complexity of robustly learning important concept classes.

1.1 Our Contributions

Our work builds on [Gourdeau et al., 2019] and its extended version [Gourdeau et al., 2021]. Our results hold for the exact-in-the-ball robustness to evasion attacks.

Robust Learning of Decision Lists: As shown in [Gourdeau et al., 2021], efficient, exact-in-the-ball robust learning is not possible without distributional assumptions on the training data. 1 We follow their line of work and establish the sample-efficient robust learnability of decision lists against a log(n)-bounded adversary under log-Lipschitz distributions, which include the uniform and product distributions. The algorithms we use to show such upper bounds are called ρrobust learning algorithms, where ρ is the allowed perturbation budget for an adversary. In proving our first result we obtain an isoperimetric bound that may be of independent interest: for a CNF formula φ we give an upper bound on the number of points in the Boolean hypercube within a given Hamming distance to a satisfying assignment of φ. An analogue result was shown only for monotone decision lists in [Gourdeau et al., 2021]. More importantly, [Gourdeau et al., 2021] suggested the following open problem:

1 This is in contrast to PAC learning, which is distribution-free.

Let A be a sample-efficient (potentially proper) PAC-learning algorithm for concept class C. Is A also a sample-efficient log(n)-robust learning algorithm for C under the uniform distribution?

So far, all the concept classes that have been studied point towards a positive answer to this question. As log-Lipschitz distributions subsume the uniform distribution, our result thus adds to the body of positive evidence for this problem.

An Adversarial Sample Complexity Lower Bound: To complement the above result, we show that any ρ-robust learning algorithm for monotone conjunctions must have a sample complexity that is exponential in the number ρ of bits an adversary is allowed to flip during an evasion attack. Previously, [Gourdeau et al., 2021] showed that there does not exist such an algorithm with polynomial sample complexity against an adversary that can perturb ω(log(n)) bits of the input.

1.2 RelatedWork

The inevitability of adversarial examples under the constantin-the-ball definition of robustness has been extensively studied, see for e.g., [Fawzi et al., 2016; Fawzi et al., 2018a; Fawzi et al., 2018b; Gilmer et al., 2018; Shafahi et al., 2018; Tsipras et al., 2019; Ilyas et al., 2019]. We first outline related work on sample complexity lower bounds for robust learning. [Bhagoji et al., 2019] work with the constant-inthe-ball definition of robustness and use an optimal transport cost function to derive lower bounds for learning classes with labels that come from a mixture of Gaussian distributions. [Montasser et al., 2019] also use this notion of robustness to show a lower bound that depends on a complexity measure adapted to robustness from the shattering dimension of a concept class. Closer to our work, [Diochnos et al., 2019; Diochnos et al., 2020] exhibit lower bounds for the exact-inthe-ball robust risk. They focus on a family of concentrated distributions, Normal L´evy families, which include, for e.g., the Gaussian distribution on Rn and product distribution of dimension n under the Hamming distance. 2 Instead of looking at a specific class of functions, they allow any concept class that contain concepts that have small enough (2-Θ(n) ) standard error with respect to each other, and so would be indistinguishable for sufficiently small samples. Note that monotone conjunctions satisfy this property. When considering the Boolean hypercube and an adversary that can perturb ρ bits of the input, they get that any robust PAC learning algorithm for their robust learning setting requires a sample of size 2Ω(ρ2 /n) . Note that this lower bound is non trivial only when considering adversaries that can perturb √n bits or more, while we show a lower bound that is strictly exponential in the adversary's budget (though for slightly more restricted concept classes), and thus meaningful for a wider class of adversaries.

2 We work with the uniform distribution, which is a special case of product distributions.

In terms of sample complexity upper bounds, [Montasser et al., 2019] show sample complexity upper bounds that are linear (ignoring log factors) in the VC dimension and the dual VC dimension of a concept class under the constantin-the-ball notion of robustness, yielding an exponential upper bound in the VC dimension. As noted in [Gourdeau et al., 2021], their techniques do not apply to the exact-in-theball setting, which is studied for evasion attacks notably in [Diochnos et al., 2018; Mahloujifar and Mahmoody, 2019; Mahloujifar et al., 2019; Gourdeau et al., 2019; Gourdeau et al., 2021]. The work of [Diochnos et al., 2018] addresses the ability of an adversary to cause a blow up the adversarial error with respect to the standard error. For instance, they show that, under the uniform distribution, a O(√n)-bounded adversary can cause the probability of a misclassification to be 1/2 given that the standard error is 0.01 for any learning problem. These results are extended in [Mahloujifar et al., 2019] for a wider family of distributions. Finally, [Gourdeau et al., 2021] exhibit sample complexity upper bounds for the robust learnability of a variety of concept classes (parities, monotone decision lists, and decision trees) under log-Lipschitz distributions for various adversarial budgets.

2 Problem Set Up

In this section, we will first recall two definitions of robustness that have been widely used in the literature, and formalize the notion of robustness thresholds in the robust PAClearning framework. We will then review relevant concept classes for this paper, as well as log-Lipschitz distributions, which were introduced in [Awasthi et al., 2013] and will be the focus of our results.

2.1 Robust Learning

We work in the PAC learning framework of [Valiant, 1984] (see Appendix A.1), but where the (standard) risk function is replaced by a robust risk function. Since we focus on the Boolean hypercube {0, 1}n as the input space, the only relevant notion of distance between points is the Hamming distance (denoted dH), i.e., the number of bits that differ between two points. Thus, the adversary's perturbation budget will be the number of bits of the input the adversary is allowed to flip to cause a misclassification. We will use the exact-in-the-ball definition of robust risk (which is called error-region risk in [Diochnos et al., 2018]). Given respective hypothesis and target functions h, c : X → {0, 1}, distribution D on X, and robustness parameter ρ ≥ 0, the exact-in-the-ball robust risk of h with respect to c is defined as REρ (h, c) = Pr x∼D (∃z ∈ Bρ(x) : h(z) ̸= c(z)), where Bρ(x) = {z ∈ {0, 1}n | dH(x, z) ≤ ρ}. This is in contrast to the more widely-used constant-in-the-ball risk function (also called corrupted-instance risk from the work of [Feige et al., 2015]) RCρ (h, c) = Pr x∼D (∃z ∈ Bρ(x) : h(z) ̸= c(x))

where the hypothesis is required to be constant in the perturbation region in addition to being correct with respect to the unperturbed point's label c(x).

Both [Diochnos et al., 2018] and [Gourdeau et al., 2021] offer a thorough discussion on the advantages and drawbacks of the two notions of robust risk. We will study the exactin-the-ball robust risk, as our learning problems have considerable probability mass near the decision boundary. Thus it makes sense to consider the faithfulness of the hypothesis with respect to the target function. The exact-in-the-ball robust risk also has various advantages: if the distribution is supported on the whole input space (e.g., the uniform distribution), exact learnability implies robust learnability and the target concept is always the robust risk minimizer. 3 We have from [Gourdeau et al., 2021] the following definition of robust learnability with respect to the exact-in-the-ball robust risk. Note that we will henceforth drop the superscript and simply use Rρ to denote the exact-in-the-ball robust risk.

Definition 1 ([Gourdeau et al., 2021]). Fix a function ρ : N → N. We say that an algorithm A efficiently ρ-robustly learns a concept class C with respect to distribution class D if there exists a polynomial poly(·, ·, ·, ·) such that for all n ∈ N, all target concepts c ∈ Cn, all distributions D ∈ Dn, and all accuracy and confidence parameters ϵ, δ > 0, if m ≥ poly(n, 1/ϵ, 1/δ, size(c)), whenever A is given access to a sample S ∼ Dm labelled according to c, it outputs a polynomially evaluable function h : {0, 1}n → {0, 1} such that Pr S∼Dm (Rρ(h, c) < ϵ) > 1 - δ.

2.2 Concept Classes and Distribution Families

Our work uses formulas in the conjunctive normal form (CNF) to show the robust learnability of decision lists. This concept class was proposed and shown to be PAC learnable in [Rivest, 1987]. Formally, given the maximum size k of a conjunctive clause, a decision list f ∈ k-DL is a list (K1, v1), . . . , (Kr, vr) of pairs where Kj is a term in the set of all conjunctions of size at most k with literals drawn from {x1, ¯ x1, . . . , xn, ¯ xn}, vj is a value in {0, 1}, and Kr is true. The output f(x) of f on x ∈ {0, 1}n is vj, where j is the least index such that the conjunction Kj evaluates to true.

Given k, n ∈ N, we denote by φ a k-CNF on n variables, where k refers to the size of the largest clause in φ. Note that the class MON-CONJ of monotone conjunctions, where each variable appears as a positive literal, is a subclass of 1-CNF formulas. Moreover, since decision lists generalize formulas in disjunctive normal form (DNF) and conjunctive normal form, in the sense that k-CNF ∪ k-DNF ⊆ k-DL, a robust learnability result for k-DL holds for k-CNF and k-DNF as well. We refer the reader to Appendix A.2 for more background on conjunctions and k-CNF formulas.

For a formula φ, we will denote by S0(φ) the probability Pr x∼D (x |= φ) that x drawn from distribution D results in a satisfying assignment of φ. We will also denote the probability mass Pr x∼D (∃z ∈ Bρ(x) . z |= φ) of the ρ-expansion of a satisfying assignment by Sρ(φ).

3 This is not necessarily the case with the constant-in-the-ball definition [Gourdeau et al., 2021].

Our robust learnability results will hold for a class of sufficiently smooth distributions, called log-Lipschitz distributions, originally introduced in [Awasthi et al., 2013]:

Definition 2. A distribution D on {0, 1}n is said to be α-logLipschitz if for all input points x, x′ ∈ {0, 1}n , if dH(x, x′ ) = 1, then | log(D(x)) - log(D(x′ ))| ≤ log(α).

Neighbouring points in {0, 1}n have probability masses that differ by at most a multiplicative factor of α under αlog-Lipschitz distributions. The decay of probability mass along a chain of neighbouring points is thus at most exponential; not having sharp changes to the underlying distribution is a very natural assumption, and one weaker than many often make in the literature. Note that features are allowed a small dependence between each other and, by construction, log-Lipschitz distributions are supported on the whole input space. Notable examples of log-Lipschitz distributions are the uniform distribution (with parameter α = 1) and the class of product distributions with bounded means.

3 The log(n)-Expansion of Satisfying Assignments for k-CNF Formulas

In this section, we show that, under log-Lipschitz distributions, the probability mass of the log(n)-expansion of the set of satisfying assignments of a k-CNF formula can be bounded above by an arbitrary constant ε > 0, given an upper bound on the probability of a satisfying assignment. The latter bound is polynomial in ε and 1/n. While this result is of general interest, our goal is to prove the efficient robust learnability of decision lists against a log(n)-bounded adversary. Here the relevant fact is that, given two decision lists c, h ∈ k-DL, the set of inputs in which c and h differ can be written as a disjunction of quadratically many (in the combined length of c and h) k-CNF formulas. The log(n)- expansion of this set is then the set of inputs where a log(n)- bounded adversary can force an error at test time. This is the main technical contribution of this paper, and the theorem is stated below. The combinatorial approach, below, vastly differs from the approach of [Gourdeau et al., 2021] in the special case of monotone k-DL, which relied on facts about propositional logic.

Theorem 3. Suppose that φ ∈ k-CNF and let D be an αlog-Lipschitz distribution on the valuations of φ. Then there exist constants C1,C2,C3,C4 ≥ 0 that depend on α and k such that if the probability of a satisfying assignment satisfies S0(φ) < C1εC2 min {εC3 , n-C4 }, then the log(n)- expansion of the set of satisfying assignments has probability mass bounded above by ε.

Corollary 4. The class of k-decision lists is efficiently log(n)-robustly learnable under log-Lipschitz distributions.

The proof of Corollary 4 is similar to Theorem 24 in [Gourdeau et al., 2021], and is included in Appendix B. We note that it is imperative that the constants Ci do not depend on the learning parameters or the input dimension, as the quantity C1εC2 min {εC3 , n-C4 } is directly used as the accuracy parameter in the (proper) PAC learning algorithm for decision lists, which is used as a black box.

To prove Theorem 3, we will need several lemmas outlined below, which are either taken directly or slightly adapted from [Gourdeau et al., 2021]. The first is an adaptation of Lemma 17 in [Gourdeau et al., 2021] for conjunctions, which was originally stated for decision lists:

Lemma 5. Let φ be a conjunction and let D be an α-logLipschitz distribution. If Pr x∼D (x |= φ) < (1+α)-d , then φ is a conjunction on at least d variables.

The second result, which states an upper bound on the expansion of satisfying assignments for conjunctions, will be used for the base case of the induction proof.

Lemma 6. Let D be an α-log-Lipschitz distribution on the n-dimensional Boolean hypercube and let φ be a conjunction of d literals. Set η = 1 1+α . Then for all 0 < ε < 1/2, if d ≥ max { 4 η2 log ( 1ε ) , 2ρ η }, then Pr x∼D ((∃y ∈ Bρ(x) · y |= φ)) ≤ ε.

Finally, we will use the following lemma, which will be used in the inductive step of the induction proof.

Lemma 7. Let φ be a k-CNF formula that has a set of variable-disjoint clauses of size M. Let D be an α-logLipschitz distribution on valuations for φ. Let 0 < ε < 1/2 be arbitrary and set η := (1+α)-k . If M ≥ max { 4 η2 log ( 1ε ) , 2ρ η } then Pr x∼D (∃y ∈ Bρ(x) · y |= φ) ≤ ε.

We are now ready to prove Theorem 3. The main idea behind the proof is to consider a given k-CNF formula φ and distinguish two cases: (i) either φ contains a sufficiently-large set of variable-disjoint clauses, in which case the adversary is not powerful enough to make φ satisfied by Lemma 7; or (ii) we can rewrite φ as the disjunction of a sufficiently small number of (k - 1)-CNF formulas, which allows us to use the induction hypothesis to get the desired result. The final step of the proof is to derive the constants mentioned in the statement of Theorem 3.

Proof of Theorem 3. We will use the lemmas above and restrictions on φ to show the following.

Induction hypothesis: Suppose that φ ∈ (k - 1)-CNF and let D be an α-log-Lipschitz distribution on the valuations of φ. Then there exists constants C1,C2,C3,C4 ≥ 0 that depend on α and k and satisfy C3 ≥ η2 C4 such that if S0(φ) < C1εC2 min {εC3 , n-C4 }, then Slog(n)(φ) ≤ ε.

Base case: This follows from Lemmas 5 and 6. Set η to (1+α)-1 , and C1 = 1, C2 = 0, C3 = 4 η2 and C4 = 2 η . Note that C3 ≥ η2 C4.

Inductive step: Suppose φ ∈ k-CNF and let D be an α-logLipschitz distribution on the valuations of φ. Set η = (1 + α)-k . Let C ′1 ,C ′2 ,C ′3 ,C ′4 be the constants in the induction hypothesis for φ′ ∈ (k-1)-CNF. Set the following constants:

and note that these are all constants that depend on k and α by the induction hypothesis, and that C3 ≥ η2 C4.

Let S0(φ) < C1εC2 min {εC3 , n-C4 }. Let M be a maximal set of clauses of φ such that no two clauses contain the same variable. Denote by IM the indices of the variables in M and let M = max { 4 η2 log 1ε , 2 η logn}.

We distinguish two cases:

We can then invoke Lemma 7 and guarantee that Slog(n) ≤ ε, and we get the required result.

Then let AM be the set of assignments of variables inM, i.e. a ∈ AM is a function a : IM → {0, 1}, which represents a partial assignment of variables in φ. We can thus rewrite φ as follows:

where φa is the restriction of φ under assignment a and li is xi in case a(i) = 1 and ¯ xi otherwise. For short, denote by φ′a the formula φa ∧ ∧i∈IM li. By the maximality of M every clause in φ mentions some variable in M, and hence φ′a is (k - 1)-CNF. Moreover, the formulas φ′a are disjoint, in the sense that if some assignment x satisfies φ′a , it will not satisfy another φ′b for a distinct index b. Note also that

Thus,

By the induction hypothesis, we can guarantee that if

for all φ′a then the log(n)-expansion Slog(n)(φ) can be bounded as follows:

By Equation 1, the upper bound S0(φ) < C1εC2 min {εC3 , n-C4 } on the probability of a satisfying assignment for φ implies an upper bound S0(φ′a ) < C1εC2 min {εC3 , n-C4 } on the probability

.

of the restrictions φ′a . Thus it only remains to show that the condition on S0(φ) implies that Equation 2 holds.

Let us rewrite the RHS of Equation 2 as follows, where each of the equations is a stricter condition on S0(φ′a ) than its predecessor:

where the first step is by definition of An,ε, the second from the induction hypothesis, which guarantees C ′3 ≥ η2 C ′4 , and the fourth from the property min{a, b} · min{c, d} ≥ min {a2 , b2 , c2 , d2}. Finally, the last equality follows by the definition of the Ci's.

Note that we set η = (1 + α)-k to be able to apply Lemma 7 in the first part of the inductive step. Then, An,ϵ is a function of η = (1 + α)-k . When we consider the distribution on the valuations of the restriction φ′a , we still operate with an α-log-Lipschitz distribution on its valuations, by logLipschitz facts (see Appendix A.3).

Constants. We want to get explicit constants C1,C2,C3 and C4 as a function of k and η. Note that η = (1 + α)-k is dependent on k. Let us recall the recurrence system from the inductive step:

It is easy to see that C (k) 3 ≥ C (k) 2 for all k ∈ N. If we fix η = (1 + α)-k at each level of the recurrence, we can now consider the following recurrence system, which dominates the previous one:

We can now see that

Finally, we can get a lower bound on the value of C (k) 1 as follows:

4 An Adversarial Sample Complexity Lower Bound

In this section, we will show that any robust learning algorithm for monotone conjunctions under the uniform distribution must have an exponential sample-complexity dependence on an adversary's budget ρ. This result extends to any superclass of monotone conjunctions, such as CNF formulas, decision lists and halfspaces. It is a generalization of Theorem 13 in [Gourdeau et al., 2021], which shows that no sample-efficient robust learning algorithm exists for monotone conjunctions against adversaries that can perturb ω(log(n)) bits of the input under the uniform distribution.

The idea behind the proof is to show that, for a fixed constant κ < 2, and sufficiently large input dimension, a sample of size 2κρ from the uniform distribution won't be able to distinguish between two disjoint conjunctions of length 2ρ. However, the robust risk between these two conjunctions can be lower bounded by a constant. Hence, there does not exist a robust learning algorithm with sample complexity 2κρ that works for the uniform distribution, and arbitrary input dimension and confidence and accuracy parameters.

Recall that the sample complexity of PAC learning conjunctions is Θ(n) in the non-adversarial setting. On the other hand, our adversarial lower bound in terms of the robust parameter is super linear in n as soon as the adversary can perturb more than log(√n)) bits of the input.

Theorem 8. Fix a positive increasing robustness function ρ : N → N. For κ < 2 and sufficiently large input dimensions n, any ρ(n)-robust learning algorithm for MON-CONJ has a sample complexity lower bound of 2κρ(n) under the uniform distribution.

The proof of the theorem follows similar reasoning as Theorem 13 in [Gourdeau et al., 2021], and is included in Appendix C. The main difference in the proof is its reliance on the following lemma, which shows that, for sufficiently large input dimensions, a sample of size 2κρ from the uniform distribution will look constant with probability 1/2 if labelled by two disjoint monotone conjunctions of length 2ρ. As shown in Lemma 14, which can be found in Appendix C, these two conjunctions have a robust risk bounded below by a constant against each other.

Lemma 9. For any constant κ < 2, for any robustness parameter ρ ≤ n/4, for any disjoint monotone conjunctions c1, c2 of length 2ρ, there exists n0 such that for all n ≥ n0, a sample S of size 2κρ sampled i.i.d. from D will have that c1(x) = c2(x) = 0 for all x ∈ S with probability at least 1/2.

Proof. We begin by bounding the probability that c1 and c2 agree on an i.i.d. sample of size m. We have

In particular, if

then the RHS of Equation 3 is at least 1/2.

Now, let us consider the following limit, where ρ is a function of the input parameter n:

where the first two equalities follow from l'Hˆopital's rule.

Remark 10. Note that for a given κ < 2, the lower bound 2κρ holds only for sufficiently large ρ(n). By looking at Equation 3, and letting m = 2ρ , we get that ρ(n) ≥ 2 is a sufficient condition for it to hold. If we want a lower bound for robust learning that is larger than that of standard learning (where the dependence is Θ(n)) for a log(n) adversary, setting m = 21.7ρ and requiring ρ(n) ≥ 6, for e.g., would be sufficient.

5 Conclusion

We have shown that the class k-DL is efficiently robustly learnable against a logarithmically-bounded adversary, thus making progress on the open problem of [Gourdeau et al., 2021] of whether PAC-learnable classes are always robust in general against a logarithmically-bounded adversary. The main technical tool was an isoperimetric result concerning CNF formulas. Moreover, we have shown that, for monotone conjunctions and any superclass thereof, any ρ-robust learning algorithm must have a sample complexity that is exponential in the adversarial budget ρ.

Deriving sample complexity bounds for the robust learnability of halfspaces under the uniform distribution is perhaps the most natural next step towards resolving the abovementioned open problem. Another direction of further research concerns improving the sample complexity bounds for k-DL in the present paper. Here we have used a proper PAC-learning algorithm as a black box in our robust learning procedure (see Corollary 4). By controlling the accuracy parameter of the standard PAC-learning algorithm, we are able to get a robust learning algorithm. From this, we get polynomial sample complexity upper bounds for k-DL in terms of the robustness accuracy parameter ε, the distribution parameter α, and the input dimension n. The resulting polynomial has degree O(8k (1 + α)2k2 ) in the term 1/ε and degree O(k8k (1 + α)2k2 ) in the dimension n. It is natural to ask whether these bounds can be improved in a significant way, e.g., by adapting the learning procedure to directly take robustness into account, rather than using a PAC-learning algorithm as a black box. Connected to this, we note that our lower bound focuses on establishing the exponential dependence of the number of samples on the robustness parameter. The bound is derived from the case of monotone conjunctions (a special case of 1-DL) under the uniform distribution and so does not mention k, nor the distribution parameter α. Likewise, it does not mention the desired accuracy ε. Deriving sample complexity lower bounds with a dependence on these parameters, potentially through other techniques, would help give a complete picture of the robust learnability of k-DL.

Acknowledgments

MK and PG received funding from the ERC under the European Union's Horizon 2020 research and innovation programme (FUN2MODEL, grant agreement No. 834115).