5,337
edits
Line 725: | Line 725: | ||
===Are adversarial examples inevitable?=== | ===Are adversarial examples inevitable?=== | ||
====Notations==== | |||
<math>S^{d-1} = \{x \in \mathbb{R} \mid \Vert x \Vert = 1\}</math> | <math>S^{d-1} = \{x \in \mathbb{R} \mid \Vert x \Vert = 1\}</math> | ||
Let the geodesic distance be denoted by <math>d_{g}</math>. | Let the geodesic distance be denoted by <math>d_{g}</math>. | ||
Line 738: | Line 738: | ||
<math>A(\epsilon, d) = \{x \mid d(x,z)\leq \epsilon \text{ for some } z \in A\}</math>. | <math>A(\epsilon, d) = \{x \mid d(x,z)\leq \epsilon \text{ for some } z \in A\}</math>. | ||
====Isoperimetric Inequality==== | |||
Of all closed surfaces that encloses a unit volume, the sphere has the smallest surface. | Of all closed surfaces that encloses a unit volume, the sphere has the smallest surface. | ||
Very intuitive but difficult to prove. (Osserman et al 1976) | Very intuitive but difficult to prove. (Osserman et al 1976) | ||
Line 770: | Line 770: | ||
The area of the complement is <math>u_1(R^c) \geq \frac{1}{2}</math>. | The area of the complement is <math>u_1(R^c) \geq \frac{1}{2}</math>. | ||
The area of the epsilon expansion is <math>u_1(R^c(\epsilon)) \geq 1 - (\pi/8)^{1/2} \exp(-\frac{d-1}{2}\epsilon^2)</math>. Thus the ''safe zone'' is very small in high dimension. | The area of the epsilon expansion is <math>u_1(R^c(\epsilon)) \geq 1 - (\pi/8)^{1/2} \exp(-\frac{d-1}{2}\epsilon^2)</math>. Thus the ''safe zone'' is very small in high dimension. | ||
====Cubes==== | |||
Geometric isoparametric inequalities do not exist for cubes. | |||
However, algebraic inequalities exist. | |||
;Lemma | ;Lemma | ||
Line 781: | Line 785: | ||
This shows if you pick a random sample, there is a high probability of it being misclassified or there being an adversarial example within epsilon. | This shows if you pick a random sample, there is a high probability of it being misclassified or there being an adversarial example within epsilon. | ||
====Are adversarial examples inevitable in practice?==== | |||
This is an ill-posed question. | This is an ill-posed question. | ||
It depends on the data distribution, threat model, and hypothesis class. | It depends on the data distribution, threat model, and hypothesis class. |