We focus on the problem of black-box adversarial attacks, where the aim is to generate adversarial examples using information limited to loss function evaluations of input-output pairs. We use Bayesian optimization (BO) to specifically cater to scenarios involving low query budgets to develop query efficient adversarial attacks. We alleviate the issues surrounding BO in regards to optimizing high dimensional deep learning models by effective dimension upsampling techniques. Our proposed approach achieves performance comparable to the state of the art black-box adversarial attacks albeit with a much lower average query count. In particular, in low query budget regimes, our proposed method reduces the query count up to 80% with respect to the state of the art methods.
This paper proposed a BO-based black-box attack generation method. In general, it is very well written and easy to follow. The main contribution is to combine BO with dimension reduction, which leads to the effectiveness in generating black-box adversarial examples in the regime of limited queries.  However, I still have some concerns about this paper. 
1) The benefits of BO? It seems that the step of dimension reduction is crucial to make BO scablable to high-dimensional problems. I wonder if the gradient estimation-based attack methods can apply the similar trick and yield the similar performance. That is, one can solve problem min_{\delta} attack_loss( x, y, g(\delta) ) by estimating gradients via finite-difference of function values, where g(\cdot) is the dimension-reduction operator, and \delta is the low-dimensional perturbation. Such a baseline is not clear in the paper, and the comparison with (Tu et al., 2019) is not provided in the paper. 
2) Moreover, in experiments, it seems that only query-efficiency was reported. What about distortion-efficiency for BO-based attack? For $\ell_\infty$-attacks, the other $\ell_p$ norms can be used as distortion metrics. I wonder what perturbation does the BO method converge to. It was shown in (https://arxiv.org/pdf/1907.11684.pdf, Table 1) that BO usually leads to larger \ell_1 and \ell_2 distortion. 
3) It might be useful to show the convergence of BO in terms of objective value versus iterations/queries. This may give a clearer picture on how BO works in the attack generation setting. 
4) Minor comment: In related work "Bayesian optimization has played a supporting role in several methods,
including Tu et al. (2019), where ...." However,  Tu et al. (2019) does not seem using BO and ADMM. 
############ Post-feedback ##########
Thanks for the clarification and the additional experiments. I am satisfied with the response, and have increased my score to 6.