Does this algorithm divide into L2 norm version and Linf norm version?

[machanic]

Does this algorithm divide into L2 norm version and Linf norm version?

[machanic]

I mean does the algorithm logic procedure the same in L2 and Linf norm versions?

[jinghuichen]

Technically speaking, there is no barrier in applying RayS to L2 norm case. The only caveat here is that our discrete formulation is defined based on Linf norm and therefore our search method favors Linf norm case. We did not really invest in how to build L2 norm version of RayS as robust training methods are commonly defined based on Linf norm. Personally, I believe that RayS can be directly applied to L2 norm but in order to achieve the best performance, one may need to change optimization formulation and search strategy carefully.

[machanic]

@jinghuichen Can you made a new version of Ray to be also apply to L2 norm? I still cannot understand how to modify the code to apply L2 norm case.

[jinghuichen]

Thanks for your interest and sorry that RayS itself only support Linf norm case currently. It would be nice to further have L2 norm support, however, we might not have enough bandwidth recently and therefore it could take some time. I will be happy to further discuss with you if you wanna help/collaborate or having any other question

[machanic]

I think there is no difference between L2 norm and Linf norm in your algorithm, because RayS is an unbounded attack(which means it does not require a L_p norm projection step.)
In traditional query-based attack that both supports L2 norm and Linf norm attack (eg. Bandits).
The update of adversarial image is :

x = x + lr * g / torch.norm(g, 2)  #L2 norm and g is gradient
x = x + lr * torch.sign(g)  #Linf norm and g is gradient which is similar with your self.sgn_t

However, you directly uses L2 normalized sign:

sgn_norm = torch.norm(sgn.view(len(x), -1), 2, 1)

in line https://github.com/uclaml/RayS/blob/master/RayS.py#L89
Another possible difference may lie in the radius, but it is calculated is by binary search in def binary_search. For example, you wrote self.d_t[to_update_ind] = d_end[to_update_ind], and d_end is determined by using binary search ( divide by 2, and 2, ...)
So the radius computation does not involve with L2 or Linf norm.
Conclusion:
I beilieve the only difference of RayS in L2 and Linf norms lies in the count of queries and attack success rate. (The Statistics, rather than the procedure of finding adversarial image).

[machanic]

@uclaml @jinghuichen Am I correct?

[jinghuichen]

What you describe is a naive way to extend RayS to L2 norm case and it can work in my opinion. However, as I mentioned before, this trivial extension may not lead to the best performance. The reason is that we are currently searching directions of [-1,1]^d, which is kind of optimal in Linf norm case but may be not quite well for L2 norm (successful L2 norm attack may concentrate on 1 or few pixels rather than add perturbations on all pixels). This is why I mentioned that we may need to rethink about optimization formulation and search strategy carefully.