Efficient Non-Parametric Optimizer Search for Diverse Tasks
Authors: Ruochen Wang
Yuanhao Xiong
Minhao Cheng
Cho-Jui Hsieh
Venue: NeurIPS 2022 Accept (2022)
Keywords: AutoML
Optimizer Search
Optimization
Adversarial Robustness
Graph Neural Networks
BERT

Abstract: Efficient and automated design of optimizers plays a crucial role in full-stack AutoML systems. However, prior methods in optimizer search are often limited by their scalability, generability, or sample efficiency. With the goal of democratizing research and application of optimizer search, we present the first efficient, scalable and generalizable framework that can directly search on the tasks of interest. We first observe that optimizer updates are fundamentally mathematical expressions applied to the gradient. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the space of optimizers into a super-tree, where each path encodes an optimizer. This way, optimizer search can be naturally formulated as a path-finding problem, allowing a variety of well-established tree traversal methods to be used as the search algorithm. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent-form detection that leverage the characteristics of optimizer update rules to further boost the sample efficiency. We provide a diverse set of tasks to benchmark our algorithm and demonstrate that, with only 128 evaluations, the proposed framework can discover optimizers that surpass both human-designed counterparts and prior optimizer search methods. Our code is publicly available at https://github.com/ruocwang/enos.

Efficient Non-Parametric Optimizer Search for Diverse Tasks
Ruochen Wang', Yuanhao Xiong', Minhao Cheng', Cho-Jui Hsich'
Depparteent of Computer Science, UCLA, PKKUST ruocvangducla.co edu minhaochengoust.. .kk {chohsieh, yhxiong)ecs wwceeesssclll..o wula.
Abstract
Efficient and automated design of optimizers plays crucial role in full-stack AutoML systems. However, prior methods in optimizer search are often limited by their scalability, generalization, tizing research and application of optimizer search, we present the first efficient, scalable and generalizable framework that directly search the tasks of in- terest. We first observe that optimizer updates are fundamentally mathematical expressions applied the gradient. Inspired by the innate structure of the un- derlying math expressions, we re-arrange the space of optimizers into a super-tree, where each path encodes an optimizer. This way, optimizer search can be naturally formulated
sample efficiency. With the goal of democra-
path-finding problem, allowing a variety of well-established tree traversal methods to be used as the search algorithm. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent-fome detection that leverage the characteristics of optimizer update rules to further boost the sample efficiency. We provide a diverse set of tasks to benchmark our algorithm and demonstrate that, with only 128 evaluations, the proposed framework counterparts and prior optimizer search methods. Our code is publicly available at /ttpp://githnn com http///uowwangggneee enos
discover optimizers that surpass both
Introductions
Motivated by a vision of democratizing machine learning, the central objective for automated machine
learning (AutoML), such automated architecture [22] 26
29
40
55
60
62
55
optimizer
lies in reducing the need for expert design on diverse set of tasks. To achieve this goal, it is critical for AutoML systems to exhibit
10
12 15
68 loss [36] augmentation search 37 39
high level of efficiency, so that they can be directly applied to variety of tasks without consuming humongous amount of computing resources. widely successful example of such an effort is DARTS 40 in Neural Architecture Search (NAS), which reduces the search cost from thousands of GPU days early RL-based algorithms a single digit, enabling direct application of NAS systems to wide range of tasks 32
36
48
50
attention another important but much less studied area of AutoMI. Automated optimizer search, where an efficient, scalable and generalizahle framework is still absent. Optimizer search aims automatically design a suitable update function that takes gradients as inputs and produces update directions for the optimizee's parameters. Pioneering work in this area, coined Learning to Optimize (L20), adopts a data-driven approach by replacing human-designed update rules with a learnable parametric 12 17 59]. However, parametric optimizers are fundamentally not scalable large models or datasets, as inferring its parameters typically requires expensive meta-learning steps such as backpropagating through gradient descent
Inspired by the success of efficient NAS methods,
function 1T0
(10) 68 Moreover, the learned optimizer often generalizes poorly to even minor variants of its training task (Figure H0 68
Poor scalability and
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

generalization prevent L20 from being served as a general-purposs. optimizer search framework that can be directly applied to tasks of interest.
The aforementioned limitations of parametric optimizers bring our attention to another line of method that searches over the discrete space of non-parametric update functions which generally exhibit the same level of scalability and generality as human-designed optimizers T5 5T. NOS-RL [[S] extends early RL-based NAS framework p2 optimizer search, proposing to learn sequential controller to produce optimizer update rules according to a predefined pattern. However, NOS-RL is sample inefficient, requiring over 10k evaluations to find good candidates. More recently, AutoML- Zero [51 699] proposes to search over the vast space of computer codes for the entire ML pipeline (including the optimizer). The excessive generality of its search space makes even more costly to run than RL-based method. The search cost of existing non- -oraameettiic optimizer search frameworks makes them computationally prohibitive not only for practitioners to apply but also for researchers to analyze.
With the goal of democratizing research and practical applications of automated optimizer design, we introduce the first efficient, scalable, and generalizable optimizer search framework that can be directly applied to wide range of tasks. We observe that non-parametric update rules are essentially mathematical expressions, with an innate tree structure where nodes are elementary math operators and edges represent their I/Os. Consequently, generating an update rule can be viewed as progressively appending nodes to the expression tree until it is complete. Inspired by this observation, we re-imagine the optimizer search space super-tree of mathematical expressions. Each leaf node on the super-tree contains an optimizer, and the path towards it represents the generation process of that optimizer's underlying expression. With the tree-structured search space, optimizer search can be naturally formulated as a path-finding problem, allowing wide range of well-established tree-traversal methods to be used as the search algorithm. We show that a simple adaptation of Monte Carlo Sampling [30 [3 equipped with our proposed rejection sampling and fqui detection, can already produce remarkable results on our search space within a fraction of budgets compared with NOS-RL (~ 1%).
We extensively evaluate the proposed framework on a diverse set of learning tasks: digit clas- sification with MNISTNET [0. image classification with ConvNet (15), graph learning with (Cluster)GGAT 21 28 noundbounded adversarial attack on robustly trained models 2 55
and BERT fine-tuning on NLP datasets 33 [56.. These tasks cover both constraint and unconstrained optimizations and span over large variety of models and datasets. Despite the simplicity, the pro- posed framework is able to discover update rules that surpass human-designed optimizers and prior optimizer search methods, with a budget of only 128 evaluations. We hope the proposed framework could lower the barrier of entry to practical nonpparametric optimizer search, thereby providing an entry point for researchers and practitioners from ML community and beyond to study and utilize automated optimizer search systems.
2 Efficient, scalable and generalizable framework for optimizer search
2.1 Optimizer design space
Notations and problem formulation Deep learning tasks are frequently expressed as optimizing a loss function I(-) defined over parameter domain 0 E O. The minimizer of I. can thus be obtained by 8" arg mingge (0). For differentiable functions, a standard optimizer typically takes the form of iterative gradient descent: 0c+1 = 0g 7 * ø( o()T.(())) (0:))), where / is the current iteration, is the learning rate and & denote the update function. Existing optimizers primarily differ in their design of update function Φ; For example, vanilla gradient descent uses identity mapping ((x) as the update function, whereas Adam adopts a momentum- dynamic learning rate schema: o( (()) = m m(VoL((..) V an internal state.
where m--) denotes the momentum function with
The goal of optimizer search is to automatically find a suitable update function & over some hypothesis space क. The hypothesis spaces used in prior work can be divided into two categories: ooraamamttric and parametric spaces. Most numan-designed optimizers belong to the first category, where the update
'Sometime it is referred to as symbolic optimizers, which is somewhat inaccurate categorization as symbolic functions could also contain learnable parameters.

---

function & is not trainable. Learnable optimizers, such as L2LGD2 [0] and SymbolicL20 [68,, fall into the second category. Our work mainly focuses on non non-parametric optimizer search, with the goal of providing an efficient, scalable and generalizable optimizer search framework that can be directly apply to various tasks.
Optimizer update rules as expression trees The first step toward such a framework is to under- stand the structure of non-parametric optimizers. We realize that, fundamentally, optimizers are mathematical expressions consisting of elementary operators (+. -, sign(), inputs, e.t.c.). Math expressions have an inherent tree structure that preserves its order of execution, where nodes operators and edges represent their I/Os. For instance, Diagram shows the expression tree of Adam 9
log( D
sign()
deoon))
m2
Diagram 2: Our discovered Optimizer for adver- sarial attack
Diagram Adam optimizer
where mi and my denote the first and second order momentum (which also be broken down into their own expression trees).
Therefore, the generation of an update rule, as a mathematical expression, can also be conducted via top-down node selection: Take Adam as an example, we first select division (/) as the root node, For its left child, we pick m., which is leaf node and thus ends the branch. For the right child, we select VT, and subsequently pick m2 to follow it. At this point, there is no empty branches left, and we obtain the complete update rule for Adam.
A tree-structured search space Inspired by the completion process of update rules, we rear- range all expressions into super-tree, where each leaf node contains an update rule and each path represents its completion process. The super-tree can be generated in top-down man- ner: Starting from the root node with empty update rule, we generate each of its child nodes by inserting different operator into the update rule, and repeat this process for the generated nodes. Consequently, an optimizer can be sam- pled by traversing the super-tree tree until leaf node reached. Since the super-tree can grow in- finitely deep, it is often desirable to restrict the tree to a predefined depth N, where only the paths that can be completed within depth N are included. Figure provides an instantiation of our super-tree, where the paths leading to Adam and SGD optimizers are displayed as example.
rool
<L>/ER>
L- 2011
R
< R
171
Plty Ving (Adai))
Figure
An illustration of traversing the super- tree to discover Adam and SGD.
The benefit of arranging the optimizer space into tree is two folds. Firstly, the tree-based search space is tight:
Proposition 1 Define the length of update rule as the number of operators it includes, then the above tree-based search space is tight: a super-tree with a maximun depth of N covers all update rules of length greater than N.
In tight search space, all optimizers can be represented the right level of complexity, allowing them to be visited by the search algorithm without exploring unnecessarily deep into the super-tree. Although tightness is a fairly obvious result for our space, it not case for the previous search space defined in NOS-RL, as we will explain later. Secondly, with our super-tree, optimizer search can naturally formulated as a path-finding problem, allowing a variety of well-established tree traversal methods to be deployed as search algorithms.
3

---

To concretize the content of the search space, we allow three types of operators in the optimizer update rule:
Contents
a set of p1 unary operators (e.g. log(1 : 1), exp(-), vT sign(-), drop(-))
a set of P2 binary operators (e.g. + x, /, pow((,))
a set of L leaf values (input operators) containing gradient-based terms (e.g. 9, m1), decays
(e.g. mosine_decay)) and constants (e.g. 1. 2)
This categorization of mathematical operators is not new, as it is also adopted in symbolic math solver 351 and NOS-RL 15
Comparison with NOS-RL's search space Although both NOS-RL [15] and our framework use elementary math operators as building blocks for optimizers, they have little in common in terms of the arrangement of the search spaces. Optimizers in NOS-RL's search space are formed by a chain of predefined motifs: b(u(I), u())), where b, u. denote binary, unary and input operators. Due to the fixed structure of such motifs, NOS-RL's search space not tight: there exist many optimizers that take extra longer sequences to express, potentially lowering their chance of being discovered by the search algorithm. For instance, Diagram 2 shows an optimizer of length 5, but takes (10 1) nodes (two chained motifs) to represent it under NOS-RL's arrangement; Morcover, NOS-RI search space also requires extra bypass operators (c.g. u(z) = x and b( y) = z) to cover even human- guman-design optimizers such Adam and PGD, further increasing the complexity. In contrast, representation of optimizers is directly inspired by the innate structure of its underlying mathematical expressions, resulting in tight tree-based search space. In our search space, optimizer search can be naturally formulated as a form of top-down path-finding problem. In the next sections, we will detail our choice of algorithms for traversing the super-tree, as well as several techniques that leverage the characteristics of optimizer update rules to boost the sample efficiency.
2.2 Monte Carlo Sampling for tree traversal
We adopt a simple adaptation of Monte Carlo Sampling to tree traversal search algorithm. The idea is to assign scores the nodes in the super-tree (Figure D and use these scores to guide the tree traversal. We define the score of a node v as a Monte Carlo estimation over unrolling steps from If is internal node, we randomly generate set of unrolled paths from to the corresponding leaf nodes, and take the average score of the resulting optimizers as the score for ;; If is leaf node, set its score to it cannot be expanded. The search
30 33 70
(MCT) as the
thus be conducted as follows: 1). Starting from the root node ((()) at level 0, we generate all child nodes (v(") of (0) by inserting each operator from the candidate pool to the update rule in (0)); 2). From there, select the child node (1) with the highest MC. score to expand, and move on to the next level; 3). The
process is repeated until predefined maximum search level is reached. Algorithm I in the Appendix provides a detailed summary of the complete search process.
Directly applying the MCT algorithm to optimizer search would not perform well under limited search budgets, due to two unique characteristics of optimizer update rules that challenge the sample efficiency of the Monte Carlo estimates. Firstly, the majority of mathematical expressions, when deployed as optimizer update rules, perform poorly or even would not converge. This is usually not the case for other AutoML tasks such as neural architecture search, as most networks in the search space perform reasonably well. The large body of noor-performing optimizers not only consumes precious search budget, but also causes the MC estimation to be unstable. Secondly, there exists many mathematical redundancies in the expression space, for example: sign(sign) (sign(sign(()) (s)) can
be reduced to sign(x), and mi+yiz is equivalent vm2 + Identifying and eliminating these mmz
redundancies would not only save budget, but also prevent the sampling distribution from biasing toward mathematically simple and shallow update rules. To address these issues and further boost the sample efficiency, we propose two sets of techniques rejection sampling and equivalent-form detection. When combined with these techniques, the simple MCT algorithm becomes particularly effective for the optimizer search task. We will discuss them in detail in the following sections.
2.3 Rejection sampling

---

Eliminating poor optimizers with train-free task- agnostic test Inspired by the characteristics of op- timizer update rules, we develop train-free task- agnostic test eliminate poor optimizers without evaluating them. We propose a necessary condition for a valid optimizer: must produce an acute angle with steepest descent direction (i.e. gradients). We check the validity of optimizers against this condition and only evaluate those that pass the test. For the test to dask-agnostic, we feed the optimizer with a batch of random Gaussian vectors in place of actual gradients. Formally, the descent test can be written
Original Diriiutiin
800-
applying cescent
Number optimizers
703-
600-
100
300
220
Accuracy
Figure 2: Performance distribution of op- timizers after applying descent test, under d 0.15 and batch size of 25.
1a (oos VoC) Aa
where Aa is a predefined threshold. Although our descent test is by-no-mean comprehensive, it can effectively rule out a large chunk of poor optimizers with negligible false-negative rates, as demonstrated in Figure
Reducing the variance MC estimates via score thresholding After applying the descent test, there still remains a non-negligible portion of poor optimizers. When sampled during the unrolling step, these optimizers would drastically lower the Monte Carlo score of the stem node, causing the MC estimation to exhibit high variance and thus become unreliable. This adverse effect is especially severe under the efficient setting when the sample size is small. Therefore, we propose to simply reject candidates with scores lower than predefined threshold, thereby removing them from the MC scores of the corresponding stem nodes.
2.4 Detecting and handling redundancies in mathematically equivalent forms
On-the-fly constraint tree-traversal for redundant path pruning One benefit of formulating the search problem as top-down path-finding is that we can easily apply constraints on-the-fly to eliminate undesirable branches those that lead to mathematically redundant expressions in our case.
We identify three main categories of such constraints:
child operator that nullifies its parent's operator. e.g. -1-
child operator that redundant under its parent. e.g. clip(clip(z)) = clip(x)
sequence of operators that reduces to constant in the search space. e.g. V(sign(z) =
The complete sets of constraints used can be found in the Appendix. Enforeing these constraints during the traversal can effectively trim down the search tree, allowing the algorithm to explore branches that lead more diverse and complex expressions.
Hashing mathematically equivalent expressions Besides enforcing constraints during the traver- sal, is also important to detect mathematically equivalent optimizers avoid duplicated evaluations. One can always apply off-the-shelf symbolic solvers to identify the equivalence of two expressions, ó and ø'. by checking (Ø- Φ') can be reduced to O. However, it could become extremely slow as the pool of evaluated optimizers {Ø h gets larger and larger, since we need to solve N pair of equations every time new update rule is sampled. Instead, we apply hashing to efficiently query the evaluated candidate pool for mathematically equivalent optimizers. Concretely, we assign each optimizer a hash code, obtained by feeding a fixed probing vector as input to the optimizer and recording its output. The probing vector is pre-sampled from Gaussian distribution. When newly sampled optimizer arrives, we only need to compare its code with the hash table to check the existence of its equivalent form. Empirically, it is much faster to run the proposed hashing- based checker than symbolic solvers.
3 Discussions and relationship to prior work
Automated optimizer design Optimization plays a crucial role training deep learning models. Generally, there does not exist one optimizer that aces all scenarios, different tasks (dataset,
5

---

architecture, loss, parameterization, e.t.c.) might favor different optimization methods 2 [0]. The demand for task-specific optimizers stimulates research interest in developing automated systems Early work adopts a data-driven method by
for optimizer design [T0 12 15
51
59
66
68
modeling the optimizer update with a parametric function [10 12 59 1.2LGDD2 [TQ] deploys an
LSTM model as the update function that takes historical gradients as input and produces the update direction. However, parametric optimizer search methods are fundamentally limited by its scalability, as inferring its parameters requires expensive meta-learning steps such as back-propagation through optimization ITC.
59 68]. Although SymbolicL20 [68] improves the scalability of the learned symbolic optimizer, it still requires pretrained LSTM model to begin with. Instead of learning a parametric optimizer, NOS-RL [[5] directly searches over discrete space of non-parametre update functions comprised of mathematical operators. It extends early RL--based NAS method [22] to optimizer search, by training a sequential controller to produce the optimizer update rule according predefined pattern. However, similar to its NAS counterpart, NOS-RL is also computationally expensive, requiring over 10k evaluations to find good candidates.
LSTM optimizer by distilling it into
Symbolic optimization and differential program synthesis Symbolic optimization (SO) 53 61 63 64 aims at optimizing an objective over a symbolic hypothesis space of functions (or more broadly, programs). One line of work attempts to recover the unknown equation from its generated data, with great potential in automating scientific discoveries (54]
Another line of methods aims at finding more interpretable and generalizable symbolic model replace the black-bol -bx
neural networks (53] 61 631
Applications that witnessed some success include learning symbolic
policy networks for RL
65 and sequential classification models [53 O1. The latter is often studied
under the concept of Program Synthesis [24]. where a model is extended to include programmatic
rules such as if-else clause, indexing, e.t.c. SO is closely connected to AutoML at high level, as both fields frame their problems as discrete optimization. Indeed, many existing optimizer search methods can find their counterparts in symbolic optimization. Our method is also inspired by the rich body of literature in deep symbolic mathematics and program synthesis. which also explores However, due to significant differences in taskonomy, SO and AutoML methods are often developed separately, converging into different branches of techniques. Symbolic optimization often studies tasks where
tree-based expression spaces for differential equations and programs 30 35 53
51 64
candidates are cheap to evaluate but finding the global optimal is desired [] [5 64]; As a result, sample efficiency is often not the primary concern. Much the opposite, in AutoML tasks, candidate evaluations are extremely expensive: Therefore, it is more beneficial to identify good-enough candidate within a limited amount of budget.
4 Empirical evaluations on a diverse set of tasks
We extensively evaluate the proposed framework on a suite of tasks, covering a variety of models and datasets. On standard benchmark tasks for optimizer search, our method is able to discover optimizers that outperform its duman-designed and automatically searched counterparts. In addition, we also show that the proposed framework enables automated optimizer design for many other popular learning tasks, such as adversarial attack, GNN training, and BERT finetuning. Due to the space limits, we will include detailed descriptions, search settings, and discovered optimizers for each task in the Appendix.
4.1 General setting
MCT algorithm Across all experiments, we limit the maximum level MCT traversal to 4, and set the number of Monte Carlo samples to 32 (a multiple of 8 for parallelism 8-GPU servers) for each level. This amounts to a fixed total budget of 128 evaluations. The maximum depth for the super-tree is set to 10, which already covers many hop-performing optimizers for various tasks. We use a similar set of elementary operations as NOS-RL to build the optimizers, with only minor adjustments for some tasks (see Appendix for more details).
Optimizer evaluation We follow the default settings and hyperparameters for each task, and only swap out the optimizer; This potentially puts our algorithm at a disadvantage, as the hyperparameters usually tuned around the default optimizers. Before optimizer evaluation, we perform grid search

---

on small proxy task (fewer steps) to find proper learning rate. During the grid search, we also aggressively terminate optimizers if their performance falls under certain threshold. Since early stopped optimizers consume fewer resources than full evaluation, we do not count them into the budget (number of evaluations).
4.2 Hand-writter digit classification
Taving Irsjectryyy of IOEETTEEEO
LOTH 1220000
LSTP 8.260011
50B ream
MM2
SOD PRAT
Aeym
OOA SOw. screch
Nestow
AEWY
Sic2a
Stago
Figure 3: Training loss trajectory on hand-written digit classification task (log scaled). Each optimizer evaluated for 4 random seeds. Our method is marked in red.
We first compare our method with the LSTM-based optimizer (L2LGD2) on hand-writter digit classification. Following L22GGD2 [10 the goal is to minimize the cumulative training loss of a single-hidden
MLP with Sigmoid activation (MNISTNET) on the MNIST dataset; The search conducted on MNISTNET for 100 steps with a batch size of 128, and the discovered optimizers are subsequently transferred to three variants of MNISTNET with different activations (MNISTNET- ReLU),, number of hidden layers (MNISTNET-22 Leyya,,,,,,,, and dimensions (MNISTNET-Big) Under this setting, our method finishes in 0.92h on RTX 2080ti, much faster than L2LGG2 (2.62h).
As shown in Figure 3] our discovered optimizer achieves the lowest training loss under both direct search and transfer settings. Notable, the 1STM-based parametric update function indeed converges faster when the number of steps is close to the search phase (black-dotted vertical line on Figure 3). However, it extrapolates poorly to longer trajectories. As the training proceeds, all other non- parametric optimizers eventually catch-up, achieving much lower training loss. Moreover, LSTM- based optimizer also generalizes poorly to other model variants (most noticeably MNISTNET-ReLU) revealing its tendency overfit the search task.
4.3 Image classification with ConyNet
We proceed to evaluate our method the CIFAR-10 X classification task proposed in NOS-RL [15.. The model of choice is a 2-layer ConvNet. Each layer this network contains a 32-filter 3x3 convolution with ReLU activation and batch normalization. Following NOS-RL's setting, for every optimizer, the best learning rate is searched over a grid of (1e-5, 1e_ 1e-3, 1e_2, le 1, with epoch of training, and the discovered learning rate is subsequently used to train the model for longer period of time (5 epochs). Since NOS-RL's implementation is not open-sourced, we reproduce and compare with the two families of discovered optimizers described in NOS-RL paper: AddSign and PowSign.
The results summarized in Table For NOS-RL, display the performance of the top variants of PowSign and AddSign, which are obtained after training the controller for over 10k evaluations (Figure 4 in the NOS-RL paper [I3)). With only fraction (~1%) of the search budget, our framework is able to discover optimizers that reach a test accuracy of 77.02%, topping both PowSign and AddSign optimizers and also human-designed ones by sizable margin. The sheer reduction in search cost and the improvement in search performance evince the efficiency and effectiveness of the proposed framework for discovering better optimizers.
4.4 Adversarial attack
Next, we apply our framework to discover optimizers for constraint optimization. We select adver- sarial attack, which aims at finding norm-bounded perturbations in the input space that alter the model's 's predictions. The de facto optimizer used in adversarial attack is Projected Gradient Descent
7

---

Table Performance of automated search algorithms on CIFAR-10.
Test Accuracy
Search
Search Budget
Optimizer
(%)
Method
(#evaluations)
SGD
70.99% 2.12
manual
SGD + Momentum
74.12% + 0.44
manual
Nesterov
74.15% + 0.52
manual
Adam
73.42% 0.56
manual
RMSprup
71.42% 1.42
manual
PowSign-Id
75.48% + 0.45
RL on hand-crafted patterns
>10,000
PowSign-cd
76.21 0.16
RL on hand-crafted patterns
>10,000
AddSign-Id
75.54% 0.39
RL hand-crafted pattern spuce
>10,000
AddSign-cd
76.07% 0.59
RL hand-crufted pattern space
>10,000
Ours
77.02% + 0.19
MCT on super-trce space
128
(PGD) [2). We consider the most popular loo -nom setting. For lo -orm bounded attack, PGD takes the form of: x = (r.) + ysign( (rign((alla (vL(x)))),, where (x,) represents a e ball around the original image To w.r.t. nnrm.. The models of choice come from the Auto/ttack
library 46), which holds a leaderboard of top defense methods. Following their settings, we set
255, and run each optimizer once for 100 steps every image from the test split [46
On this task, we mainly search for the update rule inside the projection operator (e.g. sign() for PGD). The search is conducted on the pre- trained Carmon2019 model [ and the pro-
Table 2: Attack success rate of different optimizers on top defense methods on CIFAR-10.
Defense Models
PGD
APGD
Ours
Camon2019 (WRN:28 10)
37.83%
38.22%
38.35%
posed optimizer is subsequently evaluated on
Gowal2020' (WRN-70-16)
88
31.10%
32.00%
32.00%
other top defense methods for WideResNet [14]
Gowal2020 (WRN-34-20)
48
40.05%
40.46%
40.50%
(WRN-<depth>--wiitth) and ResNet (11) (RN-
Gowal2020- (WRN-28-100
33.65%
34.34%
Schwag202u (WRN-28-10)
XM
40.00%
40.43%
40.46%
<depth>). As shown in Table
discov-
Wu2020 (WRN-28-10) [5X]
36.41%
36. 36.70%
36.78%
ered optimizer consistently outperforms PGD
Wang (000:020000RN222..010
37.78%
16%
38.27%
by a sizable margin. Surprisingly, we found that the algorithm tends to pick loy(] 1) rather than sign(-) as the first operator, resulting in many log-base lageb optimizers that surpass sign-based PGD.
Engstrom2019 (RN-50)
31
47.76%
48, 48.25%
48.32%
Wong2020Fast (RN-18)
53.69%
54.11%
54.19%
Methods that explore extra data during robust training.
In addition to PGD, we also compare our log-based optimizer with the best handcrafted and tuned optimizer for adversarial attack: Adaptive PGD (APGD) [46;; The design of APGD is packed with domain expertises expertise: it combines a well-tuned momentum update rule with conditional learning rate
decay based on a handcrafted schedule and sophisticated decay conditions (see Appendix for details). However, the performance of our automatically discovered optimizer rivals APGD across various defense methods, despite of having a much simpler form (see Appendix for details). This result demonstrates the potential of applying our framework to reduce the need of human expertise in designing optimizers for diverse tasks.
4.5
Node classification on graphs
We next test framework for optimizing graph neural networks to classify nodes on graphs. The model of interest is Graph Attention Network (GAT) (11), one of the most widely used ar- chitectures in graph learning tasks. We com- pare our method against Adam [ the standard optimizer for optimizing GATs on five com- monly used graph datasets: OGBN-Product Cora Citeseer B PubMed d and PPI [
Table 3: Performance of our discovered optimizers against Adam on GATs on five commonly used Graph datasets of diverse size. Results that use the same GAT implementations are grouped together.
Dataset
Adam
Ours
Products
77.49% 1 0.56
80.15% 1 0.16
49
Cora
84.72% - 0.32
85.20% 1 0.19
Citeseer
71.70% 1.03
73.10% = 0.43
Among them, CGBN-Product is the largest in scale, consisting of 2,449,029 nodes. Since stan- dard GATs cannot scale to this dataset, we in- stead adopt an adaptation of cluster-GCN (28 to GAT as the testbed, termed Cluster-GATT Cluster-GAT trains standard GAT on smaller partitions of the original graph, thereby allow-
PubMed
78.20% + 0.22
79.25%
+ 0.70
PPI
97.53% - 0.45t
98.13% + 0.10
1 Our reproduced accuracy using ogbn- leaderboard's implementation is lower than the displayed number (79.23% + 0.78).
$ Fl Score
8

---

ing the model to be applied to large-scur scale graphs. We refer the reader to the Appendix for detailed deseriptions of all GAT implementations and experimental setups.
The results are summarized in Table On all datasets, our search algorithm is able to discover optimizers that outperform Adam. An interesting observation is that the top-performing optimizers discovered for this task almost always contain sign(-) operators, revealing the potential of adopting sign-based optimizers improve the training of graph neural networks.
4.6 BERT fine-tuning on NLP datasets
We also evaluate the proposed framework on BERT finetuning task on GLUE benchmark [25]. For this task, we follow all configurations of the Hugging- Face [56] implementations: we finetune a pretrained BERT (base cased) model for epochs on Cola 4 STS-B B [6 and RTE 7 dataset, and 5 epochs on
Table 4: Performance of our discovered opti- mizers for BERT finetuning on GLUE tasks.
Dataset
AdamW
Ours
Cola
59.56 + 2.04*
60.89 + 1.33"
MRPC
82.84 + 0.571
86.64
0.941
STS-B
87.80 + 1.14f
88,91 0.30
MRPC 5 and WNLI 25 dataset. The batch size is set to 32. We compare our discovered optimizers with the default A [9] shown Table I our automatically discovered optimizers outperform AdamW on all datasets.
RTE
65.97 = 1.56
68.50
1.931
WNLI
53.17 + 5.49
56.34 0.00
Mathews Correlation.
Spearman Correlation.
Accuracy (%)
Ablation study
In this section, we ablate the proposed framework using the MNISTNET task. All experiments repeated over random seeds to account for randomness the search phase.
Random search baseline We study the effectiveness of our MCT algorithm alone by comparing it with random sampling. Concretely, instead of traversing the tree based on MC scores, we randomly generate all optimizers from the root. Everything else in our framework remains un- changed, including our rejection sampling and equivalent- form detection techniques. This is equivalent to Random Search on our search space. As shown in Table 5 MCT algorithm outperforms Random Search baseline by sizable margin, showing that the Monte Carlo node scoring schema can indeed guide the traversal towards promising branches of the tree.
Table 5: Performance comparison of Random Search and MCT.
Method
Training Loss (sum)
Test Accuracy
Random MCT
60.25
1.33
59.25 + 2.50
89.43% + 0.85
Score thresholding As discussed in prior sections, score thresholding is important to the perfor- mance of the MCT algorithm. To verify this, we ablate this technique by disabling it in our framework while keeping everything else the same. Without score thresholding, the cumulative training loss of the proposed optimizers raises from 59.25 + 2.50 60.25 + 2.87, similar to that of random search.
Conclusion
Despite the recent advancement of practical AutoMI. systems in automatizing the design of architec- tures, data augmentation policies, and hyperparameters, progress in automated discovery of optimizers is still inadequate due to the limitations of prior methods in terms of 1). efficiency, 2). generalization, and 3). scalability. In this paper, we introduce the first optimizer search framework that meets all these criteria, allowing it to be directly applied to the tasks of interest. The proposed framework demonstrates promising results across a variety of tasks, from image classification, adversarial attack, to graph learning and BERT finetuning. Our method by-no-mean solves the optimizer search problem, as there is plenty of room for improvement on the algorithm and search space; Rather, our goal is to open up new possibility for future development in non-parametric optimizer search methods. We hope the proposed framework could democratize research and applications of automated optimizer search, and stimulate interest among researchers and practitioners.

---

7 Limitations
Our view of this work is starting point of efficient, scalable, and generalizable framework for optimizer search. And expect plenty of room for improvement for future works. For instance, we identify the following concrete limitations of the method:
1. We pre-computed momentum terms input to search space. This is practice borrowed from NOS-RL. Adding commonly used terms ease the job the search algorithm because it does not have to rediscover them from scratch every time. However, searching for novel momentum update rules could potentially help to find even stronger optimizers. In principle, framework allows it: can do this by inserting operator with its own internal state. This would serve as direction for future explorations.
2. Identifying proper hyperparameters for an optimizer is essentially for evaluation. In the current work, we use a simple grid search to discover the best learning rate for an optimizer: While works fine for our tasks, this could potentially suboptimal timate some optimizers. Leveraging advanced fast HPO during the search phase could be another direction to explore.
might underes-
3. Although our framework 100x faster than the comparable method (NOS-RL), still requires 128 evaluations in the search phase. These evaluations can be largely parallelized. But potentially, the efficiency can be improved further with better search algorithms, more train-free tests, knowledge transfer, e.t.c.
Reproducibility & ethics statements
Reproducibility We have specified the setup for ours experiments the main paper and Appendix, including settings for each task and hyperparameters for our method. The code and the optimizers found by our methods will also published on Github upon acceptance to encourage future development. Before then, copy of our code is included in the supplementary material for reference.
Ethics
We are not aware of any potential ethical concerns regarding our work.
Acknowledgments and Disclosure of Funding
This work is supported in part by NSF under ITS-20081 1100877 13, IIS-2048280, Okawa research grant and Google research scholar award.
10

---

References
[1] Miles Cranmer. Pysr: Fast & parallelized symbolic regression in python/julia, september 2020.
URL https://doi. org//0.528l/zenodo, 4052869.
[2] David Wolpert and William G Macready. No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 1(1):67-82, 1997.
[3] C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pages 89-98, 1998.
[4] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
[5] Bill Dolan and Chris Brockett. Automatically constructing a corpus of sentential paraphrases. In Third International Workshop on Paraphrasing (/WP2005), 2005.
[6] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
[7] Luisa Bentivogli, Peter Clark, Ido Dagan, and Danilo Giampiccolo. The fifth pascal recognizing textual entailment challenge. In TAC, 2009.
[8] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[9] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[10] 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. Advances in neural information processing systems, 29, 2016.
[11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[12] Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint arXiv:1606.018855, 2016.
[13] Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. arXiv preprint 1...v.1611.01855, 2016.
[14] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. 1rXiv:1605.07146, 2016.
arXiv preprint
[15] Irwan Bello, Barret Zoph, Vijay Vasudevan, and Quoc V Le. Neural optimizer search with reinforcement learning. In International Conference on Machine Learning, pages 459 468. PMLR, 2017.
[16] Daniel Cer, Mona Diab, Eneko Agirre, Inigo Lopez-Gazpin and Lucia Specia. Semeval-2011 task I: Semantic textual preprint 170..007700005. 2017.
and cross-lingual focused evaluation. arXiv
[17) Yutian Chen, Matthew W Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Timothy P Lillicrap, Matt Botvinick, and Nando Freitas. Learning to learn without gradient descent by gradient descent. In International Conference on Machine Learning, pages 748-756. PMLR, 2017.
[18] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[19] Uya Loshchilov and Frank Hutter. Decoupled weight decay regularization, arXiv preprint axX1v1171.051001, 2017.

---

[20] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.00 06083, 2017.
[21] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
[22] Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning, In ICLR, 2017.
[23] Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter optimization at scale. In International Conference on Machine Learning, pages 1437-1446. PMLR, 2018
[24] Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri. Houdini: Lifelong learning as program synthesis. Advances in Neural Information Processing Systems, 31, 2018.
[25] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In International Conference on Learning Representations, 2018.
[26] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprint arXiv:1812.09996. 2018.
[27] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang. Unlabeled data improves adversarial robustness. Advances in Neural Information Processing Systems, 32, 2019.
[28] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 257-266, 2019.
[29] Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four gpu hours. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1761-1770, 2019.
[30] Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar- Lezama. Write, execute, assess: Program synthesis with repl. Advances in Neural Information Processing Systems, 32, 2019.
[31] Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robust- ness (python library), 2019.
[32] Golnaz Ghiasi, Tsung- Yi Lin, and Quoe V Le. Nas-fpn: Learning scalable feature pyramid architecture for object detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7036-7045, 2019.
[33] Yufan Jiang, Chi Hu, Tong Xiao, Chunliang Zhang, and Jingbo Zhu. Improved differentiable architecture search for language modeling and named entity recognition. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 3585-3590, 2019.
[34] Jacob Devlin Ming-Was Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-IILT, pages 4171-4186, 2019.
[35] Guillaume Lample and François Charton. Deep learning for symbolic mathematics. In Interna- tional Conference on Learning Representations, 2019.
[36] Chuming Li, Xin Yuan, Chen Lin, Minghao Guo, Wei Wu, Junjie Yan, and Wanli Ouyang. Am- Ifs: Automl for loss function search. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 8419, 2019.
12

---

[37] Sungbin Lim, Ildoo Kim, Taesup Kim, Chiheon Kim, and Sungwoong Kim. Fast autoaugment. Advances in Neural Information Processing Systems, 32, 2019.
[38] Chenxi Liu, Liang-Chiele Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L Yuille, and Li Fei-Fei. Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation. Pruceedings of the IEEE/CVF conference on computer vision and puttern recognition, pages 82-92, 2019.
[39] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Autoaugment: Learning augmentation policies from data. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019.
[40] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019.
[41] Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstee Understanding and correcting pathologies in the training of learned optimizers. In International Conference on Machine Learning, pages 4556-4565. PMLR, 2019.
[42] Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. International Conference on Learning Representations, 2019.
[43] Alex Warstadt, Amanpreet Singh, and Samuel R Bowman. Neural network acceptability judgments. Transactions of the Association for Computational Linguistics, 7:625-641. 641, 2019.
[44] Daoyuan Chen, Yaliang Li, Minghui Qiu, Zhen Wang, Bofang Li, Bolin Ding, Hongbo Deng, Jun Huang, Wei Lin, and Jingren Zhou. Adabert: Task-adaptive bert compression with differentiable neural architecture search. arXiv preprint 2xXi::2001.04246, 2020.
[45] Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: standardized adversarial robustness benchmark. arxiv preprint arXiv:2010.099: 09670, 2020.
[46] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In ICML, 2020.
[47] Lukasz Dudziak, Thomas Chau, Mohamed S. Abdelfattah, Royson Lee, Hyeji Kim, and Nicholas D. Lane. Brp-nas: Prediction-basse nas using gens. In NeurlPS, 2020.
[48] Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arXiv:2010.03593 2020.
[49] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 222133, 2020.
[50] Abhinav Mehrotra, Alberto Gil CP Ramos, Sourav Bhattacharya, Lukasz Dudziak, Ravichander Vipperla, Thomas Chau, Mohamed S Abdelfattah, Samin Ishtiaq, and Nicholas Donald Lane. aas-bench-asr: Reproducible neural architecture search for speech recognition. In International Conference on Learning Representations, 2020.
[51] Esteban Real, Chen Liang, David So, and Quoc Le. Automl-zero Evolving machine learning algorithms from scratch. In International Conference on Machine Learning, pages 8007-8019. PMLR, 2020.
[52] Vikash Sehwag, Shiqi Wang, Prateck Mittal, and Suman Jana. Hydra: Pruning adversarially robust neural networks. Advances Neural Information Processing Systems, 33:19655-19966 19666, 2020.
[53] Ameesh Shah, Eric Zhan, Jennifer Sun, Abhinav Verma, Yisong Yue, and Swarat Chaud- huri. Learning differentiable programs with admissible neural heuristics. Advances in neural information processing systems, 33:4940-4952, 2020.
13

---

[54] Silviu-Marian Udrescu and Max Tegmark. Ai feymman: A poysics-inspiree method for symbolic regression. Science Advances, 6116)eaay2631, 2020.
[55] Ruochen Wang, Minhao Cheng, Xiangning Chen, Xiaocheng Tang, and Cho-Jui Hsieh. Re- thinking architecture selection in differentiable nas. In International Conference on Learning Representations, 2020.
[56] Thomas Wolf. Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the- art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38 45, Online, October 2020. Association for Computational Linguistics.
[57] Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint arXiv:2001.03000 2020.
[58] Dongxian Wu, Shu-Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust generalization. In NeurlPS, 2020.
[59] Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: A primer and a benchmark. arXiv preprint arXiv:2103. /2828, 2021.
[60] Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsich. DrNAS: Dirichlet neural architecture search. In ICLR, 2021.
[61] Guofeng Cui and He Zhu. Differentiable synthesis of program architectures. Advances in Neural Information Processing Systems, 34, 2021.
[62] Shoukang Hu, Ruochen Wang, HONG Lanqing, Zhenguo Li, Cho-Jui Hsieh, and Jiashi Feng. Generalizing few-shot nas with gradient matching. In International Conference on Learning Representations, 2021.
[63] Mikel Landajuela, Brenden K Petersen, Sookyung Kim, Claudio P Santiago, Ruben Glatt, Nathan Mundhenk, Jacob Pettit, and Daniel Faissol. Discovering symbolic policies with deep reinforcement learning. In International Conference on Machine Learning, pages 5979-5999 PMLR, 2021.
[64] Brenden K Petersen, Mikel Landajuela, T Nathan Mundhenk, Claudio P Santiago, Soo K Kim, and Joanne T Kim. Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients. In Proc. of the International Conference on Learning Representations, 2021.
[65] Nicholas Roberts, Mikhail Khodak, Tri Dao, Liam Li, Christopher Ré, and Ameet Talwalkar. Rethinking neural operations for diverse tasks. Advances in Neural Information Processing Systems, 34, 2021.
[66] Paul Vicol, Luke Metz, and Jascha Sohl-Dickstein. Unbiased gradient estimation in unrolled computation graphs with persistent evolution strategies. In International Conference on Machine Learning, pages 10553-10563. PMLR, 2021.
[67] Ruochen Wang, Xiangning Chen, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. RANK- NOSH: Efficient predictor-based architecture search via non-uniform successive halving. In ICCV, 2021.
[68] Wenqing Zheng, Tianlong Chen, Ting-Kuei Hu, and Zhangyang Wang. Symbolic learning to optimize: Towards interpretability and scalability. In International Conference on Learning Representations, 2021.
[69] Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Yao Liu, Kaiyuan Wang, Cho-Jui Hsieh, Yifeng Lu, and Quoe V Le. Evolved optimizer for visio. In AutoMI. 2022 Workshop, 2022.
[70] Yu A Shreider. The Monte Carlo method: the method of statistical trials, volume 87, Elsevier, 2014.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section g
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We are not aware of any negative societal impacts of this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Due to space limits, some of these training details are included in the Appendix
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] The error bars for all optimizers are shown in the main text. The only exception is MNISTNET task, where we removed error bar for a cleaner plot. We will display the error bar for this task in the Appendix.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "yde0QRJ33m7", "reviewer": "Reviewer_8MmY", "summary": "This paper presents an approach to learning to optimize (L2O) in which the goal is to automatically configure the best gradient update rule.", "questions": "- maybe I overlooked this, but do you have an example/reference that gives clear evidence for different tasks that have different best optimizers? Which datasets, for which learners, and which are the optimal optimizers, and what is the difference in performance/time?\n- how are the L2O and essential optimization phases connected? Do you select a different update rule based on the MCT approach each time?\n- what is generability?", "limitations": "The authors do not discuss limitations. There is such a section and gladly the authors recognize that they have not solved the whole problem yet, but no concrete limitations are mentioned.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of the paper is that it addresses a relevant problem and that it mostly discusses well the related work.\n\nMy major concern is the soundness and clarity of the paper. To me it did not become clear when the optimization happens? Is this an online procedure that updates the update rule over time? It does not become clear enough how the MCT approach is interleaved/connected to the essential optimization process. Without this, it is hard to judge on the rest, and I would make my final assessment dependent on how this is clarified.", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "VaHxTshByCO", "reviewer": "Reviewer_d4Bz", "summary": "This paper designs a new search space over optimizers and a search algorithm combining rejection sampling with Monte Carlo search. They evaluate the optimizer search on image classification, adversarial attacks, training GNNs, and BERT fine-tuning.", "questions": "Notes:\n- 38: generability -> generalization\n- 137: m_1 is a gradient, not a state vector?\n- 173: do you have a citation for this claim about NAS? also in regular hyperparameter optimization my experience is that many configurations are poor\n- Figure 2: Side-by-side columns might be more clear than overlapping.", "limitations": "There was no real discussion of specific limitations in the “Conclusion and Limitations” section, only the acknowledgment that the paper does not solve everything.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Post-Rebuttal:** The authors answered my questions largely satisfactorily. Under the assumption that the new comparisons to regular HPO baselines and more careful discussion of the limitations of the search space (preferably in the main text for the latter if given extra space) are included in the revision I believe this paper should be accepted and have raised my score.\n\nSummary: \nThis submission is cleanly formulated, fairly easy-to-read, and has a rather extensive evaluation. However, in the weaknesses I have listed concerns, especially about the automation, budgeting, and task selection, that make me hesitant to give it a stronger score. \n\nStrengths:\n1. The construction of the search space seems novel and improves upon past constructions like NOS-RL in terms of representation efficiency.\n2. Code is released and extensive experimental details are provided.\n3. The paper is clear and fairly straightforward to read, although terse in parts.\n4. The optimization procedure is evaluated on a diverse set of deep learning tasks.\n\nWeaknesses:\n1. The search procedure comes with its own hyperparameters. Rejection sampling, score thresholding, and depth all require tuning and how the levels were chosen is not explained\n2. The full pipeline is not truly automated, as for individual tasks the initial grid search for the step-size uses a different grid over learning rates. Given how cheap it is, it is unclear to me why not use the same one for all of them.\n3. The overall search budget is somewhat opaque to me. In Section 4.1 the number of evaluations is fixed at 128. How much more expensive is this than just running SGD on a deep net on different tasks? Full-pipeline time comparisons would be very useful here. My rough estimation is that the proposed procedure takes 32x the amount of time to train a deep net. How does this compare if a regular parallel hyperparameter tuner such as ASHA (Li et al., 2018) is given the same budget but tunes only SGD/Adam?\n4. It is unclear if the proposed search space could actually discover stateful optimizers such as Adam if they were not explicitly included. The paper uses Adam as an example frequently, but could the momentum terms actually be discovered by such a system from elementary operations (adds, sorts, etc.)?\n5. A common difficulty with AutoML papers is guaranteeing that the results are indeed evaluated on a representative set of tasks, without arbitrary exclusions. For example, for the GLUE benchmark, why are only five of the nine tasks evaluated? For CNN training, why was only image classification looked at? \n\nReferences:\n1. Li, Jamieson, Rostamizadeh, Gonna, Ben-Tzur, Hardt, Recht, Talwalkar. A system for massively parallel hyperparameter tuning. MLSys 2020.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QEKUvfx-04z", "reviewer": "Reviewer_deaa", "summary": "The paper tackles the problem of automatic optimizer search with a focus on deep learning problems.\nThe authors define a set of math operators, frame the problem as a tree-based path search and apply Monte-Carlo sampling to find an optimizer. Experiments on a diverse set of tasks shows that the proposed method outperforms a number of baselines.", "questions": "A few more questions (in addition to the novelty one from the previous section):\n\nLine 224: How is the probing vector selected for different domains? Testing the equvalence of expressions based on only one vector might produce many false positives. How would it affect the perfromance of the method?\n\nLine 278: What would be the authors guidlines on selecting the set of operators for a general task, if this set has to be adjusted from task to task? Does it mean that \"On-the-fly constraint tree-traversal\" and other heuristics will have to be adjusted as well?\n\nLine 397: How is score thresholding defined from task to task? is the same threshold used for every task?\n\nFigure 3 of experiments: Could the authors elaborate on the stability of found optimizers compared to other methods? For example, some error bars could help here, since the results are averaged only over 4 seeds.", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Post-rebuttal:\n\nI would like to thank the authors for their effort answering my questions.\nThe authors satisfactory resolved most of my concerns, so I am happy to increase my score to 6.\n_______________\nThe paper is well-written and easy to follow. The problem and solution are well-defined. The experiments are comprehensive and cover a large number of relevant tasks/problems.\n\nMy main concern is about the novelty of the work. The problem of automatically selecting an optimizer is not novel as outlined in the relevant work section. The closest competitor NOS-RL already frames the problem as a search on mathematical operators (and uses a similar set of basic operators). While I do agree that the proposed method is significantly more efficient than NOS-RL, it appears that the main novelty of the paper comparing to NOS-RL is plugging a more efficient data structure and applying Monte-Carlo on it (which as not a novel technique by itself). That makes the overall contribution of the paper quite incremental. I would appreciate if authors would elaborate a bit more on the novelty of their work.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept