We study the problem of generating adversarial examples in a black-box setting, where we only have access to a zeroth order oracle, providing us with loss function evaluations. We employ Markov Random Fields (MRF) to exploit the structure of input data to systematically model the covariance structure of the gradients. The MRF structure in addition to Bayesian inference for the gradients facilitates one-step attacks akin to Fast Gradient Sign Method (FGSM) albeit in the blackbox setting. The resulting method uses fewer queries than the current state of the art to achieve comparable performance. In particular, in the regime of lower query budgets, we show that our method is particularly effective in terms of fewer average queries with high attack accuracy while employing one-step attacks.
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.