When are Local Queries Useful for Robust Learning Pascale Gourdeau Varun Kanade Marta Kwiatkowska and James Worrell University of Oxford

2025-04-26 0 0 962.48KB 25 页 10玖币

侵权投诉

When are Local Queries Useful for Robust Learning?

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell

University of Oxford

Abstract

Distributional assumptions have been shown to be necessary for the robust learnability of concept

classes when considering the exact-in-the-ball robust risk and access to random examples by Gourdeau

et al. (2019). In this paper, we study learning models where the learner is given more power through

the use of local queries, and give the ﬁrst distribution-free algorithms that perform robust empirical

risk minimization (ERM) for this notion of robustness. The ﬁrst learning model we consider uses local

membership queries (LMQ), where the learner can query the label of points near the training sample. We

show that, under the uniform distribution, LMQs do not increase the robustness threshold of conjunctions

and any superclass, e.g., decision lists and halfspaces. Faced with this negative result, we introduce the

local equivalence query (

LEQ

) oracle, which returns whether the hypothesis and target concept agree in

the perturbation region around a point in the training sample, as well as a counterexample if it exists. We

show a separation result: on the one hand, if the query radius

is strictly smaller than the adversary’s

perturbation budget

, then distribution-free robust learning is impossible for a wide variety of concept

classes; on the other hand, the setting

allows us to develop robust ERM algorithms. We then bound

the query complexity of these algorithms based on online learning guarantees and further improve these

bounds for the special case of conjunctions. We ﬁnish by giving robust learning algorithms for halfspaces

{0,1}n

and then obtaining robustness guarantees for halfspaces in

against precision-bounded

adversaries.

1 Introduction

Adversarial examples have been widely studied since the work of (Dalvi et al., 2004; Lowd and Meek, 2005a,b),

and later (Biggio et al., 2013; Szegedy et al., 2013), the latter having coined the term. As presented in Biggio

and Roli (2018), two main settings exist for adversarial machine learning: evasion attacks, where an adversary

perturbs data at test time, and poisoning attacks, where the data is modiﬁed at training time.

The majority of the guarantees and impossibility results for evasion attacks are based on the existence

of adversarial examples, potentially crafted by an all-powerful adversary. However, what is considered to

be an adversarial example has been deﬁned in two diﬀerent, and in some respects contradictory, ways in

the literature. The exact-in-the-ball notion of robustness (also known as error region risk in Diochnos et al.

(2018)) requires that the hypothesis and the ground truth agree in the perturbation region around each test

point; the ground truth must thus be speciﬁed on all input points in the perturbation region. On the other

hand, the constant-in-the-ball notion of robustness (which is also known as corrupted input robustness from

the work of Feige et al. (2015)) requires that the unperturbed point be correctly classiﬁed and that the points

in the perturbation region share its label, meaning that we only need access to the test point labels; see,

e.g., (Diochnos et al., 2018; Dreossi et al., 2019; Gourdeau et al., 2021; Pydi and Jog, 2021) for thorough

discussions on the subject.

We study the problem of robust classiﬁcation against evasion attacks under the exact-in-the-ball deﬁnition

of robustness. Previous work for this problem, e.g., (Diochnos et al., 2020; Gourdeau et al., 2021), has

considered the setting where the learner only has access to random examples. However, many defences against

evasion attacks have used adversarial training, the practice by which a dataset is augmented with previously

arXiv:2210.06089v2 [cs.LG] 20 Jul 2023

misclassiﬁed points. Moreover, in the learning theory literature, some learning models give more power to the

learner, e.g., by using membership and equivalence queries. Our work studies the robust learning problem

mentioned above from a learning theory point of view, and investigates the power of local queries in this

setting.

1.1 Our Contributions

We outline our contributions below. All our results use the exact-in-the-ball deﬁnition of robustness.

Conceptually, we study the powers and limitations of robust learning with access to oracles that only reveal

information nearby the training sample. Our results are particularly relevant as they contrast with the

impossibility of robust learning in the distribution-free setting when only random examples are given, as

demonstrated in Gourdeau et al. (2019).

Limitations of the Local Membership Query Model. In the local membership query (

LMQ

) model,

