PAC-learning with adversary

By LI Haoyang 2020.11.4 - 2020.11.14 (intermittent reading)

Content

PAC-Learning

Definition

A concept class $\mathcal{C}$ is said to be PAC-learnable if there exists an algorithm $\mathcal{A}$ and a polynomial function $\text{poly}(\cdot,\cdot,\cdot,\cdot)$ such that for any $\epsilon>0$ and $\delta>0$, for all distributions $\mathcal{D}$ on $\mathcal{X}$ and for any target concept $c\in\mathcal{C}$, the following holds fro any sample size $m\ge\text{poly}(1/\epsilon,1/\delta,n,\text{size}(c))$:

If $\mathcal{A}$ further runs in $\text{poly}(1/\epsilon,1/\delta,n,\text{size}(c))$, then $\mathcal{C}$ is said to be efficiently PAC-learnable. When such an algorithm $\mathcal{A}$ exists, it is called a PAC-learning algorithm for $\mathcal{C}$.

This theorem states that as long the sample complexity (the number of samples) is larger enough, a PAC learnable algorithm can learn a hypothesis that the difference between the empirical risk and actual risk (i.e. the approximation error) is smaller than $\epsilon$ at a probability larger than $\delta$.

VC-dimension

From VC dimension - Wikipedia:

The VC dimension of a model $f$ is the maximum number of points that can be arranged so that f shatters them. More formally, it is the maximum cardinal $D$ such that some data point set of cardinality $D$ can be shattered by $f$.

If a set of points can be shattered by some model, it means that the model can always classify these points assigned with arbitrary labels from $\{0,1\}$. For a set with $n$ data points, the number of the possible assignments of labels is $2^n$.

==The VC dimension of a hypothesis (model) is the largest number (cardinality, i.e. $|\cdot|$) of elements in a set that can be shattered by this hypothesis.

PAC-learning in the presence of evasion adversaries - NIPS 2018

Paper: https://dl.acm.org/doi/10.5555/3326943.3326965

Daniel Cullina, Arjun Nitin Bhagoji, Prateek Mittal. PAC-learning in the presence of evasion adversaries. NIPS 2018. arXiv:1806.01471

In this paper, we step away from the attackdefense arms race and seek to understand the limits of what can be learned in the presence of an evasion adversary.

They are interested in the effect of an adversary on sample complexity, i.e.

If we add an adversary to the learning setting defined in Definition 3, what happens to the gap in performance between the optimal classifier and the learned classifier?

We explicitly compute the adversarial VC-dimension for halfspace classifiers with adversaries with standard $l_p(p\ge 1)$-distance constraints on adversarial perturbations, and show that it matches the standard VC-dimension.

This implies that the sample complexity of PAC-learning does not increase in the presence of an adversary.

We also show that this is not always the case by constructing hypothesis classes where the adversarial VC-dimension is arbitrarily larger or smaller than the standard one.

Adversarial agnostic PAC-learning

They extend the PAC-learning to that in the presence of an adversary.

Symbol defintion:

• $\mathcal{X}$ - Space of examples
• $\mathcal{C}=\{-1,1\}$- Set of classes
• $\mathcal{H}\sube (\mathcal{X}\to\mathcal{C})$ - Set of hypothesis (labeling of examples)
• $\ell(c,\hat{c})=\bold{1}(c\neq\hat{c})$ - 0-1 loss function
• $R\sube\mathcal{X}\times\mathcal{X}$ - Binary nearness relation
• $N(x)=\{y\in\mathcal{X}:(x,y)\in R\}$ - Neighborhood of nearby adversarial examples

The learning problem is as follows.

There is an unknown $P\in\Bbb{P}(\mathcal{X}\times\mathcal{C})$. The learner receives labeled training data, i.e. $(\bold{x},\bold{c})=((x_0,c_0),\dots,(x_{n-1},c_{n-1}))\sim P^n$ and must select $\hat{h}\in\mathcal{H}$.

The power set $P^n$ denotes the set of functions relating $\mathcal{X}$ to $\mathcal{C}$. A labeled training dataset is than a sampled relation.

The adversary receives a labeled natural example $(x_{Test},c_{Test})\sim P$ and selects $y\in N(x_{Test})$, i.e. the set of adversarial examples in the neighborhood of $x_{Test}$.

The adversary gives $y$ to the learner and the learner must estimate $c_{Test}$.

$\Bbb{P}(\mathcal{X}\times\mathcal{C})$ is the set of probability measures on $(\mathcal{X}\times\mathcal{C},\Sigma)$. $\Sigma\sube 2^{\mathcal{X}\times\mathcal{C}}$ is a set of events.

