Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper proposes a black-box attack method that optimises both the adversarial perturbation and the optimal dimensionaity reduction in a Bayesian Optimization framework. The formulation seem sound and the experiments show improvements wrt competitors in terms of performance and query efficiency with comparable attack success rates.

* In section 4.3 the authors claim that the additive surrogate makes the GP-based BO able to deal with the problem of high dimensionality. Given that the typical dimensionality for BayesOpt is d <= 20, how are the experiments with dimensions up to 14x14x3 provided for GP-BO and GP-BO-auto-dT performed?

* The image selection protocol seems arbitrary and it does not correspond to the Tu et al. protocol which selects 50 random images from  CIFAR-100 and MNIST.

* I feel the experiments lack some details: which is the decoder used for dimensionality reduction?


review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper studied the problem of black-box adversarial attack generation by leveraging Bayesian optimization (BO).

Merits of this paper:
1) The combination of BO and dimension reduction, which makes BO more efficient under a low-dimensional space. 
2) Good experiment results.

Comments/questions about this paper:

1) Comment on "Finally, to the best of our knowledge, the only prior work that uses Bayesian optimisation is a workshop paper by...". BO was also used for generating black-box adversarial examples at https://arxiv.org/pdf/1907.11684.pdf
This is a missing related work, and please elaborate on the differences. 

2) The presentation of the proposed algorithm is not clear. Please explicitly state the acquisition function. And how to tune the hyperparameter in the acquisition function? What decoder is used in experiments? Have authors tested the sensitivity of the decoder (not reduced dimension)?  

3) In experiments, the authors mentioned "we randomly select 3 correctly classified images for each class from CIFAR10 test data which sums up to 27 CIFAR10 images, and randomly select 7 correctly classified images from MNIST test data."
I feel that the number of tested images is not sufficient. How about conducting experiments on a large number of tested images for untargeted attack?

4) In Table 1, what does 0,0,0, mean in ZOO? 

5) It is known that BO has itself parameter to tune, and is not computationally efficient. It might be good to show the computation efficiency of BO for different reduced dimensions together with the corresponding attack performance. 

6) The convergence of BO is usually not stable. However, Figure 3 shows that BO converges very smoothly in terms of ASR. Could authors also show the loss value of using BO-attacks against iteration numbers? 
Meanwhile, in Figure 3 is the best ASR  (up to the current query counts) reported or the ASR at the current query number?


Based on the aforementioned questions, my initial rating is weak reject. 


############## Post-feedback ################
Thanks for the response. Most of my questions have been addressed. Thus, I increased my score to 6. 
I suggested to have a clearer presentation on the possible pros and cons of BO in attack generation, e.g., making a comparison between BO and other methods in both query efficiency and computation efficiency.

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors propose to use Bayesian optimization with a GP surrogate for adversarial image generation. In addition to the standard BayesOpt algorithm, the authors use a variant that exploits additive structure, as well as a variant that uses Bayesian model selection to determine an optimal dimensionality reduction.

For the experimental results, I find it extremely surprising that vanilla GP-BO works at all, even downsampling e.g. to d=588 (Table 2). This is extraordinarily high dimensionality for vanilla BayesOpt, and conventional wisdom suggests that this should not work at all. I'd like to see a discussion of this, particularly as I've seen unsuccessful attempts at this in the past. What differentiating factors lead to it working here? The set of images considered is quite small, presumably because of the rather extreme wall clock expense of running hundreds of sequential BayesOpt iterations without GPU acceleration. This is particularly true for methods that require Bayesian model selection and therefore training multiple GPs in each iteration of BayesOpt.

Along the same lines of dimensionality concerns, I would view a lack of results on ImageNet images as a significant weakness, particularly as these are probably much harder for general purpose blackbox optimizers, as the initial dimensionality of those images is ~150000. A decent amount of missing related literature studies transformations of ImageNet images, including the QL Attack (Ilyas et al., 2018), Bandits-TD (Ilyas et al., 2019) and others. These papers also focus specifically on query budget, so it would be hard to claim that BayesOpt is SOTA if it can't scale to images this large.

Can you provide additional details on the learning mechanism for the additive decomposition? Are you learning kernel outputscales for different predefined additive components as in Duvenaud et al., 2011? Note that this is a fairly different structure than considered in Kandasamy et al., 2015 (despite both being called "additive GPs") -- the type of additive structure in Kandasamy et al., 2015 usually needs to be learned through approximate model selection mechanisms (usually via Metropolis-Hastings or Gibbs sampling).
review_title: Official Blind Review #3

Meta-review: This paper proposes a query-efficient black-box attack that uses Bayesian optimization in combination with Bayesian model selection to optimize over the adversarial perturbation and the optimal degree of search space dimension reduction. The method can achieve comparable success rates with 2-5 times fewer queries compared to previous state-of-the-art black-box attacks. The paper should be further improved in the final version (e.g., including more results on ImageNet data).
Decision: Accept (Poster)