Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper deals with the problem of finding an adversarial examples when only the output of a model can be evaluated, but not its gradient. The key idea of the paper is building a Gaussian MRF (a Gaussian with a sparse inverse covariance matrix with a special band structure) to maintain a model for the gradients for predicting search directions. The approach is sensible and uses the FFT trick applicable for diagonalizing covariance matrices with circulant structure.

- The ideas in this paper have practical utility. The paper is unfortunately not very carefully written, and the arguments require occasionally some guesswork.

- There is not a sufficient discussion of experimental findings. Why does the proposed method works better than a white box FGSM for instance? 

- I don’t fully understand what ‘solving for GMRF’ means (Alg 1). I would expect it is estimating the parameters of the covariance function but this algorithm just calculates the likelihood. 

- Given the simple coupling structure with parameter tying, this problem seems to be closely related to estimating AR(N) style models (alpha and beta parameters) so I am surprised to see only a general treatment. 
In this problem, it seems much more natural to estimate theta and g recursively and concurrently, and there are very well known algorithms related to Kalman filtering. Please discuss.

- The evaluation of the idea is not complete While it is certainly interesting to see that such a simple heuristic can achieve comparable performance on standard datasets over other black-box attack methods in the limited query budget regime, I would expect to see some experiments that illustrate the quality of the gradient estimator more closely (not only its final effectiveness for finding a search direction inside of an optimization method) and more strong justification of the proposed model. 

- As the entire contribution hinges on the observation that gradients across dimensions of an example as well as across examples in a dataset are correlated, it would have been also very informative to show estimates of autocorrelation functions of  the gradients on different datasets to justify the basic modelling choices. 


review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors propose a method for black box adversarial image generation. The idea is to learn a parameterization of a precision matrix so that gradients of a network's loss are assumed to be drawn from a corresponding Gaussian. The parameters of this model are fit efficiently using the spectral theorem that their particular parameterization of the precision matrix allows them to use. Gradient estimation is then viewed as a Gaussian conditioning problem given observations (see last equation on page 5).

Overall, I think the method is elegant -- particular in comparison to many existing approaches in the literature that rely on highly complex machinery like genetic algorithms and the like. My main source of questions is the experimental results section, which I currently view as somewhat weak and a little confusing -- I would be more than happy to increase my score if my concerns are sufficiently addressed.

First, I'm not sure that the story told by Figure 3 and Table 1 is entirely clear. On the whole at a given sufficiently high success rate (say, 80%), it seems that the authors' approach consistently loses to the Parsimonious attack of Moon et al., 2019? The authors' method seems to perform strictly better than Bandits_{TD} and NES, but the gap between the Parsimonious attack and the authors' is quite substantial past 300 evaluations.

This ultimately leaves me with the question of what to do with this paper. The learning framework used to estimate gradients is clever, but doesn't seem to me to be methodologically groundbreaking to the point where it can stand on its own merits independent of its performance in comparison to other techniques. Particularly considering other papers have been published since the Ilyas et al., 2019 paper that outperform Bandits_{TD} and NES in terms of query efficiency, I worry that this paper simply presents a decent idea with middling results.

I'd therefore like the authors to primarily comment on the broader impact they believe their paper will have. The conclusion primarily focuses on the introduction of the method: does it have substantial merits past its empirical performance?
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: This paper employs Markov random fields to exploit the input data structure and further model the covariance structure of the gradients. This embeds covariance structures of input data space into the gradient operator for an adversary attack.
They further use this gradient operator with a fast gradient sign Method. The numerics show effective for using fewer queries to obtain high attack accuracy. This paper is well written with clear derivations. I suggest the publication of the paper.

 In fact, modeling the structure of an input space structure into the adversary attack is a good direction. For similar intuitions in this direction, I recommend a related work:
      
         "A. Lin, Y. Dukler, W. Li, G. Montufar, Wasserstein Diffusion Tikhonov Regularization" 
 
review_title: Official Blind Review #1

Meta-review: This paper presents a Markov Random Fields (MRF) for generating adversarial examples in a black-box setting, where only it has access to loss function evaluations. The method exploits the structure of input data to model the covariance structure of the gradients. Empirically, the resulting method uses fewer queries than the current state of the art to achieve comparable performance. Overall, the paper has valuable contributions. The main issue is on empirical evaluation, which can be strengthened, e.g., by including results with multi-step methods and more thorough analysis of the estimated gradients.
Decision: Reject