Overview

Sign-based optimization replaces gradient magnitudes with coordinate-wise signs, as in signSGD and Lion, to reduce optimizer memory or communication. Methods add momentum, smooth or stochastic sign transformations, error feedback, adaptive step sizes, and matrix-aware spectral directions such as Muon. Theory studies convergence under different noise, smoothness, and data-geometry assumptions, while experiments test vision models, distributed training, and large language model pretraining. The central tension is that signs can be efficient and robust to some forms of imbalance or sparse noise, but discarding magnitude can hurt stability or convergence when parameters have heterogeneous scales or data is anisotropic.

Latest papers

33 papers3 papers in the last four weeks, down 57% on the four weeks before. 0.0% of all new papers.

Nov 30, 2025

Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance

Adaptive and non-Euclidean optimizers often outperform Euclidean methods such as stochastic gradient descent (SGD) in language modeling by a large margin. Existing theory usually explains this gap by assuming favorable smoothness geometry or noise structure tailored to the specific optimizer. We instead ask whether such geometry can be induced from a concrete learning setting. Starting from an optimizer gap that persists across realistic language-modeling experiments, we progressively remove sequence dependence, architectural complexity, and stochasticity. We find that the gap exists in a minimal setting: the softmax unigram model with heavy-tailed data. This model exposes a simple deterministic mechanism under heavy-tailed class imbalance. We prove that GD learns rare tokens slowly because the corresponding logits receive only tiny updates, while SignGD removes this magnitude dependence and moves rare and common coordinates on a more comparable scale. We make this precise with upper and lower bounds for the convergence rate of GD and upper bounds for the convergence of SignGD. Our stochastic bounds contain additional noise-dependent terms that can obscure this advantage in the convergence guarantees and can be reduced by increasing the batch size
Jul 16, 2025

Better Convergence Guarantees for Sign-Based Momentum Methods

This paper presents an improved analysis for sign-based methods with momentum updates. Traditional sign-based methods obtain a convergence rate of O(T−1/4)\mathcal{O}(T^{-1/4}) under the separable smoothness assumption, but they typically require large batch sizes or assume unimodal symmetric stochastic noise. To address these limitations, we demonstrate that signSGD with momentum can achieve the same convergence rate using constant batch sizes without additional assumptions. We also establish a convergence rate under the l2l_2-smoothness condition, improving upon the result of prior work by a factor of O(d1/2)\mathcal{O}(d^{1/2}), where dd is the problem dimension. Furthermore, we explore sign-based methods in distributed settings and show that the proposed methods yield convergence rates of O(d1/2T−1/2+dn−1/2)\mathcal{O}\left( d^{1/2}T^{-1/2} + dn^{-1/2} \right) and O(d1/4T−1/4)\mathcal{O}\left(d^{1/4}T^{-1/4}\right), which outperform the previous results of O(dT−1/4+dn−1/2)\mathcal{O}\left( dT^{-1/4} + dn^{-1/2} \right) and O(d3/8T−1/8)\mathcal{O}\left( d^{3/8}T^{-1/8} \right), respectively. Numerical experiments also validate the effectiveness of the proposed methods.
Nov 12, 2024

Convergence Rate Analysis of LION

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 O(dK−1/4)\cal O(\sqrt{d}K^{-1/4}) measured by gradient ℓ1\ell_1 norm, where dd is the problem dimension and KK 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 dd but also tightly matches the theoretical lower bound for nonconvex stochastic optimization algorithms, which is typically measured using the gradient ℓ2\ell_2 norm, with respect to the number of iterations KK. 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 ℓ1/ℓ2\ell_1/\ell_2 norm ratio aligns with Θ(d)Θ(\sqrt{d}), thus proving that our convergence rate matches the theoretical lower bound with respect to dd in the empirical sense.