{"id":"arxiv/2605.06615","url":"https://arxiv.org/abs/2605.06615","tags":["cs.LG","cs.AI","cs.CL","math.OC"],"score":0,"title":"When and Why SignSGD Outperforms SGD: A Theoretical Study Based on $\\ell_1$-norm Lower Bounds","domain":"cs.LG","source":"arxiv","authors":["Hongyi Tao","Dingzhi Yu","Lijun Zhang"],"reviews":0,"subject":"cs.LG","summary":"Sign-based optimization algorithms, such as SignSGD and Muon, have garnered significant attention for their remarkable performance in training large foundation models. Despite this empirical success, we still lack a theoretical understanding of when and why these sign-based methods outperform vanilla SGD. The core obstacle is that under standard smoothness and finite variance conditions, SGD is known to be minimax optimal for finding stationary points measured by $\\ell_2$-norms, thereby fundamentally precluding any complexity gains for sign-based methods in standard settings. To overcome…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-07","reactions":{}}