Adversarial examples from computational constraints

Introduction

Such an input $X+z$ in the above event is colloquially referred to as an adversarial exampleIn the literature one sometimes uses a more stringent definition of adversarial examples, where $X$ and $z$ are in addition required to satisfy $f(X+z)=f(X)$. We ignore this requirement here..

Following Szegedy et al. there is a rapidly expanding literature exploring the vulnerability of neural networks to adversarially chosen perturbations. The surprising observation is that, say in vision applications, for most images $X\sim D$ the perturbation can be chosen in a way that is imperceptible to a human yet dramatically changes the output of state-of-the-art neural networks. This is a particularly important issue as these neural networks are currently being deployed in real-world situations. Naturally there is by now a large literature (in fact going back at least to ) on attacks (finding adversarial perturbations) and defenses (making classifiers robust against certain type of attacks).

While we have a sophisticated theory for the classical goal of minimizing the non-robust probability of error, our understanding of the robust scenario is still very rudimentary. At the moment, the “attackers” seem to be winning the arms race against the “defenders”, see e.g., . We identify four mutually exclusive possibilities for why all known classification algorithms are vulnerable to adversarial examples:

Identifying a robust classifier requires too much training data.

Identifying a robust classifier from limited training data is information theoretically possible but computationally intractable.

We just have not found the right algorithm yet.

The goal of this paper is to provide two pieces of evidence, one in favor of hypothesis 3 and one against hypothesis 2. Our primary result is that hypothesis 3 is indeed possible: there exist robust classification tasks that are information theoretically easy but computationally intractable under a powerful model of computation (namely the statistical query model, see below). Our secondary result is evidence against hypothesis 2, showing that if a robust classifier exists then it can be found with relatively few training examples under a standard assumption on the data distribution (for example, that the distribution within each label is close to a Lipschitz generative model, or is drawn from a finite set of exponential size).

In Section 1.1 we discuss related work on adversarial examples in light of those four hypotheses. In Section 1.2 we introduce the model of computation under which we will prove intractability. We conclude the introduction with Section 1.3 where we give a brief proof overview for our primary and secondary result. These results are discussed in greater depth respectively in Section 4 and Section 3.

To the best of our knowledge, previous works have not linked computational constraints to adversarial examples, but instead have focused on the other three hypotheses.

Another work arguing the inevitability of adversarial examples is Gilmer et al. . There the authors propose a simple classification task, namely distinguishing between samples on the unit sphere in high dimension and samples on a sphere of radius $R$ bounded away from $1$. They show experimentally that even in such a simple setup, state-of-the-art neural networks have adversarial examples at most points. We note however that this example only applies to specific classifiers, since it is easy to construct an efficient robust classifier for the given example (e.g., just use a linear model on the norm of the features); thus the “hardness” here only appears for a given network structure.

2 The SQ model

Proving computational hardness is a notoriously difficult problem. To circumvent this difficulty one usually either (i) reduces the problem at hand to a well-established computational hardness conjecture (e.g., proving NP-hardness), or (ii) proves an unconditional hardness within a limited computational framework (such as the oracle lower bounds in convex optimization, ). Our task here is further complicated by the average-case nature of the problem (the datasets are i.i.d. from some fixed distribution). Fortunately there is a growing set of results on computational hardness in learning theory that we can leverage. The statistical query (SQ) model of computation from Kearns is a particularly successful instance of approach (ii) for learning theory: (a) most known learning algorithms fall in the framework, including in particular logistic regression, SVM, stochastic gradient descent, etc; and (b) SQ-hardness has been proved for many interesting problems that are believed to be computationally hard, such as learning parity with noise , learning intersection of halfspaces , the planted clique problem , robust estimation of high-dimensional Gaussians , or learning a function computable by a small neural network . Thus we naturally use this model to prove our main result on the computational hardness of robust learning. We now recall the definition of the SQ model and state informally our main result.

not efficiently and robustly learnable in the statistical query model, in the sense that even with an exponential (in $d$) precision statistical query oracle one needs an exponential (in $d$) number of queries in order to robustly learn with robustness parameter $\varepsilon$.

Of course, a number of natural machine learning algorithms such as nearest neighbor are not based on statistical queries. Although we cannot prove it, we believe that our input distributions are computationally hard in general. For the case of nearest neighbor, the distance to points of each class have very similar distributions—indeed, the two distributions match on polynomially many moments. This suggests that exponentially many samples are necessary for nearest neighbor. For more information about nearest neighbor classifiers in the context of adversarial examples, see .

Moreover, there are very few problems in any domain with exponential SQ hardness for which polynomial time algorithms are known; in fact, the only such problems involve solving systems of linear equations over finite fields . Since Theorem 1.1 involves a real-valued problem, finding a polynomial time algorithm that avoids the SQ lower bound would be a remarkable breakthrough in SQ theory.

3 Overview of proofs

Our secondary result, on the information theoretic achievability of robustness, is proved via simple arguments reminiscent of PAC-learning theory. Namely, if a classifier is not good enough for a given pair of distributions, we can rule it out with high confidence by looking at not too many samples. Then, we use a union bound to claim the result for a family of pairs that is either at most exponentially large, or is at least covered by a net of at most exponential size (the only subtlety is in the proper definition of a net in this robust context).

Our primarily result, on the hardness of robustness, is technically much more challenging. The central object in the proof is a natural high-dimensional generalization of a construction from Diakonikolas et al. . Roughly speaking, a hard pair of distributions is obtained by taking a standard multivariate Gaussian, choosing a random $k$-dimensional subspace and planting there two well-separated distributions that match many moments of a Gaussian (in only the case $k=1$ is considered). To show an SQ lower bound, we use – as in – the framework of to reduce the question to computing a certain non-standard notion of correlation between the distributions. To bound said correlation, we deviate from significantly, since their argument is tailored crucially to the case $k=1$. Our argument is less precise, but allows $k\gg 1$ which is necessary to obtain a large separation between the distributions (which in turn controls the parameter $M$ in Theorem 1.1).

Definitions

We say that $\mathcal{D}$ is $(\varepsilon,\delta)$-robustly learnable with $n$ samples if there is a classification algorithm such that, for every $D\in\mathcal{D}$, with probability at least $2/3$ over $\underline{X}_{0}$ and $\underline{X}_{1}$, the algorithm produces a classifier $f$ that is $(\varepsilon,\delta)$-robust for $D$.

The success probability $2/3$ is an arbitrary constant larger than $1/2$. It is easy to see that, for any $\eta>0$, by using $O(n\log(1/\eta))$ samples one can obtain a success probability of $1-\eta$.

We say that $\mathcal{D}$ is $(\varepsilon,\delta)$-robustly feasible if every $D\in\mathcal{D}$ admits an $(\varepsilon,\delta)$-robust classifier. When it exists we denote $f_{D}$ for such a classifier (chosen arbitrarily among all robust classifiers for $D$), and $\mathcal{F}_{\mathcal{D}}=\{f_{D},D\in\mathcal{D}\}$.

Robust learning with few samples

Obviously robust feasibility is a necessary condition for robust learnability. We show that it is in fact sufficient, even for sample efficient robust learnability. We first do so when a finite set of classifiers $\mathcal{F}_{\mathcal{D}}$ suffices for robust feasibility.

Assume that $\mathcal{D}$ is $(\varepsilon,\delta)$-robustly feasible. Then it is $(\varepsilon,\delta+\delta^{\prime})$-robustly learnable with $n=\Omega\left(\frac{\delta+\delta^{\prime}}{\delta^{\prime 2}}\log(|\mathcal{F}_{\mathcal{D}}|)\right)$.

Let $\hat{D}_{i}=\frac{1}{n}\sum_{j=1}^{n}\delta_{\underline{X}_{i}(j)}$ be the empirical measure corresponding to the dataset $\underline{X}_{i}$. We will show that ERM on the $\varepsilon$-robust loss gives the claimed sample complexity. More precisely we consider the classification algorithm that outputs:

Now observe that for $n\geq 4\frac{\delta+\delta^{\prime}}{\delta^{\prime 2}}\log(|\mathcal{F}_{\mathcal{D}}|)$ one can has $\sqrt{p_{f_{D}}\log(|\mathcal{F}_{\mathcal{D}}|)/n}\leq\delta^{\prime}/2$ , and thus we obtain with $n=\Omega\left(\frac{\delta+\delta^{\prime}}{\delta^{\prime 2}}\log(|\mathcal{F}_{\mathcal{D}}|)\right)$,

