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