$R$ is the binary nearness relation that generates the neighborhood $N(x)$ of possible adversarial samples. $N(x)$ is required to be nonempty so some choice of $y$ is always available.

• $R$ is the identity relation, i.e. $I_{\mathcal{X}}=\{(x,x):x\in\mathcal{X}\}$.

  The neighborhood is $N(x)=\{x\}$ and $y=x_{Test}$. The problem boils down to the standard problem of learning without adversary.

• If $R_1$,$R_2$ are two nearness relations and $R_1\sube R_2$, then $R_2$ represents a stronger adversary.

• One way to produce a relation $R$ is from a distance $d$ on $\mathcal{X}$ and an adversarial budget constraint $\epsilon$, i.e.

  $$R=\{(x,y):d(x,y)\le\epsilon\}$$

Adversarial Expected Risk (Definition 1)

The learner's risk under the true distribution in the presence of an adversary constraint by the relation $R$ is

The risk will be minimized when the worst-case adversarial example can still be handled by the hypothesis $h$.

Let $h^*=\arg\min_{h\in\mathcal{H}}L_P(h,R)$. Then, learning is possible if there is an algorithm that, with high probability, gives us $\hat{h}_n$ such that $L_{P}(\hat{h}_n)-L_P(h^*)\to 0$.

The unaccessible true distribution $P$ is approximated with the distribution of the empirical random variable for the learner.

Adversarial Empirical Risk Minimization (ERM) (Definition 2)

The adversarial empirical risk minimizer $AERM_{\mathcal{H},R}:(\mathcal{X}\times\mathcal{C})^n\to(\mathcal{X}\to\mathcal{C})$ is defined as

where $L_{(\bold{x},\bold{c})}$ is the expected loss under the empirical distribution.

$(\bold{x},\bold{c})$ is an empirical distribution drawn from the potential space of distributions.

AERM is the best hypothesis based on the empirical distribution.

Lemma 1

Let $A:(\mathcal{X}\times\mathcal{C})^n\to(\mathcal{X}\to\mathcal{C})$ be learning algorithm for a hypothesis class $\mathcal{H}$. Suppose $R_1$,$R_2$ are nearness relations and $R_1\sube R_2$. For all $P$,

For all $P$ and all $(\bold{x},\bold{c})$,

In other words, if we design a learning algorithm for an adversary constrained by $R_2$, its performance against a weaker adversary is better.

This is natural by definition.

Learnability (Definition 3)

A hypothesis class $\mathcal{H}$ is learnable by empirical risk minimization in the presence of an evasion adversary constrained by $R$ if there is a function $m_{\mathcal{H},R}:(0,1)^2\to\N$ (the sample complexity) with the following property.

For all $0<\delta<1$ and $0<\epsilon<1$, all $n\ge m_{\mathcal{H},R}(\delta,\epsilon)$, and all $P\in\Bbb{P}(\mathcal{X}\times\mathcal{C})$,

When the sample complexity exceeds a certain value, the probability that the difference between empirical risk and expected risk is smaller than $\epsilon$ is larger than $1-\delta$.

Adversarial VC-dimension and sample complexity

Corrupted hypothesis

The presence of the adversary forces us to learn using a corrupted set of hypotheses.

The so-called corrupted hypothesis introduces a new output $\bot$ that means "always wrong".

With the new label set $\tilde{\mathcal{C}}=\{-1,1,\bot\}$, the information in $\mathcal{H}$ and $R$ can be combined into a single set $\tilde{\mathcal{H}}\sube(\mathcal{X}\to\tilde{\mathcal{C}})$ by defining a mapping $\kappa_R:(\mathcal{X}\to\mathcal{C})\to(\mathcal{X}\to\tilde{\mathcal{C}})$ and $\kappa_R(h):\mathcal{X}\to\tilde{\mathcal{C}}$:

This mapping maps the original hypothesis to a hypothesis with a corrupted label. If two points in the same neighborhood of $x$ are classified into different labels, then $x$ is labeled as corrupted.

The corrupted set of hypothesis is then $\tilde{\mathcal{H}}=\{\kappa_R(h):h\in \mathcal{H}\}$.

It's equivalent between learning an ordinary hypothesis with an adversary and learning a corrupted hypothesis without an adversary.

Lemma 2

For any nearness relation $R$ and distribution $P$,

Proof

Let $\tilde{h}=\kappa_R(h)$. For all $(x,c)$,

