Symbolic Discovery of Optimization Algorithms

We present a method to formulate algorithm discovery as program search, and apply it to discover optimization algorithms for deep neural network training. We leverage efficient search techniques to explore an infinite and sparse program space. To bridge the large generalization gap between proxy and target tasks, we also introduce program selection and simplification strategies. Our method discovers a simple and effective optimization algorithm, $\textbf{Lion}$ ($\textit{Evo$\textbf{L}$ved S$\textbf{i}$gn M$\textbf{o}$me$\textbf{n}$tum}$). It is more memory-efficient than Adam as it only keeps track of the momentum. Different from adaptive optimizers, its update has the same magnitude for each parameter calculated through the sign operation. We compare Lion with widely used optimizers, such as Adam and Adafactor, for training a variety of models on different tasks. On image classification, Lion boosts the accuracy of ViT by up to 2% on ImageNet and saves up to 5x the pre-training compute on JFT. On vision-language contrastive learning, we achieve 88.3% $\textit{zero-shot}$ and 91.1% $\textit{fine-tuning}$ accuracy on ImageNet, surpassing the previous best results by 2% and 0.1%, respectively. On diffusion models, Lion outperforms Adam by achieving a better FID score and reducing the training compute by up to 2.3x. For autoregressive, masked language modeling, and fine-tuning, Lion exhibits a similar or better performance compared to Adam. Our analysis of Lion reveals that its performance gain grows with the training batch size. It also requires a smaller learning rate than Adam due to the larger norm of the update produced by the sign function. Additionally, we examine the limitations of Lion and identify scenarios where its improvements are small or not statistically significant. Lion is also successfully deployed in production systems such as Google search ads CTR model.

Paper

Similar papers

Peer review

Reviewer Y4eN6/10 · confidence 5/52023-07-05

Summary

The paper introduces Lion, an automatic search strategy for deep learning optimizers. The paper claims that the resulting optimizer is more compute efficient than the baselines and achieves better accuracy on a variety of tasks from vision and language and model architectures. The search uses an evolutionary algorithm initialized wih AdamW that gradually mutates a population of optimizers and contains several additional strategies to increase search efficiency eg the removal of redundant instructions and a hash-based caching as well as funnel selection to mitigate overfitting on the proxy task. The standout discovery of the Lion optimizer is the use of a sign function in combination with a specific momentum strategy. Throughout their experiments, the authors demonstrate significant improvements, especially on larger architectures with large datasets.

Strengths

- The evaluation is very thorough. The authors include several vision and language models, contrastive learning as well as diffusion models. Throughout the experiments on Transformer models, I found the results to be a significant improvement over AdamW, especially since there has not really been a significant upgrade to AdamW in recent years. I am not fully convinced by the results on ResNets and I also think that it would have been better to have a larger selection of convolutional neural networks. But given the importance of transformers in ML, I think this is still a good result. - In general, I find the idea of the paper to automatically search for an optimizer to be relevant. - The presentation is clear overall.

Weaknesses

- I think the contribution is mostly technical and seems mostly like an engineering effort as the actual search strategy seems relatively simple. For me, the results are still interesting enough for acceptance. - There is no code available and a lot of experiments are done on Google internal datasets such as JFT and the Imagen dataset which makes it impossible to reproduce a lot of the results in the paper. I could also not find any search hyperparameters in the appendix, eg learning rate used during the search. - The search method still produces quite a lot of unnecessary statements that need to be manually removed to arrive at the final program. While I understand the complexity of the task, I would still prefer a method that produces cleaner code automatically. Being able to produce simplified optimizers during training might even improve results, for example, what would happen if one would start the search again starting at the Lion optimizer instead of AdamW.

Questions

- Program 4 is an automatic simplification of Program 8. However, the authors further do manual simplifications to arrive at the final optimizer in program 1. I understand that the sign simplification (from the code in red) might be hard to automatically find, however, the method also includes a step to remove statements with minimal effect. Why does this removal step not remove the arcsin and clip functions if the authors manually found that their removal does not cause a quality drop? - The authors discuss that Lion needs a smaller learning rate due to the sign operation compared to AdamW. How does this lr compare to the one used during the search? Did you use a small learning rate during the search which might bias the search towards the sign operation or does the search actually find an optimizer that is optimal for a learning rate that is orders of magnitude smaller than the one used during the search process? In the second case, do you think that searching with a smaller lr might influence the results? - Would it be possible to do a similar search for a second-order method, eg initialized with Newton's method or do you think the additional complexity of the hessian integration would make the search space too complex?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

On some tasks, the improvements are rather minimal. Also, the set of instructions is rather limited and does not allow for complex structures like for-loops. All significant limitations are addressed by the authors in the Appendix.

Reviewer weMp6/10 · confidence 3/52023-07-06

Summary

