Learning to Learn by Zeroth-Order Oracle
Authors: Yangjun Ruan
Yuanhao Xiong
Sashank Reddi
Sanjiv Kumar
Cho-Jui Hsieh
Venue:  (2020)
Keywords: learning to learn
zeroth-order optimization
black-box adversarial attack

Abstract: 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 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.

Published as a conference paper at ICLR 2020
LEARNING TO LEARN BY ZEROTH-ORDER ORACLE
Yangjun Ruan', Yuanhao Xiong", Sashank Reddi', Sanjiy Kumar", Cho-Jui Hsieh 2.3 l 'Department of Infomation Science and Electrical Engineering, Zhejiang University *Department of Computer Science, UCLA
GGoogle Research
sranyj3107@zjor edu. en, yhxiongêcs ucla.edu, {sashank, sanjivk/egoogie com, chohsiehêcs. ucla. edu
ABSTRACT
In the learning to learn (L2L) framework, we cast the design of optimization algo- rithms as 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) op- timization setting, where no explicit gradient information is available. Our learned optimizer, modeled as recurrent neural networks (RNNs), first approximates gra- dient by 70 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 sam- pling rule and dynamically guide the query direction sampling. Our learned op- timizer outperforms hand-designed algorithms in terms of convergence rate and final solution on both synthetic and practical ZO optimization problems (in partic- ular, the black-box adversarial attack task, which is one of the most widely used applications of ZO optimization). We finally conduct extensive analytical experi- ments to demonstrate the effectiveness of our proposed optimizer!
INTRODUCTION
Learning learn (I.2L.) is recently proposed meta-learning framework where leverage deep neural networks to learn optimization algorithms automatically. The most common choice for the learned optimizer recurrent neural network (RNN) since can capture long-term dependencies and propose parameter updates based on knowledge of previous iterations. By training RNN opti- mizers on predefined optimization problems, the optimizers are capable of learning explore the loss landscape and adaptively choose descent directions and steps (Lv et al., 2017). Recent works (Andrychowicz al.) 2016 Wichrowska et al. 2017, Lv al. [017] have shown promising results that these learned optimizers can often outperform widely used hand-designed algorithms such as SGD, RMSProp, ADAM, etc. Despite great prospects in this field, almost all previous learned op- timizers gradient-basedd which cannot be applied solve optimization problems where explicit gradients are difficult or infcasible to obtain.
Such problems mentioned above are called zeroth-order (ZO) optimization problems, where the optimizer is only provided with function values (zeroth-order information) rather than explicit gra- dients (first-order information). They are attracting increasing attention for solving ML problems in the black-box setting or when computing gradients is too expensive (Liu et al., (2018)). Recently, one of the most important applications of Z0 optimization is the black-box adversarial attack well- trained deep neural networks, since in practice only input-output correspondence of targeted models rather than internal model information accessible (Papernot et al. 2017 Chen al. 2017a).
Although ZO optimization is popular for solving ML problems, the performance of existing algo- rithms barely satisfactory. The basic idea behind these algorithms is to approximate gradients via ZO oracle (Nesterov & Spokoiny| [017]] Ghadimi & Lan 2013). Given the loss function f with its parameter é to be optimized (called the optimizee), we can obtain its ZO gradient estimator by:
f = (1/uq) Σ 9 1 f(0)]u
(1)
Our code is availahle at

---

Published as a conference paper at ICLR 2020
where μ is the smoothing parameter, {u.} are random query directions drawn from standard Gaus- sian distribution (Nesterov & Spokoiny 2017) and is the number of sampled query directions. However, the high variance of 2O gradient estimator which results from both random query direc- tions and random samples (in stochastic setting) hampers the convergence rate of current ZO algo- rithms. Typically, problem dimension d increases, these 70 algorithms suffer from increasing iteration complexity by a small polynomial of d to explore the higher dimensional query space.
In this paper, we propose learn a zeroth-order optimizer. Instead of designing variance reduced and faster converging algorithms by hand as in Liu et al. (2018a we replace parameter update rule as well as guided sampling rule for query directions with learned recurrent neural networks (RNNs). The main contributions of this paper are summarized as follows:
We extend the 1.2I. framework to ZO optimization setting and propose to use RNN to learn ZO update rules automatically. Our learned optimizer contributes to faster convergence and lower final loss compared with hand-designed ZO algorithms.
Instead of using standard Gaussian sampling for random query directions as in traditional ZO algorithms, we propose to learn the Gaussian sampling rule and adaptively modify the search distribution. We use another RNN to adapt the variance of random Gaussian sam- pling. This new technique helps the optimizer to automatically sample on a more important search space and thus results in more accurate gradient estimator at each iteration.
Our learned optimizer leads to significant improvement on some ZO optimization tasks (especially the black-box adversarial attack task). We also conduct extensive experiments to analyze the effectiveness of our learned optimizer.
2 RELATED WORK
Learning to learn (L2L) In the L2L framework, the design of optimization algorithms is cast as learning problem and deep neural network is used to learn the update rule automatically. In InfCoteer & Conwell (1990), early attempts were made to model adaptive learning algorithms as recurrent ral network (RNN) and were further developed in Younger et al. (2001) where RNN was trained to optimize simple convex functions. Recently, (Andrychowicz et al. (2016) proposed coordinatewise LSTM optimizer model to learn the parameter update rule tailored to a particular class of optimiza- tion problems and showed the learned optimizer could be applied to train deep neural networks. In Wichrowska et al. (2017) and [v et al. (017), several elaborate designs were proposed to improve the generalization and scalability of learned optimizers. [L & Malik (2016) and & Malik (2017) took a reinforcement learning (RI.) perspective and used policy search to learn the optimization al- gorithms (viewed as RL policies). However, most previous learned optimizers rely on first-order information and use explicit gradients to produce parameter updates, which is not applicable when explicit gradients are not available.
In this paper, we aim to learn an optimizer for ZO optimization problems. The most relevant work to ours is Chen et al.] (2017)). In this work, the authors proposed to learn a global black-box (zeroth-order) optimizer which takes inputs current query point and function value and outputs the next query point. Although the learned optimizer achieves comparable performance with tradi- tional Bayesian optimization algorithms on some black-box optimization tasks, has several crucial drawbacks. As is pointed out in their paper, the learned optimizer scales poorly with long training fixed problem dimension. Furthermore, it not suitable for solving
steps and is specialized black-box optimization problems of high dimensions.
Zeroth-order (ZO) optimization The most common method of ZO optimization is to approx- imate gradient by ZO gradient estimator. Existing ZO optimization algorithms include ZO-SGD Ghadiii & Lan 2013). ZO-SCD (Lian et al. 2016), Z0-signSGID (Liu et al. 2019). ZO-ADAM (Chen et al.) 201 7a), etc. These algorithms suffer from high variance of ZO gradient estimator and typically increase the iteration complexity of their first-order counterparts by a small-degree polyno- mial of problem dimension d. To tackle this problem, several variance reduced and faster converging algorithms were proposed. ZO-SVRG (Liu et al., 2018b) reduced the variance of random samples by dividing optimization steps into several epochs and maintaining snapshot point at each epoch whose gradient was estimated using a larger or the full batch. And the snapshot point served as a reference in building modified stochastic gradient estimate each inner iteration. Z0-SZVR-G
2