the learner is allowed to query the label of points in the vicinity of the training sample. This model was

introduced by Awasthi et al. (2013) and shown to guarantee the PAC learnability of various concept classes

(which are believed or known to be hard to learn with only random examples) under distributional assumptions.

However, we show that LMQs do not improve the robustness threshold of the class of conjunctions under the

uniform distribution. Indeed, any

-robust learning algorithm will need a joint sample and query complexity

that is exponential in

, and thus superpolynomial in the input dimension

against an adversary that can

ﬂip ρ=ω(log n)input bits.

The Local Equivalence Query Model. Faced with the query lower bound for the

LMQ

above, one may

consider giving a diﬀerent power to the learner to improve robust learning guarantees. We thus introduce

the local equivalence query (

LEQ

) model, where the learner is allowed to query whether a hypothesis and

the ground truth agree in the vicinity of points in the training sample. The

LEQ

oracle is the natural

exact-in-the-ball analogue of the Perfect Attack Oracle introduced in Montasser et al. (2021), which was

developed for the constant-in-the-ball robustness. It is also a variant of Angluin’s equivalence query oracle

(Angluin, 1987).

Distribution-Free Robust ERM with an

LEQ

Oracle. We show that having access to a robustly

consistent learner (i.e., one that can get zero robust risk on the training sample) gives sample complexity

upper bounds that are logarithmic in the size of the hypothesis class or linear in the VC dimension of the

robust loss–a complexity measure akin to the adversarial VC dimension of Cullina et al. (2018), which we

adapted for our notion of robustness. We study the setting where the learner has access to random examples

and an

LEQ

oracle. In the case where the query radius

of the

LEQ

oracle is strictly smaller than the

adversarial perturbation budget

, we show that, for a wide variety of concept classes, distribution-free

robust learning is impossible, regardless of the training sample size. In contrast, when

we exhibit

robustly consistent learners that use an

LEQ

oracle. This separation result further validates the need for

LEQ

oracle in the distribution-free setting. We furthermore use online learning setting results to exhibit

upper bounds on the

LEQ

oracle query complexity and then improve these bounds in the speciﬁc case of

conjunctions. Finally, we study the sample and query complexity of halfspaces on

{0,1}n

, giving robustness

guarantees in this case. For halfspaces in

, we obtain sample complexity bounds for linear classiﬁers against

bounded

ℓ2

-norm adversaries. To obtain query complexity bounds, we more generally consider adversaries

with bounded precision, and exhibit robust learning algorithms for this setting. To the best of our knowledge,

the results presented in this paper feature the ﬁrst robust empirical risk minimization (ERM) algorithms for

the exact-in-the-ball robust risk in the literature.1

Note that previous work, e.g., Gourdeau et al. (2021), used PAC learning algorithms as black boxes, which are not in general

robust risk minimizers, unless they also happen to be exact learning algorithms, and that (Montasser et al., 2019, 2021) use the

constant-in-the-ball deﬁnition of robustness.

1.2 Related Work

Learning with Membership and Equivalence Queries. Membership and equivalence queries (MQ

and EQ, respectively) have been widely used in learning theory. Membership queries allow the learner to

query the label of any point in the input space

, namely, if the target concept is

returns

(

)when

queried with

x∈ X

. Recall that, in the probably approximately correct (

PAC

) learning model of Valiant

(1984), the learner has access to the example oracle

(

c, D

), which upon being queried returns a point

x∼D

sampled from the underlying distribution and its label

(

), and the goal is to output

such that with

high probability

has low error.

The

oracle takes as input a hypothesis

and returns whether

and provides a counterexample

such that

(

)

(

)when

c̸

. The seminal work of Angluin (1987)

showed that deterministic ﬁnite automata (DFA) are exactly learnable with a polynomial number of queries

and

in the size of the DFA. Many classes were then shown to be learnable in this setting as well as

others, see e.g., (Bshouty, 1993; Angluin, 1988; Jackson, 1997). Moreover, the

model has recently

been used to extract weighted automata from recurrent neural networks (Weiss et al., 2018, 2019; Okudono

et al., 2020), for binarized neural network veriﬁcation (Shih et al., 2019), and interpretability (Camacho and

McIlraith, 2019). But even these powerful learning models have limitations: learning DFAs only with