So there exists lemma 2, i.e.

Lemma 2 states that the risk of a hypothesis with the presence of an adversary in neighborhood bounded by relation $R$ is equal to the risk of the corresponding corrupted hypothesis constructed by relation $R$ with the presence of an "adversary" that is not capable of changing the data point (there is only one point in the neighborhood), i.e. in the neighborhood bounded by identity relation.

Loss classes

The loss classes (composition of loss and classifier functions) $\mathcal{F},\tilde{\mathcal{F}}\sube (\mathcal{X}\times\tilde{\mathcal{C}}\to\{0,1\})$ derived from $\mathcal{H}$ and $\tilde{\mathcal{H}}$ respectively are defined as:

In which, $\lambda$ maps a hypothesis to a loss class, i.e.

And $\lambda(h)$ is defined as:

If the predicted label of the hypothesis on a data point is not correct, then $\lambda(h)(h(x),c)=1$, otherwise 0.

An element of $\mathcal{F}$ is an error measure on the hypothesis.

Lemma 3

Let $\hat{f}=\lambda(\kappa(AERM_{\mathcal{H},R}(\bold{x},\bold{c})))$. With probability $1-\delta$,

where

This lemma states that the error rate of the corrupted hypothesis corresponding to the Adversarial Empirical Risk Minimizer hypothesis minus the infimum of the error rate of the corrupted hypothesis is upper bounded.

Adversarial VC-dimension

Equivalent shattering coefficient definitions

The $i^{th}$ shattering coefficient of a family of binary classifiers $\mathcal{H}\sube (\mathcal{X}\times\mathcal{C})$ is $\sigma(\mathcal{H},i)=\max_{\bold{y}\in\mathcal{X}^i}|\{(h(y_0),\dots,h(y_{i-1})):h\in\mathcal{H}\}|$.

The alternative definition of shatter in terms of the loss class $\mathcal{F}\sube (\mathcal{X}\times\mathcal{C}\to\{0,1\})$ is

These two definitions are equivalent as they shown.

The ordinary VC-dimension is then

From VC dimension - Wikipedia:

The VC dimension of a model $f$ is the maximum number of points that can be arranged so that f shatters them. More formally, it is the maximum cardinal $D$ such that some data point set of cardinality $D$ can be shattered by $f$.

If a set of points can be shattered by some model, it means that the model can always classify these points assigned with arbitrary labels from $\{0,1\}$. For a set with $n$ data points, the number of the possible assignments of labels is $2^n$.

The VC dimension of a hypothesis (model) is the largest number (cardinality, i.e. $|\cdot|$) of elements in a set that can be shattered by this hypothesis.

Adversarial VC-dimension

The adversarial VC-dimension is

The ordinary VC-dimension of corrupted hypothesis.

These definitions and lemmas can now be combined to obtain a sample complexity upper bound for PAC-learning in the presence of an evasion adversary.

Theorem 1 (Sample complexity upper bound with an evasion adversary)

For a space $\mathcal{X}$, a classifier family $\mathcal{H}$, and an adversarial constraint $R$, there is a universal constant $C$ such that

where $d=AVC(\mathcal{H},\mathcal{R})$.

It seems to state that the number of samples required by the learning in the presence of an adversary is finite?

The adversarial VC-dimension of halfspace classifiers

A halfspace classifier has a hyperplane as a binary classification boundary.

Convex constraint on binary adversarial relation

Let $\mathcal{B}$ be a nonempty, closed, convex origin-symmetric set.

The seminorm derived from $\mathcal{B}$ is $||x||_{\mathcal{B}}=\inf\{\epsilon\in\R_{\ge 0}:x\in\epsilon \mathcal{B}\}$, and the associated distance $d_{\mathcal{B}}(x,y)=||x-y||_{\mathcal{B}}$.

Let $V_{\mathcal{B}}$ be the largest linear subspace contained in $\mathcal{B}$.

The adversarial constraint derived from $\mathcal{B}$ is $R=\{(x,y):y-x\in\mathcal{B}\}$, or equivalently $N(x)=x+\mathcal{B}$.

This definition of $R$ encompasses all $\ell_p$ bounded adversaries, as long as $p\ge 1$.

Definition 7

Let $\mathcal{H}$ be a family of classifiers on $\mathcal{X}=\R^d$.

For an example $x\in\mathcal{X}$ and a classifier $h\in\mathcal{H}$, define the signed distance to the boundary to be

For a list of examples $\bold{x}=(x_0,\dots,x_{n-1})\in\mathcal{X}^n$, define the signed distance set to be

