Deriving FGSM attack

Question

In a book deriving the update for Fast Gradient Sign Method (FGSM) attack, it is said

$g$ is the target loss, and we can conduct the first-order Taylor expansion of $g(x)$ on the initial solution $x_0$ (assuming that we start from the original natural example): $$g(x)\approx g(x_0) + \nabla g(x_0)^T(x-x_0)$$ We can solve the following constraint optimization problem, which is an approximation of $$\text{argmax}_x \nabla g(x_0)^T (x − x_0) \text{ s.t. } x \in \|x − x_0\|_{\infty} \leq\epsilon $$ Now we can easily see that it has a closed-form solution $$x_1 = x_0 + \text{sign}(\nabla g(x_0))$$

May I ask how is the closed form solution derived? (I tried to use Lagrange while have difficulty in taking derivative on the $l_{\infty}$ norm)

Any help would be appreciated!

Answer 1

$\def\ed{\stackrel{\text{def}}{=}} $ Hints

• There's a typo in what you've given as easily seen to be the solution. It should be $$ x_1=x_0+\color{red}\epsilon\,\text{sign}\big(\nabla g\big(x_0\big)\big)$$
• Let $\ a\ed\nabla g\big(x_0\big)\ $, $\ y\ed x-x_0\ $. Your problem is then equivalent to finding $$\arg\max_{\|y\|_\infty\le\epsilon}a^Ty=\arg\max_{\|y\|_\infty\le\epsilon}\sum_{i=1}^na_iy_i\ ,$$where $\ n\ $ is the number of components in your vectors.
• $\ \|y\|_\infty\le\epsilon\ $ if and only if $\ -\epsilon\le y_i\le\epsilon\ $ for every $\ i=1,2,\dots,n\ $. If $\ a_i>0\ $, then what is $\ \max_\limits{-\epsilon\le y_i\le\epsilon}a_iy_i\ $ and what is the value of $\ y_i\ $ that achieves the maximum? On the other hand, if $\ a_i<0\ ,$ then what is $\ \max_\limits{-\epsilon\le y_i\le\epsilon}a_iy_i\ $ and what is the value of $\ y_i\ $ that achieves the maximum. Can you see how the solutions of these two subproblems enable you to obtain the solution of the original?