This paper proposes to formulate algorithm discovery as program search and discover optimization algorithms for deep neural network training. To bridge the large generalization gap between proxy and target tasks, the authors introduce program selection and simplification strategies. The proposed method discovers a simple and effective optimization algorithm called Lion, which is more memory-efficient than Adam as it only keeps track of the momentum. Lion is compared with widely used optimizers, such as Adam and Adafactor, for training a variety of models on different tasks. Empirical results demonstrate that Lion significantly outperforms these optimizers. The authors also examine the limitations of Lion and identify scenarios where its improvements are small or not statistically significant.

Strengths

- The proposed method is clear and easy to understand - Empirical results are very sufficient to demonstrate the superiority of proposed method

Weaknesses

- The computation resources required by the proposed search method is unaffordable for most research groups - Theoretical analysis is missing in this work

Questions

Despite its sound empirical performances, I would also like to see some theoretical analysis on the searched Lion optimizer. How it can converge under which conditions? The authors may consider referring to [7] and see if similar convergence results can be obtained.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I suppose the key limitation of this work is its huge demand on computation power. For most research groups, the value of this work is solely the Lion optimizer (which is rather simple) instead of the search method, though it is certainly good to see some new optimizers no matter how they are found (by human or by machine).

Reviewer Gizf6/10 · confidence 4/52023-07-06

Summary

In this paper, a new optimizer is designed by program search. The search process overcomes the problem of distribution differences for small data set proxies and large tasks. The new optimizer converges faster and at the same time has strong generalization over a wide range of models for different tasks.

Strengths

1. Apply the idea of program search of AutoML-Zero to the field of optimizer design. Efficient and highly generalized optimizers are designed. 2. Solved the problem of complex and sparse search space by abstract execution pruning, warm-start and proxy task. 3. solved the problem of distribution difference between proxy tasks and larger tasks by funnel selection. 4. Sufficient experiments. The experiments include the validation of extensive models on different tasks.

Weaknesses

1. The original algorithm obtained from the search is still more complex. It needs expert knowledge and labor cost for simplification. See the simplification of Program 4 to Program 1 for details. 2. No specific validation experiments or theoretical analysis of the high memory efficiency of Lion compared to adam. It is only outlined at L233-L239. The authors can use some metrics, such as memory peaks, to compare the memory footprint of different optimizers. 3. The design for the search space is heuristic. In some places, the authors just make statements about the approach, which makes it difficult to understand. For example, the last of the three forms of mutation. Why is the hyperparameter in the statement modified instead of replacing the statement itself?

Questions

See weaknesses.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations have been well discussed

Reviewer hEv66/10 · confidence 5/52023-07-26

Summary

Summary: The authors' work undoubtedly stands as an exceptional and noteworthy contribution to the field, showcasing a plethora of remarkable achievements that have the potential to significantly influence and shape the landscape of optimization and extend their impact well beyond its boundaries. As I delve into the intricacies of their research, it becomes evident that their dedication and innovative approach have yielded results that are both impressive and promising. However, amidst the numerous commendable aspects of their study, there also exist certain primary concerns that warrant attention and resolution. While I acknowledge the impressive strides made by the authors, it is essential to critically address certain aspects that could further enhance the credibility and applicability of their findings. In the following detailed comments, I will highlight specific areas that require closer scrutiny, offering constructive feedback and suggestions to fortify the integrity and comprehensiveness of their research.

Strengths

I am elated to express my joy and satisfaction upon the efficiency of the authors' method has transcended that of the renowned Adam optimizer, exhibiting its superiority across various tasks. This notable achievement undoubtedly highlights the ingenuity and prowess of the authors in devising such a remarkable approach. The profound impact of their work is vividly demonstrated through the astonishing results presented in Table 1 and Figure 1, which undoubtedly leave one in awe. In particular, the Discovered optimizer, aptly named "Lion," showcased in Program 1, stands as a testament to the authors' ability to craft a solution that is both simplistic and elegant, evoking admiration from peers and fellow researchers alike. Moreover, the decision made by the authors to simplify Program 4 and refine it into the more efficient Program 1 is not only logical but also reinforces the practicality of their approach. This thoughtful choice not only streamlines the methodology but also adds to the elegance and cohesiveness of their research. In their diligent pursuit of showcasing the sparsity of the high-performance optimizer, the authors undertook a remarkably extensive and rigorous experimental endeavor, involving the execution of a staggering 2 million randomly selected programs. With meticulous precision and analytical acumen, they thoroughly assessed the performance of each program, leaving no stone unturned in their quest for a superior alternative to AdamW. Upon meticulously scrutinizing the results obtained from this monumental experiment, the authors arrived at a rather intriguing and significant revelation: none of the 2 million randomly selected programs exhibited a performance that surpassed the prowess of AdamW. This particular finding stands as a testament to the exceptional capabilities and efficiency of AdamW as a high-performance optimizer, solidifying its position as a prominent and leading choice in the optimization landscape. The sheer scale and comprehensiveness of this experimental undertaking are truly commendable, underscoring the authors' unwavering commitment to pursuing scientific rigor and thoroughness. Their methodical approach and the impressive volume of data analyzed serve as an invaluable resource for the scientific community, contributing to a deeper understanding of optimizer performance and fostering future advancements in the realm of optimization algorithms. The authors' insightful use of meta-validation to select programs with superior generalization ability is indeed a reasonable and effective approach. Especially noteworthy is their ingenious technique of progressively increasing the complexity of the meta-validation task, aptly termed "Funnel selection." This strategic refinement undoubtedly enhances the efficiency of the selection process, allowing for the identification of programs with enhanced generalization capabilities. Additionally, the thoughtful incorporation of sign updates and regularization is highly justified, especially when considering the context of adversarial attacks, where techniques like L_inf PGD attacks often rely on such sign update mechanisms. In fact, sign updates have also been previously employed as optimizers in prior works. Undoubtedly, the analysis presented in Section 3.2 is both captivating and intellectually stimulating, offering valuable insights that resonate with the broader research community. The robustness and trustworthiness of these findings are indeed commendable and a testament to the authors' thoroughness in their investigations. One fascinating observation that delights me is the correlation between model size and Lion's validation accuracy. The authors' remark on the positive relationship between increased model size and enhanced validation accuracy raises intriguing possibilities. The plausible explanation that the sign update technique increases uncertainty and ultimately improves the model's generalization ability opens exciting avenues for future research.

