In the paper 'Intriguing Properties of Neural Networks', the process of finding adversarial examples is set up as follows (section 4.1):

We denote by $f : \mathbb{R}^m → \{1 . . . k\}$ a classifier mapping image pixel value vectors to a discrete label set. We also assume that $f$ has an associated continuous loss function denoted by $\text{loss}_f$ : $\mathbb{R}^m × \{1 . . . k\} → \mathbb{R}^+$. For a given $x ∈ \mathbb{R}^m$ image and target label $l ∈ \{1 . . . k\}$, we aim to solve the following box-constrained optimization problem:

Minimize $\lVert r \rVert_2$ subject to:

  1. $f(x + r) = l$
  2. $x + r ∈ [0, 1]^m$

The minimizer $r$ might not be unique, but we denote one such $x + r$ for an arbitrarily chosen minimizer by $D(x, l)$. Informally, $x + r$ is the closest image to $x$ classified as $l$ by $f$. Obviously, $D(x, f(x)) = f(x)$, so this task is non-trivial only if $f(x) \neq l$. In general, the exact computation of $D(x, l)$ is a hard problem, so we approximate it by using a box-constrained L-BFGS. Concretely, we find an approximation of $D(x, l)$ by performing line-search to find the minimum $c > 0$ for which the minimizer $r$ of the following problem satisfies $f(x + r) = l$.

Minimize $c|r| + \text{loss}_f (x + r, l)$ subject to $x + r ∈ [0, 1]^m$

I have two questions about this passage.

  1. Why is $D(x,f(x))=f(x)$? My interpretation of the definition of $D(x,l)$ from the sentence before is that it is equal to $x+r$ where $r$ is the minimum magnitude vector such that $f(x+r)=l$. It appears that $D(x,f(x))=x$. Am I misunderstanding something here?

  2. Why are we looking for the minimum such $c$? My intuition is that the $c|r|$ term of the problem serves to pull $r$ towards the $0$ vector, while the $loss_f$ term serves to pull $r$ towards the "perfect" input image representing label $l$, which will likely be away from the $0$ vector. If this intuition is true, then increasing $c$ should pull the minimizer $r$ towards the $0$ vector and reduce its magnitude. So I would think we would want to find the maximum $c$ for which the minimizer $r$ of that expression satisfies $f(x+r)=l$, as this would lead to a smaller perturbation that still causes an adversarial example. What is wrong with this logic?


For your first question -- probably just a typo. For your second question, the lagrangian dual of the first formulation would be

$$\max_{\lambda > 0} \min_{r} |r|+ \lambda \text{loss}(x+r,l)$$

If we set $c = 1/\lambda$ and multiply through, then we have

$$\min_{c,r} c|r|+\text{loss}(x+r,l)$$

To gain better intuition on this part, it might help to search for some geometric illustrations of duality (i think math stack exchange has some nice posts about this).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.