---

Published as a conference paper at ICLR 2020
192 1
LSTM
Vart
NOO, Varz)
LSTM
zo Oracle
[0|- 46
LSTM
Vard
A(O, Varz")
LSTM
Aof
surrogate gradient
Query RNN
predicted variance
Gaussian sampling
query direction
zo Oracle
gradient estimator
Update RNN
parameter update
Model architecture of our proposed optimizer. the operations are applied coordinate- wisely except querying 70 Oracle to obtain 70 gradient estimator (equation Tb. Each coordinate shares the QueryRNN and the UpdateRNN parameters but maintains its own hidden state.
Figure I:
(Liu et al. 2018a) adopted similar strategy and extended reduce the variance of both random
samples and random query directions. But these query complexity. In this paper. we avoid laborious hand design of these algorithms and aim to learn ZO optimization algorithms automatically.
methods reduce the variance at the cost of higher
3 METHOD
3.1 MODEL ARCHITECTRRE
Our proposed RNN optimizer consists of three main parts: UpdateRNN, Guided ZO Oracle, and QueryRNN, as shown in Figure
The function of the UpdateRNN mization. Following the idea in in/Andrycooiccze..mm et al. (2016), we use coordinatewise LSTT to model the UpdateRNN. Each coordinate the optimizee shares the same network but maintains its own separate hidden state, which means that different parameters rule based on their own knowledge of previous iterations. Different from previous design in the first-order setting, UpdateRNN takes as input ZO gradient estimator in equation [1] rather than exact gradient and outputs parameter update for each coordinate. Thus the parameter update rule is:
UPdateRNN
learn the parameter update rule of 70 opti-
optimized using the same update
0, 0,-1 + UpdateRNNN
where O, is the optimizee parameter at iteration f. Besides learning to adaptively compute parameter updates by exploring the loss landscape, the UPdateRNN can also reduce negative effects caused by the high variance of ZO gradient estimator due to its long-term dependency.
Guided ZO Oracle In current ZO optimization approaches, ZO gradient estimator computed by finite difference along the query direction which is randomly sampled from multivariate standard Gaussian distribution. But this estimate suffers from high variance and leads to poor convergence rate when applied to optimize problems of high dimensions (Duchi et al. 2015). To tackle this prob- lem, we propose to use some prior knowledge learned from previous iterates during optimization to guide the random query direction search and adaptively modify the search distribution. Specifically, at iteration 4, we use (0, Σ,) to sample query directions (E, is produced by the QueryRNN which introduced later) and then obtain ZO gradient estimator along sampled directions via ZO Oracle (equation]] I]. The learned adaptive sampling strategy will automatically identify important sampling space which leads increases the convergence rate in ZO optimization tasks. For example, in the black-box adversarial attack task, there is usually a clear important subspace for successful attack, and sampling directions from that subspace will lead to much faster convergence. This idea is similar to that of search distri- bution augmentation techniques for evolutionary strategies (ES) such as Natural ES (Wierstra et al, 2008), CMA-ES (Hansen 2016) and Guided ES (Maheswaranathan
more accurate gradient estimator under a fixed query budget, thus further
al. 2018). However, these methods explicitly define the sampling rule whereas we propose to learn the Gaussian sampling rule (i.e., the adaption of covariance matrix Σ,) in automatic manner.
3

---

Published as a conference paper at ICLR 2020
QueryRNN We propose to another LSTM network called QueryRNN learn the Gaussian sampling rule and dynamically predict the covariance matrix Σ, We assume Σ, is diagonal so that it could be predicted in a coordinatewise manner in the UpdateRNN and the learned QueryRNN is invariant to the dimension of optimizee parameter. It takes as input 70 gradient estimator and pa- rameter update last iterate (which could be viewed surrogate gradient information) and outputs the sampling variance coordinatewisely, which can be written as:
Σ; = Query)NN((V$
The intuition is that if estimated gradients or parameter updates of previous iterates are biased toward a certain direction, then we can probably increase the sampling probability toward that direction.
Using predicted covariance Σ, to sample query directions increases the bias of estimated gradient and reduces the variance, which leads to tradeoff between bias and variance. The reduction of variance contributes to faster convergence, but too much bias tends make the learned optimizer stuck at bad local optima (See more illustrations in Appendix C.3). To balance the bias and variance, at test time we randomly use the covariance of standard Gaussian distribution Ia and the predicted covariance Σ, the input of Guided ZO Oracle: Σ, XΣ, + (1 X) where X ~ Ber(p) is a Bernoulli random variable that trades off between bias and variance. Note that the norm of the sampling covariance |ا may not equal to that of standard Gaussian sampling covariance || which makes the expectation of the sampled query direction norm || change. To keep the norm of query direction invariant, we then normalize the norm of Σ to the norm of Ia-
3.2 OBJECTIVE FUNCTION
The objective function of training our proposed optimizer can be written as follows:
T
((Φ)
Σ wi +
+
Iall
(4)
where Φ is the parameter of the optimizer including both the UpdateRNN and the QueryRNN, 0, is updated by the optimizer (equation[] [ and thus determined by Φ. T is the horizon of the optimization trajectory and } are predefined weights associated with each time step (. The objective function consists of two terms. The first one is the weighted sum of the optimizee loss values at each time step. We use linearly increasing weight (i.e., We = () to force the learned optimizer to attach greater importance to the final loss rather than focus on the initial optimization stage. The second one the regularization term of predicted Gaussian sampling covariance E, with regularization parameter X. This term prevents the QueryRNN from predicting too big or too small variance value.
3.3 TRAINING THE LEARNED OPTIMIZER
In experiments, we do not train the UpdateRNN and the QueryRNN jointly for the sake of stability. Instead, we first train the UpdateRNN using standard Gaussian random vectors query directions. Then we freeze the parameters of the UpdateRNN and train the QueryRNN separately. Both two modules are trained by truncated Backpropagation Through Time (BPTT) and using the same ob- jective function in equation 4
In order to backpropagate through the random Gaussian sampling module to train the QueryRNN, we use the reparameterization trick (Kingma & Welling 2013) to generate random query directions. Specifically, to generate query direction u ~ (O, E.), we first sample standard Gaussian vector (0, Ia), and then apply the reparameterization u 1//2
To train the optimizer, we first need to take derivatives of the optimizee loss function w.r.t. the opti- mizee parameters, and then backpropagate to the optimizer parameters by unrolling the optimziation steps. However, the gradient information of the optimizee is not available in zeroth-order setting. In order to obtain the derivatives, we can follow the assumption in [Chen et al. (b) that we could get the gradient information of the optimizee loss function at training time, and this information is not needed at test time. However, this assumption cannot hold when the gradient of optimizee loss func- tion is not available neither at training time. In this situation, we propose to approximate the gradient of the optimizee loss function w.r.t its parameter using coordinatewise 70 gradient estimator (Lian)
4

---

Published as a conference paper at ICLR 2020
al. 2016 Liu et al. 2018b):
ff(0)= Σ (1/2 - f(O p.e.)le.
(5)
where d is the dimension of the optimizee loss function, μ4, is the smoothing parameter for the 7h coordinate, and e; Rd is the standard basis vector with its ith coordinate being 1, and others being Os. This estimator deterministic and could achieve an accurate estimate when {1r} are sufficiently small. And it is used only to backpropagate the error signal from the optimizee loss function to its parameter to train the optimizer, which is different from the estimator in equation [] that is used by the optimizer to propose parameter update. Note that this estimator requires function queries scaled with d, which would slow down the training speed especially when optimizee is of high dimension. However, we can compute the gradient estimator of each coordinate in parallel to significantly reduce the computation overhead.
4 EXPERIMENTAL RESULTS
In this section, we empirically demonstrate the superiority of our proposed ZO optimizer on a prac- tical application (black-box adversarial attack on MINST and CIFAR-10 dataset) and a synthetic problem (binary classification in stochastic zeroth-order setting). We compare our learned optimizer (called ZO-LSTM below) with existing hand-designed ZO optimization algorithms, including ZO- SGD (Ghadimi & Lan, 2013), Z0-signSGD (Liu et al. 2019). and ZO-ADAM (Chen et al. 2017a) For each task, we tune the hyperparameters of baseline algorithms to report the best performance. Specifically, we set the learning rate of baseline algorithms to 8/d. We first coarsely tune the con- stant å on a logarithmic range {0.01, 0.1, 1, 10, 100, 1000} and then finetune on linear range. For ZO-ADAM, we tune 31 values over {0.9, 0.99) and 3g values over (0.99, 0.996, 0.999). To ensure fair comparison, all optimizers are using the same number of query directions to obtain ZO gradient estimator each iteration.
In all experiments, we use I-layer LSTM with 10 hidden units for both the UpdateRNN and the QueryRNN. For each RNN, another linear layer is applied project the hidden state to the output (1-dim parameter update for the UpdateRNN and 1-dim predicted variance for the QueryRNN). The regularization parameter À in the training objective function (equation 4 is ADAM to train our proposed optimizer with truncated BPTT, each optimization is run for 200 steps and unrolled for 20 steps unless specified otherwise. At test time, we set the Bernoulli random
0.005. We use
variable (see Section 3.1) X ~ (0r(..
4.1 ADVERSARIAL ATTACK TO BLACK BOX MODELS
We first consider an important application of our learned ZO optimizer: generating adversarial ex- amples to attack black-bor box models. In this problem. given the targeted model F(-) and an original example To, the goal is to find an adversarial example æ with small perturbation that minimizes a loss function Loss(.) which reflects attack successfulness. The black-box attack loss function
be formulated as f(x) cl a mol + Loss( Fx)). where balances the perturbation norm and attack successfulness (Carlini & Wagner 2017 Tu al. 2019). Due to the black-bor setting, one can only compute the function value of the above objective, which leads to ZO optimization problems (Chen) (et al. 2017a). Note that attacking each sample By in the dataset corresponds a particular 20 optimization problem instance, which motivates us to train ZO optimizer (or "attacker") offline with a small subset and apply to online attack to other samples with faster convergence (which means lower query complexity) and lower final loss (which means less distortion).
Here we experiment with black-box attack to deep neural network image classifier, see detailed problem formulation in Appendix I We follow the same neural network architectures used in Cheng et al. (2019) for MNIST and CIFAR-10 dataset, which achieve 99.2% and 82.7% test accu- racy respectively. We randomly select 100 images that are correctly classified by the targeted model in each test set to train the optimizer and select another 100 images to test the learned optimizer. The dimension of the optimizee function is d 28 28 for MNIST and d 32 32 3 for CIFAR-10. The number of sampled query directions is set to q = 20 for MNIST and q = 50 for CIFAR-10 respectively. All optimizers use the same initial points for finding adversarial examples.
5

---

Published as a conference paper at ICLR 2020
20:5G0 ZO SGD
20.500
20.92D
sig
Z0-LSTH
76-SST
20-LSTM
Roration
(a) MNIST Test ID 1094
(b) MNIST Test ID 1933
(c) MNIST Average
233
20-SCD
20-5CD
20-53D
360
ZD-igrdGD
ZD-igr0GD
ZD-ign55G
315
ZO-ADAM
Z0-ADAN
ZO-ADAN
Z0-LSTM
20-LSTM
20-LSTM
Zo-iSTN--nnetuee
Zo-iSTH-imeetme
125
ZD-ISTM-ireetue
50
Iteration
iteration
iteration
(d) CIFAR Test 4293
(e) CIFAR Test ID 9208
(f) CIFAR Average
Figure 2: (a)-(b (d)-(e): Black-box attack loss versus iterations on selected test images. The loss curves averaged over 10 independent random trails and the shaded areas indicate the standard deviation. (c) & (f): Black-box attack loss curves averaged over all 100 test images. Attack on each image is run for 10 trails. On CIFAR-10 attack task, also test the performance of the learned optimizer trained on MINST attack task with finetuning (Z0-LSTM-finetune, which will be introduced in Section 4.3).
Figure shows black-box attack loss versus iterations using different optimizers. We plot the loss curves of two selected test images (see Appendix [o.3 more plots on other test images) as well as the average loss curve over all 100 test images for each dataset. clear that our learned optimizer (ZO-LSTM) leads to much faster convergence and lower final loss than other baseline optimizers both on MNIST and CIFAR-10 10 attack tasks. The visualization of generated adversarial examples versus iterations be found in Appendix A.2
4.2 STOCHASTIC ZEROTH-ORDER BINARY CLASSIFICATION
Next we apply learned optimizer in the stochastic 70 optimization setting. We consider synthetic binary classification problem (Liu et al. 2019) with non-convex least squared loss function: ((0) = Ei= (y: 1/(1 + - =.))² To generate one dataset for the binary classification task, first randomly sample d-dimensional vector
Idd from (0 Ia) the ground-truth. Then we draw samples (æ;) from A(0, Ia) and obtain the label yA = 0T æ; > 0 and y, = otherwise. The size of training set is 2000 for each dataset. Note that each dataset corresponds optimizee function in the class of binary classification problem. We generate 100 different datasets in total, and use 90 generated datasets (i.e. 90 binary classification problem instances) train the optimizer and other 10 to test the performance of the learned optimizer. Unless specified otherwise, the problem dimension is d 100; the batch size and the number of query directions are set to b = 64 and 20 respectively. At each iteration of training, the optimizer is allowed to run 500 steps and unrolled for 20 steps.
different
In Figure 3a we compare various ZO optimizers and observe that our learned optimizer outperforms
all other hand-designed ZO optimization algorithms. Figure 3b compares the performance of ZO-SGD and ZO-LSTM with different query direction number q and batch size b. ZO-LSTM consistently outperforms ZO-SGD in different optimization settings. In Figure [d we generate binary classification problems with different dimension d and test the performance of ZO-LSTM. Our learned optimizer generalizes well and still achieves better performance than ZO-SGD.
4.3 GENERALIZATION OF THE LEARNED OPTIMIZER
In previous experiments, we train the optimizer using a small subset problem instances in a particular 70 optimization task and apply the learned optimizer in other problem instances, which

---

Published as a conference paper at ICLR 2020
20
201 updds
XOMM
125
STw
114
teration
14
201i7 lx180
35 350
350 125 122
(d)
Figure 3: Optimization performance comparison on synthetic binary classification problem. Each line is averaged over 10 test datasets with random initialization. (a): Training loss against iterations. ZO-LSTM-fineture denotes the learned optimizer trained on the MNIST attack task and fintuned on the binary classification task (see Section 4.3). (b)-(d): Effects of query direction number g, batch size 6, and problem dimension d, respectively.
demonstrates the generalization in specific class of ZO optimization problems. In this subsection, we study the generalization the learned optimizer across different classes of ZO optimization problems.
Current L2L framework (first-order) aims to train an optimizer on small subset problems and make the learned optimizer generalize to wide range of different problems. However, in practice, it is difficult to train general optimizer that can achieve good performance on problems with different structures and loss landscapes. In experiments, generalize to those problems with different relative scales between parameter update and estimated gradient (similar to the definition of learning rate). Therefore, we scale the parameter update pro- duced by the UpdateRNN by a factor a when generalizing the learned optimizer to another totally different task and tune this hyperparameter on that task (similar to SGD/Adam).
find that the learned optimizer could not easily
We first train the optimizer MNIST attack task and then finetune it on CIFAR- 10 attack tas as shown in Figure 2d 21 We see that the finetuned optimizer (ZO-LSTM- (-0-LStM-finetune) achieves compa- rable performance with Z0-L-TM which is trained from scratch on CIFAR-10 subset. We also generalize the learned optimizer trained on the MNIST attack task to the totally different binary clas- sification task (Figure 3a) and surprisingly find that it could achieve almost identical performance with ZO-LSTM directly trained on this target task. These results demonstrate that our optimizer has learned rather general ZO optimization algorithm which can generalize to different classes of ZO optimization problems well.
4.4 ANALYSIS
In this section, we conduct experiments analyze the effectiveness of each module and understand the function mechanism of our proposed optimizer (especially the QueryRNN).
Ablation study To assess the effectiveness of each module, we conduct ablation study on each task, as shown in Figure 4c We compare the performance of ZO-SGD, ZO-LSTM (our model), ZO-LSTM-no- -u-urry (our model without the QueryRNN, i.e., use standard Gaussian sampling). ZO- LSTM-no-update (our model without the UpdateRNN, i.e., ZO-SGD with the QueryRNN). We observe that both the QueryRNN and the UpdateRNN improves the performance of the learned
2 Althoogh black- box attack tasks on MNIST and CIFAR- 10 dataset seem to be similar on intuition, the ZO optimization problems on these two datasets are not such similar. Because targeted models are of very different architectures and image features also vary lot, the loss landscape and gradient scale rather different.

---

Published as a conference paper at ICLR 2020
20-6DD
102
20 SGD
20 LSTM
20-5TTM
2.00
predicted variance
20- ZO-LSTM no--itt
2045 Bontouurryy
Z0 LSTM
18500 updace
1.15
STN-GuidedTS
20-157866.uttee
1.0
gradion: cotimator
15a
120
110
Hteteition
value
0.3
(a)
(b)
1.2
20-
Ab Vida
20:3 10.5Ti Wins-query
20.5TH
$20
Ab aadaas
Cubeedd
parameter (p0.t STMO
paramater update 500)
0.205
parameter updat ADAMI
140
-0.505
Itteration
Iteration
query number
(c)
(d)
(c)
Figure 4: Analytical experiments demonstrating the effectiveness of our proposed optimizer. (a)- (c): Ablation study on MNIST attack task. CIFAR-I0 attack task, and binary classification task respectively. For MINST and CIFAR-10 attack task, We average the loss curve over all 100 test images and attack on each image run for 10 independent trails (see Appendix A.4 for additional plots single test images). (d): Evaluation of average cosine similarity between ZO gradient estimator and ground-tre -ruth gradient with and without the QueryRNN. (e): Optimization trajectory of one coordinate when applying ZO-LSTM on MNIST attack task. In the bottom figure, we apply ZO-SGD and ZO-ADAM to the same optimization trajectory as ZO-LSTM, i.e., assume they use the same ZO gradient estimator at each iteration but produce different parameter updates.
optimizer in terms of convergence rate or/and final solution. Noticeably, the improvement induced by the QueryRNN is less significant on binary classification task than on black-box attack task. We conjecture the reason is that the gradient directions are more random in binary classification task so much more difficult for the QueryRNN identify the important sampling space. To further demonstrate the effectiveness of the QueryRNN, we also compare 70-LSTM, Z0-LSTM- no-query with CO-LSSTM-GuidedlR the covariance matrix of random Gaussian sampling is adapted by guided evolutionary strategy (Guided ES). For fair comparison, we use the ZO gradient estimator and the parameter update at last iterate (the same as the input of our QueryRNN) Appendix B for details). We find that using GuidedES to guide the query direction search also improves the convergence speed MNIST attack task, but the improvement is much less than that of the QueryRNN. In addition, GuidedES leads to negligible effects on the other two tasks.
whose parameter update is produced by the UpdateRNN but
surrogate gradients for GuidedES (see
Estimated gradient evaluation In this experiment, evaluate the estimated gradient produced by the Guided ZO Oracle with and without the QueryRNN. Specifically, we test our learned optimizer on MNIST attack task and compute the average cosine similarity between the ground- truth gradient and the ZO gradient estimator over optimization steps before convergence. In Figure 4d we plot the average cosine similarity of ZO-LSTM and ZO-LSTM-no-query against different query direction number q. We observe that the cosine similarity becomes higher with the QueryRNN, which means that the direction of ZO gradient estimator is closer to that of the ground -ouun gradient. And with the query direction number y increasing. the improvement of cosine similarity becomes more significant. These results can explain the effectiveness of the QueryRNN in terms of obtaining more accurate ZO gradient estimators. In Appendix C.I evaluate the iteration complexity with and without the QueryRNN to further verify its improved convergence rate and scalability with problem dimension.
Optimization trajectory analysis To obtain more in-depth understanding of what our proposed optimizer learns, we conduct another analysis on the MNIST attack task. We use the learned opti- mizer (or "attacker") to attack one test image in the MNIST dataset. Then select one pixel in the image (corresponds to one coordinate to be optimized), and trace the predicted variance, the gradient estimator and the parameter update of that coordinate at each iteration, shown in Figure 4e We
8

---

Published as a conference paper at ICLR 2020
observe that although the ZO gradient estimator is noisy due to the high variance of random Gaussian sampling, the parameter update produced by the UpdateRNN is less noisy, which makes the optimization process less stochastic. The smoothing effect of the UpdateRNN is similar to that of ZO-ADAM, but it is learned automatically rather than by hand design. The predicted variance produced by the QueryRNN is even smoother. With larger value of 70 gradient estimator the parameter update, the QueryRNN produces larger predicted variance to increase the sampling bias toward that coordinate. We observe that the overall trend of the predicted variance is more similar to that of the parameter update, which probably means the parameter update plays a more important
role in the prediction of the Gaussian sample variance. Finally, in Appendix C.2 we also visualize
the predicted variance by the QueryRNN and compare it with final added perturbation to the image (i.e., the final solution of attack task).
CONCLUSION
In this paper, we study the learning to learn framework for zeroth-order optimization problems. We propose novel RNN-based optimizer that learns both the update rule and the Gaussian sampling rule. Our learned optimizer leads to significant improvement in terms of convergence speed and final loss. Experimental results on both synthetic and practical problems validate the superiority of our learned optimizer over other hand-designed algorithms. We also conduct extensive analytical experiments to show the effectiveness of each module and understand learned optimizer.
Despite the prospects of the 1.21. framework, current learned optimizers still have several drawbacks, such lack of theoretical convergence proof and extra training overhead. In our future work, we aim to prove the improved convergence in theory and further improve the training methodology.
REFERENCES
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in neural information processing systems, pp. 3981-3989, 2016.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy (SP), pp. 39-57. IEBE, 2017.
Pin-V Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26. ACM, 2017a.
Yutian Chen, Matthew W Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Timothy P Lillicrap. Matt Botvinick, and Nando de Freitas. Learning learn without gradient descent by gradient descent. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 748-756. JMLR. org, 2017b.
Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsieh. Query- efficient hard-label black-box attack: An optimization-base approach. In ICLR, 2019.
Neil E Cotter and Peter R Conwell. Fixeh-weight networks can learn. In 1990 IJCNN International Joint Conference on Neural Networks, pp. 553-559. IEEE, 1990.
John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 6155)2788-2806, 2015.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
Nikolaus Hansen. The ema evolution strategy: tutorial. arXiv preprint arXiv: /604.00077 2016.
Diederik Kingma and Max Welling. 1312v 2013.
Auto-encoding variational bayes.
arXiv preprint

---

Published as a conference paper at ICLR 2020
Ke Li and Jitendra Malik. Learning optimize. arXiv preprint
2016.
Ke Li and Jitendra Malik. Learning optimize neural nets. arXiv preprint arXiv: 173104 2017.
Xiangru Lian, Huan Zhang, Cho-Jui Hsieh, Yijun Huang, and Liu. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first- order. Advances in Neural Information Processing Systems, pp. 3054-3062, 2016.
Liu Liu, Minhao Cheng, Cho-Jui Hsieh, and Dacheng Tao. Stochastic zeroth-order optimization via variance reduction method. arXiv preprint arXiv: 1805. 1811,, 2018a.
Sijia Liu, Bhavya Kailkhura, Pin- Pu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth- order stochastic variance reduction for nonconvex optimization. In Advances in Neural Informa- fion Processing Systems, pp. 3727-3737, 2018b.
Sijia Liu, Pin-Yu Chen, Xiangyi Chen, and Mingyi Hong. signSGD via zeroth-order oracle. In International Conference on Learning Representations, 2019. URL /ttps:t:s:///peereeaa
DsC5Fm
Kaifeng Lv, Shunhua Jiang, and Jian Li. Learning gradient descent: Better generalization and longer horizons. In Proceedings the 34th International Conference Machine Learning-Voiin Volume 70, pp. 2247-2255. JMLR. org, 2017.
Niru Maheswaranathan, Luke Metz, George Tucker, Dami Choi, and Jascha Sohl-Dickstein. Guided evolutionary strategies: Augmenting random search with surrogate gradients. arXiv preprint 1806. 2018.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp. 506-519. ACM, 2017.
Chun-Chen Tu, Paishun Ting, Pin- Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder-base based zeroth order optimization method for attack- ing black-box neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 742-749, 2019.
Olga Wichrowska, Niru Maheswaranathan, Matthew W Hoffman, Sergio Gomez Colmenarejo, Misha Denil, Nando de Freitas, and Jascha Sohl-Dickstein. Learned optimizers that scale and generalize. In Proceedings of the 34th International Conference on Machine Learning-Var Volume 70. pp. 3751-3760. JMLR. org, 2017.
Daan Wierstra, Tom Schaul, Jan Peters, and Juergen Schmidhuber. Natural evolution strategies. In 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence). pp. 3381-3387. IEEE, 2008
Steven Younger, Sepp Hochreiter, and Peter Conwell. Meta-learning with backpropaga- tion. In IJCNN'01 International Joint Conference on Neural Networks. Proceedings (Cat. No. 01CH37222), volume 3. IEEE, 2001.
10

---

Published as a conference paper at ICLR 2020
A APPLICATION: ADVERSARIAL ATTACK TO BLACK-BOX MODELS
A.1 PROBLEM FORMULATION FOR BLACK-BOX ATTACK
We consider generating adversarial examples attack black-box DNN image classifier and for- mulate it as zeroth-order optimization problem. The targeted DNN image classifier F(x) [Fi, F2, .... Fk] takes as input an image [0. 1]d and outputs the prediction scores (i.e. log prob- abilities) of K classes. Given image æo E [0. 1] and its corresponding true label lo [1, 2,, K], an adversarial example æ is visually similar the original image zo but leads the targeted model F to make wrong prediction other than to (i.e., untargeted attack). The black-box attack loss is defined as:
min [Fa max (x)) 3710
cll -xpll-
xollp
(6)
The first term is the attack loss which measures how successful the adversarial attack is and pe- nalizes correct prediction by the targeted model. The second term is the distortion loss (p-norm of added perturbation) which enforces the perturbation added to be small and is the regularization coefficient. In our experiment, we use norm (i.e., p = 1), and set e 0.1 for MNIST attack task and c = 0.25 for CIFAR-10 attack task. To ensure the perturbed image still lies within the valid image space, we can apply simple transformation æ (tanhi( w) + 1)/2 such that æ [0, 1jd. Note that in practice, we can only get access to the inputs and outputs of the targeted model, thus cannot obtain explicit gradients of above loss function, rendering it a ZO optimization problem.
A.2 VISUALIZATION OF GENERATED ADVERSARIAL EXAMPLES VERSUS ITERATIONS
Iteration
25
48
62
75
100
116
150
2.
2
2
2
2
2
2
2
ZO-LSTM
Predicted label
2
2
7
7
7
7
2
2
2
2
2 2
2.
2
2
ZO-SGD
Predicted label
2
2
2
2
7
2
2
2
2
2
2
2
2
ZO-signSGD
Predicted label
2
2
7
7
2 2
2 2
2
2
2
2 7
2
2
ZO-ADAM
Predicted label
2
Table 1: Generated adversarial examples of each optimization algorithms versus iterations on
MNIST Test ID 1933 (corresponding black-box attack loss curve is shown in Figure 2b

---

Published as a conference paper at ICLR 2020
A.3
ADDITIONAL PLOTS OF BLACK-BOX -OX ATTACK LOSS VERSUS ITERATIONS
Z0-SGD
Z0-SGD
20.0
20-signSGO
20-signSGD
Z0-ADAM 20-LSTM
Z0-ADAM
15.5
20-LSTM
lass
10.5
3.0
25
100
175
200
25
50
100
150
175
200
iteration
iteration
(a) MNIST Test ID 9082
(b) MNIST Test ID 258
14
ZO-SGD
14-
ZO-SGD
12
20-sign5 GD
20-signSGD
Z0-ADAM
Z0-ADAM
12-
20-LSTM
20-LSTM
15-
1055
l05s
25
100
175
200
25
100
175
200
Iteration
iteration
(c) MNIST Test ID 748
(d) MNIST Test ID 4558
14
ZO-SGD
ZO-SGD
20-signs GD
20-signSGD GD
ZO-ADAM Z0-LSTM
ZO-ADAM Z0-LSTM
loss
25
102
375
200
25
100
150
175
200
iteration
iteration
(c) MNIST Test ID 6218
(f) MNIST Test ID 9827
14
Z0-SGD
181
Z0-SGD
Z0-signS GD
15:
Z0-signSGD
ZO-ADAM
14
ZO-ADAM Z0-LSTM
12.
Z0-LSTM
12
loss
25
102
375
200
25
375
200
Iteration
Iteration
(g) MNIST- Test ID 2350
(h) MNIST Test ID 2221
Figure 5: Additional plots of black-box attack loss curves on random selected MNIST test images. The loss curves are averaged over 10 independent random trails and the shaded areas indicate the standard deviation.
12

---

Published as a conference paper at ICLR 2020
20-SGD
20-9GD
ZO-sign5GD
Z0-sign5GD
12
15.2
20-LSTM
20-LSTM
l055
ZO LSTM finctune
ZO LSTM finctune
5.2
2,5
Iteration
(a) CIFAR Test ID 7007
(b) CIFAR Test ID 9139
ZO-SGD
20-SGD
15
ZO-signSGD
ZO-signSGD
Z0-LSTM
Z0-LSTM
ZO-LSTM-1netune
ZO-LSTM-Iinetune
12.5
5.0-
25
iteration
iteration
(c) CIFAR Test ID 692
(d) CIFAR Test ID 5138
ZO-SGD
Z0-SGD
20.0
ZO-signSGD
ZO-signSGD
ADAM
20-ADAM
ZO-LSTM
ZO-LSTM
15.0
20-LSTM-1netune
ZO-LSTM-Inettune
7.5
5.2
2.5
2.5
iteration
iteration
(c) CIFAR Test ID 8212
(f) CIFAR Test ID 8392
22.5
17.5
ZO-SGD
Z0-SGD
signSGD
SignSGD
15.0-
ADAM
ADAM
ZO-LSTM
15.2
ZO-LSTM
ZO-L5TM--fnetune
ZO-LSTM--fnetune
12.5
7.5
7.5
5.2
5.-
2.5
iteration
iteration
(g) CIFAR Test ID 9687
(h) CIFAR Test 7974
Figure 6: Additional plots of black-box box attack loss curves random selected CIFAR- test images. The loss curves are averaged over 10 independent random trails and the shaded areas indicate the standard deviation.
13

---

Published as a conference paper at ICLR 2020
A.4
ADDITIONAL PLOTS FOR ABLATION STUDY
ZO-SGD
Z0-SGD
12
ZO-LSTM
20-LSTM
Z0-LSTM--no-queyy
12-
Z0-LSTM-no-query
10
220-LSTM-no update
100LLSM-mn MoM--o-uun update
105s
20 ES
loss
20 SSMdedd
25
100
150
175
200
25
50
100
125
150
175
200
iteratioo
iteration
(a) MNIST Test ID 748
(b) MNIST Test ID 4558
ZO-SGD
ZO-SGD
ZO-LSTM
ZO-LSTM
ZO-LSTMM-noqquery
Zo-LSTM--n-query
L-STM-o--udee
ZO-LSTM-no updatee
l0s5
20 LSTM GuidedES
loss
20 LSTM GuidedES
25
100
150
175
200
25
50
100
125
150
175
200
Iteration
Iteration
(c) .NMSNSST- - Test ID 6218
(d) MNIST - Test ID 2221
ZO-SGD
ZO-SGD
15-
ZO-LSTM
ZO-LSTM
17.5
ZO-LSTM--n-qqery
ZO-LSTM-nn-query
2D--LSMM-no-uddee
15.2-
ZO-LSTM-no update
12
20 LSTM GuidedES
12.5
20 LSTM GuidedES
10.0
5.2
2,5
25
50
102
150
375
200
25
50
100
125
150
175
200
iteration
Iteration
(e) CIFAR Test ID 692
(I) CIFAR Test ID 5138
ZO-SGD
ZO-SGD
23.0
ZO-LSTM
ZO-LSTM
17.5
ZO-LSTMM-no-qurry
17.5
ZO-LSTM--n-query
Z0-L5TM--n-uudate
15.5-
20-L5TM-no-update
ZO-L5TM-GuldedES
ZO-LSTM-GuldedES
32.5
12.5
19.0
13.2
5.2
5.5-
2.5
2.5
25
50
102
150
375
200
25
50
75
100
125
150
375
200
Iteration
Iteration
(g) CIFAR - Test ID 4293
(b) CIFAR - Test ID 7974
Figure 7: Additional plots for ablation study on single test images. (a)- Plots on randomly selected test images in MNIST dataset. (e)-(h): Plots on randomly selected test images in CIFAR-10 dataset.
14

---

Published as a conference paper at ICLR 2020
B IMPLEMENTATION DETAILS FOR GUIDED EVOLUTIONARY STRATEGY
Guided evolutionary strategy (GuidedES) in Maheswaranathan et al. (0118) incorporates surrogate gradient information (which is correlated with true gradient) into random search. It keeps track of a low dimensional guided subspace defined by k surrogate gradients, which is combined with the full space for query direction sampling. Denote U E Rd as the orthonormal basis of the guided subspace (i.e., U = Is). GuidedES samples query directions from distribution (0, E), where the covariance matrix modified as:
= + (1-
where trades off between the full space and the guided space and we tune the hyperparameter
= 0.5 with the best performance in our experiments. Similar to what we have discussed in Sec- tion 3.1 we normalize the norm of sampled query direction to keep invariant.
our experiments, GuidedES uses the ZO gradient estimator and the parameter update at last iterate (the same as the input of our QueryRNN) as input for fair comparison with our proposed QueryRNN.
C ADDITIONAL ANALYTICAL STUDY
C.I ITERATION COMPLEXITY VERSUS PROBLEM DIMENSION
90
ZO-LSTM-no-update
ZO-SGD
iteration
60
49 98
196
392
588
784
dimension
Figure 8: Iteration complexity versus problem dimension on MNIST attack task. Iteration complex- ity is defined as iterations required to achieve initial attack success which are averaged over 100 test images.
In this experiment, we evaluate the iteration complexity with and without the QueryRNN. Specif- ically, we test the performance of ZO-SGD and QueryRNN) on MNIST attack task and compare the iterations required achieve initial attack suc- cess. In Figure g we plot iteration complexity against problem dimension d. We generate MNIST attack problems with different dimensions E (28 x 28, 21 28, 14 28, x 14, 7 x 14, 7 7) by rescaling the added perturbation using bilinear interpolation method. From Figure 8 we find that with the problem dimension increasing, ZO-SGD scales poorly and requires much more iterations (i.e.. function queries) to attain initial attack success. With the QueryRNN, ZO-LSTM-no-upddle consistently requires lower iteration complexity and leads to more significant improvement on prob- lems of higher dimensions. These results show the effectiveness of the QueryRNN in terms of convergence rate and scalability with problem dimensions.
(i.e., ZO-SGD with the
C.2 VISUALIZATION OF ADDED PERTURBATION AND PREDICTED VARIANCE
To further verify the effectiveness of the QueryRNN, we select one image from MNIST dataset and visualize final added perturbation to the image (i.e., the final solution of MNIST attack task) well as sampling variance predicted by the QueryRNN, as illustrated in Figure 9 We first compare final perturbation produced by ZO-LSTM (Figure 9b) and RO-L.STM-no--quee (Figure 9ch. We observe
15

---

Published as a conference paper at ICLR 2020
(a)
(b)
(c)
(d)
Figure 9: Visualization of final added perturbation to the image and predicted variance by the QueryRNN. (a): Original image of digit class "1". (b): Final perturbation generated by 70- LSTM (with the QueryRNN). (c): Final perturbation generated by Z0-LSTM--n--qery (without the QueryRNN). (d): Average predicted variance by the QueryRNN of ZO-LSTM over iterations before convergence.
that the perturbation produced by these two optimizers are generally similar, but that produced by ZO-LSTM is less distributed due to the sampling bias induced by the QueryRNN. Then we take the predicted variance by the QueryRNN of ZO-LSTM (averaged over iterations before convergence) into comparison (Figure 9dh. We find that there are some similar patterns between average predicted variance by the QueryRR QueryRNN RNN and final added perturbation generated by ZO-LSTM. It expected since ZO-LSTM uses the predicted variance by the QueryRNN to sample query directions, which would that
thus guide the optimization trajectory and influence the final solution. Surprisingly, the average predicted variance by the QueryRNN of Z0-LSTM is also similar to final perturbation produced by 70-LLSTM-no-qeery (which doesn't i utilize the QueryRNN). These results demonstrate that the QueryRNN could recognize useful features quickly in the early optimization stage and produces sampling space toward the final solution.
C.3 ILLUSTRATION OF THE TRADFOFF BET WEEN BIAS AND VARIANCE
55
2.30
loss
iteration
45
ittraation
2.20
2.28
40
2,00
2.22
sample frequency
Figure 10: Sensitivity analysis sample frequency in the predicted subspace on MNIST attack task. Iteration complexity and loss are defined iterations required achieve initial attack success and the corresponding loss, which are both averaged over 100 test images.
This experiment means to illustrate the concept of the tradeoff between bias and variance (Sec- tion 3.1.. We test our learned optimizer on MNIST attack task with different sample frequency in the predicted subspace (i.e., the probability p for the Bernoulli variable X ~ Ber(p) in Section 3.11. As shown in Figure I0, with the sampling frequency increasing, the learned optimizer converges faster but obtains higher loss, which means reduced variance and increased bias respectively. No- tably, the sensitivity (i.e., the relative difference) of the final loss w.r the sampling frequency is much lower than that of the iteration complexity, which means that can sample in the predicted
16

---

Published as a conference paper at ICLR 2020
subspace with higher frequency. In our experiments, simply set the sampling frequency to 0.5 without extra tuning.
C.4 COMPARISON WITH VARIANCE REDUCED ALGORITHM
ZO:SGD
ZO-SGD
Z0-SZVR-G ZO-LSTM-nn-update
Z0-SZVR-G
10-
ZO-LSTM-nnoupdatee
loss
25
50
75
100
150
175
230
50
75
100
125
150
375
296
Reration
query/20
(a) Loss iteration number
(b) Loss versus query number
Figure 11: Comparison between with existing zeroth-order variance reduced algorithm (ZO-SZVR- G) on MNIST attack task. Loss curves are averaged over all 100 test images and attack on each image is rum for 10 trails.
In this experiment, we compare the performance of ZO-SGD with the QueryRNN (ZO-LSTM-no- update) and ZO-SGD with the variance reduced method (C--SVV-GG) on MNIST attack task. For fair comparison, each method uses g = 20 query directions to obtain 70 gradient estimator each iteration. For ZO-SZVR-G, we divide iterations into epochs of length 10. At the beginning of each epoch, we maintain a snapshot whose gradient is estimated using q' = 100 query directions and this snapshot is used as reference to modify the gradient estimator at each inner iteration. We refer readers to
Liu et al. 2018a) for more details.
In Figure la we compare the black-box attack loss versus iterations. We observe that although ZO- SZVR-G converges faster than ZO-SGD because of reduced variance, it leads to higher final loss values. But our QueryRNN brings about improvements both in terms of convergence rate and final loss. Note that 20-SZVR-C requires more function queries to obtain the snapshot and modify the gradient estimator at each iteration, also plot black-box attack loss versus queries in Figure[1h] We observe that ZO-SZVR-G needs much more queries than ZO-SGD and our method.
17


Reviews:
[{"review_id": "rylVGWoAFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a learning to learn (L2L) framework for zeroth-order (ZO) optimization, and demonstrated its effectiveness on black-box adversarial example generation.  The approach is novel since L2L provides a new perspective to zeroth-order optimization. \n\nHowever, I have some concerns about the current version. \n\n1) The knowledge that one should use to train UpdateRNN and  QueryRNN is not clear. A clear presentation is required \n\n2) Please clarify the optimization variables in (4). In general, the problem is not clearly defined. \n\n3) Eq. 5 is a query-expensive gradient estimate. Will it make training extremely expensive?\n\n4) The computation and query complexity are unclear during training and testing.\n\n5) Pros and cons of L2L? It seems that training a L2L network is not easy. Does its advantage exist only when inference? A better discussion should be made.\n\n########## post-feedback #######\nThanks for the response. In the pros of L2L, the authors mentioned \"The learned optimizer is trained on a small subset of optimization problems and apply in a wide range of problems in similar classes.\" In the setting of attack generation, does it mean that there exists an attack transferbility from a small group of training images to a large group of testing images? Is the transferbility a requirement for applying L2L in design of attacks. Please try to make these points clearer in the revised version. I keep my decision 'weak accept'. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HylOroWRYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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). \n\nGiven 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.\n\nThe paper includes a large number of typos (e.g., CIFAR-->CIAFR) and grammatical errors, but is otherwise clear.\n\nADDITIONAL COMMENTS/QUESTIONS\n\n* The related work discussion would benefit from a discussion of how Liu et al. 2018 and Guo et al. 2016 reduce variance\n\n* 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?\n\n* 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.\n\n* 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?\n\n* The discussion of Eqn. 5 as it relates to Eqn. 1 is unclear.\n\n\nUPDATE AFTER AUTHOR RESPONSE\n\nI 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).", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgs4nvCFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a novel learning to learn framework based on zeroth-order optimization. Specifically, the framework consists of three parts: (1) UpdateRNN for learning the parameter update rules (2) Guided gradient estimation and search (3) QueryRNN that dynamically adapts the Gaussian sampling rules for covariance estimation in (2). \n\nExperimental results on generating adversarial examples from black-box machine learning models as well as a binary classification problem demonstrate improved performance over several existing baselines, such as better query efficiency or faster empirical convergence in the loss function. An ablation study is also conducted to study the effect of each component in the proposed framework. \n\nOverall, this paper is pleasant to read and well-motivated. The applications are of practical importance. Given that the empirical results suggest faster convergence than the compared methods, it will be great if the authors can also discuss how to prove the improved convergence in theory.\n\n*** Post-rebuttal comments\nI thank the authors for the clarification.\n***", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to extend learning to learn framework based on zeroth-order optimization. Generally, the paper is well presented and easy to follow. The core idea is to incorporate another RNN to adaptively to learn the Gaussian sampling rule.  Although the method does not seem to have a strong theorical support, its effectiveness is evaluated in the well-organized experiments including realistic tasks like black-box adversarial attack. 
All reviewers including two experts in this field admit the novelty of the methods and are positive to the acceptance. I’d like to support their opinions and recommend accepting the paper.
As R#1 still finds some details unclear, please try to clarify these points in the final version of the paper.
Decision: Accept (Poster)