언제 그리고 왜 SignSGD가 SGD보다 우수한가: $\ell_1$-norm 하한 기반 이론적 연구

When and Why SignSGD Outperforms SGD: A Theoretical Study Based on $\ell_1$-norm Lower Bounds

SignSGD 및 Muon과 같은 sign 기반 최적화 알고리즘은 대규모 기초 모델 훈련에서 뛰어난 성능을 보여주며 상당한 주목을 받고 있습니다. 그러나 이러한 sign 기반 방법이 기존 SGD보다 우수한 이유에 대한 이론적 이해는 아직 부족합니다. 핵심적인 문제는 표준적인 smoothness 및 유한 분산 조건 하에서 SGD가 $\ell_2$-norm으로 측정되는 stationary point를 찾는 데 minimax optimal하다는 점이며, 이는 sign 기반 방법이 표준적인 환경에서 복잡성 이점을 얻는 것을 근본적으로 방해합니다. 이러한 장벽을 극복하기 위해, 우리는 $\ell_1$-norm stationarity, $\ell_\infty$-smoothness, 그리고 분리된 노이즈 모델을 활용하여 sign 기반 최적화기를 분석합니다. 이러한 모델은 signed 업데이트의 좌표별 특성을 더 잘 반영할 수 있습니다. 이러한 특정한 문제 구조 하에서, 우리는 SignSGD에 대한 matched upper 및 lower bound를 도출하고, SignSGD가 SGD보다 우수함을 증명할 수 있는 문제 클래스를 명확하게 규정합니다. 특히, 우리는 SignSGD의 \*upper bound*와 SGD의 \*lower bound*를 비교하여, SignSGD가 \*희소 노이즈* 환경에서 문제의 복잡성을 $d$만큼 효과적으로 감소시킨다는 것을 보여줍니다 (여기서 $d$는 문제의 차원입니다). 또한, 우리는 이 프레임워크를 행렬 공간으로 확장하여 Muon 최적화기의 equivalent optimal lower bound를 제공하고, sign 연산자를 행렬로 확장하는 것이 이러한 최적의 스케일링을 유지한다는 것을 증명합니다. 마지막으로, 우리는 우리의 이론적 경계를 실제 적용으로 연결하여, SignSGD의 이론적인 우수성이 1억 2천 4백만 개의 파라미터를 가진 GPT-2 모델의 사전 훈련 과정에서 더 빠른 수렴 속도를 정확하게 예측한다는 것을 보여줍니다.

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 this barrier, we analyze sign-based optimizers leveraging $\ell_1$-norm stationarity, $\ell_\infty$-smoothness, and a separable noise model, which can better capture the coordinate-wise nature of signed updates. Under this distinct problem geometry, we derive matched upper and lower bounds for SignSGD and explicitly characterize the problem class in which SignSGD provably dominates SGD. Specifically, we compare the \emph{upper bound of SignSGD} with the \emph{lower bound of SGD}, illustrating that SignSGD effectively reduces the complexity by a factor of $d$ under \emph{sparse noise}, where $d$ is the problem dimension. Furthermore, we elevate this framework to the matrix domain, providing an equivalent optimal lower bound for the Muon optimizer, proving that extending the sign operator to matrices preserves this optimal scaling with dimensionality. Finally, we bridge our theoretical bounds to practice, demonstrating that the theoretical superiority of SignSGD accurately predicts its faster convergence during the pretraining of a 124M parameter GPT-2 model.