Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper tackles the problem of automatic optimizer search with a focus on deep learning problems.
The 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.
strengths_and_weaknesses: Post-rebuttal:

I would like to thank the authors for their effort answering my questions.
The authors satisfactory resolved most of my concerns, so I am happy to increase my score to 6.
_______________
The 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.

My 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.

questions: A few more questions (in addition to the novelty one from the previous section):

Line 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?

Line 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?

Line 397: How is score thresholding defined from task to task? is the same threshold used for every task?

Figure 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: -
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper presents an approach to learning to optimize (L2O) in which the goal is to automatically configure the best gradient update rule.
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.

My 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.
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?
- how are the L2O and essential optimization phases connected? Do you select a different update rule based on the MCT approach each time?
- 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

Summary: 
This 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. 

Strengths:
1. The construction of the search space seems novel and improves upon past constructions like NOS-RL in terms of representation efficiency.
2. Code is released and extensive experimental details are provided.
3. The paper is clear and fairly straightforward to read, although terse in parts.
4. The optimization procedure is evaluated on a diverse set of deep learning tasks.

Weaknesses:
1. 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
2. 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.
3. 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?
4. 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.)?
5. 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? 

References:
1. Li, Jamieson, Rostamizadeh, Gonna, Ben-Tzur, Hardt, Recht, Talwalkar. A system for massively parallel hyperparameter tuning. MLSys 2020.
questions: Notes:
- 38: generability -> generalization
- 137: m_1 is a gradient, not a state vector?
- 173: do you have a citation for this claim about NAS? also in regular hyperparameter optimization my experience is that many configurations are poor
- 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.
review_title: null

Meta-review: metareview: Two of the reviewers were positive on this paper and thought the work would be of interest to the community.  One reviewer felt the paper lacked clarity, but the other reviewers disagreed.  I think there will be interest in the optimizer search for deep learning that this paper presents and feel it should appear in NeurIPS.
confidence: Certain
Decision: Accept