It now suffices to observe that $s\geq\delta+\delta^{\prime}$ implies $s-\frac{\delta^{\prime}}{2}\sqrt{\frac{s}{\delta+\delta^{\prime}}}>\delta+\frac{\delta^{\prime}}{2}$. ∎

2 Robust covering number

With the above definitions one can obtain the following result as a straightforward corollary of Theorem 3.1 and the definition of total variation distance.

It is now easy to prove the following strengthening of Theorem 3.3:

3 Covering number bound from generative models

We now show that distributions approximated by generative models have bounded covering numbers (in terms of Definition 3.4), so Theorem 3.5 gives a good sample complexity for such distributions. The proof is deferred to Appendix C in the supplementary material.

Lower bound for the SQ model

The distributions $\widetilde{D}_{0}$ and $\widetilde{D}_{1}$ admits a $(\Omega(\sqrt{1/\gamma}),2^{-d^{\Omega(\gamma)}})$-robust classifier; moreover, a $\Omega(\sqrt{1/\gamma}),0.01)$-robust classifier can be learned from $O(d)$ samples from $D_{0}$ and $D_{1}$;

For $\widetilde{D_{0}}$ and $\widetilde{D_{1}}$, there exists a linear (non-robust) classifier, which can be learned in polynomial time;

For every $\varepsilon>\rho$, in order to learn a $(\varepsilon,0.01)$-robust classifier for $\widetilde{D}_{0}$ and $\widetilde{D}_{1}$, one needs at least $2^{d^{\Omega(1)}}$ statistical queries with accuracy as good as $2^{-d^{\Omega(\gamma)}}$.

For instance, if $\gamma$ is a small constant we get the existence of a $C$-robust classifier, where $C$ is a large constant. One could push $C$ as high as $\Omega(\log^{1/2-\varepsilon}d)$ at a cost of the lower bound being against SQ queries with somewhat worse accuracy ($2^{-2^{\log^{\Omega(\varepsilon)}d}}$ instead of $2^{-d^{\Omega(1)}}$).

We first show a family of pairs $(D_{0},D_{1})$ that admit a robust classifier, yet it is hard (in the SQ model) to learn any (non-robust) classifier. Later, in Section 4.3, we show a simple modification of this family to obtain the main result.

Here we define a hard family of pairs of distributions $(D_{0},D_{1})$ as discussed above. This section contains the definition and key properties of the family; proofs of those properties appear in Appendix A. This family can be seen to be a high-dimensional generalization and modification of a family considered in . The family depends on three parameters: integers $1\leq k\leq d$, $m\geq 1$ and a positive real $\varepsilon>0$.

$D_{A}$ and $D_{B}$ match $N(0,1)$ in the first $m$ moments;

$A,B\in C^{\infty}$, and for every $0\leq l\leq m+1$ and $t$, one has: $|\frac{d^{l}}{dt^{l}}\frac{A(t)}{G(t)}|,|\frac{d^{l}}{dt^{l}}\frac{B(t)}{G(t)}|\leq m^{O(l+1)}$.

For every $k\leq d^{\Omega(1)}$, there exists such a family $\mathcal{U}$ with $\varepsilon\leq d^{-0.49}$ and $|\mathcal{U}|=2^{d^{\Theta(1)}}$.

where $A(\cdot)$ and $B(\cdot)$ are densities of distributions $D_{A}$ and $D_{B}$ from Lemma 4.2, and $G(t)=\frac{1}{\sqrt{2\pi}}\cdot e^{-t^{2}/2}$ is the p.d.f. of the standard Gaussian distribution $N(0,1)$. Now we simply take $D_{0}$ to be $D_{U,A}$ and $D_{1}$ to be $D_{U,B}$.

The heart of the matter is to show that it requires $2^{d^{\Omega(1)}}$ statistical queries with precision $\tau=2^{-d^{\Theta(\gamma)}}$ to learn a classifier for $D_{U,A}$ and $D_{U,B}$ provided that all the parameters $m,k,\varepsilon$ are set correctly. The argument is fairly involved and uses the framework of to reduce the question to that of upper bounding $\chi$-correlation between the distributions. Due to space limitations, we show the argument in Appendix B of the supplementary material.

3 Making the distribution easy to learn non-robustly

Conclusion and future directions

In this paper we put forward the thesis that adversarial examples might be an unavoidable consequence of computational constraints for learning algorithms. Our main piece of evidence is a classification task, for which there essentially exists a classifier robust to Euclidean perturbations of size $\log^{1/2-\varepsilon}d$ (while with high probability any sample has norm $O(\sqrt{d})$), yet finding any non-trivial robust classifier (even for arbitrarily small perturbations, and with probability of correctness only slightly better than chance) is hard in the statistical query model (in the sense that one needs an exponential number of queries, even with a very high precision statistical query oracle). We identify several directions in which this result could be strengthened to give stronger evidence for our thesis.

The most important question for the validity of our thesis is whether one could prove a similar hardness result for natural distributions. This is a particularly challenging open problem as the concept of a natural distribution is fuzzy (for instance there is no consensus on what a natural distribution for images should look like).

We believe that our proposed classification task is really computationally hard in any sense, not only in the statistical query model. As we discussed SQ is natural for learning theory hardness, but there have been lots of works leveraging other types of hardness assumption (e.g., cryptographic). It would be interesting to explore further the position of robust learning in the hardness landscape.

Finally one might wonder whether the perturbation size $\log^{1/2-\varepsilon}d$ is optimal (for distributions essentially supported in a ball of size $\sqrt{d}$). A concrete open question could be phrased as follows: consider a classification task that is $(\Psi(d),0)$-robustly feasible, how fast does $\Psi$ need to grow in order to ensure that one can find in polynomial time a $(1,1/3)$-robust classifier?

References

Appendix A Proofs of properties of the SQ hard distribution

We start with the following lemma on Hermite polynomials:

For every $k>1$, the distance between any roots of $H_{k-1}(t)$ and $H_{k}(t)$ is at least $\Omega(1/\sqrt{k})$.

It is known that extrema of $H_{k}$ are exactly zeros of $H_{k-1}$, which follows from $H_{k}^{\prime}=2kH_{k-1}$ and a lack of double roots. Thus, it is enough to show that extrema and zeros of $H_{k}$ are $\Omega(1/\sqrt{k})$-separated.

Consider the case where $0\leq u<v<w$ are such that $H_{k}(u)=H_{k}(w)=0$, $H_{k}$ is positive between $u$ and $w$, and $H_{k}^{\prime}(v)=0$. Let us show how to lower bound $v-u$. Denote $F_{k}(t)=e^{-t^{2}/2}H_{k}(t)$. Clearly, $F_{k}(u)=F_{k}(w)=0$ and $F_{k}$ is positive between $u$ and $w$ with a unique local maximum on $[u,w]$, which we denote by $v^{\prime}$. It is not hard to check that $v^{\prime}\leq v$. Thus, it is enough to lower bound $v^{\prime}-u$. It is known (see, e.g., [19, Section 5.5] that $F_{k}$ satisfies the ODE $Z^{\prime\prime}+(2k+1-t^{2})Z=0$. By comparing with $Z^{\prime\prime}+(2k+1)Z=0$, we can get that lower bound $v-u\geq v^{\prime}-u\geq\frac{\pi}{2\sqrt{2k+1}}=\Omega(1/\sqrt{k})$.

Now let us lower bound $w-v$. It is known [19, Section 5.5] that $H_{k}$ satisfies the ODE $Z^{\prime\prime}-2tZ^{\prime}+2kZ=0$. By comparing this ODE with $Z^{\prime\prime}-2wZ^{\prime}+2kZ=0$, we get that $w-v\geq\frac{\arctan\left(\frac{\sqrt{2k-w^{2}}}{w}\right)}{\sqrt{2k-w^{2}}}\geq\Omega(1/\sqrt{k})$. The latter step is due to $w\leq\sqrt{2k}$ and that the lower bound on $w-v$ is nonincreasing in $w$.

$D_{A}$ and $D_{B}$ match $N(0,1)$ in the first $m$ moments;

$A,B\in C^{\infty}$, and for every $0\leq l\leq m+1$ and $t$, one has: $|\frac{d^{l}}{dt^{l}}\frac{A(t)}{G(t)}|,|\frac{d^{l}}{dt^{l}}\frac{B(t)}{G(t)}|\leq m^{O(l+1)}$.

Let $H_{m}(t)$ and $H_{m+1}(t)$ be two consecutive (physicist’s) Hermite’s polynomials. It is a classic result in Gaussian quadrature (see, e.g., ) that for every $k$, there exists a discrete distribution supported on the zeros of $H_{k}(t/\sqrt{2})$, which matches $N(0,1)$ in the first $2k-1$ moments. Let $\widetilde{D}_{A}$ denote such a distribution for $H_{m}$ and $\widetilde{D}_{B}$ the same for $H_{m+1}$. By Lemma A.1, the distance between the supports of $\widetilde{D}_{A}$ and $\widetilde{D}_{B}$ is at least $\Omega(1/\sqrt{m})$ and they both match $N(0,1)$ in the first $2m-1\geq m$ moments.

Now, we obtain the desired distributions $D_{A}$ and $D_{B}$ as follows. Fix a small $\delta>0$. The distribution $D_{A}$ is defined as $\sqrt{1-\delta}\cdot x+\sqrt{\delta}\cdot y$, where $x\sim\widetilde{D}_{A}$, $y\sim N(0,1)$, and $x$ and $y$ are independent. The distribution $D_{B}$ is defined similarly, but instead of $\widetilde{D}_{A}$ we use $\widetilde{D}_{B}$. It is easy to check that $D_{A}$ and $D_{B}$ match the first $m$ moments of $N(0,1)$. Now suppose that $\delta=1/m^{2}$. The second property follows from the supports of $\widetilde{D}_{A}$ and $\widetilde{D}_{B}$ being $\Omega(1/\sqrt{m})$ separated and the standard concentration inequalities; specifically, we take $S_{A}$ to be the Minkowski sum of the support of scaled down $\widetilde{D}_{A}$ and the ball of radius $\Theta(1/\sqrt{m})$, and $S_{B}$ to be similar with $\widetilde{D}_{B}$ instead of $\widetilde{D}_{A}$. Then the chance $x\sim D_{A}$ is not in $S_{A}$ is at most the chance $y\sim N(0,1)$ has $|\sqrt{\delta}y|>\Omega(1/\sqrt{m})$, which is $e^{-\Omega(m)}$.

Now let us prove the bounds on $\frac{d^{l}}{dt^{l}}\frac{A(t)}{G(t)}$, for the $B(\cdot)$ similar bounds follows exactly the same way.

Denote $x_{1}<x_{2}<\ldots<x_{m}$ the roots of $H_{m}(t)$.

We have for every $i$ the bound $p_{i}e^{x_{i}^{2}}=O(1)$ . Therefore, if $Q(t)$ denotes the p.d.f. of $N(0,\delta/(1-\delta))$ we have

For every $k\leq d^{\Omega(1)}$, there exists such a family $\mathcal{U}$ with $\varepsilon\leq d^{-0.49}$ and $|\mathcal{U}|=2^{d^{\Theta(1)}}$.

Thus, we can set $\varepsilon=d^{-0.49}$, and $k\leq d^{\sigma}$ for a sufficiently small positive $\sigma$, which yields $|\mathcal{U}|=2^{d^{\Theta(1)}}$. ∎

The points $x\in S_{U,A}$ and $y\in S_{U,B}$ are well-separated, since in at least a $0.8$-fraction of $1\leq i\leq k$, both $\langle x,u_{i}\rangle\in S_{A}$ and $\langle y,u_{i}\rangle\in S_{B}$. Since $S_{A}$ and $S_{B}$ are $\Omega(1/\sqrt{m})$-separated, we obtain the result.

The bounds on the probabilities follow from the respective bounds in Lemma 4.2 and standard Chernoff bounds. ∎

Appendix B SQ lower bound

Now let us show that if we set all the parameters appropriately, it is hard in the SQ model to learn a good classifier (robust or otherwise) for distributions $D_{U,A}$ and $D_{U,B}$ defined above, where $U\in\mathcal{U}$ is an unknown subspace. The main idea is to show that if the subspace $U\in\mathcal{U}$ is chosen uniformly at random, unless we perform more than $2^{d^{\Omega(1)}}$ queries, we can not tell apart $D_{U,A}$ or $D_{U,B}$ from the standard Gaussian $N(0,I_{d})$ (and as a result, from each other). Intuitively, any since query can only reliably distinguish $D_{U,A}$ from $N(0,I_{d})$ for a tiny fraction of subspaces $U\in\mathcal{U}$. The result then follows by a simple counting argument. To formalize the above intuition, we use an argument similar at a high-level to the one used in .

In Section B.2, we show that for an appropriate setting of parameters (namely, when $\varepsilon m^{\Theta(1)}k\leq d^{-\Omega(1)}$), for every $U_{1},U_{2}\in\mathcal{U}$, one has:

Then by repeating the proof of Lemma 3.3 from , we get that if the number of queries is significantly smaller than:

then with high probability over a random subspace $U\in\mathcal{U}$, all the queries asked can be answered as if both $D_{U,A}$ and $D_{U,B}$ were $N(0,I_{d})$. As a result, we cannot distinguish them from $N(0,I_{d})$ and, as a result, between each other.

Suppose that $m\log d>Ck\log m$ for a sufficiently large constant $C$, so that the $m^{O(k)}d^{-\Omega(m)}$ term is less than $d^{-\Omega(m)}<m^{-\Omega(k)}$. Then we can set the precision $\tau$ to $m^{-\Theta(k)}$ and still be unable to distinguish $D_{U,A}$ from $D_{U,B}$ from $|\mathcal{U}|m^{-O(k)}=2^{d^{\Omega(1)}}m^{-O(k)}$ queries. If $m^{O(k)}\leq 2^{d^{\sigma}}$ for a sufficiently small positive $\sigma>0$, this gives the desired lower bound of $2^{d^{\Omega(1)}}$ on the number of SQ queries the algorithm must ask.

B.2 Upper bounding pairwise correlations

We assume that $m^{C}\varepsilon k\leq d^{-\Omega(1)}$ for a sufficiently large constant $C$ to be determined later. Since by Lemma 4.3 we can take $\varepsilon=d^{-0.49}$, the required inequality holds as long as $m$ and $k$ are at most small powers of $d$.

where the fourth step is due to the independence of $\langle x,u_{i}\rangle$ (which is implied by orthogonality of $u_{i}$), and the fifth step follows from Lemma 4.2.

for some $\theta_{i}=\theta_{i}(x)$ that lies between $\langle x,\widetilde{v}_{i}\rangle$ and $\langle x,v_{i}\rangle$.

Suppose $|S|\geq|T|$. For every $l\colon T\to\{0,1,\ldots,m\}$, one has:

Since $v_{i}-\widetilde{v}_{i}\in U_{1}$, we can write $v_{i}-\widetilde{v}_{i}=\sum_{j=1}^{k}\alpha_{ij}u_{j}$. One has:

Now let us fix partitions $\beta_{ij}$ and show that:

Since $\sum_{ij}\beta_{ij}=\sum_{i}l(i)\leq|T|\cdot m$, there exists $j^{*}\in S$ such that: $\sum_{i}\beta_{ij^{*}}\leq\frac{|T|\cdot m}{|S|}\leq m$. Since $\langle x,u_{j^{*}}\rangle$ is independent from the remaining dot products, we can factor from (3) the expression

with $l\leq m$. But since $\langle x,u_{j^{*}}\rangle$ is distributed as $N(0,1)$, one has that (4) is equal to zero due to Lemma 4.2. ∎

Let us continue upper bounding (B.2). For $i\in T$ and $0\leq j\leq m+1$, denote:

Plugging (B.2) into (B.2), we get the result.

B.3 Setting parameters

We obtain a $\Omega(\sqrt{k/m})$-robust classifier, and the precision of statistical queries can be as high as $m^{O(k)}\cdot d^{-\Omega(m)}$. Thus, for $0<\gamma<1/10$, we can set $m=d^{\Theta(\gamma)}$ and $k\ll\frac{m\log d}{\log m}$. As a result we get robustness $\Omega(\sqrt{k/m})=\Omega(\sqrt{\log d/\log m})=\Omega(\sqrt{1/\gamma})$, and the precision of statistical queries can be as good as $2^{-d^{\Omega(\gamma)}}$.

Appendix C Bound on covering number of generative models

by Lemma C.1 and our chosen $\alpha$. Since $\|x\|_{2}\leq\sqrt{k}/\delta$ with probability much higher than $1-\delta$, this implies $D(g_{w^{*}})\in U_{\delta,\delta}(D(g_{\widehat{w}}))$. The triangle inequality then gives $D_{i}\in U_{\varepsilon+\delta,\delta}(D(g_{\widehat{w}}))$ as desired. ∎