is hard (Angluin, 1990) and, under cryptographic assumptions, they are also hard to learn solely with the

oracle (Angluin and Kharitonov, 1995). It is also worth noting that the

learning model has been

criticized by the applied machine learning community, as labels can be queried in the whole input space,

irrespective of the distribution that generates the data. In particular, (Baum and Lang, 1992) observed that

query points generated by a learning algorithm on the handwritten characters often appeared meaningless to

human labelers. Awasthi et al. (2013) thus oﬀered an alternative learning model to Valiant’s original model,

the PAC and local membership query (

LMQ

) model, where the learning algorithm is only allowed to

query the label of points that are close to examples from the training sample. Bary-Weisberg et al. (2020)

later showed that many concept classes, including DFAs, remain hard to learn in the EX +LMQ.

Existence of Adversarial Examples. It has been shown that, in many instances, the vulnerability of

learning models to adversarial examples is inevitable due to the nature of the learning problem. The majority

of the results have been shown for the constant-in-the-ball notion of robustness, see e.g., (Fawzi et al., 2016,

2018a,b; Gilmer et al., 2018; Shafahi et al., 2019; Tsipras et al., 2019). As for the exact-in-the-ball deﬁnition

of robustness, Diochnos et al. (2018) consider the robustness of monotone conjunctions under the uniform

distribution. Using the isoperimetric inequality for the boolean hypercube, they show that an adversary that

can perturb up to

(

√n

)bits can increase the misclassiﬁcation error from 0.01 to 1

2. Mahloujifar et al.

(2019) then generalize this result to Normal Lévy families and a class of well-behaved classiﬁcation problems

(i.e., ones where the error regions are measurable and average distances exist).

Sample Complexity of Robust Learning. Our work uses a similar approach to Cullina et al. (2018),

who deﬁne the notion of adversarial VC dimension to derive sample complexity upper bounds for robust ERM

algorithms, with respect to the constant-in-the-ball robust risk. Montasser et al. (2019) use the same notion

of robustness and show sample complexity upper bounds for robust ERM algorithms that are polynomial in

the VC and dual VC dimensions of concept classes, giving general upper bounds that are exponential in the

VC dimension–though they sometimes must be achieved by an improper learner. Ashtiani et al. (2020) build

on their work and delineate when proper robust learning is possible. On the other hand, (Khim et al., 2019;

Yin et al., 2019; Awasthi et al., 2020) study adversarial Rademacher complexity bounds for robust learning,

giving results for linear classiﬁers and neural networks when the robust risk can be minimized (in practice,

this is approximated with adversarial training). Viallard et al. (2021) derive PAC-Bayesian generalization

bounds for the averaged risk on the perturbations, rather than working in a worst-case scenario. As for the

exact-in-the-ball deﬁnition of robustness, Diochnos et al. (2020) show that, for a wide family of concept

classes, any learning algorithm that is robust against all

(

)attacks must have a sample complexity

This is known as the realizable setting. It is also possible to have an arbitrary joint distribution over the examples and

labels, in which case we are working in the agnostic setting.

that is at least an exponential in the input dimension

. They also show a superpolynomial lower bound in

case

= Θ(

√n

). Gourdeau et al. (2019) show that distribution-free robust learning is generally impossible.

They also show that monotone conjunctions have a robustness threshold of Θ(

log n

)under log-Lipschitz

distributions,

meaning that this class is eﬃciently robustly learnable against an adversary that can perturb

log n

bits of the input, but if an adversary is allowed to perturb

(

log n

)bits of the input, there does not

exist a sample-eﬃcient learning algorithm for this problem. Gourdeau et al. (2021) extended this result to

the class of monotone decision lists and Gourdeau et al. (2022a) showed a sample complexity lower bound

for monotone conjunctions that is exponential in

and that the robustness threshold of decision lists is

also Θ(

log n

). Finally, Diakonikolas et al. (2020) and Bhattacharjee et al. (2021) have used online learning

algorithms for robust learning with respect to the constant-in-the-ball notion of robustness.

Restricting the Power of the Learner and the Adversary. Most adversarial learning guarantees

and impossibility results in the literature have focused on all-powerful adversaries. Recent work has studied

learning problems where the adversary’s power is curtailed, e.g, Mahloujifar and Mahmoody (2019) and Garg

et al. (2020) study the robustness of classiﬁers to polynomial-time attacks. Closest to our work, Montasser

et al. (2020, 2021) study the sample and query complexity of robust learning with respect to the constant-

in-the-ball robust risk when the learner has access to a Perfect Attack Oracle (PAO). For a perturbation

type

X →

, hypothesis

and labelled point (

x, y

), the PAO returns the constant-in-the-ball robust

loss of

in the perturbation region

(

)and a counterexample

where

(

)

if it exists. Our

LEQ

oracle is the natural analogue of the PAO oracle for our notion of robustness. In the constant-in-the-ball

realizable setting,

the authors use online learning results to show sample and query complexity bounds that

are linear and quadratic in the Littlestone dimension of concept classes, respectively (Montasser et al., 2020).

Montasser et al. (2021) moreover use the algorithm from (Montasser et al., 2019) to get a sample complexity

OVC(H)VC∗2(H)+log(1/δ)

ϵ

and query complexity of

VC(H)2VC∗(H)2log2(VC∗(H))Lit

(

)), where

VC∗

(

)is

the dual VC dimension of the hypothesis class

. Finally, they extend their results to the agnostic setting

and derive lower bounds. As in the setting with having only access to the example oracle, diﬀerent notions

of robustness have vastly diﬀerent implications in terms of robust learnability of certain concept classes.

Whenever relevant, we will draw a thorough comparison in the next sections between our work and that of

Montasser et al. (2021).

2 Problem Set-Up

We work in the PAC learning framework (see Appendix A.1), with the distinction that a robust risk function

is used instead of the standard risk. We will study metric spaces (

Xn, d

)of input dimension

with a

perturbation budget function

N→R

deﬁning the perturbation region

Bρ

(

) :=

{z∈ Xn|d(x, z)≤ρ(n)}

When the input space is the boolean hypercube Xn={0,1}n, the metric is the Hamming distance.

We use the exact-in-the-ball robust risk, which is deﬁned w.r.t. a hypothesis

, target

and distribution

as the probability R

(

h, c

) :=

x∼D(∃z∈Bρ(x). c(z)̸=h(z))

that

and

disagree in the perturbation

region. On the other hand, the constant-in-the-ball robust risk is deﬁned as

x∼D(∃z∈Bρ(x). c(x)̸=h(z))

Note that it is possible to adapt the latter to a joint distribution on the input and label spaces, but that

there is an implicit realizability assumption in the former as the prediction on perturbed points’ labels are

compared to the ground truth

. We emphasize that choosing a robust risk function should depend on the

learning problem at hand. The constant-in-the-ball notion of robustness requires a certain form of stability:

the hypothesis should be correct on a random example and not change label in the perturbation region; this

robust risk function may be more appropriate in settings with a strong margin assumption. In contrast, the

exact-in-the-ball notion of robustness speaks to the ﬁdelity of the hypothesis to the ground truth, and may be

more suitable when a considerable portion of the probability mass is in the vicinity of the decision boundary.

3A distribution is log-Lipschitz if the logarithm of the density function is log(α)-Lipschitz w.r.t. the Hamming distance.

4In the realizable setting, there exists a hypothesis that has zero constant-in-the-ball robust loss.

Diochnos et al. (2018); Dreossi et al. (2019); Gourdeau et al. (2021); Pydi and Jog (2021) oﬀer a thorough

comparison between diﬀerent notions of robustness.

In the face of the impossibility or hardness of robustly learning certain concept classes, either through

statistical or computational limitations, it is natural to study whether these issues can be circumvented by

giving more power to the learner. The

-local membership query (

LMQ

) set up of Awasthi et al. (2013),

which is formally deﬁned in Appendix A.3, allows the learner to query the label of points that are at distance

at most

from a sample

drawn randomly from

. Inspired by this learning model, we deﬁne the

-local

equivalence query (

LEQ

) model where, for a point

in a sample

drawn from the underlying distribution

, the learner is allowed to query an oracle that returns whether

agrees with the ground truth

in the ball

