5,337
edits
Line 757: | Line 757: | ||
<math>v_c=\delta_{n-1} * u_c</math> is the max density relative to uniform density. | <math>v_c=\delta_{n-1} * u_c</math> is the max density relative to uniform density. | ||
<math>f_c = \mu_1 \{x \mid C(x)=c\}</math> is the area where the classifier <math>C</math> classifies as class c. | <math>f_c = \mu_1 \{x \mid C(x)=c\}</math> is the area where the classifier <math>C</math> classifies as class c. | ||
Pick a class <math>f_c \leq \frac{1}{2}</math>. | Pick a class such that <math>f_c \leq \frac{1}{2}</math>. | ||
Sample x from <math>\rho_c</math>. | Sample a random point x from the true density <math>\rho_c</math>. | ||
With high probability, either: | |||
One of these will happen with probability <math>1-v_c (\frac{\pi}{8})^{1/2} \exp^{- ((d-1)/2) \epsilon^2}</math> | * x is misclassified or, | ||
* x has an <math>\epsilon</math>-close adversarial example. | |||
One of these will happen with probability <math>1-v_c (\frac{\pi}{8})^{1/2} \exp^{- ((d-1)/2) \epsilon^2}</math> | |||
Proof: | Proof: | ||
Consider the region with the correct classification: <math>R=\{x \mid c(x)=c</math>. Here <math>u(R) = f_c \leq 1/2</math>. | Consider the region with the correct classification: <math>R=\{x \mid c(x)=c</math>. Here <math>u(R) = f_c \leq 1/2</math>. |