Let $\mathcal{H}$ be the family of halfspace classifiers, i.e.

And define $\text{sgn}(0)=\bot$.

It well known that the VC-dimension of this family is $d+1$.

Theorem 2

Let $\mathcal{H}$ be the family of halfspace classifiers of $\mathcal{X}=\R^d$.

Let $\mathcal{B}$ be a nonempty, closed, convex, origin-symmetric set.

Let $R=\{(x,y):y-x\in\mathcal{B}\}$.

Then $AVC(\mathcal{H},R)=d+1-\dim(V_B)$.

In particular, when $\mathcal{B}$ is a bounded $\ell_p$ ball, $\dim(V_B)=0$, giving $AVC(\mathcal{H},R)=d+1$.

The proof is in the original paper.

This theorem states that the VC-dimension of a halfspace classifier with the presence of an $\ell_p$ bounded adversary is the same as a normal halfspace classifier.

Adversarial VC dimension can be larger

We have shown in the previous section that the adversarial VC-dimension can be smaller than or equal to the standard VC-dimension.

Theorem 3

For any $d\in\N$, there is a space $\mathcal{X}$, an adversarial constraint $R\sube\mathcal{X}\times\mathcal{X}$, and a hypothesis class $\mathcal{H}:\mathcal{X}\to\mathcal{C}$ such that $VC(\mathcal{H})=1$ and $AVC(\mathcal{H},R)\ge d$.

Proof

Let $\mathcal{X}=\Z^d$. Let $\mathcal{H}=\{h_x:x\in\mathcal{X}\}$, where

The VC dimension of this family is 1 because no classifier outputs the labeling $(1,1)$ for any pair of distinct examples.

This family of hypothesis checks if the input is some designated point or not, hence it can only shatter a set of one point.

Consider the adversary with an $\ell_{\infty}$ budget of 1. No degraded classifier will ever output 1, only 0 and $\bot$.

Because for a degraded classifier to output 1, the neighborhood of the designated point should all be predicted as 1, but there is only one point can be predicted as 1.

Take $\bold{x}=(x_0,\dots,x_{d-1})\in(\Z^d)^d$:

Now consider the $2^d$ classifiers that are the indicators for $y\in\{0,1\}^{[d]}:\tilde{h}_y=\kappa(h_y)$.

Observe that

because if $y_i=1$, then $d_{\infty}(x_i,y)=2$, but if $y_i=0$ then $d_{\infty}(x_i,y)=1$.

Thus $(f_y(x_0),\dots,f_y(x_{d-1}))$ contains $\bot$ at each index that $y$ contains 1. If the examples are all labeled with $-1$, this subset of the degraded classifier family achieves all $2^d$ possible error patterns. (???)

The adversarial VC-dimension is at least $d$.

This example shows that an adversary can not only affect the optimal loss, as shown in Lemma 1, but can also slow the convergence rate to the optimal hypothesis.

Concluding remarks

While our results provide a useful theoretical understanding of the problem of learning with adversaries, the nature of the 0-1 loss prevents the efficient implementation of Adversarial ERM to obtain robust classifiers.

In practice, recent work on adversarial training [33, 52, 75], has sought to improve the robustness of classifiers by directly trying to find a classifier that minimizes the Adversarial Expected Risk, which leads to a saddle point problem [52].

A number of heuristics are used to enable the efficient solution of this problem, such as replacing the 0-1 loss with smooth surrogates like the logistic loss and approximating the inner maximum by a Projected Gradient Descent (PGD)-based adversary [52] or by an upper bound [63].

Our framework now allows for an analysis of the underlying PAC learning problem for these approaches.

• An interesting direction is thus to find the adversarial VC-dimension for more complex classifier families such as piece-wise linear classifiers and neural networks.
• Another natural next step is to understand the behavior of convex learning problems in the presence of adversaries, in particular the Regularized Loss Minimization framework.

Inspirations

This paper is pure theoretical, without supporting experiments.

They propose a framework to encompass an adversary into PAC-learning, which is meaningful but so far not that useful.

They prove that for halfspace classifiers, the VC-dimension with the presence of an adversary is equal or less than that without adversary, but this relation varies in different families of classifiers.

It means that for a halfspace classifier, with the presence of an adversary, the sample complexity required is equal or less than that without adversary. In other words, an adversary may improve the performance of a halfspace classifier with limited number of data points. (Is this understanding correct ?)

If the understanding is correct, than a proper adversary (not $\ell_p$ bounded, since the VC dimension would be the same) can improve the performance of few shot learning.