SIGNSGD VIA ZEROTH-ORDER ORACLE
In this paper, we design and analyze a new zeroth-order (ZO) stochastic optimization algorithm, ZO-signSGD, which enjoys dual advantages of gradient-free operations and signSGD. The latter requires only the sign information of gradient estimates but is able to achieve a comparable or even better convergence speed than SGD-type algorithms. Our study shows that ZO-signSGD requires 
On the application side we explore the connection between ZO-signSGD and black-box adversarial attacks in robust deep learning. Our empirical evaluations on image classification datasets MNIST and CIFAR-10 demonstrate the superior performance of ZO-signSGD on the generation of adversarial examples from black-box neural networks.
The authors proposed a zero-order version of the recent signSGD algorithm, by replacing the stochastic gradient with a usual function difference estimate. Similar convergence rates as signSGD were obtained, with an additional sqrt(d) factor which is typical in zero-order methods. Three (typical) gradient estimates based on function values were discussed. Overall, the obtained results are relatively straightforward combination of signSGD with existing zero-order techniques. 
Quality: The technical part of this paper seems to be solid. The experiments, on the other hand, are quite ambiguous. First off, why do you choose that peculiar least squares binary classification problem on page 7? Is Assumption A2 satisfied for this problem? Why not use logistic regression? The experimental results are also strange: Why would ZO-signSGD converge faster than ZO-SGD or any other ZO variant? Shouldn't they enjoy similar rates of convergence? Why would taking the sign make the algorithm converge faster? Note that the original motivation for signSGD is not for faster convergence but less communication. For the second set of experiment, how do you apply ZO-SGD to generate adversarial examples? Again, why do we expect ZO-signSGD to perform better than ZO-SGD?
Clarity: This paper is mostly well-written, but the authors at times largely overclaim their contributions or exaggerate the technical challenges. 
-- Page 2, 2nd line: the authors claim that "Our analysis removes the impractical assumption of b = O(T)", but in the later examples (page 6, top), they require q = O(T). How is this any different than b = O(T)? Even worse, the former case also require b = n, i.e., there is no stochasity at all...
-- Assumption A2: how crucial is this assumption for obtaining the convergence results? note that not many functions have Lipschitz continuous bounded gradients... (logistic regression is an example)
-- Page 4, top: "ZO-signSGD has no restriction on the mini-batch size b"? The rates at the end of page 5 suggests otherwise if we want the bound to go to 0 (due to the term sqrt(d/b)). 
-- Page 4, top: the last two technical challenges do not make sense: once we replace f by f_mu, these difficulties go away immediately, and it is well-known how to relate f_mu with f.
Originality: The originality seems to be limited. Contrary to what the authors claimed, I found the established results to be relatively straightforward combination of signSGD and existing zero-order techniques. Can the authors elaborate on what additional difficulties they need to overcome in order to extend existing zero-order results to the signSGD case?
Significance: The proposed zero-order version of signSGD may potentially be significant in applications where gradient information is not available and yet distributed optimization is needed. This, however, is not demonstrated in the paper as the authors never considered distributed optimization.
##### added after author response #####
I appreciate the authors effort in trying to make their contributions precise and appropriate. The connection between ZO-signSGD and adversarial examples is further elaborated, which I agree is an interesting and potentially fruitful direction. I commend the authors for supplying further experiments to explain the pros and cons of the proposed algorithms. Many of the concerns in my original review were largely alleviate/addressed. As such, I have raised my original evaluation.