Weaknesses

While their research presents impressive insights and advancements, it is essential to address one concern that arises from the potential handcrafted nature of the simplification and derivation process for the programs. A more elegant solution would involve automating this process as an inherent aspect of defining the search space, further enhancing the overall methodology and augmenting its potential impact. Sign updates have also been previously employed as optimizers in prior works. It is worth kindly noting that, when the proposed method is combined with more potent data augmentations, the relative performance gains might appear less pronounced. This insightful observation highlights the need for further exploration and optimization to fully unlock the method's potential under varying experimental conditions. While considering this aspect, I must admit that I personally feel a bit disappointed. I am genuinely interested in exploring the application of the Lion algorithm to the domain of Stable Diffusion. It is pertinent to acknowledge that training stable diffusion models can be an extremely resource-intensive endeavor, often incurring substantial costs (for instance, approximately 1 million dollars for stable diffusion v1). Given this context, the potential of the proposed Lion method to be utilized in conjunction with stable diffusion holds tremendous appeal and significance. If the Lion algorithm proves to be compatible with stable diffusion models, it would indeed be a highly advantageous and desirable outcome. The ability to leverage the proposed method's capabilities in optimizing stable diffusion models could potentially mitigate the significant expenses associated with their training, thereby opening up new avenues for research and applications in this area. The prospect of such synergy between Lion and Stable Diffusion sparks a sense of optimism and excitement, as it has the potential to drive transformative advancements in the field. As such, I eagerly look forward to any insights or findings that may shed light on the feasibility and practicality of applying the Lion algorithm to the challenging task of stable diffusion, as this would undoubtedly represent a valuable and impactful contribution to the scientific community. One of the concerns in the field of AutoML revolves around the efficacy of the search process, causing a great deal of apprehension among researchers and practitioners. More precisely, a central aspect of this concern is rooted in the correlation between the performance exhibited by programs during the search phase, specifically on the small proxy, and their subsequent performance on the final task. This particular correlation is viewed with heightened attention, as it holds significant implications for the overall effectiveness of the AutoML approach. For instance, in the context of Neural Architecture Search (NAS), where the exploration of different architectural configurations plays a crucial role in achieving optimal results, there is a palpable sense of unease regarding architecture ranking. How well a particular architecture performs on the small proxy tasks might not always be indicative of its actual performance when applied to more extensive and state-of-the-art tasks, and thus, researchers seek to establish a robust link between the two domains. In attempts to address this pressing concern, the authors of the present paper have diligently employed a comprehensive set of measures. Their goal is to carefully select algorithms that can demonstrate a remarkable ability to generalize from small proxy tasks to larger and more complex real-world tasks, thereby enhancing the reliability and applicability of the AutoML approach. However, despite the earnest efforts made by the authors, there remains a notable omission in their work. They have not provided a quantitative analysis that establishes the explicit correlation between the performance achieved on the small proxy tasks and the corresponding performance on the final, real-world tasks. This apparent absence of a rigorous and quantitative examination is indeed regrettable, as such analytical insights are vital for instilling greater confidence in the effectiveness and reliability of the proposed AutoML techniques. In conclusion, while significant strides have been taken in addressing concerns regarding the search effectiveness in AutoML, the lack of a robust quantitative analysis linking the performance between the small proxy and the final tasks leaves a critical aspect unanswered. Efforts to bridge this analytical gap would undoubtedly enhance the overall understanding and trustworthiness of the AutoML methodologies employed.

Questions

See *Weaknesses.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No. See *Weaknesses.

Area Chair 156V2023-08-21

Message from AC

Dear Authors, Thanks for your responses to the reviews. I wanted to let you know that even tho not all the reviewers directly responded, your rebuttal will be accounted for during the final decision stage. Best, Your AC

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC