Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: Summary: The paper develops a query efficient algorithm for computing black box adversarial examples given only hard labels in the context of deep neural networks. Intuitively, the only information of the function provided to the algorithm is the label for a given sample. Technically, the authors use the formulation proposed by Cheng et al, and derive a zeroth optimization algorithm that uses less queries with nice convergence properties. Experimentally, the proposed algorithm is very effective on three different standard datasets in vision.

I have decided to weak reject the paper for the following key reasons:

1. Novelty: the technique as such as very similar to Cheng et al, and Liu et al, as the authors themselves mention it in Section 3.2. In particular, the speed-up compared to Cheng et al, is twice -- for a bounded maximum \alpha in Algorithm 1 in Cheng et al, which is almost always the case, because otherwise it would not be "adversarial" in nature. The authors claim that the convergence result has not been proved yet for the proposed algorithm but it follows using the technique used in Bernstein et al 2018, with some minor modifications.

2. Experiments: While the experiments that the authors support the claim, I think they are missing comparison with Liu et al which is crucial. In Fig 4, their method is doing even better than white box attacks, how can this be true? or why is this true?
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors propose a new algorithm for evaluating adversarial robustness of black-box models. The aim of the proposed algorithm, SIGN-OPT is generating adversarial examples as close as possible to the decision boundary using as less queries of the black-box model as possible.

The authors follow the approach of (Cheng et al 2019) by modeling the problem as an optimization problem, where the objective function is to find the direction with the shortest distance to the decision boundary. They propose a smart modification of the previous approach by evaluating the sign of the gradient rather than the gradient itself. The advantage is that the sign of the gradient can be evaluated using a single query while the estimation of the gradient needs many queries. 
The authors have analyzed the proposed algorithm. They showed that using SIGN-OPT, the expectation of the gradient tends to zero in $O(1/\sqrt(T))$, meaning that a (local) minimum is reached.
The algorithm is favorably compared with the state-of-the-art on three image test sets (MNIST, CIFAR-10n ImageNet).

This paper is technically sound, well-written and propose an interesting modification of a previous algorithm. I vote for acceptance.

However, I have some concerns:
-	I think that the L-smoothness assumption should be discussed. Is it realistic for Deep Learning models? Does it hold for the three attacked CNN networks?
-	The analytical results of the previous algorithm RGF and the proposed algorithm SIGN-OPT are not compared and discussed. It is a pity.


review_title: Official Blind Review #1054

Meta-review: The reviewers had several concerns with the paper related to novelty and comparisons with other approaches. During the discussion phase, these concerns were adequately addressed.
Decision: Accept (Poster)