Bλ

(

)of radius

around

If they disagree, a counterexample in

Bλ

(

)is returned as well. Clearly, by

setting

, we recover the

oracle.

Note moreover that when

, this is equivalent to querying the

(exact-in-the-ball) robust loss around a point. We will show a separation result for robust learning algorithms

between models that only allow random examples and ones that allow random examples and access to

LEQ

Deﬁnition 1 (

LEQ

Robust Learning).Let

be the instance space,

a concept class over

, and

class of distributions over

. We say that

-robustly learnable using

-local equivalence queries with

respect to distribution class,

, if there exists a learning algorithm,

, such that for every

ϵ >

δ >

0, for

every distribution D∈ D and every target concept c∈ C, the following hold:7

1. Adraws a sample Sof size m=poly(n, 1/δ, 1/ϵ)using the example oracle EX(c, D)

Each query made by

x∈S

and for a candidate hypothesis

LEQ

either conﬁrms that

and

coincide on

Bλ

(

)or returns

z∈Bλ

(

)such that

(

)

(

is allowed to update

after seeing

a counterexample

3. Aoutputs a hypothesis hthat satisﬁes RD

ρ(h, c)≤ϵwith probability at least 1−δ

The running time of

(hence also the number of oracle accesses) is polynomial in

/ϵ

/δ

and the

output hypothesis his polynomially evaluable.

We remark that this model evokes the online learning setting, where the learner receives counterexamples

after making a prediction, but with a few key diﬀerences. Contrary to the online setting (and the exact

learning framework with

and

), there is an underlying distribution with which the performance of the

hypothesis is evaluated in both the

LMQ

and

LEQ

models. Moreover, in online learning, when receiving a

counterexample, the only requirement is that there is a concept that correctly classiﬁes all the data given to

the learner up until that point, and so the counterexamples can be given in an adversarial fashion, in order

to maximize the regret. However, both the

LMQ

and

LEQ

models require that a target concept be chosen a

priori. Note though that the LEQ oracle can give any counterexample for the robust loss at a given point.

In practice, one always has to ﬁnd a way to approximately implement oracles studied in theory. A possible

way to generate counterexamples with respect to the exact-in-the-ball notion of robustness is as follows.

Suppose that there is an adversary that can generate points

z∈Bρ

(

)such that

(

)

(

). Provided such

an adversary can be simulated, there is a way to (imperfectly) implement the

LEQ

oracle in practice. Thus,

the use of these oracles can be viewed as a form of adversarial training.

Both the

LMQ

and

LEQ

models are particularly well-suited for the standard and exact-in-the-ball risks,

as they address information-theoretic limitations of learning with random examples only. On the other hand,

while information-theoretic limitations of robust learning with respect to the constant-in-the-ball notion of

robustness arise when the perturbation function

is unknown to the learner, computational obstacles can also

occur even when the deﬁnition of

is available. Indeed, determining whether the hypothesis changes label in

the perturbation region could be intractable. In these cases, the Perfect Attack Oracle of Montasser et al.

Similarly to

, we implicitly consider

as a function of the input dimension

. It is also possible to extend this deﬁnition to

an arbitrary perturbation function U:X → 2X.

6This is evidently not the case for the Perfect Attack Oracle of Montasser et al. (2021).

We implicitly assume that a concept

c∈ C

can be represented in size polynomial in

, where

is the input dimension;

otherwise a parameter size(c)can be introduced in the sample and query complexity requirements.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

WhenareLocalQueriesUsefulforRobustLearning?PascaleGourdeau,VarunKanade,MartaKwiatkowska,andJamesWorrellUniversityofOxfordAbstractDistributionalassumptionshavebeenshowntobenecessaryfortherobustlearnabilityofconceptclasseswhenconsideringtheexact-in-the-ballrobustriskandaccesstorandomexamplesbyGourdeau...

展开>> 收起<<

When are Local Queries Useful for Robust Learning Pascale Gourdeau Varun Kanade Marta Kwiatkowska and James Worrell University of Oxford.pdf

共25页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

When are Local Queries Useful for Robust Learning Pascale Gourdeau Varun Kanade Marta Kwiatkowska and James Worrell University of Oxford

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: