Convergence Rate Analysis of LION

Yiming Dong, Huan Li, Zhouchen Lin

Abstract

The LION (evoLved sIgn mOmeNtum) optimizer, discovered via automated program search, has demonstrated remarkable empirical performance in training large-scale neural networks. Despite its popularity, a rigorous understanding of its convergence properties—specifically its convergence rate—has remained elusive. This paper provides a comprehensive analysis of LION, establishing its convergence to the Karush-Kuhn-Tucker (KKT) point in constrained settings and to critical points in unconstrained settings. We prove that LION achieves a convergence rate of $O(\sqrt{d}K^{-1/4})$ measured by the gradient $\ell_1$ norm, where $d$ is the problem dimension and $K$ is the number of iterations. This rate matches the theoretical lower bound for nonconvex stochastic optimization, positioning LION as a mathematically principled and highly efficient alternative to traditional human-designed optimizers.

Introduction

In the landscape of deep learning, optimization algorithms like SGD and Adam have long been the standard. However, the discovery of LION (evoLved sIgn mOmeNtum) by Google through evolutionary program search introduced a paradigm shift. LION utilizes a simple sign-based update rule that, while computationally efficient, lacks the intuitive derivation of its predecessors. While initial empirical results were impressive, the theoretical community lacked a precise convergence rate that accounted for both dimensionality ($d$) and iteration count ($K$). This research bridges that gap, moving LION from a successful heuristic to a mathematically grounded algorithm with proven efficiency.

Theoretical Framework

Constrained and Unconstrained Analysis

The authors analyze LION's update rule, which prioritizes the sign of the momentum over the magnitude of the gradient. The analysis is conducted in two primary stages:

  1. Constrained Optimization: LION is first modeled as solving a problem with "box constraints." In this setting, the authors prove convergence to a KKT point at a rate of $O(\sqrt{d}K^{-1/4})$ using the $\ell_1$ norm of the gradient.
  2. Unconstrained Optimization: To extend this to general deep learning tasks, the authors introduce the assumption of coerciveness—the property where the loss function approaches infinity as parameters do. This is a common characteristic in models utilizing weight decay. Under this assumption, LION is shown to converge to a stationary point at the same optimal rate.

The $\ell_1$ Norm and Dimensionality

Because LION’s update is based on the sign operation, the standard $\ell_2$ (Euclidean) norm is less suitable for analysis. The authors instead utilize the $\ell_1$ norm (the sum of absolute values). This choice reveals that LION’s dependence on the dimension $d$ is optimal. To reconcile this with standard optimization theory, which typically uses $\ell_2$ lower bounds ($\Omega(K^{-1/4})$), the authors establish an "empirical bridge." They demonstrate that the ratio between the gradient's $\ell_1$ and $\ell_2$ norms scales as $\Theta(\sqrt{d})$, ensuring that LION’s performance aligns with the theoretical limits of stochastic optimization.

Experimental Validation

The theoretical findings were validated through extensive testing across diverse architectures and datasets:

  • Computer Vision: Experiments on CIFAR-10, CIFAR-100, and ImageNet-1K using ResNet18, ResNet50, and ViT-S. In CIFAR-100 tests, LION consistently outperformed SGD, with ResNet18 reaching ~75% Top-1 accuracy compared to SGD's ~70% within the same 100-epoch window.
  • Language Modeling: BERT and GPT-2 models were trained from scratch on OpenWebText. LION achieved significantly lower training and test loss than SGD across all model sizes.
  • Generalization: Zero-shot perplexity tests on WikiText-103 showed that GPT-2 models trained with LION surpassed the final results of SGD-trained models within the first 10,000 steps, indicating superior generalization speed.

Key Insights

  • Optimal Convergence: LION's rate of $O(\sqrt{d}K^{-1/4})$ is not just a theoretical curiosity; it matches the known lower bounds for nonconvex stochastic optimization regarding iterations $K$.
  • Empirical Consistency: The predicted $\Theta(\sqrt{d})$ relationship between $\ell_1$ and $\ell_2$ norms was confirmed across every experimental model, from small ResNets to large Transformers, validating the theoretical assumptions.
  • Practical Superiority: While SGD is often cited as the gold standard for matching theoretical bounds, LION achieves the same theoretical rate while delivering superior training efficiency and higher test accuracy in practice.

Conclusion and Future Work

This work establishes LION as a theoretically robust optimizer for high-dimensional nonconvex problems. However, some avenues for future research remain. The unconstrained proof relies on the coerciveness of the objective function, which may not apply to every specialized loss function. Additionally, while the analysis uses specific schedules for hyperparameters like $\beta_1, \beta_2,$ and $\eta$, practical applications often use constant values. Bridging the gap between these theoretical schedules and practical implementations remains an open challenge for the optimization community.

Summary updated

Abstract

The LION (evoLved sIgn mOmeNtum) optimizer for deep neural network training was found by Google via program search, with the simple sign update yet showing impressive performance in training large scale networks. Although previous studies have investigated its convergence properties, a comprehensive analysis, especially the convergence rate, is still desirable. Recognizing that LION can be regarded as solving a specific constrained problem, this paper focuses on demonstrating its convergence to the Karush-Kuhn-Tucker (KKT) point at the rate of $\cal O(\sqrt{d}K^{-1/4})$ measured by gradient $\ell_1$ norm, where $d$ is the problem dimension and $K$ is the number of iteration steps. Step further, we remove the constraint and establish that LION converges to the critical point of the general unconstrained problem at the same rate. This rate not only delivers the currently optimal dependence on the problem dimension $d$ but also tightly matches the theoretical lower bound for nonconvex stochastic optimization algorithms, which is typically measured using the gradient $\ell_2$ norm, with respect to the number of iterations $K$. Through extensive experiments, we not only demonstrate that LION achieves lower loss and higher performance compared to standard SGD, but also empirically confirm that the gradient $\ell_1/\ell_2$ norm ratio aligns with $\Theta(\sqrt{d})$, thus proving that our convergence rate matches the theoretical lower bound with respect to $d$ in the empirical sense.
BibTeX
@misc{dong2024convergence,
  author = {Yiming Dong and Huan Li and Zhouchen Lin},
  title = {{Convergence Rate Analysis of LION}},
  year = {2024},
  eprint = {2411.07724},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.07724},
}
Figure