TensorFlow Implementation of SPSA seems to calculate gradient incorrectly

[cassidylaidlaw]

In the SPSAAdam class in cleverhans/attacks/spsa.py, the gradient is calculated with the following code:

  delta = self._delta
  delta_x = self._get_delta(x, delta)
  delta_x = tf.concat([delta_x, -delta_x], axis=0)
  loss_vals = tf.reshape(
      loss_fn(x + delta_x),
      [2 * self._num_samples] + [1] * (len(x_shape) - 1))
  avg_grad = reduce_mean(loss_vals * delta_x, axis=0) / delta

I believe the last line should instead be

  avg_grad = reduce_mean(loss_vals * tf.sign(delta_x), axis=0) / delta

or equivalently

  avg_grad = reduce_mean(loss_vals / delta_x, axis=0)

to match the description in the paper. Without this, the gradient is multiplied by delta, which is by default 0.01. Thus, the gradient is underestimated by a factor of 100. I confirmed this while working on the PyTorch implementation, which I changed to use sign(delta_x); it then estimated the gradients correctly.

This issue is also present in cleverhans/future/tf2/attacks/spsa.py. It looks like it was originally implemented by @juesato.

[juesato]

Hey, thanks! Yes, the code should read as you've proposed - otherwise, the updates will move in the right direction, but by the wrong amount.

Do you want to go ahead at making the change? The provided learning rate defaults should also be adjusted, so that default behavior is the same before/after the change. For backwards-compatibility, I would add a new parameter, say lr, since the semantics of the parameter will change, and add a deprecation warning that users should switch from learning_rate to lr.

I'm also happy to fix this, though it will probably be a week until I can get to it.

[cassidylaidlaw]

Sure, I can go ahead and make the change. That sounds good about preserving backwards compatibility. Just to make sure I got the math right, the new learning rate should be lr = learning_rate * delta right?

[juesato]

Great, thanks! Yes, that checks out to me.

[cassidylaidlaw]

@juesato I was working on fixing this issue today, but I realized that since SPSA is using Adam as an optimizer, it should be agnostic to the magnitude of the gradient. So we can't fix it by scaling the learning rate, but it shouldn't matter anyways. Does that sound right to you?