In the learning to learn (L2L) framework, we cast the design of optimization algorithms as a machine learning problem and use deep neural networks to learn the update rules. In this paper, we extend the L2L framework to zeroth-order (ZO) optimization setting, where no explicit gradient information is available. Our learned optimizer, modeled as recurrent neural network (RNN), first approximates gradient by ZO gradient estimator and then produces parameter update utilizing the knowledge of previous iterations. To reduce the high variance effect due to ZO gradient estimator, we further introduce another RNN to learn the Gaussian sampling rule and dynamically guide the query direction sampling. Our learned optimizer outperforms hand-designed algorithms in terms of convergence rate and final solution on both synthetic and practical ZO optimization tasks (in particular, the black-box adversarial attack task, which is one of the most widely used tasks of ZO optimization). We finally conduct extensive analytical experiments to demonstrate the effectiveness of our proposed optimizer.
The paper proposes a zeroth-order optimization framework that employs an RNN to modulate the sampling used to estimate gradients and a second RNN that models the parameter update. More specifically, query directions are sampled from a Gaussian distribution with a diagonal covariance whose evolution is determined by an RNN (QueryRNN). The resulting gradient estimates are used by an RNN (UpdateRNN) that learns the parameter update rule. This framework has the stated advantage that, unlike existing work in ZO optimization, it does not rely upon hand-designed strategies to reduce the variance common to ZO gradient estimators. The paper evaluates the proposed framework on MNIST and CFAR tasks, as well as a synthetic binary classification task. The results demonstrate faster convergence compared to baseline zeroth-order optimization algorithms, while ablations indicate the contributions of the different model components.
The primary contribution of the proposed method is the inclusion of a second network that learns to adapt the covariance of the Gaussian from which  query directions are sampled. The use of an RNN to model the parameter update rule is borrowed from previous work. The ablation studies show that the adaptive sampling strategy noticeably improves convergence as does the inclusion of the RNN update (the contribution of UpdateRNN is more significant in one ablation study, while the contribution of QueryRNN is greater in the other). 
Given that a stated advantage of QueryRNN is reducing variance, it would be beneficial to compare against baselines such as Liu et al., 2018a,b and/or Guo et al., 2016 which similarly seek to reduce variance.
The paper includes a large number of typos (e.g., CIFAR-->CIAFR) and grammatical errors, but is otherwise clear.
ADDITIONAL COMMENTS/QUESTIONS
* The related work discussion would benefit from a discussion of how Liu et al. 2018 and Guo et al. 2016 reduce variance
* The computational complexity of the proposed method as compared to the baselines is unclear as is the scalability with dimensionality. At various points, the paper comments that other methods scale poorly with the dimensionality of the query space, which is true of the proposed method unless the operations are parallelized. Is this not possible with the baseline methods?
* The paper makes hand wavy claims to the fact that modulating the diagonal covariance matrix allows the method to focus on certain subspaces. It would be helpful to make these claims more formal, particularly in light of the fact that the mean does not change.
* The method relies upon a bit of a hack that samples from a standard Gaussian at random times. How important is this to performance? How sensitive is convergence to the frequency with which standard Gaussian sampling is used?
* The discussion of Eqn. 5 as it relates to Eqn. 1 is unclear.
UPDATE AFTER AUTHOR RESPONSE
I appreciate the authors' thorough response, which resolved my primary questions/concerns, including comparisons to existing variance reduction methods (which should be incorporated into the main paper).