{"id":"arxiv/2602.13413","url":"https://arxiv.org/abs/2602.13413","tags":["cs.LG","math.NA","math.OC","stat.ML"],"score":0,"title":"Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise","domain":"cs.LG","source":"arxiv","authors":["Yuchen Fang","James Demmel","Javad Lavaei"],"reviews":0,"subject":"cs.LG","summary":"We develop a worst-case complexity theory for stochastically preconditioned stochastic gradient descent (SPSGD) and its accelerated variants under heavy-tailed noise, a setting that encompasses widely used adaptive methods such as Adam, RMSProp, and Shampoo. We assume the stochastic gradient noise has a finite $p$-th moment for some $p \\in (1,2]$, and measure convergence after $T$ iterations. While clipping and normalization are parallel tools for stabilizing training of SGD under heavy-tailed noise, there is a fundamental separation in their worst-case properties in stochastically…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-13","reactions":{}}