Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper proposes a meta-algorithm for the so-called "decision-based attack" problem, where a model that can be accessed only via label queries for a given input is attacked by a minimal perturbation to the input that changes the predicted label. The algorithm, BOSH, augments any iterative algorithm for this problem with a diversification strategy based on bayesian optimization and throwing away bad solutions. Empirically, it is shown that BOSH can improve the performance of recently developed algorithms for this problem, by exploring more solutions and refining them intelligently.

Overall, the decision-based attack problem is very practically relevant as it assumes minimal access to the classifier. I also really like that the authors looked into tree-based models in addition to neural networks. The algorithmic ideas that are proposed are simple and effective, as supported by the experimental results.

However, I have some serious comments about the experimental evaluation that I believe can substantially improve the quality of the paper, if addressed. Whether I raise my score or not will depend on how well the authors address these questions. I also have concerns about related work in heuristic algorithms.

Questions:
- Related work: the ideas of diversifying solution paths and throwing away bad solutions are very popular in combinatorial heuristics. You should do a thorough review of work in that area and in Genetic Algorithms (GA). You could look into the following classical/survey papers as starting points, in particular the first survey's chapter 4.

Glover, Fred, and Manuel Laguna. "Tabu search." Handbook of combinatorial optimization. Springer, Boston, MA, 1998. 2093-2229.
Feo, Thomas A., and Mauricio GC Resende. "Greedy randomized adaptive search procedures." Journal of global optimization 6.2 (1995): 109-133.

- Other Black-Box algorithms: you should compare against well-established black-box optimization algorithms such as NOMAD and RBF-OPT. Both are based on very solid mathematical foundations and have high-quality open source implementations:
NOMAD: https://www.gerad.ca/nomad/
rbf-opt: https://github.com/coin-or/rbfopt

- Runtime comparison: your analysis with respect to number of queries is very good and insightful. In addition, we should get a sense of the runtime performance. If you run each of the approaches with the same time limit, how do they fare?

- Comparing to "optimal" attacks: we need to know how well the solutions are compared to the best possible, or a close-enough approximation. You could run white-box attacks and compare the relative error to the quality of the white-box attack. Otherwise, it is hard to tell what gap remains to be closed algorithmically and it is difficult for other researchers to know whether it's worth trying to improve what you propose here in the future.

- Time complexity: please give a time complexity analysis of BOSH as a function of all its hyperparameters.

Clarity:
- Figure 1: I don't understand what this figure shows. Where are the 2 minima? Please clarify further.
- You minimize l(.) / g(.) in Algorithm 2, but maximize it in Appendix B.2. Maximizing makes more sense. Which one is it?
- Theorem 1: Is that your result or Bergstra et al.'s?

Minor comments:
- "Adversarial example generation becomes a viable method for evaluating the robustness of a machine learning model." --> "Adversarial example generation has become a viable method for evaluating the robustness of a machine learning model."
- "when searching an adversarial" --> "when searching for an adversarial"
- "Distortion" is used in the literature much less than "Perturbation"; consider switching them.
- "our mega algorithm" --> "our meta-algorithm"
- Please use consistent notation: SignOPT or Sign-OPT.
- Appendix B.1: "undifferentiable" --> "non-differentiable"
- "are the t − x1 samples" --> "are the t − 1 samples"
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors study the adversarial example generation problem, in the difficult case where the attacked model is a black box. Since the model is unknown, the approaches based on the minimization of a loss function with a gradient based optimizer do not apply. The current alternatives, known as decision-based attack, use iterative local updates from a starting point to a local minimum, where the class of the adversarial example is different from the initial example while its distance stays close to the initial one.

For handling the sensibility to starting points, the authors propose a meta-algorithm, which uses any iterative local update based attacks, and which maintains a set of solutions corresponding to different starting points. The proposed algorithm uses successive halving for iteratively maintaining empirical good solutions by discarding the worst half of solutions at each step, and uses Tree Parzen Estimator to explore by resampling promising area.

In the experiments, the meta-algorithm uses SignOPT attack. It is compared with three decision based attacks, including SignOPT. Three image datasets are used. The attacked models are neural networks and gradient boosting tree in the last experiment.

Pros:
- The paper is well-written and easy to follow.
- Generic algorithm.


Cons:
- No analysis is provided.  
- The proposed algorithm has a lot of parameters: $k, M, s, m, T, inf, \alpha$. 
- The $\epsilon$ are not the same for each attacked model (table 1 and 3). Is it the result of a post-optimization? Could you plot the curves ASR versus $\epsilon$ ?
- In algorithm 2, $min_score=inf$,  whatever $t$, so why using two variables ?

___________________________________________________________________________________________________________________________________
I read the rebuttal.
Thanks you for answering my concerns.

I think that it is possible to provide some theoretical guanrantees. For instance, may be one could show that the quality of the attacks is increasing when Algorithm 1 is run. Finding the highest increasing rate could be useful for tuning the parameters of the algorithm.
However, I understand that this could be tricky.

I took a look to Figure 6. Good point: BOSH Sign-OPT attack outperforms Sign-OPT attack whatever $\epsilon$.

review_title: Official Blind Review #1547

Meta-review: This paper proposes BOSH-attack, a meta-algorithm for decision-based attack, where a model that can be accessed only via label queries for a given input is attacked by a minimal perturbation to the input that changes the predicted label. BOSH improves over existing local update algorithms by leveraging Bayesian Optimization (BO) and Successive Halving (SH). It has valuable contributions. But various improvements as detailed in the review comments can be made to further strength the manuscript.
Decision: Reject